changeset 1493:e9465b35b0fe

BeDOZa: The add_macs method works for a single share.
author Thomas P Jakobsen <tpj@cs.au.dk>
date Wed, 14 Jul 2010 16:44:20 +0200
parents 3627b0e969c9
children cff86d2dc0ee
files viff/bedoza_triple.py viff/test/test_bedoza_triple.py
diffstat 2 files changed, 100 insertions(+), 56 deletions(-) [+]
line wrap: on
line diff
--- a/viff/bedoza_triple.py	Wed Jul 14 13:59:24 2010 +0200
+++ b/viff/bedoza_triple.py	Wed Jul 14 16:44:20 2010 +0200
@@ -114,35 +114,60 @@
 
 
 class ModifiedPaillier(object):
-    """See Ivan's paper, beginning of section 6."""
+    """A slight modification of the Paillier cryptosystem.
+
+    This modification has plaintext space [-(n-1)/ ; (n-1)/2] rather
+    than the usual Z_n where n is the Paillier modulus.
+
+    See Ivan's paper, beginning of section 6.
+    """
 
     def __init__(self, runtime, random):
         self.runtime = runtime;
         self.random = random
 
+    def _f(self, x, n):
+        if x >= 0:
+            return x
+        else:
+            return n + x
+
+    def _f_inverse(self, y, n):
+        if 0 <= y <= (n + 1) / 2:
+            return y
+        else:
+            return y - n
+
     def encrypt(self, value, player_id=None):
-        """Encrypt using public key of player player_id. Defaults to own public key."""
-        assert isinstance(value, int), \
-            "paillier encrypts only integers, got %s" % value.__class__        
-        # TODO: Assert value in the right range.
-        
+        """Encrypt using public key of player player_id.
+
+        Defaults to own public key.
+        """
+        assert isinstance(value, int) or isinstance(value, long), \
+            "paillier: encrypts only integers and longs, got %s" % value.__class__
         if not player_id:
             player_id = self.runtime.id
-
+        n = self.runtime.players[player_id].pubkey['n']
+        min = -(n - 1) / 2 + 1
+        max = (n + 1) / 2
+        assert min <= value <= max, \
+            "paillier: plaintext %d outside legal range [-(n-1)/2+1 ; (n+1)/2] = " \
+            "[%d ; %d]"  % (value, min, max)
         pubkey = self.runtime.players[player_id].pubkey
-
-        randomness = self.random.randint(1, long(pubkey['n']))
-        # TODO: Transform value.
-        enc = pypaillier.encrypt_r(value, randomness, pubkey)
-        return enc
+        randomness = self.random.randint(1, long(n))
+        return pypaillier.encrypt_r(self._f(value, n), randomness, pubkey)
 
     def decrypt(self, enc_value):
         """Decrypt using own private key."""
-        assert isinstance(enc_value, long), \
+        assert isinstance(enc_value, int) or isinstance(enc_value, long), \
             "paillier decrypts only longs, got %s" % enc_value.__class__
-        # TODO: Assert enc_value in the right range.
+        n = self.runtime.players[self.runtime.id].pubkey['n']
+        n_square = self.runtime.players[self.runtime.id].pubkey['n_square']
+        assert 0 <= enc_value < n_square, \
+            "paillier: ciphertext %d not in range [0 ; n^2] = [0 ; %d]" \
+            % (enc_value, n_square)
         seckey = self.runtime.players[self.runtime.id].seckey
-        return pypaillier.decrypt(enc_value, seckey)
+        return self._f_inverse(pypaillier.decrypt(enc_value, seckey), n)
 
 
 class TripleGenerator(object):
@@ -202,12 +227,13 @@
     def _add_macs(self, partial_shares):
         """Adds macs to the set of PartialBeDOZaShares.
         
-        Returns a list of full shares, e.g. including macs.
-        (the full shares are deferreds of type BeDOZaShare.)
-        """
-        
-        # TODO: Currently only does this for one partial share.
+        Returns a tuple with a single element that is a list of full
+        shares, e.g. including macs.  (the full shares are deferreds
+        of type BeDOZaShare.)
 
