Home  Trees  Indices  Help 



Methods for pseudorandom secret sharing. Normal Shamir sharing (see the viff.shamir module) requires secure channels between the players for distributing shares. With pseudorandom 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 pseudorandom functions (PRFs)  or rather the seeds for such functions. In VIFF, such seeds are generated by viff.config.generate_configs. The viff.config.Player.prfs and viff.config.Player.dealer_prfs methods give access to the PRFs.
In this module the function prss is used to calculate shares for a pseudorandom 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 SecretSharing and Applications to Secure Computation" by Ronald Cramer, Ivan Damgård, and Yuval Ishai in Proc. of TCC 2005, LNCS 3378. Download.


PRF Models a pseudo random function (a PRF). 

















_f_in_j_cache =
Cache the coefficients used to construct the share. 

Return a replicated sharing of a random number. The shares are for player j based on the pseudorandom 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. 
Return a pseudorandom secret share for a random number. The share is for player j based on the pseudorandom 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 pseudorandom 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 quantity pseudorandom secret zerosharings of degree 2t. >>> 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_zero(3, 1, 1, Zp, prfs, "key", 1) [{16}] >>> prss_zero(3, 1, 2, Zp, prfs, "key", 1) [{13}] >>> prss_zero(3, 1, 3, Zp, prfs, "key", 1) [{14}] If we recombine 2t + 1 = 3 shares we can verify that this is indeed a zerosharing: >>> from shamir import recombine >>> recombine([(Zp(1), Zp(4)), (Zp(2), Zp(0)), (Zp(3), Zp(11))]) {0}

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

_f_in_j_cacheCache the coefficients used to construct the share. They depend on the field, the player concerned, the total number of players, and the subset.

Home  Trees  Indices  Help 


Generated by Epydoc 3.0.1 on Mon Oct 19 16:43:37 2009  http://epydoc.sourceforge.net 