viff

changeset 856:c2c1fcdd710c

Implemented first part of PRSS zero-sharing.
author Martin Geisler <mg@daimi.au.dk>
date Wed, 30 Jul 2008 22:04:15 +0200
parents 28506572a2ca
children f89875736767
files viff/prss.py
diffstat 1 files changed, 49 insertions(+), 0 deletions(-) [+]
line diff
     1.1 --- a/viff/prss.py	Wed Jul 30 21:08:23 2008 +0200
     1.2 +++ b/viff/prss.py	Wed Jul 30 22:04:15 2008 +0200
     1.3 @@ -147,6 +147,55 @@
     1.4      return (convert_replicated_shamir(n, j, field, rep_shares),
     1.5              convert_replicated_shamir(n, j, GF256, lsb_shares))
     1.6  
     1.7 +def prss_zero(n, t, j, field, prfs, key):
     1.8 +    """Return a pseudo-random secret zero-sharing of degree 2t.
     1.9 +
    1.10 +    >>> from field import GF
    1.11 +    >>> Zp = GF(23)
    1.12 +    >>> prfs = {frozenset([1,2]): PRF("a", 7),
    1.13 +    ...         frozenset([1,3]): PRF("b", 7),
    1.14 +    ...         frozenset([2,3]): PRF("c", 7)}
    1.15 +    >>> prss_zero(3, 1, 1, Zp, prfs, "key")
    1.16 +    {4}
    1.17 +    >>> prss_zero(3, 1, 2, Zp, prfs, "key")
    1.18 +    {0}
    1.19 +    >>> prss_zero(3, 1, 3, Zp, prfs, "key")
    1.20 +    {11}
    1.21 +
    1.22 +    If we recombine 2t + 1 = 3 shares we can verify that this is
    1.23 +    indeed a zero-sharing:
    1.24 +
    1.25 +    >>> from shamir import recombine
    1.26 +    >>> recombine([(Zp(1), Zp(4)), (Zp(2), Zp(0)), (Zp(3), Zp(11))])
    1.27 +    {0}
    1.28 +    """    
    1.29 +    # We start by generating t random numbers for each subset. This is
    1.30 +    # very similar to calling random_replicated_sharing t times, but
    1.31 +    # by doing it like this we immediatedly get the nesting we want.
    1.32 +    rep_shares = [(s, [(i+1, prf((key, i))) for i in range(t)])
    1.33 +                  for (s, prf) in prfs.iteritems() if j in s]
    1.34 +
    1.35 +    # We then proceed with the zero-sharing. The first part is like in
    1.36 +    # a normal PRSS.
    1.37 +    result = 0
    1.38 +    all = frozenset(range(1, n+1))
    1.39 +    for subset, shares in rep_shares:
    1.40 +        points = [(field(x), 0) for x in all-subset]
    1.41 +        points.append((0, 1))
    1.42 +        f_in_j = shamir.recombine(points, j)
    1.43 +        # Unlike a normal PRSS we have an inner sum where we use a
    1.44 +        # degree 2t polynomial g_i which we choose as
    1.45 +        #
    1.46 +        #   g_i(x) = f(x) * x**j
    1.47 +        #
    1.48 +        # since we already have the degree t polynomial f at hand. The
    1.49 +        # g_i are all linearly independent as required by the protocol
    1.50 +        # and can thus be used for the zero-sharing.
    1.51 +        for i, share in shares:
    1.52 +            g_i_in_j = f_in_j * j**i
    1.53 +            result += share * g_i_in_j
    1.54 +    return result
    1.55 +
    1.56  def generate_subsets(orig_set, size):
    1.57      """Generates the set of all subsets of a specific size.
    1.58