viff

changeset 1147:5ac7a2c23337

Cache the coefficients used to construct a PRSS share.
author Marcel Keller <mkeller@cs.au.dk>
date Wed, 25 Feb 2009 21:14:30 +0100
parents ecd0f77f5243
children d522f9b14b49
files viff/prss.py
diffstat 1 files changed, 13 insertions(+), 3 deletions(-) [+]
line diff
     1.1 --- a/viff/prss.py	Wed Feb 25 17:16:38 2009 +0100
     1.2 +++ b/viff/prss.py	Wed Feb 25 21:14:30 2009 +0100
     1.3 @@ -66,19 +66,29 @@
     1.4      # the subset before using it.
     1.5      return [(s, prf(key)) for (s, prf) in prfs.iteritems() if j in s]
     1.6  
     1.7 +#: Cache the coefficients used to construct the share. They depend on the field,
     1.8 +#: the player concerned, the total number of players, and the subset.
     1.9 +_f_in_j_cache = {}
    1.10 +
    1.11  def convert_replicated_shamir(n, j, field, rep_shares):
    1.12      """Convert a set of replicated shares to a Shamir share.
    1.13  
    1.14      The conversion is done for player *j* (out of *n*) and will be
    1.15      done over *field*.
    1.16      """
    1.17 +    global _f_in_j_cache
    1.18      result = 0
    1.19      all = frozenset(range(1, n+1))
    1.20      for subset, share in rep_shares:
    1.21          # TODO: should we cache the f_in_j values?
    1.22 -        points = [(field(x), 0) for x in all-subset]
    1.23 -        points.append((0, 1))
    1.24 -        f_in_j = shamir.recombine(points, j)
    1.25 +        # Yes, we probably should.
    1.26 +        if ((field, n, j, subset) in _f_in_j_cache):
    1.27 +            f_in_j = _f_in_j_cache[(field, n, j, subset)]
    1.28 +        else:
    1.29 +            points = [(field(x), 0) for x in all-subset]
    1.30 +            points.append((0, 1))
    1.31 +            f_in_j = shamir.recombine(points, j)
    1.32 +            _f_in_j_cache[(field, n, j, subset)] = f_in_j
    1.33          result += share * f_in_j
    1.34      return result
    1.35