Methods for pseudo-random secret sharing. Normal Shamir sharing (see the viff.shamir module) requires secure channels between the players for distributing shares. With pseudo-random secret sharing one can share a secret using a single broadcast instead.
PRSS relies on each player having access to a set of previously distributed pseudo-random functions (PRFs) — or rather the seeds for such functions. In VIFF, such seeds are generated by generate_configs(). The prfs() and dealer_prfs() methods give access to the PRFs.
In this module the function prss() is used to calculate shares for a pseudo-random number. The generate_subsets() function is a general utility for generating subsets of a specific size.
The code is based on the paper “Share Conversion, Pseudorandom Secret-Sharing and Applications to Secure Computation” by Ronald Cramer, Ivan Damgård, and Yuval Ishai in Proc. of TCC 2005, LNCS 3378. Download.
Models a pseudo random function (a PRF).
The numbers are based on a SHA1 hash of the initial key.
Each PRF is created based on a key (which should be random and secret) and a maximum (which may be public):
>>> f = PRF("some random key", 256)
Calling f return values between zero and the given maximum:
>>> f(1)
26L
>>> f(2)
69L
>>> f(3)
217L
Return a number based on input.
If the input is not already a string, it is hashed (using the normal Python hash built-in) and the hash value is used instead. The hash value is a 32 bit value, so a string should be given if one wants to evaluate the PRF on more that 2**32 different values.
>>> prf = PRF("key", 1000)
>>> prf(1), prf(2), prf(3)
(501L, 432L, 133L)
Since prf is a function we can of course evaluate the same input to get the same output:
>>> prf(1)
501L
The prf can take arbitrary input:
>>> prf(("input", 123))
284L
Non-string input will be converted with str, which means that the input must have a deterministic __str__ method. This means that hashable instances are probably best.
Return a pseudo-random secret share for a random number.
The share is for player j based on the pseudo-random functions given in prfs (a mapping from subsets of players to PRF instances). The key is used when evaluating the PRFs.
An example with (n,t) = (3,1) and a modulus of 31:
>>> from field import GF
>>> Zp = GF(31)
>>> prfs = {frozenset([1,2]): PRF("a", 31),
... frozenset([1,3]): PRF("b", 31),
... frozenset([2,3]): PRF("c", 31)}
>>> prss(3, 1, Zp, prfs, "key")
{22}
>>> prss(3, 2, Zp, prfs, "key")
{20}
>>> prss(3, 3, Zp, prfs, "key")
{18}
We see that the sharing is consistent because each subset of two players will recombine their shares to {24}.
Share a pseudo-random number and its least significant bit.
The random number is shared over field and its least significant bit is shared over viff.field.GF256. It is important the prfs generate numbers much less than the size of field – we must be able to do an addition for each PRF without overflow in field.
>>> from field import GF
>>> Zp = GF(23)
>>> prfs = {frozenset([1,2]): PRF("a", 7),
... frozenset([1,3]): PRF("b", 7),
... frozenset([2,3]): PRF("c", 7)}
>>> prss_lsb(3, 1, Zp, prfs, "key")
({0}, [140])
>>> prss_lsb(3, 2, Zp, prfs, "key")
({15}, [3])
>>> prss_lsb(3, 3, Zp, prfs, "key")
({7}, [143])
We see that the random value must be {8} and so the least significant bit must be [0]. We can check this by recombining any two of the three shares:
>>> from shamir import recombine
>>> recombine([(GF256(1), GF256(140)), (GF256(2), GF256(3))])
[0]
>>> recombine([(GF256(2), GF256(3)), (GF256(3), GF256(143))])
[0]
>>> recombine([(GF256(3), GF256(143)), (GF256(1), GF256(140))])
[0]
Return a replicated sharing of a random number.
The shares are for player j based on the pseudo-random functions given in prfs (a mapping from subsets of players to PRF instances). The key is used when evaluating the PRFs. The result is a list of (subset, share) pairs.
Convert a set of replicated shares to a Shamir share.
The conversion is done for player j (out of n) and will be done over field.
Generates the set of all subsets of a specific size.
>>> generate_subsets(frozenset('abc'), 2)
frozenset([frozenset(['c', 'b']), frozenset(['a', 'c']), frozenset(['a', 'b'])])
Generating subsets larger than the initial set return the empty set:
>>> generate_subsets(frozenset('a'), 2)
frozenset([])