Shamir Module

Shamir secret sharing and recombination. Based on the paper How to share a secret by Adi Shamir in Communications of the ACM 22 (11): 612-613.

viff.shamir.recombine(shares, x_recomb=0)

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.

Note that player ids must be elements in the same field as the shares or otherwise the algorithm will not work.

>>> from field import GF
>>> Zp = GF(19)
>>> shares = [(Zp(i), 7 * Zp(i) + 3) for i in range(1, 4)]
>>> print shares
[({1}, {10}), ({2}, {17}), ({3}, {5})]
>>> del(shares[1])
>>> recombine(shares)
{3}

viff.shamir.share(secret, threshold, num_players)

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

viff.shamir.verify_sharing(shares, degree)

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