viff

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 diff
     1.1 --- a/viff/aes.py	Wed Feb 25 21:14:30 2009 +0100
     1.2 +++ b/viff/aes.py	Thu Feb 26 19:35:08 2009 +0100
     1.3 @@ -34,9 +34,8 @@
     1.4      assert isinstance(share, Share) and share.field == GF256, \
     1.5          "Parameter must be GF256 share."
     1.6  
     1.7 -    r_bits = [share.runtime.prss_share_random(GF256, binary=True) \
     1.8 -                  for i in range(8)]
     1.9 -    
    1.10 +    r_bits = share.runtime.prss_share_random_multi(GF256, 8, binary=True)
    1.11 +
    1.12      if (use_lin_comb):
    1.13          r = share.runtime.lin_comb([2 ** i for i in range(8)], r_bits)
    1.14      else:
     2.1 --- a/viff/passive.py	Wed Feb 25 21:14:30 2009 +0100
     2.2 +++ b/viff/passive.py	Thu Feb 26 19:35:08 2009 +0100
     2.3 @@ -21,7 +21,7 @@
     2.4  
     2.5  from viff import shamir
     2.6  from viff.runtime import Runtime, increment_pc, Share, ShareList, gather_shares
     2.7 -from viff.prss import prss, prss_lsb, prss_zero
     2.8 +from viff.prss import prss, prss_lsb, prss_zero, prss_multi
     2.9  from viff.field import GF256, FieldElement
    2.10  from viff.util import rand, profile
    2.11  
    2.12 @@ -352,6 +352,29 @@
    2.13          return result
    2.14  
    2.15      @increment_pc
    2.16 +    def prss_share_random_multi(self, field, quantity, binary=False):
    2.17 +        """Does the same as calling *quantity* times :meth:`prss_share_random`,
    2.18 +        but with less calls to the PRF. Sampling of a binary element is only
    2.19 +        possible if the field is :class:`GF256`.
    2.20 +
    2.21 +        Communication cost: none.
    2.22 +        """
    2.23 +        assert not binary or field == GF256, "Binary sampling not possible " \
    2.24 +            "for this field, use prss_share_random()."
    2.25 +
    2.26 +        if field is GF256 and binary:
    2.27 +            modulus = 2
    2.28 +        else:
    2.29 +            modulus = field.modulus
    2.30 +
    2.31 +        # Key used for PRSS.
    2.32 +        prss_key = tuple(self.program_counter)
    2.33 +        prfs = self.players[self.id].prfs(modulus ** quantity)
    2.34 +        shares = prss_multi(self.num_players, self.id, field, prfs, prss_key,
    2.35 +                            modulus, quantity)
    2.36 +        return [Share(self, field, share) for share in shares]
    2.37 +
    2.38 +    @increment_pc
    2.39      def prss_share_zero(self, field):
    2.40          """Generate shares of the zero element from the field given.
    2.41  
     3.1 --- a/viff/prss.py	Wed Feb 25 21:14:30 2009 +0100
     3.2 +++ b/viff/prss.py	Thu Feb 26 19:35:08 2009 +0100
     3.3 @@ -120,6 +120,19 @@
     3.4      rep_shares = random_replicated_sharing(j, prfs, key)
     3.5      return convert_replicated_shamir(n, j, field, rep_shares)
     3.6  
     3.7 +def prss_multi(n, j, field, prfs, key, modulus, quantity):
     3.8 +    """Does the same as :meth:`prss`, but multiple times in order to 
     3.9 +    call the PRFs less frequently.
    3.10 +    """
    3.11 +    prf_results = random_replicated_sharing(j, prfs, key)
    3.12 +    rep_shares_list = [[] for i in range(quantity)]
    3.13 +    for subset, result in prf_results:
    3.14 +        for i in range(quantity):
    3.15 +            rep_shares_list[i].append((subset, result % modulus))
    3.16 +            result /= modulus
    3.17 +    return [convert_replicated_shamir(n, j, field, rep_shares) 
    3.18 +            for rep_shares in rep_shares_list]
    3.19 +
    3.20  @fake(lambda n, j, field, prfs, key: (field(7), GF256(1)))
    3.21  def prss_lsb(n, j, field, prfs, key):
    3.22      """Share a pseudo-random number and its least significant bit.
     4.1 --- a/viff/test/test_runtime_prss.py	Wed Feb 25 21:14:30 2009 +0100
     4.2 +++ b/viff/test/test_runtime_prss.py	Thu Feb 26 19:35:08 2009 +0100
     4.3 @@ -116,6 +116,18 @@
     4.4          return opened_a
     4.5  
     4.6      @protocol
     4.7 +    def test_prss_share_random_multi_bit(self, runtime):
     4.8 +        """Tests the sharing of several 0/1 GF256 elements using PRSS."""
     4.9 +        a_list = runtime.prss_share_random_multi(field=GF256, quantity=8, binary=True)
    4.10 +
    4.11 +        for a in a_list:
    4.12 +            self.assert_type(a, Share)
    4.13 +            opened_a = runtime.open(a)
    4.14 +            opened_a.addCallback(self.assertIn, [GF256(0), GF256(1)])
    4.15 +
    4.16 +        return gather_shares(a_list)
    4.17 +
    4.18 +    @protocol
    4.19      def test_prss_share_zero_bit(self, runtime):
    4.20          """Tests the sharing of a zero GF256 element using PRSS."""
    4.21          a = runtime.prss_share_zero(GF256)