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 wrap: on
line diff
--- a/viff/active.py	Fri Sep 11 19:11:31 2009 +0200
+++ b/viff/active.py	Thu Sep 17 14:35:26 2009 +0200
@@ -428,32 +428,35 @@
     @increment_pc
     @preprocess("generate_triples")
     def get_triple(self, field):
-        count, result = self.generate_triples(field)
+        count, result = self.generate_triples(field, quantity=1)
         result.addCallback(lambda triples: triples[0])
         return result
 
     @increment_pc
-    def generate_triples(self, field):
-        """Generate a multiplication triple using PRSS.
+    def generate_triples(self, field, quantity=20):
+        """Generate *quantity* multiplication triples using PRSS.
 
         These are random numbers *a*, *b*, and *c* such that ``c =
         ab``. This function can be used in pre-processing.
 
-        Returns a tuple with the number of triples generated (1) and a
+        Returns a tuple with the number of triples generated and a
         Deferred which will yield a singleton-list with a 3-tuple.
         """
-        a_t = self.prss_share_random(field)
-        b_t = self.prss_share_random(field)
-        r_t, r_2t = self.prss_double_share(field)
+        a_t = self.prss_share_random_multi(field, quantity)
+        b_t = self.prss_share_random_multi(field, quantity)
+        r_t, r_2t = self.prss_double_share(field, quantity)
+        c_t = [0] * quantity
 
-        # Multiply a and b without resharing.
-        c_2t = gather_shares([a_t, b_t])
-        c_2t.addCallback(lambda (a, b): a * b)
+        for i in range(quantity):
+            # Multiply a and b without resharing.
+            c_2t = gather_shares([a_t[i], b_t[i]])
+            c_2t.addCallback(lambda (a, b): a * b)
 
-        d_2t = c_2t - r_2t
-        d = self.open(d_2t, threshold=2*self.threshold)
-        c_t = r_t + d
-        return 1, succeed([(a_t, b_t, c_t)])
+            d_2t = c_2t - r_2t[i]
+            d = self.open(d_2t, threshold=2*self.threshold)
+            c_t[i] = r_t[i] + d
+
+        return quantity, succeed(zip(a_t, b_t, c_t))
 
 
 class BasicActiveRuntime(PassiveRuntime):
--- a/viff/passive.py	Fri Sep 11 19:11:31 2009 +0200
+++ b/viff/passive.py	Thu Sep 17 14:35:26 2009 +0200
@@ -375,8 +375,9 @@
         return [Share(self, field, share) for share in shares]
 
     @increment_pc
-    def prss_share_zero(self, field):
-        """Generate shares of the zero element from the field given.
+    def prss_share_zero(self, field, quantity):
+        """Generate *quantity* shares of the zero element from the
+        field given.
 
         Communication cost: none.
         """
@@ -384,19 +385,19 @@
         prss_key = tuple(self.program_counter)
         prfs = self.players[self.id].prfs(field.modulus)
         zero_share = prss_zero(self.num_players, self.threshold, self.id,
-                               field, prfs, prss_key)
-        return Share(self, field, zero_share)
+                               field, prfs, prss_key, quantity)
+        return [Share(self, field, zero_share[i]) for i in range(quantity)]
 
     @increment_pc