+        TODO: We have to return the list in a tuple due to some
+        Twisted thing.
+        """        
         # TODO: Would be nice with a class ShareContents like the class
         # PartialShareContents used here.
         
@@ -215,6 +241,7 @@
 
         mac_keys = []
 
+        # TODO: Currently only support for one share.
         i = 0
 
         c_list = []
@@ -222,43 +249,20 @@
             # TODO: This is probably not the fastes way to generate
             # the betas.
             beta = self.random.randint(0, 2**(4 * self.k))
-        
             # TODO: Outcommented until mod paillier works for negative numbers.
             #if rand.choice([True, False]):
             #    beta = -beta
-            
             enc_beta = self.paillier.encrypt(beta, player_id=j+1)
             c_j = partial_shares[i].enc_shares[j]
-            c = (pow(c_j, self.alpha, self.n2) * enc_beta) % self.n2
-            if self.runtime.id == 1 and j + 1 == 2:
-                print
-                print
-                print "p=", self.p
-                print "player 1: public key of player %s is %s" % (j+1, 
-                                                                   self.runtime.players[j+1].pubkey)
-                print "player %s encrypted share: %s" % (j+1, partial_shares[i].enc_shares[j])
-                print "alpha = %s = %s" % (self.alpha, self.Zp(self.alpha))
-                print "beta = %s = %s" %  (beta, self.Zp(beta))
-                print "enc_beta =", enc_beta
-                print "Player 1 sends c = %s to player %d" % (c, j+1)
-                print
-                print
+            n2 = self.runtime.players[j + 1].pubkey['n_square']
+            c = (pow(c_j, self.alpha, n2) * enc_beta) % n2
             c_list.append(c)
             mac_keys.append(self.Zp(beta))
         received_cs = _send(self.runtime, c_list)
 
         def finish_sharing(recevied_cs):
             mac_key_list = BeDOZaKeyList(self.alpha, mac_keys)
-            # print "received cs:", received_cs.result
             decrypted_cs = [self.Zp(self.paillier.decrypt(c)) for c in received_cs.result]
-            if self.runtime.id == 2:
-                print
-                print
-                print "PLAYER2: Got %s from player 1" % received_cs.result[0]
-                print "PLAYER2: Decrypted c from player 1: %s" % decrypted_cs[0]
-                print "PLAYER2: My share a_2 =", partial_shares[0].value
-                print
-
             mac_msg_list = BeDOZaMessageList(decrypted_cs)
             # Twisted HACK: Need to pack share into tuple.
             return BeDOZaShare(self.runtime,
--- a/viff/test/test_bedoza_triple.py	Wed Jul 14 13:59:24 2010 +0200
+++ b/viff/test/test_bedoza_triple.py	Wed Jul 14 16:44:20 2010 +0200
@@ -16,6 +16,7 @@
 # License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
 
 import sys
+from exceptions import AssertionError
 
 # We don't need secure random numbers for test purposes.
 from random import Random
@@ -100,7 +101,7 @@
         # In production, paillier keys should be something like 2000
         # bit. For test purposes, it is ok to use small keys.
         # TODO: paillier freezes if key size is too small, e.g. 13.
-        return generate_configs(paillier=NaClPaillier(70), *args)
+        return generate_configs(paillier=NaClPaillier(250), *args)
 
 
 class DataTransferTest(BeDOZaTestCase):
@@ -144,16 +145,64 @@
         encrypted_val = paillier.encrypt(val)
         decrypted_val = paillier.decrypt(encrypted_val)
         self.assertEquals(val, decrypted_val)
+
+    @protocol
+    def test_modified_paillier_can_decrypt_encrypted_zero(self, runtime):
+        paillier = ModifiedPaillier(runtime, Random(338301))
+        val = 0
+        encrypted_val = paillier.encrypt(val)
+        decrypted_val = paillier.decrypt(encrypted_val)
+        self.assertEquals(val, decrypted_val)
+
+    @protocol
+    def test_modified_paillier_can_decrypt_encrypted_minus_one(self, runtime):
+        paillier = ModifiedPaillier(runtime, Random(19623))
+        val = -1
+        encrypted_val = paillier.encrypt(val)
+        decrypted_val = paillier.decrypt(encrypted_val)
+        self.assertEquals(val, decrypted_val)
+
+    @protocol
+    def test_modified_paillier_can_decrypt_encrypted_max_val(self, runtime):
+        paillier = ModifiedPaillier(runtime, Random(825604))
+        n = runtime.players[runtime.id].pubkey['n']
+        val = (n + 1) / 2
+        encrypted_val = paillier.encrypt(val)
+        decrypted_val = paillier.decrypt(encrypted_val)
+        self.assertEquals(val, decrypted_val)
+
+    @protocol
+    def test_modified_paillier_can_decrypt_encrypted_min_val(self, runtime):
+        paillier = ModifiedPaillier(runtime, Random(554424))
+        n = runtime.players[runtime.id].pubkey['n']
+        val = -(n - 1) / 2 + 1
+        encrypted_val = paillier.encrypt(val)
+        decrypted_val = paillier.decrypt(encrypted_val)
+        self.assertEquals(val, decrypted_val)
  
     @protocol
     def test_modified_paillier_can_decrypt_encrypted_positive(self, runtime):
         paillier = ModifiedPaillier(runtime, Random(777737))
-        val = 7
+        val = 73423
         encrypted_val = paillier.encrypt(val)
         decrypted_val = paillier.decrypt(encrypted_val)
         self.assertEquals(val, decrypted_val)
 
     @protocol
+    def test_encrypting_too_large_number_raises_exception(self, runtime):
+        paillier = ModifiedPaillier(runtime, Random(825604))
+        n = runtime.players[runtime.id].pubkey['n']
+        val = 1 + (n + 1) / 2
+        self.assertRaises(AssertionError, paillier.encrypt, val)
+
+    @protocol
+    def test_encrypting_too_small_number_raises_exception(self, runtime):
+        paillier = ModifiedPaillier(runtime, Random(554424))
+        n = runtime.players[runtime.id].pubkey['n']
+        val = -(n - 1) / 2
+        self.assertRaises(AssertionError, paillier.encrypt, val)
+
+    @protocol
     def test_modified_paillier_can_encrypt_to_other(self, runtime):
         paillier = ModifiedPaillier(runtime, Random(57503))
         msg = []
@@ -165,13 +214,7 @@
             self.assertEquals(range(1, self.num_players + 1), plain)
         runtime.schedule_callback(received, verify)
         return received
-        
 
-#    @protocol
-#    def test_modified_paillier_can_decrypt_encrypted_negative(self, runtime):
-#        pass
-
-    # TODO: Boundary tests.
 
 def partial_share(random, runtime, Zp, val, paillier=None):
     if not paillier:
@@ -246,7 +289,6 @@
                 # Twisted HACK: Need to unpack value ls[0] from tuple.
                 opened_share = runtime.open(ls[0][0])
                 def verify(open_share):
-                    print "Share opened:", open_share
                     self.assertEquals(secret, open_share.value)
                 runtime.schedule_callback(opened_share, verify)
                 return opened_share
@@ -255,8 +297,6 @@
         runtime.schedule_callback(share, add_macs)
         return share
 
-    test_add_macs_produces_correct_sharing.skip = "add_macs not implemented fully yet"
-
         
 #    @protocol
 #    def test_add_macs_preserves_value_of_sharing(self, runtime):