viff

view viff/test/bedoza/test_bedoza_triple.py @ 1573:d2d8fda44084

find changesets by author, revision, files, or words in the commit message
BeDOZa: Added tests of Share protocol.
author Thomas P Jakobsen <tpj@cs.au.dk>
date Mon Oct 04 12:04:47 2010 +0200 (19 months ago)
parents 6a727af6cb6c
children 0d3b99e1e3eb
line source
1 # Copyright 2010 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 import sys
19 from exceptions import AssertionError
20
21 import operator
22
23 # We don't need secure random numbers for test purposes.
24 from random import Random
25
26 from twisted.internet.defer import gatherResults, Deferred, DeferredList
27
28 from viff.test.util import protocol
29 from viff.constants import TEXT
30 from viff.runtime import gather_shares, Share
31 from viff.config import generate_configs
32 from viff.field import FieldElement, GF
33 from viff.config import generate_configs
34
35 from viff.bedoza.bedoza import BeDOZaShare
36 from viff.bedoza.keylist import BeDOZaKeyList
37 from viff.bedoza.bedoza_triple import TripleGenerator, ModifiedPaillier
38 from viff.bedoza.shares import PartialShare, PartialShareContents
39 from viff.bedoza.util import _send, _convolute, _convolute_gf_elm
40 from viff.bedoza.add_macs import add_macs
41 from viff.bedoza.share_generators import ShareGenerator, PartialShareGenerator
42
43 from viff.test.bedoza.util import BeDOZaTestCase, skip_if_missing_packages
44 from viff.test.bedoza.util import TestShareGenerator
45
46
47 # Ok to use non-secure random generator in tests.
48 #from viff.util import rand
49 import random
50
51
52 class DataTransferTest(BeDOZaTestCase):
53
54 @protocol
55 def test_convolute_int(self, runtime):
56 res = _convolute(runtime, runtime.id)
57 def verify(result):
58 self.assertEquals(runtime.players.keys(), result)
59 runtime.schedule_callback(res, verify)
60 return res
61
62 @protocol
63 def test_send(self, runtime):
64 msg_send = [100 * p + runtime.id for p in runtime.players]
65 msg_receive = [100 * runtime.id + p for p in runtime.players]
66 res = _send(runtime, msg_send)
67 def verify(result):
68 self.assertEquals(msg_receive, result)
69 runtime.schedule_callback(res, verify)
70 return res
71
72 @protocol
73 def test_convolute_field_element(self, runtime):
74 Zp = GF(17)
75 res = _convolute_gf_elm(runtime, Zp(runtime.id))
76 def verify(result):
77 self.assertEquals(runtime.players.keys(), result)
78 runtime.schedule_callback(res, verify)
79 return res
80
81
82 class ModifiedPaillierTest(BeDOZaTestCase):
83
84 @protocol
85 def test_modified_paillier_can_decrypt_encrypted_one(self, runtime):
86 paillier = ModifiedPaillier(runtime, Random(234838))
87 val = 1
88 encrypted_val = paillier.encrypt(val)
89 decrypted_val = paillier.decrypt(encrypted_val)
90 self.assertEquals(val, decrypted_val)
91
92 @protocol
93 def test_modified_paillier_with_different_randomness_are_not_equal(self, runtime):
94 random = Random(3423434)
95 n = runtime.players[runtime.id].pubkey['n']
96 paillier = ModifiedPaillier(runtime, Random(random.getrandbits(128)))
97 val = 47
98 random_elm = random.randint(1, long(n))
99 encrypted_val_1 = paillier.encrypt(val, random_elm=random_elm)
100 encrypted_val_2 = paillier.encrypt(val, random_elm=random_elm)
101 self.assertEquals(encrypted_val_1, encrypted_val_2)
102
103 @protocol
104 def test_modified_paillier_with_same_randomness_are_equal(self, runtime):
105 random = Random(234333)
106 paillier = ModifiedPaillier(runtime, Random(random.getrandbits(128)))
107 n = runtime.players[runtime.id].pubkey['n']
108 val = 46
109 random_elm_1 = random.randint(1, long(n))
110 random_elm_2 = (random_elm_1 + 1) % n
111 encrypted_val_1 = paillier.encrypt(val, random_elm=random_elm_1)
112 encrypted_val_2 = paillier.encrypt(val, random_elm=random_elm_1)
113 self.assertEquals(encrypted_val_1, encrypted_val_2)
114
115 @protocol
116 def test_modified_paillier_can_decrypt_encrypted_zero(self, runtime):
117 paillier = ModifiedPaillier(runtime, Random(338301))
118 val = 0
119 encrypted_val = paillier.encrypt(val)
120 decrypted_val = paillier.decrypt(encrypted_val)
121 self.assertEquals(val, decrypted_val)
122
123 @protocol
124 def test_modified_paillier_can_decrypt_encrypted_minus_one(self, runtime):
125 paillier = ModifiedPaillier(runtime, Random(19623))
126 val = -1
127 encrypted_val = paillier.encrypt(val)
128 decrypted_val = paillier.decrypt(encrypted_val)
129 self.assertEquals(val, decrypted_val)
130
131 @protocol
132 def test_modified_paillier_can_decrypt_encrypted_max_val(self, runtime):
133 paillier = ModifiedPaillier(runtime, Random(825604))
134 n = runtime.players[runtime.id].pubkey['n']
135 val = (n - 1) / 2
136 encrypted_val = paillier.encrypt(val)
137 decrypted_val = paillier.decrypt(encrypted_val)
138 self.assertEquals(val, decrypted_val)
139
140 @protocol
141 def test_modified_paillier_can_decrypt_encrypted_min_val(self, runtime):
142 paillier = ModifiedPaillier(runtime, Random(554424))
143 n = runtime.players[runtime.id].pubkey['n']
144 val = -(n - 1) / 2
145 encrypted_val = paillier.encrypt(val)
146 decrypted_val = paillier.decrypt(encrypted_val)
147 self.assertEquals(val, decrypted_val)
148
149 @protocol
150 def test_modified_paillier_can_decrypt_encrypted_positive(self, runtime):
151 paillier = ModifiedPaillier(runtime, Random(777737))
152 val = 73423
153 encrypted_val = paillier.encrypt(val)
154 decrypted_val = paillier.decrypt(encrypted_val)
155 self.assertEquals(val, decrypted_val)
156
157 @protocol
158 def test_encrypting_too_large_number_raises_exception(self, runtime):
159 paillier = ModifiedPaillier(runtime, Random(825604))
160 n = runtime.players[runtime.id].pubkey['n']
161 val = 1 + (n - 1) / 2
162 self.assertRaises(AssertionError, paillier.encrypt, val)
163
164 @protocol
165 def test_encrypting_too_small_number_raises_exception(self, runtime):
166 paillier = ModifiedPaillier(runtime, Random(554424))
167 n = runtime.players[runtime.id].pubkey['n']
168 val = -(n - 1) / 2 - 1
169 self.assertRaises(AssertionError, paillier.encrypt, val)
170
171 @protocol
172 def test_modified_paillier_can_encrypt_to_other(self, runtime):
173 paillier = ModifiedPaillier(runtime, Random(57503))
174 msg = []
175 for p in runtime.players:
176 msg.append(paillier.encrypt(runtime.id, player_id=p))
177 received = _send(runtime, msg)
178 def verify(enc):
179 plain = [paillier.decrypt(e) for e in enc]
180 self.assertEquals(range(1, self.num_players + 1), plain)
181 runtime.schedule_callback(received, verify)
182 return received
183
184
185 def partial_share(random, runtime, Zp, val, paillier=None):
186 if not paillier:
187 paillier_random = Random(random.getrandbits(128))
188 paillier = ModifiedPaillier(runtime, paillier_random)
189 share_random = Random(random.getrandbits(128))
190 gen = PartialShareGenerator(Zp, runtime, share_random, paillier)
191 return gen.generate_share(Zp(val))
192
193
194 class PartialShareGeneratorTest(BeDOZaTestCase):
195
196 @protocol
197 def test_shares_have_correct_type(self, runtime):
198 Zp = GF(23)
199 share = partial_share(Random(23499), runtime, Zp, 7)
200 def test(share):
201 self.assertEquals(Zp, share.value.field)
202 runtime.schedule_callback(share, test)
203 return share
204
205 @protocol
206 def test_shares_are_additive(self, runtime):
207 secret = 7
208 share = partial_share(Random(34993), runtime, GF(23), secret)
209 def convolute(share):
210 values = _convolute_gf_elm(runtime, share.value)
211 def test_sum(vals):
212 self.assertEquals(secret, sum(vals))
213 runtime.schedule_callback(values, test_sum)
214 runtime.schedule_callback(share, convolute)
215 return share
216
217 @protocol
218 def test_encrypted_shares_decrypt_correctly(self, runtime):
219 random = Random(3423993)
220 modulus = 17
221 secret = 7
222 paillier = ModifiedPaillier(runtime, Random(random.getrandbits(128)))
223 share = partial_share(Random(random.getrandbits(128)), runtime, GF(modulus), secret, paillier=paillier)
224 def decrypt(share):
225 decrypted_share = paillier.decrypt(share.enc_shares[runtime.id - 1])
226 decrypted_shares = _convolute(runtime, decrypted_share)
227 def test_sum(vals):
228 self.assertEquals(secret, sum(vals) % modulus)
229 runtime.schedule_callback(decrypted_shares, test_sum)
230 runtime.schedule_callback(share, decrypt)
231 return share
232
233 class ShareGeneratorTest(BeDOZaTestCase):
234
235 @protocol
236 def test_encrypted_real_share_open_correctly(self, runtime):
237 random = Random(3423993)
238 modulus = 17
239 Zp = GF(modulus)
240 bits_in_p = 5
241 u_bound = 2**(4 * bits_in_p)
242 alpha = 15
243
244 paillier = ModifiedPaillier(runtime, Random(random.getrandbits(128)))
245
246 share_random = Random(random.getrandbits(128))
247 gen = ShareGenerator(Zp, runtime, share_random, paillier, u_bound, alpha)
248 share = gen.generate_share(7)
249 def check(v):
250 self.assertEquals(7, v)
251 r = runtime.open(share)
252 runtime.schedule_callback(r, check)
253 return r
254
255 @protocol
256 def test_encrypted_random_real_shares_open_correctly(self, runtime):
257 random = Random(3423993)
258 modulus = 17
259 Zp = GF(modulus)
260 bits_in_p = 5
261 u_bound = 2**(4 * bits_in_p)
262 alpha = 15
263
264 paillier = ModifiedPaillier(runtime, Random(random.getrandbits(128)))
265
266 share_random = Random(random.getrandbits(128))
267 gen = TestShareGenerator(Zp, runtime, share_random, paillier, u_bound, alpha)
268 shares = gen.generate_random_shares(7)
269 expected_result = [9,16,7,12,3,5,6]
270 results = []
271 for inx, share in enumerate(shares):
272 def check(v, expected_result):
273 self.assertEquals(expected_result, v)
274 r = runtime.open(share)
275 results.append(r)
276 runtime.schedule_callback(r, check, expected_result[inx])
277 return gather_shares(results)
278
279 class AddMacsTest(BeDOZaTestCase):
280
281 timeout = 10
282
283 @protocol
284 def test_add_macs_produces_correct_sharing(self, runtime):
285 # TODO: Here we use the open method of the BeDOZa runtime in
286 # order to verify the macs of the generated full share. In
287 # order to be more unit testish, this test should use its own
288 # way of verifying these.
289 p = 17
290 Zp = GF(p)
291 secret = 6
292 random = Random(283883)
293 paillier_random = Random(random.getrandbits(128))
294 paillier = ModifiedPaillier(runtime, random)
295
296 add_macs_random = Random(random.getrandbits(128))
297
298 shares_random = Random(random.getrandbits(128))
299 shares = []
300 shares.append(partial_share(shares_random, runtime, Zp, secret, paillier=paillier))
301 shares.append(partial_share(shares_random, runtime, Zp, secret + 1, paillier=paillier))
302 shares.append(partial_share(shares_random, runtime, Zp, secret + 2, paillier=paillier))
303 shares.append(partial_share(shares_random, runtime, Zp, secret + 3, paillier=paillier))
304
305 bits_in_p = 5
306 u_bound = 2**(4 * bits_in_p)
307 alpha = 15
308
309 zs = add_macs(runtime, Zp, u_bound, alpha,
310 add_macs_random, paillier, shares)
311 def verify(open_shares):
312 inx = secret
313 for open_share in open_shares:
314 self.assertEquals(inx, open_share.value)
315 inx += 1
316
317 opened_shares = []
318 for s in zs:
319 opened_shares.append(runtime.open(s))
320 d = gather_shares(opened_shares)
321 d.addCallback(verify)
322 return d
323
324
325 # @protocol
326 # def test_add_macs_preserves_value_of_sharing(self, runtime):
327 # partial_share = self._generate_partial_share_of(42)
328 # full_share = TripleGenerator()._add_macs(partial_share)
329 # secret = self._open_sharing(full_share)
330 # self.assertEquals(42, secret)
331 # return partial_share
332 # #test_add_macs_preserves_value_of_sharing.skip = "nyi"
333 #
334 # @protocol
335 # def test_add_macs_preserves_value_of_zero_sharing(self, runtime):
336 # partial_share = self._generate_partial_share_of(0)
337 # full_share = TripleGenerator()._add_macs(partial_share)
338 # secret = self._open_sharing(full_share)
339 # self.assertEquals(0, secret)
340 # return partial_share
341 # #test_add_macs_preserves_value_of_zero_sharing.skip = "nyi"
342 #
343
344 class TripleTest(BeDOZaTestCase):
345
346 timeout = 25
347
348 @protocol
349 def test_generate_triples_generates_correct_single_triple(self, runtime):
350 p = 17
351 Zp = GF(p)
352 random = Random(574566 + runtime.id)
353 triple_generator = TripleGenerator(runtime, self.security_parameter, p, random)
354 triples = triple_generator._generate_triples(1)
355
356 def check((a, b, c)):
357 self.assertEquals(c, a * b)
358
359 def open(triple):
360 d1 = runtime.open(triple.a)
361 d2 = runtime.open(triple.b)
362 d3 = runtime.open(triple.c)
363 d = gatherResults([d1, d2, d3])
364 runtime.schedule_callback(d, check)
365 return d
366
367 for triple in triples:
368 runtime.schedule_callback(triple, open)
369 return gatherResults(triples)
370
371 @protocol
372 def test_generate_triples_generates_correct_triples(self, runtime):
373 p = 17
374
375 Zp = GF(p)
376
377 random = Random(574566 + runtime.id)
378 triple_generator = TripleGenerator(runtime, self.security_parameter, p, random)
379
380 triples = triple_generator._generate_triples(10)
381
382 def check((a, b, c)):
383 self.assertEquals(c, a * b)
384
385 def open(triple):
386 d1 = runtime.open(triple.a)
387 d2 = runtime.open(triple.b)
388 d3 = runtime.open(triple.c)
389 d = gatherResults([d1, d2, d3])
390 runtime.schedule_callback(d, check)
391 return d
392
393 for triple in triples:
394 runtime.schedule_callback(triple, open)
395 return gatherResults(triples)
396
397 @protocol
398 def test_generate_triple_candidates_generates_correct_triples(self, runtime):
399 p = 17
400
401 Zp = GF(p)
402
403 random = Random(283883)
404 triple_generator = TripleGenerator(runtime, self.security_parameter, p, random)
405
406 triples = triple_generator._generate_triple_candidates(5)
407 def verify(triples):
408 for inx in xrange(len(triples) // 3):
409 self.assertEquals(triples[10 + inx], triples[inx] * triples[5 + inx])
410 opened_shares = []
411 for s in triples:
412 opened_shares.append(runtime.open(s))
413 d = gather_shares(opened_shares)
414 d.addCallback(verify)
415 return d
416
417 class MulTest(BeDOZaTestCase):
418
419 timeout = 10
420
421 @protocol
422 def test_mul_computes_correct_result(self, runtime):
423 p = 17
424
425 random = Random(283883)
426 triple_generator = TripleGenerator(runtime, 32, p, random)
427
428 Zp = GF(p)
429
430 ais = [Zp(6), Zp(6), Zp(6), Zp(6)]
431 b2 = Zp(7)
432 cs = []
433 for ai in ais:
434 cs.append(triple_generator.paillier.encrypt(b2.value, 2))
435
436 n = len(ais)
437
438 if runtime.id == 1:
439 r1 = triple_generator._mul(1, 2, n, ais, cs)
440 def check1(shares):
441 for share in shares:
442 pc = tuple(runtime.program_counter)
443 runtime.protocols[2].sendData(pc, TEXT, str(share.value))
444 return True
445 r1.addCallback(check1)
446 return r1
447 else:
448 r1 = triple_generator._mul(1, 2, n)
449 def check(shares):
450 deferreds = []
451 for share in shares:
452 if runtime.id == 2:
453 def check_additivity(zi, zj):
454 self.assertEquals((Zp(long(zi)) + zj).value, 8)
455 return None
456 d = Deferred()
457 d.addCallback(check_additivity, share.value)
458 runtime._expect_data(1, TEXT, d)
459 deferreds.append(d)
460 else:
461 self.assertEquals(share.value, 0)
462 return gatherResults(deferreds)
463 r1.addCallback(check)
464 return r1
465
466 @protocol
467 def test_mul_same_player_inputs_and_receives(self, runtime):
468 p = 17
469
470 random = Random(283883)
471 triple_generator = TripleGenerator(runtime, self.security_parameter, p, random)
472
473 Zp = GF(p)
474
475 ais = [Zp(6), Zp(6), Zp(6), Zp(6)]
476 b2 = Zp(7)
477 cs = []
478 for ai in ais:
479 cs.append(triple_generator.paillier.encrypt(b2.value, 2))
480
481 n = len(ais)
482
483 r1 = triple_generator._mul(2, 2, n, ais, cs)
484 def check(shares):
485 for share in shares:
486 if runtime.id == 2:
487 self.assertEquals(share.value, 8)
488 return True
489
490 r1.addCallback(check)
491 return r1
492
493
494 class ShareTest(BeDOZaTestCase):
495
496 timeout = 10
497
498 @protocol
499 def test_share_protocol_single(self, runtime):
500 p = 17
501 Zp = GF(p)
502 random = Random(3455433 + runtime.id)
503 elms = [Zp(runtime.id)]
504 paillier_random = Random(random.getrandbits(128))
505 paillier = ModifiedPaillier(runtime, paillier_random)
506 from viff.bedoza.share import generate_partial_share_contents
507 partial_shares = generate_partial_share_contents(elms, runtime, paillier)
508
509 def decrypt(share_contents):
510 self.assertEquals(1, len(share_contents))
511 decrypted_share = paillier.decrypt(share_contents[0].enc_shares[runtime.id - 1])
512 decrypted_shares = _convolute(runtime, decrypted_share)
513 def test_sum(vals):
514 self.assertEquals([Zp(e) for e in [1, 2, 3]], vals)
515 runtime.schedule_callback(decrypted_shares, test_sum)
516
517 runtime.schedule_callback(partial_shares, decrypt)
518 return partial_shares
519
520 @protocol
521 def test_share_protocol_multi(self, runtime):
522 p = 17
523 Zp = GF(p)
524 random = Random(3455433 + runtime.id)
525 elms = [Zp(runtime.id), Zp(runtime.id * 3)]
526 paillier_random = Random(random.getrandbits(128))
527 paillier = ModifiedPaillier(runtime, paillier_random)
528 from viff.bedoza.share import generate_partial_share_contents
529 partial_shares = generate_partial_share_contents(elms, runtime, paillier)
530
531 def decrypt(share_contents):
532 self.assertEquals(2, len(share_contents))
533 decrypted_shares = [paillier.decrypt(share_contents[i].enc_shares[runtime.id - 1])
534 for i in range(2)]
535 decrypted_shares = [_convolute(runtime, decrypted_shares[i]) for i in range(2)]
536 def test_sum(vals, should_be):
537 self.assertEquals([Zp(e) for e in should_be], vals)
538 runtime.schedule_callback(decrypted_shares[0], test_sum, [1, 2, 3])
539 runtime.schedule_callback(decrypted_shares[1], test_sum, [3, 6, 9])
540
541 runtime.schedule_callback(partial_shares, decrypt)
542 return partial_shares
543
544
545 class FullMulTest(BeDOZaTestCase):
546
547 timeout = 10
548
549 @protocol
550 def test_fullmul_computes_the_correct_result(self, runtime):
551 p = 17
552
553 Zp = GF(p)
554
555 random = Random(283883)
556 triple_generator = TripleGenerator(runtime, self.security_parameter, p, random)
557
558 paillier = triple_generator.paillier
559
560 share_as = []
561 share_bs = []
562 share_as.append(partial_share(random, runtime, GF(p), 6, paillier=paillier))
563 share_bs.append(partial_share(random, runtime, GF(p), 7, paillier=paillier))
564 share_as.append(partial_share(random, runtime, GF(p), 5, paillier=paillier))
565 share_bs.append(partial_share(random, runtime, GF(p), 4, paillier=paillier))
566 share_as.append(partial_share(random, runtime, GF(p), 2, paillier=paillier))
567 share_bs.append(partial_share(random, runtime, GF(p), 3, paillier=paillier))
568
569
570 share_zs = triple_generator._full_mul(share_as, share_bs)
571 def check(shares):
572 def test_sum(ls):
573 self.assertEquals(8, Zp(sum(ls[0])))
574 self.assertEquals(3, Zp(sum(ls[1])))
575 self.assertEquals(6, Zp(sum(ls[2])))
576 values = []
577 for share in shares:
578 value = _convolute(runtime, share.value.value)
579 values.append(value)
580 d = gatherResults(values)
581 runtime.schedule_callback(d, test_sum)
582 return d
583
584 d = gatherResults(share_zs)
585 d.addCallback(check)
586 return d
587
588 @protocol
589 def test_fullmul_encrypted_values_are_the_same_as_the_share(self, runtime):
590 p = 17
591
592 Zp = GF(p)
593
594 random = Random(283883)
595 triple_generator = TripleGenerator(runtime, self.security_parameter, p, random)
596
597 paillier = triple_generator.paillier
598
599 share_as = []
600 share_bs = []
601 share_as.append(partial_share(random, runtime, GF(p), 6, paillier=paillier))
602 share_bs.append(partial_share(random, runtime, GF(p), 7, paillier=paillier))
603 share_as.append(partial_share(random, runtime, GF(p), 5, paillier=paillier))
604 share_bs.append(partial_share(random, runtime, GF(p), 4, paillier=paillier))
605 share_as.append(partial_share(random, runtime, GF(p), 2, paillier=paillier))
606 share_bs.append(partial_share(random, runtime, GF(p), 3, paillier=paillier))
607
608 share_zs = triple_generator._full_mul(share_as, share_bs)
609 def check(shares):
610 all_enc_shares = []
611 for share in shares:
612 def test_enc(enc_shares, value):
613 all_the_same, zi_enc = reduce(lambda x, y: (x[0] and x[1] == y, y), enc_shares, (True, enc_shares[0]))
614 zi_enc = triple_generator.paillier.decrypt(zi_enc)
615 self.assertEquals(value, Zp(zi_enc))
616 return True
617 for inx, enc_share in enumerate(share.enc_shares):
618 d = _convolute(runtime, enc_share)
619 if runtime.id == inx + 1:
620 d.addCallback(test_enc, share.value)
621 all_enc_shares.append(d)
622 return gatherResults(all_enc_shares)
623
624 d = gatherResults(share_zs)
625 d.addCallback(check)
626 return d
627
628
629 skip_if_missing_packages(
630 ModifiedPaillierTest,
631 PartialShareGeneratorTest,
632 TripleTest,
633 DataTransferTest,
634 MulTest,
635 FullMulTest,
636 ShareGeneratorTest,
637 AddMacsTest)