1.1 --- a/viff/bedoza/bedoza_triple.py	Mon Oct 04 12:04:47 2010 +0200
     1.2 +++ b/viff/bedoza/bedoza_triple.py	Mon Oct 04 21:51:33 2010 +0200
     1.3 @@ -65,6 +65,7 @@
     1.4          self.k = self._bit_length_of(p)
     1.5          self.security_parameter = security_parameter
     1.6          self.u_bound = 2**(self.security_parameter + 4 * self.k)
     1.7 +        self.zk_random = Random(self.random.getrandbits(128))
     1.8  
     1.9          paillier_random = Random(self.random.getrandbits(128))
    1.10          alpha_random = Random(self.random.getrandbits(128))
    1.11 @@ -374,7 +375,7 @@
    1.12                  return None
    1.13              
    1.14              d.addCallback(lambda values: generate_partial_share_contents(
    1.15 -                    values, self.runtime, self.paillier))
    1.16 +                    values, self.runtime, self.paillier, self.k, self.zk_random))
    1.17              d.addCallback(callBackPartialShareContents, result_shares)
    1.18              return d
    1.19          result_shares = [PartialShare(self.runtime, self.Zp) for _ in a]

     2.1 --- a/viff/bedoza/share.py	Mon Oct 04 12:04:47 2010 +0200
     2.2 +++ b/viff/bedoza/share.py	Mon Oct 04 21:51:33 2010 +0200
     2.3 @@ -15,12 +15,14 @@
     2.4  # You should have received a copy of the GNU Lesser General Public
     2.5  # License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
     2.6  
     2.7 +from gmpy import mpz
     2.8 +
     2.9  from twisted.internet.defer import gatherResults
    2.10  
    2.11 +from viff.bedoza.zero_knowledge import ZKProof
    2.12  from viff.bedoza.shares import PartialShareContents
    2.13 -from viff.bedoza.util import _convolute
    2.14  
    2.15 -def generate_partial_share_contents(field_elements, runtime, paillier):
    2.16 +def generate_partial_share_contents(field_elements, runtime, paillier, k, random):
    2.17      """Protocol for generating partial shares.
    2.18  
    2.19      This protocol corresponds to the "Share" protocol in the document
    2.20 @@ -34,34 +36,71 @@
    2.21      plaintexts are of limited size.
    2.22  
    2.23      Returns a deferred, which yields a list of PartialShareContents.
    2.24 -    """
    2.25 -    
    2.26 +
    2.27 +    """    
    2.28 +    # TODO: We should assert that len(field_elements) == s.
    2.29 +
    2.30 +    # TODO: The gatherResults is used several times in this method in
    2.31 +    # a way that prevents maximal asynchronicity. E.g. all players
    2.32 +    # wait until all zero-knowledge proofs are completed before they
    2.33 +    # start constructing partial shares. However, the callback for a
    2.34 +    # particular partial share could be triggered as soon as the
    2.35 +    # players have completed the zk proof for that share.
    2.36 +
    2.37      runtime.increment_pc()
    2.38  
    2.39      N_squared_list = [paillier.get_modulus_square(player_id)
    2.40                        for player_id in runtime.players]
    2.41  
    2.42      list_of_enc_shares = []
    2.43 +    list_of_random_elements = []
    2.44      for field_element in field_elements:
    2.45 -        list_of_enc_shares.append(paillier.encrypt(field_element.value))
    2.46 +        r, e = paillier.encrypt_r(field_element.value)
    2.47 +        list_of_enc_shares.append(e)
    2.48 +        list_of_random_elements.append(r)
    2.49         
    2.50 -    list_of_enc_shares = runtime.broadcast(runtime.players.keys(), runtime.players.keys(),
    2.51 -                                           str(list_of_enc_shares))
    2.52 -    
    2.53 -    def create_partial_share(list_of_enc_shares, field_elements):
    2.54 -        list_of_enc_shares = [eval(x) for x in list_of_enc_shares]
    2.55 +    list_of_enc_shares = runtime.broadcast(
    2.56 +        runtime.players.keys(), runtime.players.keys(),
    2.57 +        str(list_of_enc_shares))
    2.58  
    2.59 +    def construct_partial_shares(zk_results, list_of_enc_shares, field_elements):
    2.60 +        if False in zk_results:
    2.61 +            raise Exception("Zero-knowledge proof failed")
    2.62          reordered_encrypted_shares = [[] for _ in list_of_enc_shares[0]]
    2.63          for enc_shares in list_of_enc_shares:
    2.64              for inx, enc_share in enumerate(enc_shares):
    2.65                  reordered_encrypted_shares[inx].append(enc_share)
    2.66 +        partial_share_contents = []
    2.67 +        for enc_shares, field_element \
    2.68 +                in zip(reordered_encrypted_shares, field_elements):
    2.69 +            partial_share_contents.append(PartialShareContents(
    2.70 +                    field_element, enc_shares, N_squared_list))
    2.71 +        return partial_share_contents
    2.72  
    2.73 -        partialShareContents = []
    2.74 -        for enc_shares, field_element in zip(reordered_encrypted_shares, field_elements):
    2.75 -            partialShareContents.append(PartialShareContents(field_element, enc_shares, N_squared_list))
    2.76 -        return partialShareContents
    2.77 +    def do_zk_proofs(list_of_enc_shares, field_elements):
    2.78 +        zk_results = []
    2.79 +        list_of_enc_shares = [eval(x) for x in list_of_enc_shares]
    2.80 +
    2.81 +        # We expect all players to broadcast the same number of
    2.82 +        # encrypted shares.
    2.83 +        assert all([len(enc_shares) == len(list_of_enc_shares[0]) 
    2.84 +                    for enc_shares in list_of_enc_shares])
    2.85 +
    2.86 +        for i in range(runtime.num_players):
    2.87 +            x, r = None, None
    2.88 +            if runtime.id == i + 1:
    2.89 +                x, r = [mpz(e.value) 
    2.90 +                        for e in field_elements], list_of_random_elements
    2.91 +            zk_proof = ZKProof(
    2.92 +                len(field_elements), i + 1, k, runtime, list_of_enc_shares[i],
    2.93 +                random=random, x=x, r=r, paillier=paillier)
    2.94 +            zk_result = zk_proof.start()
    2.95 +            zk_results.append(zk_result)
    2.96 +        d = gatherResults(zk_results)
    2.97 +        runtime.schedule_callback(
    2.98 +            d, construct_partial_shares, list_of_enc_shares, field_elements)
    2.99 +        return d
   2.100  
   2.101      d = gatherResults(list_of_enc_shares)
   2.102 -    runtime.schedule_callback(d, create_partial_share, field_elements)
   2.103 +    runtime.schedule_callback(d, do_zk_proofs, field_elements)
   2.104      return d
   2.105 -        

     3.1 --- a/viff/test/bedoza/test_bedoza_triple.py	Mon Oct 04 12:04:47 2010 +0200
     3.2 +++ b/viff/test/bedoza/test_bedoza_triple.py	Mon Oct 04 21:51:33 2010 +0200
     3.3 @@ -39,6 +39,7 @@
     3.4  from viff.bedoza.util import _send, _convolute, _convolute_gf_elm
     3.5  from viff.bedoza.add_macs import add_macs
     3.6  from viff.bedoza.share_generators import ShareGenerator, PartialShareGenerator
     3.7 +from viff.bedoza.share import generate_partial_share_contents
     3.8  
     3.9  from viff.test.bedoza.util import BeDOZaTestCase, skip_if_missing_packages
    3.10  from viff.test.bedoza.util import TestShareGenerator
    3.11 @@ -497,18 +498,20 @@
    3.12  
    3.13      @protocol
    3.14      def test_share_protocol_single(self, runtime):
    3.15 -        p = 17
    3.16 +        p, k = 17, 5
    3.17          Zp = GF(p)
    3.18          random = Random(3455433 + runtime.id)
    3.19          elms = [Zp(runtime.id)]
    3.20          paillier_random = Random(random.getrandbits(128))
    3.21 +        zk_random = Random(random.getrandbits(128))
    3.22          paillier = ModifiedPaillier(runtime, paillier_random)
    3.23 -        from viff.bedoza.share import generate_partial_share_contents
    3.24 -        partial_shares = generate_partial_share_contents(elms, runtime, paillier)
    3.25 +        partial_shares = generate_partial_share_contents(
    3.26 +            elms, runtime, paillier, k, zk_random)
    3.27  
    3.28          def decrypt(share_contents):
    3.29              self.assertEquals(1, len(share_contents))
    3.30 -            decrypted_share = paillier.decrypt(share_contents[0].enc_shares[runtime.id - 1])
    3.31 +            decrypted_share = paillier.decrypt(
    3.32 +                share_contents[0].enc_shares[runtime.id - 1])
    3.33              decrypted_shares = _convolute(runtime, decrypted_share)
    3.34              def test_sum(vals):
    3.35                  self.assertEquals([Zp(e) for e in [1, 2, 3]], vals)
    3.36 @@ -519,24 +522,29 @@
    3.37  
    3.38      @protocol
    3.39      def test_share_protocol_multi(self, runtime):
    3.40 -        p = 17
    3.41 +        p, k = 17, 5
    3.42          Zp = GF(p)
    3.43 -        random = Random(3455433 + runtime.id)
    3.44 +        random = Random(345453 + runtime.id)
    3.45          elms = [Zp(runtime.id), Zp(runtime.id * 3)]
    3.46          paillier_random = Random(random.getrandbits(128))
    3.47 +        zk_random = Random(random.getrandbits(128))
    3.48          paillier = ModifiedPaillier(runtime, paillier_random)
    3.49 -        from viff.bedoza.share import generate_partial_share_contents
    3.50 -        partial_shares = generate_partial_share_contents(elms, runtime, paillier)
    3.51 +        partial_shares = generate_partial_share_contents(
    3.52 +            elms, runtime, paillier, k, zk_random)
    3.53  
    3.54          def decrypt(share_contents):
    3.55              self.assertEquals(2, len(share_contents))
    3.56 -            decrypted_shares = [paillier.decrypt(share_contents[i].enc_shares[runtime.id - 1])
    3.57 +            decrypted_shares = [paillier.decrypt(
    3.58 +                    share_contents[i].enc_shares[runtime.id - 1])
    3.59                                  for i in range(2)]
    3.60 -            decrypted_shares = [_convolute(runtime, decrypted_shares[i]) for i in range(2)]
    3.61 +            decrypted_shares = [_convolute(runtime, decrypted_shares[i])
    3.62 +                                for i in range(2)]
    3.63              def test_sum(vals, should_be):
    3.64                  self.assertEquals([Zp(e) for e in should_be], vals)
    3.65 -            runtime.schedule_callback(decrypted_shares[0], test_sum, [1, 2, 3])
    3.66 -            runtime.schedule_callback(decrypted_shares[1], test_sum, [3, 6, 9])
    3.67 +            runtime.schedule_callback(
    3.68 +                decrypted_shares[0], test_sum, [1, 2, 3])
    3.69 +            runtime.schedule_callback(
    3.70 +                decrypted_shares[1], test_sum, [3, 6, 9])
    3.71  
    3.72          runtime.schedule_callback(partial_shares, decrypt)
    3.73          return partial_shares
    3.74 @@ -627,6 +635,7 @@
    3.75          
    3.76  
    3.77  skip_if_missing_packages(
    3.78 +    ShareTest,
    3.79      ModifiedPaillierTest,
    3.80      PartialShareGeneratorTest,
    3.81      TripleTest,