changeset 1148:d522f9b14b49

Added possibility to share multiple random bits in GF256 with less calls of the PRF.
author Marcel Keller <mkeller@cs.au.dk>
date Thu, 26 Feb 2009 19:35:08 +0100
parents 5ac7a2c23337
children e2759515f57f
files viff/aes.py viff/passive.py viff/prss.py viff/test/test_runtime_prss.py
diffstat 4 files changed, 51 insertions(+), 4 deletions(-) [+]
line wrap: on
line diff
--- a/viff/aes.py	Wed Feb 25 21:14:30 2009 +0100
+++ b/viff/aes.py	Thu Feb 26 19:35:08 2009 +0100
@@ -34,9 +34,8 @@
     assert isinstance(share, Share) and share.field == GF256, \
         "Parameter must be GF256 share."
 
-    r_bits = [share.runtime.prss_share_random(GF256, binary=True) \
-                  for i in range(8)]
-    
+    r_bits = share.runtime.prss_share_random_multi(GF256, 8, binary=True)
+
     if (use_lin_comb):
         r = share.runtime.lin_comb([2 ** i for i in range(8)], r_bits)
     else:
--- a/viff/passive.py	Wed Feb 25 21:14:30 2009 +0100
+++ b/viff/passive.py	Thu Feb 26 19:35:08 2009 +0100
@@ -21,7 +21,7 @@
 
 from viff import shamir
 from viff.runtime import Runtime, increment_pc, Share, ShareList, gather_shares
-from viff.prss import prss, prss_lsb, prss_zero
+from viff.prss import prss, prss_lsb, prss_zero, prss_multi
 from viff.field import GF256, FieldElement
 from viff.util import rand, profile
 
@@ -352,6 +352,29 @@
         return result
 
     @increment_pc
+    def prss_share_random_multi(self, field, quantity, binary=False):
+        """Does the same as calling *quantity* times :meth:`prss_share_random`,
+        but with less calls to the PRF. Sampling of a binary element is only
+        possible if the field is :class:`GF256`.
+
+        Communication cost: none.
+        """
+        assert not binary or field == GF256, "Binary sampling not possible " \
+            "for this field, use prss_share_random()."
+
+        if field is GF256 and binary:
+            modulus = 2
+        else:
+            modulus = field.modulus
+
+        # Key used for PRSS.
+        prss_key = tuple(self.program_counter)
+        prfs = self.players[self.id].prfs(modulus ** quantity)
+        shares = prss_multi(self.num_players, self.id, field, prfs, prss_key,
+                            modulus, quantity)
+        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.
 
--- a/viff/prss.py	Wed Feb 25 21:14:30 2009 +0100
+++ b/viff/prss.py	Thu Feb 26 19:35:08 2009 +0100
@@ -120,6 +120,19 @@
     rep_shares = random_replicated_sharing(j, prfs, key)
     return convert_replicated_shamir(n, j, field, rep_shares)
 
+def prss_multi(n, j, field, prfs, key, modulus, quantity):
+    """Does the same as :meth:`prss`, but multiple times in order to 
+    call the PRFs less frequently.
+    """
+    prf_results = random_replicated_sharing(j, prfs, key)
+    rep_shares_list = [[] for i in range(quantity)]
+    for subset, result in prf_results:
+        for i in range(quantity):
+            rep_shares_list[i].append((subset, result % modulus))
+            result /= modulus
+    return [convert_replicated_shamir(n, j, field, rep_shares) 
+            for rep_shares in rep_shares_list]
+
 @fake(lambda n, j, field, prfs, key: (field(7), GF256(1)))
 def prss_lsb(n, j, field, prfs, key):
     """Share a pseudo-random number and its least significant bit.
--- a/viff/test/test_runtime_prss.py	Wed Feb 25 21:14:30 2009 +0100
+++ b/viff/test/test_runtime_prss.py	Thu Feb 26 19:35:08 2009 +0100
@@ -116,6 +116,18 @@
         return opened_a
 
     @protocol
+    def test_prss_share_random_multi_bit(self, runtime):
+        """Tests the sharing of several 0/1 GF256 elements using PRSS."""
+        a_list = runtime.prss_share_random_multi(field=GF256, quantity=8, binary=True)
+
+        for a in a_list:
+            self.assert_type(a, Share)
+            opened_a = runtime.open(a)
+            opened_a.addCallback(self.assertIn, [GF256(0), GF256(1)])
+
+        return gather_shares(a_list)
+
+    @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)