viff

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 diff
     1.1 --- a/viff/bedoza_triple.py	Wed Jul 14 13:59:24 2010 +0200
     1.2 +++ b/viff/bedoza_triple.py	Wed Jul 14 16:44:20 2010 +0200
     1.3 @@ -114,35 +114,60 @@
     1.4  
     1.5  
     1.6  class ModifiedPaillier(object):
     1.7 -    """See Ivan's paper, beginning of section 6."""
     1.8 +    """A slight modification of the Paillier cryptosystem.
     1.9 +
    1.10 +    This modification has plaintext space [-(n-1)/ ; (n-1)/2] rather
    1.11 +    than the usual Z_n where n is the Paillier modulus.
    1.12 +
    1.13 +    See Ivan's paper, beginning of section 6.
    1.14 +    """
    1.15  
    1.16      def __init__(self, runtime, random):
    1.17          self.runtime = runtime;
    1.18          self.random = random
    1.19  
    1.20 +    def _f(self, x, n):
    1.21 +        if x >= 0:
    1.22 +            return x
    1.23 +        else:
    1.24 +            return n + x
    1.25 +
    1.26 +    def _f_inverse(self, y, n):
    1.27 +        if 0 <= y <= (n + 1) / 2:
    1.28 +            return y
    1.29 +        else:
    1.30 +            return y - n
    1.31 +
    1.32      def encrypt(self, value, player_id=None):
    1.33 -        """Encrypt using public key of player player_id. Defaults to own public key."""
    1.34 -        assert isinstance(value, int), \
    1.35 -            "paillier encrypts only integers, got %s" % value.__class__        
    1.36 -        # TODO: Assert value in the right range.
    1.37 -        
    1.38 +        """Encrypt using public key of player player_id.
    1.39 +
    1.40 +        Defaults to own public key.
    1.41 +        """
    1.42 +        assert isinstance(value, int) or isinstance(value, long), \
    1.43 +            "paillier: encrypts only integers and longs, got %s" % value.__class__
    1.44          if not player_id:
    1.45              player_id = self.runtime.id
    1.46 -
    1.47 +        n = self.runtime.players[player_id].pubkey['n']
    1.48 +        min = -(n - 1) / 2 + 1
    1.49 +        max = (n + 1) / 2
    1.50 +        assert min <= value <= max, \
    1.51 +            "paillier: plaintext %d outside legal range [-(n-1)/2+1 ; (n+1)/2] = " \
    1.52 +            "[%d ; %d]"  % (value, min, max)
    1.53          pubkey = self.runtime.players[player_id].pubkey
    1.54 -
    1.55 -        randomness = self.random.randint(1, long(pubkey['n']))
    1.56 -        # TODO: Transform value.
    1.57 -        enc = pypaillier.encrypt_r(value, randomness, pubkey)
    1.58 -        return enc
    1.59 +        randomness = self.random.randint(1, long(n))
    1.60 +        return pypaillier.encrypt_r(self._f(value, n), randomness, pubkey)
    1.61  
    1.62      def decrypt(self, enc_value):
    1.63          """Decrypt using own private key."""
    1.64 -        assert isinstance(enc_value, long), \
    1.65 +        assert isinstance(enc_value, int) or isinstance(enc_value, long), \
    1.66              "paillier decrypts only longs, got %s" % enc_value.__class__
    1.67 -        # TODO: Assert enc_value in the right range.
    1.68 +        n = self.runtime.players[self.runtime.id].pubkey['n']
    1.69 +        n_square = self.runtime.players[self.runtime.id].pubkey['n_square']
    1.70 +        assert 0 <= enc_value < n_square, \
    1.71 +            "paillier: ciphertext %d not in range [0 ; n^2] = [0 ; %d]" \
    1.72 +            % (enc_value, n_square)
    1.73          seckey = self.runtime.players[self.runtime.id].seckey
    1.74 -        return pypaillier.decrypt(enc_value, seckey)
    1.75 +        return self._f_inverse(pypaillier.decrypt(enc_value, seckey), n)
    1.76  
    1.77  
    1.78  class TripleGenerator(object):
    1.79 @@ -202,12 +227,13 @@
    1.80      def _add_macs(self, partial_shares):
    1.81          """Adds macs to the set of PartialBeDOZaShares.
    1.82          
    1.83 -        Returns a list of full shares, e.g. including macs.
    1.84 -        (the full shares are deferreds of type BeDOZaShare.)
    1.85 -        """
    1.86 -        
    1.87 -        # TODO: Currently only does this for one partial share.
    1.88 +        Returns a tuple with a single element that is a list of full
    1.89 +        shares, e.g. including macs.  (the full shares are deferreds
    1.90 +        of type BeDOZaShare.)
    1.91  
    1.92 +        TODO: We have to return the list in a tuple due to some
    1.93 +        Twisted thing.
    1.94 +        """        
    1.95          # TODO: Would be nice with a class ShareContents like the class
    1.96          # PartialShareContents used here.
    1.97          
    1.98 @@ -215,6 +241,7 @@
    1.99  
   1.100          mac_keys = []
   1.101  
   1.102 +        # TODO: Currently only support for one share.
   1.103          i = 0
   1.104  
   1.105          c_list = []
   1.106 @@ -222,43 +249,20 @@
   1.107              # TODO: This is probably not the fastes way to generate
   1.108              # the betas.
   1.109              beta = self.random.randint(0, 2**(4 * self.k))
   1.110 -        
   1.111              # TODO: Outcommented until mod paillier works for negative numbers.
   1.112              #if rand.choice([True, False]):
   1.113              #    beta = -beta
   1.114 -            
   1.115              enc_beta = self.paillier.encrypt(beta, player_id=j+1)
   1.116              c_j = partial_shares[i].enc_shares[j]
   1.117 -            c = (pow(c_j, self.alpha, self.n2) * enc_beta) % self.n2
   1.118 -            if self.runtime.id == 1 and j + 1 == 2:
   1.119 -                print
   1.120 -                print
   1.121 -                print "p=", self.p
   1.122 -                print "player 1: public key of player %s is %s" % (j+1, 
   1.123 -                                                                   self.runtime.players[j+1].pubkey)
   1.124 -                print "player %s encrypted share: %s" % (j+1, partial_shares[i].enc_shares[j])
   1.125 -                print "alpha = %s = %s" % (self.alpha, self.Zp(self.alpha))
   1.126 -                print "beta = %s = %s" %  (beta, self.Zp(beta))
   1.127 -                print "enc_beta =", enc_beta
   1.128 -                print "Player 1 sends c = %s to player %d" % (c, j+1)
   1.129 -                print
   1.130 -                print
   1.131 +            n2 = self.runtime.players[j + 1].pubkey['n_square']
   1.132 +            c = (pow(c_j, self.alpha, n2) * enc_beta) % n2
   1.133              c_list.append(c)
   1.134              mac_keys.append(self.Zp(beta))
   1.135          received_cs = _send(self.runtime, c_list)
   1.136  
   1.137          def finish_sharing(recevied_cs):
   1.138              mac_key_list = BeDOZaKeyList(self.alpha, mac_keys)
   1.139 -            # print "received cs:", received_cs.result
   1.140              decrypted_cs = [self.Zp(self.paillier.decrypt(c)) for c in received_cs.result]
   1.141 -            if self.runtime.id == 2:
   1.142 -                print
   1.143 -                print
   1.144 -                print "PLAYER2: Got %s from player 1" % received_cs.result[0]
   1.145 -                print "PLAYER2: Decrypted c from player 1: %s" % decrypted_cs[0]
   1.146 -                print "PLAYER2: My share a_2 =", partial_shares[0].value
   1.147 -                print
   1.148 -
   1.149              mac_msg_list = BeDOZaMessageList(decrypted_cs)
   1.150              # Twisted HACK: Need to pack share into tuple.
   1.151              return BeDOZaShare(self.runtime,
     2.1 --- a/viff/test/test_bedoza_triple.py	Wed Jul 14 13:59:24 2010 +0200
     2.2 +++ b/viff/test/test_bedoza_triple.py	Wed Jul 14 16:44:20 2010 +0200
     2.3 @@ -16,6 +16,7 @@
     2.4  # License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
     2.5  
     2.6  import sys
     2.7 +from exceptions import AssertionError
     2.8  
     2.9  # We don't need secure random numbers for test purposes.
    2.10  from random import Random
    2.11 @@ -100,7 +101,7 @@
    2.12          # In production, paillier keys should be something like 2000
    2.13          # bit. For test purposes, it is ok to use small keys.
    2.14          # TODO: paillier freezes if key size is too small, e.g. 13.
    2.15 -        return generate_configs(paillier=NaClPaillier(70), *args)
    2.16 +        return generate_configs(paillier=NaClPaillier(250), *args)
    2.17  
    2.18  
    2.19  class DataTransferTest(BeDOZaTestCase):
    2.20 @@ -144,16 +145,64 @@
    2.21          encrypted_val = paillier.encrypt(val)
    2.22          decrypted_val = paillier.decrypt(encrypted_val)
    2.23          self.assertEquals(val, decrypted_val)
    2.24 +
    2.25 +    @protocol
    2.26 +    def test_modified_paillier_can_decrypt_encrypted_zero(self, runtime):
    2.27 +        paillier = ModifiedPaillier(runtime, Random(338301))
    2.28 +        val = 0
    2.29 +        encrypted_val = paillier.encrypt(val)
    2.30 +        decrypted_val = paillier.decrypt(encrypted_val)
    2.31 +        self.assertEquals(val, decrypted_val)
    2.32 +
    2.33 +    @protocol
    2.34 +    def test_modified_paillier_can_decrypt_encrypted_minus_one(self, runtime):
    2.35 +        paillier = ModifiedPaillier(runtime, Random(19623))
    2.36 +        val = -1
    2.37 +        encrypted_val = paillier.encrypt(val)
    2.38 +        decrypted_val = paillier.decrypt(encrypted_val)
    2.39 +        self.assertEquals(val, decrypted_val)
    2.40 +
    2.41 +    @protocol
    2.42 +    def test_modified_paillier_can_decrypt_encrypted_max_val(self, runtime):
    2.43 +        paillier = ModifiedPaillier(runtime, Random(825604))
    2.44 +        n = runtime.players[runtime.id].pubkey['n']
    2.45 +        val = (n + 1) / 2
    2.46 +        encrypted_val = paillier.encrypt(val)
    2.47 +        decrypted_val = paillier.decrypt(encrypted_val)
    2.48 +        self.assertEquals(val, decrypted_val)
    2.49 +
    2.50 +    @protocol
    2.51 +    def test_modified_paillier_can_decrypt_encrypted_min_val(self, runtime):
    2.52 +        paillier = ModifiedPaillier(runtime, Random(554424))
    2.53 +        n = runtime.players[runtime.id].pubkey['n']
    2.54 +        val = -(n - 1) / 2 + 1
    2.55 +        encrypted_val = paillier.encrypt(val)
    2.56 +        decrypted_val = paillier.decrypt(encrypted_val)
    2.57 +        self.assertEquals(val, decrypted_val)
    2.58   
    2.59      @protocol
    2.60      def test_modified_paillier_can_decrypt_encrypted_positive(self, runtime):
    2.61          paillier = ModifiedPaillier(runtime, Random(777737))
    2.62 -        val = 7
    2.63 +        val = 73423
    2.64          encrypted_val = paillier.encrypt(val)
    2.65          decrypted_val = paillier.decrypt(encrypted_val)
    2.66          self.assertEquals(val, decrypted_val)
    2.67  
    2.68      @protocol
    2.69 +    def test_encrypting_too_large_number_raises_exception(self, runtime):
    2.70 +        paillier = ModifiedPaillier(runtime, Random(825604))
    2.71 +        n = runtime.players[runtime.id].pubkey['n']
    2.72 +        val = 1 + (n + 1) / 2
    2.73 +        self.assertRaises(AssertionError, paillier.encrypt, val)
    2.74 +
    2.75 +    @protocol
    2.76 +    def test_encrypting_too_small_number_raises_exception(self, runtime):
    2.77 +        paillier = ModifiedPaillier(runtime, Random(554424))
    2.78 +        n = runtime.players[runtime.id].pubkey['n']
    2.79 +        val = -(n - 1) / 2
    2.80 +        self.assertRaises(AssertionError, paillier.encrypt, val)
    2.81 +
    2.82 +    @protocol
    2.83      def test_modified_paillier_can_encrypt_to_other(self, runtime):
    2.84          paillier = ModifiedPaillier(runtime, Random(57503))
    2.85          msg = []
    2.86 @@ -165,13 +214,7 @@
    2.87              self.assertEquals(range(1, self.num_players + 1), plain)
    2.88          runtime.schedule_callback(received, verify)
    2.89          return received
    2.90 -        
    2.91  
    2.92 -#    @protocol
    2.93 -#    def test_modified_paillier_can_decrypt_encrypted_negative(self, runtime):
    2.94 -#        pass
    2.95 -
    2.96 -    # TODO: Boundary tests.
    2.97  
    2.98  def partial_share(random, runtime, Zp, val, paillier=None):
    2.99      if not paillier:
   2.100 @@ -246,7 +289,6 @@
   2.101                  # Twisted HACK: Need to unpack value ls[0] from tuple.
   2.102                  opened_share = runtime.open(ls[0][0])
   2.103                  def verify(open_share):
   2.104 -                    print "Share opened:", open_share
   2.105                      self.assertEquals(secret, open_share.value)
   2.106                  runtime.schedule_callback(opened_share, verify)
   2.107                  return opened_share
   2.108 @@ -255,8 +297,6 @@
   2.109          runtime.schedule_callback(share, add_macs)
   2.110          return share
   2.111  
   2.112 -    test_add_macs_produces_correct_sharing.skip = "add_macs not implemented fully yet"
   2.113 -
   2.114          
   2.115  #    @protocol
   2.116  #    def test_add_macs_preserves_value_of_sharing(self, runtime):