Package viff :: Module shamir
[hide private]
[frames] | no frames]

Module shamir

source code

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.
Functions [hide private]
 
share(secret, threshold, num_players)
Shamir share secret.
source code
 
recombine(shares, x_recomb=0)
Recombines list of (xi, yi) pairs.
source code
 
verify_sharing(shares, degree)
Verifies that a sharing is correct.
source code
Variables [hide private]
  _recombination_vectors = {}
Cached recombination vectors.
Function Details [hide private]

share(secret, threshold, num_players)

source code 

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)])

recombine(shares, x_recomb=0)

source code 

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])

verify_sharing(shares, degree)

source code 

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

Variables Details [hide private]

_recombination_vectors

Cached recombination vectors.

The recombination vector used by recombine depends only on the recombination point and the player IDs of the shares, and so it can be cached for efficiency.

Value:
{}