viff

changeset 748:fac2d1f8dbe1

Function to do PRSS while returning a share of the LSB.
author Martin Geisler <mg@daimi.au.dk>
date Tue, 13 May 2008 15:24:27 +0200
parents 18ef1b1ca1e1
children 65a61fc798bc
files viff/prss.py
diffstat 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