viff

changeset 838:bba8a625972a

Two-player runtime based on Paillier encryption. This implements a multiplication protocol for two players described here by Claudio Orlandi: http://article.gmane.org/gmane.comp.cryptography.viff.devel/290 The key ingredient is the homomorphic Paillier encryption scheme.
author Martin Geisler <mg@daimi.au.dk>
date Tue, 15 Jul 2008 23:35:59 +0200
parents 99dc1bb4cddf
children 45dfc10a1363
files viff/paillier.py
diffstat 1 files changed, 126 insertions(+), 0 deletions(-) [+]
line diff
     1.1 --- a/viff/paillier.py	Sat Jun 21 13:02:57 2008 +0200
     1.2 +++ b/viff/paillier.py	Tue Jul 15 23:35:59 2008 +0200
     1.3 @@ -15,9 +15,12 @@
     1.4  # You should have received a copy of the GNU Lesser General Public
     1.5  # License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
     1.6  
     1.7 +from twisted.internet.defer import Deferred, gatherResults
     1.8  import gmpy
     1.9  
    1.10 +from viff.runtime import BasicRuntime, increment_pc, Share, gather_shares
    1.11  from viff.util import rand, find_random_prime
    1.12 +from viff.field import GF
    1.13  
    1.14  def L(u, n):
    1.15      return (u-1)/n
    1.16 @@ -51,3 +54,126 @@
    1.17      numer = L(pow(c, lm, n*n), n)
    1.18      denom = L(pow(g, lm, n*n), n)
    1.19      return (numer*gmpy.invert(denom, n)) % n
    1.20 +
    1.21 +
    1.22 +class PaillierRuntime(BasicRuntime):
    1.23 +
    1.24 +    def add_player(self, player, protocol):
    1.25 +        BasicRuntime.add_player(self, player, protocol)
    1.26 +        if player.id == self.id:
    1.27 +            self.player = player
    1.28 +        else:
    1.29 +            self.peer = player
    1.30 +
    1.31 +    @increment_pc
    1.32 +    def share(self, inputters, field, number=None):
    1.33 +        """Share *number* additively."""
    1.34 +        assert number is None or self.id in inputters
    1.35 +
    1.36 +        results = []
    1.37 +        for peer_id in inputters:
    1.38 +            if peer_id == self.id:
    1.39 +                a = field(rand.randint(0, field.modulus - 1))
    1.40 +                b = number - a
    1.41 +
    1.42 +                results.append(Share(self, a.field, a))
    1.43 +                pc = tuple(self.program_counter)
    1.44 +                self.protocols[self.peer.id].sendShare(pc, b)
    1.45 +            else:
    1.46 +                share = self._expect_share(peer_id, field)
    1.47 +                results.append(share)
    1.48 +
    1.49 +        # Unpack a singleton list.
    1.50 +        if len(results) == 1:
    1.51 +            return results[0]
    1.52 +        else:
    1.53 +            return results
    1.54 +
    1.55 +    @increment_pc
    1.56 +    def open(self, share, receivers=None):
    1.57 +        """Open *share* to *receivers* (defaults to both players)."""
    1.58 +
    1.59 +        def exchange(a):
    1.60 +            pc = tuple(self.program_counter)
    1.61 +            self.protocols[self.peer.id].sendShare(pc, a)
    1.62 +            result = self._expect_share(self.peer.id, share.field)
    1.63 +            result.addCallback(lambda b: a + b)
    1.64 +            return result
    1.65 +
    1.66 +        result = share.clone()
    1.67 +        self.schedule_callback(result, exchange)
    1.68 +        return result
    1.69 +
    1.70 +    def add(self, share_a, share_b):
    1.71 +        """Addition of shares.
    1.72 +
    1.73 +        Communication cost: none.
    1.74 +        """
    1.75 +        field = getattr(share_a, "field", getattr(share_b, "field", None))
    1.76 +        if not isinstance(share_a, Share):
    1.77 +            share_a = Share(self, field, share_a)
    1.78 +        if not isinstance(share_b, Share):
    1.79 +            share_b = Share(self, field, share_b)
    1.80 +
    1.81 +        result = gather_shares([share_a, share_b])
    1.82 +        result.addCallback(lambda (a, b): a + b)
    1.83 +        return result
    1.84 +
    1.85 +    def mul(self, share_a, share_b):
    1.86 +        """Multiplication of shares."""
    1.87 +        field = getattr(share_a, "field", getattr(share_b, "field", None))
    1.88 +
    1.89 +        k = self.options.security_parameter
    1.90 +        n = min(self.player.pubkey[0], self.peer.pubkey[0])
    1.91 +        assert field.modulus**2 + 2**k < n, \
    1.92 +            "Need bigger Paillier keys to multiply."
    1.93 +
    1.94 +        if not isinstance(share_a, Share):
    1.95 +            share_a = Share(self, field, share_a)
    1.96 +        if not isinstance(share_b, Share):
    1.97 +            share_b = Share(self, field, share_b)
    1.98 +
    1.99 +        def finish_mul((a, b)):
   1.100 +            pc = tuple(self.program_counter)
   1.101 +            send_data = self.protocols[self.peer.id].sendData
   1.102 +
   1.103 +            if hash(pc) % 2 == self.id:
   1.104 +                # We play the role of P1.
   1.105 +                a1, b1 = a, b
   1.106 +                enc_a1 = encrypt(a1.value, self.player.pubkey)
   1.107 +                enc_b1 = encrypt(b1.value, self.player.pubkey)
   1.108 +                send_data(pc, "paillier", enc_a1)
   1.109 +                send_data(pc, "paillier", enc_b1)
   1.110 +
   1.111 +                enc_c1 = Share(self, field)
   1.112 +                self._expect_data(self.peer.id, "paillier", enc_c1)
   1.113 +                c1 = enc_c1.addCallback(decrypt, self.player.seckey)
   1.114 +                c1.addCallback(lambda c: long(c) + a1 * b1)
   1.115 +                return c1
   1.116 +            else:
   1.117 +                # We play the role of P2.
   1.118 +                a2, b2 = a, b
   1.119 +                enc_a1 = Deferred()
   1.120 +                self._expect_data(self.peer.id, "paillier", enc_a1)
   1.121 +                enc_b1 = Deferred()
   1.122 +                self._expect_data(self.peer.id, "paillier", enc_b1)
   1.123 +
   1.124 +                nsq = self.peer.pubkey[0]**2
   1.125 +                # Calculate a1 * b2 and b1 * a2 inside the encryption.
   1.126 +                enc_a1_b2 = enc_a1.addCallback(pow, b2.value, nsq)
   1.127 +                enc_b1_a2 = enc_b1.addCallback(pow, a2.value, nsq)
   1.128 +
   1.129 +                # Chose and encrypt r.
   1.130 +                r = rand.randint(0, 2 * field.modulus**2 + 2**k)
   1.131 +                enc_r = encrypt(r, self.peer.pubkey)
   1.132 +
   1.133 +                c1 = gatherResults([enc_a1_b2, enc_b1_a2])
   1.134 +                c1.addCallback(lambda (a,b): a * b * enc_r)
   1.135 +                c1.addCallback(lambda c: send_data(pc, "paillier", c))
   1.136 +
   1.137 +                c2 = a2 * b2 - r
   1.138 +                return Share(self, field, c2)
   1.139 +
   1.140 +        result = gather_shares([share_a, share_b])
   1.141 +        result.addCallback(finish_mul)
   1.142 +        return result