Module prss

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.

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

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

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)

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