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

Module prss

source code

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 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 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.

Classes [hide private]
  PRF
Models a pseudo random function (a PRF).
Functions [hide private]
 
random_replicated_sharing(j, prfs, key)
Return a replicated sharing of a random number.
source code
 
convert_replicated_shamir(n, j, field, rep_shares)
Convert a set of replicated shares to a Shamir share.
source code
 
prss(n, j, field, prfs, key)
Return a pseudo-random secret share for a random number.
source code
 
prss_multi(n, j, field, prfs, key, modulus, quantity)
Does the same as prss, but multiple times in order to call the PRFs less frequently.
source code
 
prss_lsb(n, j, field, prfs, key)
Share a pseudo-random number and its least significant bit.
source code
 
prss_zero(n, t, j, field, prfs, key, quantity)
Return quantity pseudo-random secret zero-sharings of degree 2t.
source code
 
generate_subsets(orig_set, size)
Generates the set of all subsets of a specific size.
source code
Variables [hide private]
  _f_in_j_cache = {}
Cache the coefficients used to construct the share.
Function Details [hide private]

random_replicated_sharing(j, prfs, key)

source code 

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_replicated_shamir(n, j, field, rep_shares)

source code 

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.

prss(n, j, field, prfs, key)

source code 

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}.

Decorators:
  • @fake(lambda n, j, field, prfs, key: field(7))

prss_lsb(n, j, field, prfs, key)

source code 

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]
Decorators:
  • @fake(lambda n, j, field, prfs, key:(field(7), GF256(1)))

prss_zero(n, t, j, field, prfs, key, quantity)

source code 

Return quantity pseudo-random secret zero-sharings 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 zero-sharing:

>>> from shamir import recombine
>>> recombine([(Zp(1), Zp(4)), (Zp(2), Zp(0)), (Zp(3), Zp(11))])
{0}
Decorators:
  • @fake(lambda n, t, j, field, prfs, key, quantity: [field(0)]* quantity)

generate_subsets(orig_set, size)

source code 

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

Variables Details [hide private]

_f_in_j_cache

Cache the coefficients used to construct the share. They depend on the field, the player concerned, the total number of players, and the subset.
Value:
{}