### changeset 1246:591451fd23dc

Optimize PRSS multiplication triples preprocessing. This is done by using only one PRF call for several shares.
author Marcel Keller Thu, 17 Sep 2009 14:35:26 +0200 be9c8eb7b4d0 5ffc93111d70 viff/active.py viff/passive.py viff/prss.py viff/test/test_runtime_prss.py viff/test/test_util.py 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)
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.
"""
+        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
-        """Generate shares of the zero element from the field given.
+        """Generate *quantity* shares of the zero element from the
+        field given.

Communication cost: none.
"""
@@ -384,19 +385,19 @@
prfs = self.players[self.id].prfs(field.modulus)
-        return Share(self, field, zero_share)
+        return [Share(self, field, zero_share[i]) for i in range(quantity)]

@increment_pc
-        """Make a double-sharing using PRSS.
+        """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.
"""
-        return (r_t, r_t + z_2t)
+        return (r_t, [r_t[i] + z_2t[i] for i in range(quantity)])

@increment_pc
```--- 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
-    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
"""Tests the sharing of a zero GF256 element using PRSS."""
self.assert_type(a, Share)

opened_a = runtime.open(a, threshold=2*runtime.threshold)
@@ -140,7 +140,7 @@
@protocol
"""Tests the sharing of a zero Zp element using PRSS."""
self.assert_type(a, Share)

opened_a = runtime.open(a, threshold=2*runtime.threshold)
@@ -150,7 +150,7 @@
@protocol
"""Test double-sharing of random numbers using PRSS."""
+        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))