## viff

### changeset 748:fac2d1f8dbe1

Function to do PRSS while returning a share of the LSB.
author Martin Geisler Tue, 13 May 2008 15:24:27 +0200 18ef1b1ca1e1 65a61fc798bc viff/prss.py 1 files changed, 39 insertions(+), 1 deletions(-) [+]
line diff
1.1 --- a/viff/prss.py	Tue May 13 13:46:20 2008 +0200
1.2 +++ b/viff/prss.py	Tue May 13 15:24:27 2008 +0200
1.3 @@ -51,7 +51,7 @@
1.4  from gmpy import numdigits
1.5
1.6  from viff import shamir
1.7 -
1.8 +from viff.field import GF256
1.9
1.10  def random_replicated_sharing(j, prfs, key):
1.11      """Return a replicated sharing of a random number.
1.12 @@ -108,6 +108,44 @@
1.13      rep_shares = random_replicated_sharing(j, prfs, key)
1.14      return convert_replicated_shamir(n, j, field, rep_shares)
1.15
1.16 +def prss_lsb(n, j, field, prfs, key):
1.17 +    """Share a pseudo-random number and its least significant bit.
1.18 +
1.19 +    The random number is shared over *field* and its least significant
1.20 +    bit is shared over :class:`viff.field.GF256`. It is important the
1.21 +    *prfs* generate numbers much less than the size of *field* -- we
1.22 +    must be able to do an addition for each PRF without overflow in
1.23 +    *field*.
1.24 +
1.25 +    >>> from field import GF
1.26 +    >>> Zp = GF(23)
1.27 +    >>> prfs = {frozenset([1,2]): PRF("a", 7),
1.28 +    ...         frozenset([1,3]): PRF("b", 7),
1.29 +    ...         frozenset([2,3]): PRF("c", 7)}
1.30 +    >>> prss_lsb(3, 1, Zp, prfs, "key")
1.31 +    ({0}, [140])
1.32 +    >>> prss_lsb(3, 2, Zp, prfs, "key")
1.33 +    ({15}, [3])
1.34 +    >>> prss_lsb(3, 3, Zp, prfs, "key")
1.35 +    ({7}, [143])
1.36 +
1.37 +    We see that the random value must be ``{8}`` and so the least
1.38 +    significant bit must be ``[0]``. We can check this by recombining
1.39 +    any two of the three shares:
1.40 +
1.41 +    >>> from shamir import recombine
1.42 +    >>> recombine([(GF256(1), GF256(140)), (GF256(2), GF256(3))])
1.43 +    [0]
1.44 +    >>> recombine([(GF256(2), GF256(3)),   (GF256(3), GF256(143))])
1.45 +    [0]
1.46 +    >>> recombine([(GF256(3), GF256(143)), (GF256(1), GF256(140))])
1.47 +    [0]
1.48 +    """
1.49 +    rep_shares = random_replicated_sharing(j, prfs, key)
1.50 +    lsb_shares = [(s, r & 1) for (s, r) in rep_shares]
1.51 +    return (convert_replicated_shamir(n, j, field, rep_shares),
1.52 +            convert_replicated_shamir(n, j, GF256, lsb_shares))
1.53 +
1.54  def generate_subsets(orig_set, size):
1.55      """Generates the set of all subsets of a specific size.
1.56