viff

view viff/paillier.py @ 1575:cfb8e1485006

find changesets by author, revision, files, or words in the commit message
Updated email address.
author Thomas P Jakobsen <tpj@cs.au.dk>
date Wed Dec 15 13:00:00 2010 +0100 (17 months ago)
parents 7115ba16f72a
children
line source
1 # Copyright 2008 VIFF Development Team.
2 #
3 # This file is part of VIFF, the Virtual Ideal Functionality Framework.
4 #
5 # VIFF is free software: you can redistribute it and/or modify it
6 # under the terms of the GNU Lesser General Public License (LGPL) as
7 # published by the Free Software Foundation, either version 3 of the
8 # License, or (at your option) any later version.
9 #
10 # VIFF is distributed in the hope that it will be useful, but WITHOUT
11 # ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
12 # or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
13 # Public License for more details.
14 #
15 # You should have received a copy of the GNU Lesser General Public
16 # License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
17
18 """Paillier crypto system and two-party runtime.
19
20 The :class:`PaillierRuntime` is a special two-player runtime based on
21 the homomorphic Paillier crypto system.
22
23 From the paper "Public-Key Cryptosystems Based on Composite Degree
24 Residuosity Classes" by Pascal Paillier in EUROCRYPT 1999, 223-238.
25 """
26
27 from twisted.internet.defer import Deferred, gatherResults
28 import gmpy
29
30 from viff.runtime import Runtime, Share, gather_shares
31 from viff.constants import PAILLIER
32 from viff.util import rand, find_random_prime
33
34 def L(u, n):
35 return (u-1)/n
36
37 def generate_keys(bit_length):
38 # Make an RSA modulus n.
39 p = find_random_prime(bit_length/2)
40 while True:
41 q = find_random_prime(bit_length/2)
42 if p<>q: break
43
44 n = p*q
45 nsq = n*n
46
47 # Calculate Carmichael's function.
48 lm = gmpy.lcm(p-1, q-1)
49
50 # Generate a generator g in B.
51 while True:
52 g = rand.randint(1, long(nsq))
53 if gmpy.gcd(L(pow(g, lm, nsq), n), n) == 1: break
54
55 return {'n':n, 'g': g}, {'n': n, 'g': g, 'lm': lm}
56
57 def encrypt(m, pubkey):
58 r = rand.randint(1, long(pubkey['n']))
59 return encrypt_r(m, r, pubkey)
60
61 def encrypt_r(m, r, pubkey):
62 n = pubkey['n']
63 g = pubkey['g']
64 nsq = n*n
65 return (pow(g, m, nsq)*pow(r, n, nsq)) % nsq
66
67 #: Cache for ciphertext-independent factors.
68 _decrypt_factors = {}
69
70 def decrypt(c, seckey):
71 c = long(c)
72 n = seckey['n']
73 g = seckey['g']
74 lm = seckey['lm']
75 numer = L(pow(c, lm, n*n), n)
76 key = (n, g, lm)
77 try:
78 factor = _decrypt_factors[key]
79 except KeyError:
80 denom = L(pow(g, lm, n*n), n)
81 factor = gmpy.invert(denom, n)
82 _decrypt_factors[key] = factor
83 return (numer * factor) % n
84
85
86 class PaillierRuntime(Runtime):
87 """Two-player runtime based on the Paillier crypto system."""
88
89 def add_player(self, player, protocol):
90 Runtime.add_player(self, player, protocol)
91 if player.id == self.id:
92 self.player = player
93 else:
94 self.peer = player
95
96 def prss_share_random(self, field):
97 """Generate a share of a uniformly random element."""
98 prfs = self.players[self.id].prfs(field.modulus)
99 # There can only be one PRF in the dictionary.
100 prf = prfs.values()[0]
101 share = field(prf(tuple(self.program_counter)))
102 return Share(self, field, share)
103
104 def input(self, inputters, field, number=None):
105 """Input *number* to the computation.
106
107 The input is shared using the :meth:`share` method.
108 """
109 return self.share(inputters, field, number)
110
111 def share(self, inputters, field, number=None):
112 """Share *number* additively."""
113 assert number is None or self.id in inputters
114
115 results = []
116 for peer_id in inputters:
117 # Unique program counter per input.
118 self.increment_pc()
119
120 if peer_id == self.id:
121 a = field(rand.randint(0, field.modulus - 1))
122 b = number - a
123
124 results.append(Share(self, a.field, a))
125 pc = tuple(self.program_counter)
126 self.protocols[self.peer.id].sendShare(pc, b)
127 else:
128 share = self._expect_share(peer_id, field)
129 results.append(share)
130
131 # Unpack a singleton list.
132 if len(results) == 1:
133 return results[0]
134 else:
135 return results
136
137 def output(self, share, receivers=None):
138 return self.open(share, receivers)
139
140 def open(self, share, receivers=None):
141 """Open *share* to *receivers* (defaults to both players)."""
142
143 def exchange(a):
144 pc = tuple(self.program_counter)
145 self.protocols[self.peer.id].sendShare(pc, a)
146 result = self._expect_share(self.peer.id, share.field)
147 result.addCallback(lambda b: a + b)
148 return result
149
150 result = share.clone()
151 self.schedule_callback(result, exchange)
152 return result
153
154 def add(self, share_a, share_b):
155 """Addition of shares.
156
157 Communication cost: none.
158 """
159 field = getattr(share_a, "field", getattr(share_b, "field", None))
160 if not isinstance(share_a, Share):
161 share_a = Share(self, field, share_a)
162 if not isinstance(share_b, Share):
163 share_b = Share(self, field, share_b)
164
165 result = gather_shares([share_a, share_b])
166 result.addCallback(lambda (a, b): a + b)
167 return result
168
169 def mul(self, share_a, share_b):
170 """Multiplication of shares."""
171 field = getattr(share_a, "field", getattr(share_b, "field", None))
172
173 k = self.options.security_parameter
174 n = min(self.player.pubkey['n'], self.peer.pubkey['n'])
175 assert field.modulus**2 + 2**k < n, \
176 "Need bigger Paillier keys to multiply."
177
178 if not isinstance(share_a, Share):
179 share_a = Share(self, field, share_a)
180 if not isinstance(share_b, Share):
181 share_b = Share(self, field, share_b)
182
183 def finish_mul((a, b)):
184 pc = tuple(self.program_counter)
185 send_data = self.protocols[self.peer.id].sendData
186
187 if hash(pc) % 2 == self.id:
188 # We play the role of P1.
189 a1, b1 = a, b
190 enc_a1 = encrypt(a1.value, self.player.pubkey)
191 enc_b1 = encrypt(b1.value, self.player.pubkey)
192 send_data(pc, PAILLIER, str(enc_a1))
193 send_data(pc, PAILLIER, str(enc_b1))
194
195 enc_c1 = Share(self, field)
196 self._expect_data(self.peer.id, PAILLIER, enc_c1)
197 c1 = enc_c1.addCallback(decrypt, self.player.seckey)
198 c1.addCallback(lambda c: long(c) + a1 * b1)
199 return c1
200 else:
201 # We play the role of P2.
202 a2, b2 = a, b
203 enc_a1 = Deferred()
204 self._expect_data(self.peer.id, PAILLIER, enc_a1)
205 enc_a1.addCallback(long)
206 enc_b1 = Deferred()
207 self._expect_data(self.peer.id, PAILLIER, enc_b1)
208 enc_b1.addCallback(long)
209
210 nsq = self.peer.pubkey['n']**2
211 # Calculate a1 * b2 and b1 * a2 inside the encryption.
212 enc_a1_b2 = enc_a1.addCallback(pow, b2.value, nsq)
213 enc_b1_a2 = enc_b1.addCallback(pow, a2.value, nsq)
214
215 # Chose and encrypt r.
216 r = rand.randint(0, 2 * field.modulus**2 + 2**k)
217 enc_r = encrypt(r, self.peer.pubkey)
218
219 c1 = gatherResults([enc_a1_b2, enc_b1_a2])
220 c1.addCallback(lambda (a,b): a * b * enc_r)
221 c1.addCallback(lambda c: send_data(pc, PAILLIER, str(c)))
222
223 c2 = a2 * b2 - r
224 return Share(self, field, c2)
225
226 result = gather_shares([share_a, share_b])
227 result.addCallback(finish_mul)
228 return result