viff

changeset 1246:591451fd23dc

Optimize PRSS multiplication triples preprocessing. This is done by using only one PRF call for several shares.
author Marcel Keller <mkeller@cs.au.dk>
date Thu, 17 Sep 2009 14:35:26 +0200
parents be9c8eb7b4d0
children 5ffc93111d70
files viff/active.py viff/passive.py viff/prss.py viff/test/test_runtime_prss.py viff/test/test_util.py
diffstat 5 files changed, 57 insertions(+), 42 deletions(-) [+]
line diff
     1.1 --- a/viff/active.py	Fri Sep 11 19:11:31 2009 +0200
     1.2 +++ b/viff/active.py	Thu Sep 17 14:35:26 2009 +0200
     1.3 @@ -428,32 +428,35 @@
     1.4      @increment_pc
     1.5      @preprocess("generate_triples")
     1.6      def get_triple(self, field):
     1.7 -        count, result = self.generate_triples(field)
     1.8 +        count, result = self.generate_triples(field, quantity=1)
     1.9          result.addCallback(lambda triples: triples[0])
    1.10          return result
    1.11  
    1.12      @increment_pc
    1.13 -    def generate_triples(self, field):
    1.14 -        """Generate a multiplication triple using PRSS.
    1.15 +    def generate_triples(self, field, quantity=20):
    1.16 +        """Generate *quantity* multiplication triples using PRSS.
    1.17  
    1.18          These are random numbers *a*, *b*, and *c* such that ``c =
    1.19          ab``. This function can be used in pre-processing.
    1.20  
    1.21 -        Returns a tuple with the number of triples generated (1) and a
    1.22 +        Returns a tuple with the number of triples generated and a
    1.23          Deferred which will yield a singleton-list with a 3-tuple.
    1.24          """
    1.25 -        a_t = self.prss_share_random(field)
    1.26 -        b_t = self.prss_share_random(field)
    1.27 -        r_t, r_2t = self.prss_double_share(field)
    1.28 +        a_t = self.prss_share_random_multi(field, quantity)
    1.29 +        b_t = self.prss_share_random_multi(field, quantity)
    1.30 +        r_t, r_2t = self.prss_double_share(field, quantity)
    1.31 +        c_t = [0] * quantity
    1.32  
    1.33 -        # Multiply a and b without resharing.
    1.34 -        c_2t = gather_shares([a_t, b_t])
    1.35 -        c_2t.addCallback(lambda (a, b): a * b)
    1.36 +        for i in range(quantity):
    1.37 +            # Multiply a and b without resharing.
    1.38 +            c_2t = gather_shares([a_t[i], b_t[i]])
    1.39 +            c_2t.addCallback(lambda (a, b): a * b)
    1.40  
    1.41 -        d_2t = c_2t - r_2t
    1.42 -        d = self.open(d_2t, threshold=2*self.threshold)
    1.43 -        c_t = r_t + d
    1.44 -        return 1, succeed([(a_t, b_t, c_t)])
    1.45 +            d_2t = c_2t - r_2t[i]
    1.46 +            d = self.open(d_2t, threshold=2*self.threshold)
    1.47 +            c_t[i] = r_t[i] + d
    1.48 +
    1.49 +        return quantity, succeed(zip(a_t, b_t, c_t))
    1.50  
    1.51  
    1.52  class BasicActiveRuntime(PassiveRuntime):
     2.1 --- a/viff/passive.py	Fri Sep 11 19:11:31 2009 +0200
     2.2 +++ b/viff/passive.py	Thu Sep 17 14:35:26 2009 +0200
     2.3 @@ -375,8 +375,9 @@
     2.4          return [Share(self, field, share) for share in shares]
     2.5  
     2.6      @increment_pc
     2.7 -    def prss_share_zero(self, field):
     2.8 -        """Generate shares of the zero element from the field given.
     2.9 +    def prss_share_zero(self, field, quantity):
    2.10 +        """Generate *quantity* shares of the zero element from the
    2.11 +        field given.
    2.12  
    2.13          Communication cost: none.
    2.14          """
    2.15 @@ -384,19 +385,19 @@
    2.16          prss_key = tuple(self.program_counter)
    2.17          prfs = self.players[self.id].prfs(field.modulus)
    2.18          zero_share = prss_zero(self.num_players, self.threshold, self.id,
    2.19 -                               field, prfs, prss_key)
    2.20 -        return Share(self, field, zero_share)
    2.21 +                               field, prfs, prss_key, quantity)
    2.22 +        return [Share(self, field, zero_share[i]) for i in range(quantity)]
    2.23  
    2.24      @increment_pc
    2.25 -    def prss_double_share(self, field):
    2.26 -        """Make a double-sharing using PRSS.
    2.27 +    def prss_double_share(self, field, quantity):
    2.28 +        """Make *quantity* double-sharings using PRSS.
    2.29  
    2.30          The pair of shares will have degree t and 2t where t is the
    2.31          default threshold for the runtime.
    2.32          """
    2.33 -        r_t = self.prss_share_random(field)
    2.34 -        z_2t = self.prss_share_zero(field)
    2.35 -        return (r_t, r_t + z_2t)
    2.36 +        r_t = self.prss_share_random_multi(field, quantity)
    2.37 +        z_2t = self.prss_share_zero(field, quantity)
    2.38 +        return (r_t, [r_t[i] + z_2t[i] for i in range(quantity)])
    2.39  
    2.40      @increment_pc
    2.41      def prss_share_bit_double(self, field):
     3.1 --- a/viff/prss.py	Fri Sep 11 19:11:31 2009 +0200
     3.2 +++ b/viff/prss.py	Thu Sep 17 14:35:26 2009 +0200
     3.3 @@ -169,21 +169,21 @@
     3.4      return (convert_replicated_shamir(n, j, field, rep_shares),
     3.5              convert_replicated_shamir(n, j, GF256, lsb_shares))
     3.6  
     3.7 -@fake(lambda n, t, j, field, prfs, key: field(0))
     3.8 -def prss_zero(n, t, j, field, prfs, key):
     3.9 -    """Return a pseudo-random secret zero-sharing of degree 2t.
    3.10 +@fake(lambda n, t, j, field, prfs, key, quantity: [field(0)] * quantity)
    3.11 +def prss_zero(n, t, j, field, prfs, key, quantity):
    3.12 +    """Return *quantity* pseudo-random secret zero-sharings of degree 2t.
    3.13  
    3.14      >>> from field import GF
    3.15      >>> Zp = GF(23)
    3.16      >>> prfs = {frozenset([1,2]): PRF("a", 7),
    3.17      ...         frozenset([1,3]): PRF("b", 7),
    3.18      ...         frozenset([2,3]): PRF("c", 7)}
    3.19 -    >>> prss_zero(3, 1, 1, Zp, prfs, "key")
    3.20 -    {16}
    3.21 -    >>> prss_zero(3, 1, 2, Zp, prfs, "key")
    3.22 -    {13}
    3.23 -    >>> prss_zero(3, 1, 3, Zp, prfs, "key")
    3.24 -    {14}
    3.25 +    >>> prss_zero(3, 1, 1, Zp, prfs, "key", 1)
    3.26 +    [{16}]
    3.27 +    >>> prss_zero(3, 1, 2, Zp, prfs, "key", 1)
    3.28 +    [{13}]
    3.29 +    >>> prss_zero(3, 1, 3, Zp, prfs, "key", 1)
    3.30 +    [{14}]
    3.31  
    3.32      If we recombine 2t + 1 = 3 shares we can verify that this is
    3.33      indeed a zero-sharing:
    3.34 @@ -200,12 +200,19 @@
    3.35  
    3.36      # We then proceed with the zero-sharing. The first part is like in
    3.37      # a normal PRSS.
    3.38 -    result = 0
    3.39 +    result = [0] * quantity
    3.40      all = frozenset(range(1, n+1))
    3.41 +    modulus = field.modulus
    3.42 +
    3.43      for subset, shares in rep_shares:
    3.44 -        points = [(field(x), 0) for x in all-subset]
    3.45 -        points.append((0, 1))
    3.46 -        f_in_j = shamir.recombine(points, j)
    3.47 +        try:
    3.48 +            f_in_j = _f_in_j_cache[(field, n, j, subset)]
    3.49 +        except KeyError:
    3.50 +            points = [(field(x), 0) for x in all-subset]
    3.51 +            points.append((0, 1))
    3.52 +            f_in_j = shamir.recombine(points, j)
    3.53 +            _f_in_j_cache[(field, n, j, subset)] = f_in_j
    3.54 +
    3.55          # Unlike a normal PRSS we have an inner sum where we use a
    3.56          # degree 2t polynomial g_i which we choose as
    3.57          #
    3.58 @@ -214,9 +221,13 @@
    3.59          # since we already have the degree t polynomial f at hand. The
    3.60          # g_i are all linearly independent as required by the protocol
    3.61          # and can thus be used for the zero-sharing.
    3.62 -        for i, share in shares:
    3.63 +        for i, packed_share in shares:
    3.64              g_i_in_j = f_in_j * j**i
    3.65 -            result += share * g_i_in_j
    3.66 +
    3.67 +            for k in range(quantity):
    3.68 +                result[k] += (packed_share % modulus) * g_i_in_j
    3.69 +                packed_share /= modulus
    3.70 +
    3.71      return result
    3.72  
    3.73  def generate_subsets(orig_set, size):
     4.1 --- a/viff/test/test_runtime_prss.py	Fri Sep 11 19:11:31 2009 +0200
     4.2 +++ b/viff/test/test_runtime_prss.py	Thu Sep 17 14:35:26 2009 +0200
     4.3 @@ -130,7 +130,7 @@
     4.4      @protocol
     4.5      def test_prss_share_zero_bit(self, runtime):
     4.6          """Tests the sharing of a zero GF256 element using PRSS."""
     4.7 -        a = runtime.prss_share_zero(GF256)
     4.8 +        a = runtime.prss_share_zero(GF256, 1)[0]
     4.9          self.assert_type(a, Share)
    4.10  
    4.11          opened_a = runtime.open(a, threshold=2*runtime.threshold)
    4.12 @@ -140,7 +140,7 @@
    4.13      @protocol
    4.14      def test_prss_share_zero_int(self, runtime):
    4.15          """Tests the sharing of a zero Zp element using PRSS."""
    4.16 -        a = runtime.prss_share_zero(self.Zp)
    4.17 +        a = runtime.prss_share_zero(self.Zp, 1)[0]
    4.18          self.assert_type(a, Share)
    4.19  
    4.20          opened_a = runtime.open(a, threshold=2*runtime.threshold)
    4.21 @@ -150,7 +150,7 @@
    4.22      @protocol
    4.23      def test_prss_double_share(self, runtime):
    4.24          """Test double-sharing of random numbers using PRSS."""
    4.25 -        r_t, r_2t = runtime.prss_double_share(self.Zp)
    4.26 +        r_t, r_2t = zip(*runtime.prss_double_share(self.Zp, 1))[0]
    4.27  
    4.28          self.assert_type(r_t, Share)
    4.29          self.assertEquals(r_t.field, self.Zp)
     5.1 --- a/viff/test/test_util.py	Fri Sep 11 19:11:31 2009 +0200
     5.2 +++ b/viff/test/test_util.py	Thu Sep 17 14:35:26 2009 +0200
     5.3 @@ -70,7 +70,7 @@
     5.4          self.assertEquals(bit, GF256(1))
     5.5  
     5.6      def test_prss_zero(self):
     5.7 -        share = prss.prss_zero(None, None, None, self.field, None, None)
     5.8 +        share = prss.prss_zero(None, None, None, self.field, None, None, 1)[0]
     5.9          self.assertEquals(share, self.field(0))
    5.10  
    5.11