5.1.1.7.1.3. `FedEval.secure_protocols.shamir_secret_sharing`

The following Python implementation of Shamir’s Secret Sharing is released into the Public Domain under the terms of CC0 and OWFa: https://creativecommons.org/publicdomain/zero/1.0/ http://www.openwebfoundation.org/legal/the-owf-1-0-agreements/owfa-1-0

5.1.1.7.1.3.1. Module Contents

`_extended_gcd`(a, b)	Division in integers modulus p means finding the inverse of the
`_div_mod`(num, den, p)	Compute num / den modulo prime p
`_lagrange_interpolate`(x, x_s, y_s, p)	Find the y-value for the given x, given n (x, y) points;

FedEval.secure_protocols.shamir_secret_sharing._extended_gcd(a, b): Division in integers modulus p means finding the inverse of the denominator modulo p and then multiplying the numerator by this inverse (Note: inverse of A is B such that A*B % p == 1) this can be computed via extended Euclidean algorithm http://en.wikipedia.org/wiki/Modular_multiplicative_inverse#Computation

FedEval.secure_protocols.shamir_secret_sharing._div_mod(num, den, p)

Compute num / den modulo prime p

To explain what this means, the return value will be such that the following is true: den * _divmod(num, den, p) % p == num

FedEval.secure_protocols.shamir_secret_sharing._lagrange_interpolate(x, x_s, y_s, p): Find the y-value for the given x, given n (x, y) points; k points will define a polynomial of up to kth order.

class FedEval.secure_protocols.shamir_secret_sharing.ShamirSecretSharing(m, n, p=2**521 - 1)

_eval_at(poly, x): Evaluates polynomial (coefficient tuple) at x, used to generate a shamir pool in make_random_shares below.

share(secret): Generates a random shamir pool for a given secret, returns share points.

recon(shares): Recover the secret from share points (x, y points on the polynomial).