Module shamir

Shamir share secret.

The threshold indicates the maximum number of shares that reveal nothing about secret. The return value is a list of (player id, share) pairs.

It holds that sharing and recombination cancels each other:

>>> from field import GF
>>> Zp = GF(47)
>>> secret = Zp(42)
>>> recombine(share(secret, 7, 15)[:8]) == secret
True

The threshold can range from zero (for a dummy-sharing):

>>> share(Zp(10), 0, 5)
[({1}, {10}), ({2}, {10}), ({3}, {10}), ({4}, {10}), ({5}, {10})]

up to but not including num_players:

>>> share(Zp(10), 5, 5)
Traceback (most recent call last):
  ...
AssertionError: Threshold out of range

Decorators:

• @fake(lambda s, t, n: [(s.field(i+ 1), s) for i in range(n)])

Recombines list of (xi, yi) pairs.

Shares is a list of threshold + 1 (player id, share) pairs. Recombination is done in the optional point x_recomb.

Decorators:

• @fake(lambda s, x= 0: s [0] [1])

Verifies that a sharing is correct.

It is verified that the given shares correspond to points on a polynomial of at most the given degree.

>>> from field import GF
>>> Zp = GF(47)
>>> shares = [(Zp(i), Zp(i**2)) for i in range(1, 6)]
>>> print shares
[({1}, {1}), ({2}, {4}), ({3}, {9}), ({4}, {16}), ({5}, {25})]
>>> verify_sharing(shares, 2)
True
>>> verify_sharing(shares, 1)
False