Mercurial > mkeller
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 wrap: on
line diff
--- a/viff/prss.py Wed Jul 30 21:08:23 2008 +0200 +++ b/viff/prss.py Wed Jul 30 22:04:15 2008 +0200 @@ -147,6 +147,55 @@ return (convert_replicated_shamir(n, j, field, rep_shares), convert_replicated_shamir(n, j, GF256, lsb_shares)) +def prss_zero(n, t, j, field, prfs, key): + """Return a pseudo-random secret zero-sharing 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") + {4} + >>> prss_zero(3, 1, 2, Zp, prfs, "key") + {0} + >>> prss_zero(3, 1, 3, Zp, prfs, "key") + {11} + + 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} + """ + # We start by generating t random numbers for each subset. This is + # very similar to calling random_replicated_sharing t times, but + # by doing it like this we immediatedly get the nesting we want. + rep_shares = [(s, [(i+1, prf((key, i))) for i in range(t)]) + for (s, prf) in prfs.iteritems() if j in s] + + # We then proceed with the zero-sharing. The first part is like in + # a normal PRSS. + result = 0 + all = frozenset(range(1, n+1)) + for subset, shares in rep_shares: + points = [(field(x), 0) for x in all-subset] + points.append((0, 1)) + f_in_j = shamir.recombine(points, j) + # Unlike a normal PRSS we have an inner sum where we use a + # degree 2t polynomial g_i which we choose as + # + # g_i(x) = f(x) * x**j + # + # since we already have the degree t polynomial f at hand. The + # g_i are all linearly independent as required by the protocol + # and can thus be used for the zero-sharing. + for i, share in shares: + g_i_in_j = f_in_j * j**i + result += share * g_i_in_j + return result + def generate_subsets(orig_set, size): """Generates the set of all subsets of a specific size.