-    def prss_double_share(self, field):
-        """Make a double-sharing using PRSS.
+    def prss_double_share(self, field, quantity):
+        """Make *quantity* double-sharings using PRSS.
 
         The pair of shares will have degree t and 2t where t is the
         default threshold for the runtime.
         """
-        r_t = self.prss_share_random(field)
-        z_2t = self.prss_share_zero(field)
-        return (r_t, r_t + z_2t)
+        r_t = self.prss_share_random_multi(field, quantity)
+        z_2t = self.prss_share_zero(field, quantity)
+        return (r_t, [r_t[i] + z_2t[i] for i in range(quantity)])
 
     @increment_pc
     def prss_share_bit_double(self, field):
--- a/viff/prss.py	Fri Sep 11 19:11:31 2009 +0200
+++ b/viff/prss.py	Thu Sep 17 14:35:26 2009 +0200
@@ -169,21 +169,21 @@
     return (convert_replicated_shamir(n, j, field, rep_shares),
             convert_replicated_shamir(n, j, GF256, lsb_shares))
 
-@fake(lambda n, t, j, field, prfs, key: field(0))
-def prss_zero(n, t, j, field, prfs, key):
-    """Return a pseudo-random secret zero-sharing of degree 2t.
+@fake(lambda n, t, j, field, prfs, key, quantity: [field(0)] * quantity)
+def prss_zero(n, t, j, field, prfs, key, quantity):
+    """Return *quantity* pseudo-random secret zero-sharings 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")
-    {16}
-    >>> prss_zero(3, 1, 2, Zp, prfs, "key")
-    {13}
-    >>> prss_zero(3, 1, 3, Zp, prfs, "key")
-    {14}
+    >>> prss_zero(3, 1, 1, Zp, prfs, "key", 1)
+    [{16}]
+    >>> prss_zero(3, 1, 2, Zp, prfs, "key", 1)
+    [{13}]
+    >>> prss_zero(3, 1, 3, Zp, prfs, "key", 1)
+    [{14}]
 
     If we recombine 2t + 1 = 3 shares we can verify that this is
     indeed a zero-sharing:
@@ -200,12 +200,19 @@
 
     # We then proceed with the zero-sharing. The first part is like in
     # a normal PRSS.
-    result = 0
+    result = [0] * quantity
     all = frozenset(range(1, n+1))
+    modulus = field.modulus
+
     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)
+        try:
+            f_in_j = _f_in_j_cache[(field, n, j, subset)]
+        except KeyError:
+            points = [(field(x), 0) for x in all-subset]
+            points.append((0, 1))
+            f_in_j = shamir.recombine(points, j)
+            _f_in_j_cache[(field, n, j, subset)] = f_in_j
+
         # Unlike a normal PRSS we have an inner sum where we use a
         # degree 2t polynomial g_i which we choose as
         #
@@ -214,9 +221,13 @@
         # 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:
+        for i, packed_share in shares:
             g_i_in_j = f_in_j * j**i
-            result += share * g_i_in_j
+
+            for k in range(quantity):
+                result[k] += (packed_share % modulus) * g_i_in_j
+                packed_share /= modulus
+
     return result
 
 def generate_subsets(orig_set, size):
--- a/viff/test/test_runtime_prss.py	Fri Sep 11 19:11:31 2009 +0200
+++ b/viff/test/test_runtime_prss.py	Thu Sep 17 14:35:26 2009 +0200
@@ -130,7 +130,7 @@
     @protocol
     def test_prss_share_zero_bit(self, runtime):
         """Tests the sharing of a zero GF256 element using PRSS."""
-        a = runtime.prss_share_zero(GF256)
+        a = runtime.prss_share_zero(GF256, 1)[0]
         self.assert_type(a, Share)
 
         opened_a = runtime.open(a, threshold=2*runtime.threshold)
@@ -140,7 +140,7 @@
     @protocol
     def test_prss_share_zero_int(self, runtime):
         """Tests the sharing of a zero Zp element using PRSS."""
-        a = runtime.prss_share_zero(self.Zp)
+        a = runtime.prss_share_zero(self.Zp, 1)[0]
         self.assert_type(a, Share)
 
         opened_a = runtime.open(a, threshold=2*runtime.threshold)
@@ -150,7 +150,7 @@
     @protocol
     def test_prss_double_share(self, runtime):
         """Test double-sharing of random numbers using PRSS."""
-        r_t, r_2t = runtime.prss_double_share(self.Zp)
+        r_t, r_2t = zip(*runtime.prss_double_share(self.Zp, 1))[0]
 
         self.assert_type(r_t, Share)
         self.assertEquals(r_t.field, self.Zp)
--- a/viff/test/test_util.py	Fri Sep 11 19:11:31 2009 +0200
+++ b/viff/test/test_util.py	Thu Sep 17 14:35:26 2009 +0200
@@ -70,7 +70,7 @@
         self.assertEquals(bit, GF256(1))
 
     def test_prss_zero(self):
-        share = prss.prss_zero(None, None, None, self.field, None, None)
+        share = prss.prss_zero(None, None, None, self.field, None, None, 1)[0]
         self.assertEquals(share, self.field(0))