## viff

### 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 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.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.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.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.17          prfs = self.players[self.id].prfs(field.modulus)
2.18          zero_share = prss_zero(self.num_players, self.threshold, self.id,
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.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.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
```
```     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.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.6          """Tests the sharing of a zero GF256 element using PRSS."""
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.15          """Tests the sharing of a zero Zp element using PRSS."""
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.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