viff: 0d3b99e1e3eb viff/test/bedoza/test_bedoza

viff

view viff/test/bedoza/test_bedoza_triple.py @ 1574:0d3b99e1e3eb

BeDOZa: Connected zero-knowledge proof to the remaining protocol.

author	Thomas P Jakobsen <tpj@cs.au.dk>
date	Mon Oct 04 21:51:33 2010 +0200 (19 months ago)
parents	d2d8fda44084
children

line source

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/>.

18 import sys

19 from exceptions import AssertionError

21 import operator

23 # We don't need secure random numbers for test purposes.

24 from random import Random

26 from twisted.internet.defer import gatherResults, Deferred, DeferredList

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

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 from viff.bedoza.share import generate_partial_share_contents

44 from viff.test.bedoza.util import BeDOZaTestCase, skip_if_missing_packages

45 from viff.test.bedoza.util import TestShareGenerator

48 # Ok to use non-secure random generator in tests.

49 #from viff.util import rand

50 import random

53 class DataTransferTest(BeDOZaTestCase):

55 @protocol

56 def test_convolute_int(self, runtime):

57 res = _convolute(runtime, runtime.id)

58 def verify(result):

59 self.assertEquals(runtime.players.keys(), result)

60 runtime.schedule_callback(res, verify)

61 return res

63 @protocol

64 def test_send(self, runtime):

65 msg_send = [100 * p + runtime.id for p in runtime.players]

66 msg_receive = [100 * runtime.id + p for p in runtime.players]

67 res = _send(runtime, msg_send)

68 def verify(result):

69 self.assertEquals(msg_receive, result)

70 runtime.schedule_callback(res, verify)

71 return res

73 @protocol

74 def test_convolute_field_element(self, runtime):

75 Zp = GF(17)

76 res = _convolute_gf_elm(runtime, Zp(runtime.id))

77 def verify(result):

78 self.assertEquals(runtime.players.keys(), result)

79 runtime.schedule_callback(res, verify)

80 return res

83 class ModifiedPaillierTest(BeDOZaTestCase):

85 @protocol

86 def test_modified_paillier_can_decrypt_encrypted_one(self, runtime):

87 paillier = ModifiedPaillier(runtime, Random(234838))

88 val = 1

89 encrypted_val = paillier.encrypt(val)

90 decrypted_val = paillier.decrypt(encrypted_val)

91 self.assertEquals(val, decrypted_val)

93 @protocol

94 def test_modified_paillier_with_different_randomness_are_not_equal(self, runtime):

95 random = Random(3423434)

96 n = runtime.players[runtime.id].pubkey['n']

97 paillier = ModifiedPaillier(runtime, Random(random.getrandbits(128)))

98 val = 47

99 random_elm = random.randint(1, long(n))

100 encrypted_val_1 = paillier.encrypt(val, random_elm=random_elm)

101 encrypted_val_2 = paillier.encrypt(val, random_elm=random_elm)

102 self.assertEquals(encrypted_val_1, encrypted_val_2)

103

104 @protocol

105 def test_modified_paillier_with_same_randomness_are_equal(self, runtime):

106 random = Random(234333)

107 paillier = ModifiedPaillier(runtime, Random(random.getrandbits(128)))

108 n = runtime.players[runtime.id].pubkey['n']

109 val = 46

110 random_elm_1 = random.randint(1, long(n))

111 random_elm_2 = (random_elm_1 + 1) % n

112 encrypted_val_1 = paillier.encrypt(val, random_elm=random_elm_1)

113 encrypted_val_2 = paillier.encrypt(val, random_elm=random_elm_1)

114 self.assertEquals(encrypted_val_1, encrypted_val_2)

115

116 @protocol

117 def test_modified_paillier_can_decrypt_encrypted_zero(self, runtime):

118 paillier = ModifiedPaillier(runtime, Random(338301))

119 val = 0

120 encrypted_val = paillier.encrypt(val)

121 decrypted_val = paillier.decrypt(encrypted_val)

122 self.assertEquals(val, decrypted_val)

123

124 @protocol

125 def test_modified_paillier_can_decrypt_encrypted_minus_one(self, runtime):

126 paillier = ModifiedPaillier(runtime, Random(19623))

127 val = -1

128 encrypted_val = paillier.encrypt(val)

129 decrypted_val = paillier.decrypt(encrypted_val)

130 self.assertEquals(val, decrypted_val)

131

132 @protocol

133 def test_modified_paillier_can_decrypt_encrypted_max_val(self, runtime):

134 paillier = ModifiedPaillier(runtime, Random(825604))

135 n = runtime.players[runtime.id].pubkey['n']

136 val = (n - 1) / 2

137 encrypted_val = paillier.encrypt(val)

138 decrypted_val = paillier.decrypt(encrypted_val)

139 self.assertEquals(val, decrypted_val)

140

141 @protocol

142 def test_modified_paillier_can_decrypt_encrypted_min_val(self, runtime):

143 paillier = ModifiedPaillier(runtime, Random(554424))

144 n = runtime.players[runtime.id].pubkey['n']

145 val = -(n - 1) / 2

146 encrypted_val = paillier.encrypt(val)

147 decrypted_val = paillier.decrypt(encrypted_val)

148 self.assertEquals(val, decrypted_val)

149

150 @protocol

151 def test_modified_paillier_can_decrypt_encrypted_positive(self, runtime):

152 paillier = ModifiedPaillier(runtime, Random(777737))

153 val = 73423

154 encrypted_val = paillier.encrypt(val)

155 decrypted_val = paillier.decrypt(encrypted_val)

156 self.assertEquals(val, decrypted_val)

157

158 @protocol

159 def test_encrypting_too_large_number_raises_exception(self, runtime):

160 paillier = ModifiedPaillier(runtime, Random(825604))

161 n = runtime.players[runtime.id].pubkey['n']

162 val = 1 + (n - 1) / 2

163 self.assertRaises(AssertionError, paillier.encrypt, val)

164

165 @protocol

166 def test_encrypting_too_small_number_raises_exception(self, runtime):

167 paillier = ModifiedPaillier(runtime, Random(554424))

168 n = runtime.players[runtime.id].pubkey['n']

169 val = -(n - 1) / 2 - 1

170 self.assertRaises(AssertionError, paillier.encrypt, val)

171

172 @protocol

173 def test_modified_paillier_can_encrypt_to_other(self, runtime):

174 paillier = ModifiedPaillier(runtime, Random(57503))

175 msg = []

176 for p in runtime.players:

177 msg.append(paillier.encrypt(runtime.id, player_id=p))

178 received = _send(runtime, msg)

179 def verify(enc):

180 plain = [paillier.decrypt(e) for e in enc]

181 self.assertEquals(range(1, self.num_players + 1), plain)

182 runtime.schedule_callback(received, verify)

183 return received

184

185

186 def partial_share(random, runtime, Zp, val, paillier=None):

187 if not paillier:

188 paillier_random = Random(random.getrandbits(128))

189 paillier = ModifiedPaillier(runtime, paillier_random)

190 share_random = Random(random.getrandbits(128))

191 gen = PartialShareGenerator(Zp, runtime, share_random, paillier)

192 return gen.generate_share(Zp(val))

193

194

195 class PartialShareGeneratorTest(BeDOZaTestCase):

196

197 @protocol

198 def test_shares_have_correct_type(self, runtime):

199 Zp = GF(23)

200 share = partial_share(Random(23499), runtime, Zp, 7)

201 def test(share):

202 self.assertEquals(Zp, share.value.field)

203 runtime.schedule_callback(share, test)

204 return share

205

206 @protocol

207 def test_shares_are_additive(self, runtime):

208 secret = 7

209 share = partial_share(Random(34993), runtime, GF(23), secret)

210 def convolute(share):

211 values = _convolute_gf_elm(runtime, share.value)

212 def test_sum(vals):

213 self.assertEquals(secret, sum(vals))

214 runtime.schedule_callback(values, test_sum)

215 runtime.schedule_callback(share, convolute)

216 return share

217

218 @protocol

219 def test_encrypted_shares_decrypt_correctly(self, runtime):

220 random = Random(3423993)

221 modulus = 17

222 secret = 7

223 paillier = ModifiedPaillier(runtime, Random(random.getrandbits(128)))

224 share = partial_share(Random(random.getrandbits(128)), runtime, GF(modulus), secret, paillier=paillier)

225 def decrypt(share):

226 decrypted_share = paillier.decrypt(share.enc_shares[runtime.id - 1])

227 decrypted_shares = _convolute(runtime, decrypted_share)

228 def test_sum(vals):

229 self.assertEquals(secret, sum(vals) % modulus)

230 runtime.schedule_callback(decrypted_shares, test_sum)

231 runtime.schedule_callback(share, decrypt)

232 return share

233

234 class ShareGeneratorTest(BeDOZaTestCase):

235

236 @protocol

237 def test_encrypted_real_share_open_correctly(self, runtime):

238 random = Random(3423993)

239 modulus = 17

240 Zp = GF(modulus)

241 bits_in_p = 5

242 u_bound = 2**(4 * bits_in_p)

243 alpha = 15

244

245 paillier = ModifiedPaillier(runtime, Random(random.getrandbits(128)))

246

247 share_random = Random(random.getrandbits(128))

248 gen = ShareGenerator(Zp, runtime, share_random, paillier, u_bound, alpha)

249 share = gen.generate_share(7)

250 def check(v):

251 self.assertEquals(7, v)

252 r = runtime.open(share)

253 runtime.schedule_callback(r, check)

254 return r

255

256 @protocol

257 def test_encrypted_random_real_shares_open_correctly(self, runtime):

258 random = Random(3423993)

259 modulus = 17

260 Zp = GF(modulus)

261 bits_in_p = 5

262 u_bound = 2**(4 * bits_in_p)

263 alpha = 15

264

265 paillier = ModifiedPaillier(runtime, Random(random.getrandbits(128)))

266

267 share_random = Random(random.getrandbits(128))

268 gen = TestShareGenerator(Zp, runtime, share_random, paillier, u_bound, alpha)

269 shares = gen.generate_random_shares(7)

270 expected_result = [9,16,7,12,3,5,6]

271 results = []

272 for inx, share in enumerate(shares):

273 def check(v, expected_result):

274 self.assertEquals(expected_result, v)

275 r = runtime.open(share)

276 results.append(r)

277 runtime.schedule_callback(r, check, expected_result[inx])

278 return gather_shares(results)

279

280 class AddMacsTest(BeDOZaTestCase):

281

282 timeout = 10

283

284 @protocol

285 def test_add_macs_produces_correct_sharing(self, runtime):

286 # TODO: Here we use the open method of the BeDOZa runtime in

287 # order to verify the macs of the generated full share. In

288 # order to be more unit testish, this test should use its own

289 # way of verifying these.

290 p = 17

291 Zp = GF(p)

292 secret = 6

293 random = Random(283883)

294 paillier_random = Random(random.getrandbits(128))

295 paillier = ModifiedPaillier(runtime, random)

296

297 add_macs_random = Random(random.getrandbits(128))

298

299 shares_random = Random(random.getrandbits(128))

300 shares = []

301 shares.append(partial_share(shares_random, runtime, Zp, secret, paillier=paillier))

302 shares.append(partial_share(shares_random, runtime, Zp, secret + 1, paillier=paillier))

303 shares.append(partial_share(shares_random, runtime, Zp, secret + 2, paillier=paillier))

304 shares.append(partial_share(shares_random, runtime, Zp, secret + 3, paillier=paillier))

305

306 bits_in_p = 5

307 u_bound = 2**(4 * bits_in_p)

308 alpha = 15

309

310 zs = add_macs(runtime, Zp, u_bound, alpha,

311 add_macs_random, paillier, shares)

312 def verify(open_shares):

313 inx = secret

314 for open_share in open_shares:

315 self.assertEquals(inx, open_share.value)

316 inx += 1

317

318 opened_shares = []

319 for s in zs:

320 opened_shares.append(runtime.open(s))

321 d = gather_shares(opened_shares)

322 d.addCallback(verify)

323 return d

324

325

326 # @protocol

327 # def test_add_macs_preserves_value_of_sharing(self, runtime):

328 # partial_share = self._generate_partial_share_of(42)

329 # full_share = TripleGenerator()._add_macs(partial_share)

330 # secret = self._open_sharing(full_share)

331 # self.assertEquals(42, secret)

332 # return partial_share

333 # #test_add_macs_preserves_value_of_sharing.skip = "nyi"

334 #

335 # @protocol

336 # def test_add_macs_preserves_value_of_zero_sharing(self, runtime):

337 # partial_share = self._generate_partial_share_of(0)

338 # full_share = TripleGenerator()._add_macs(partial_share)

339 # secret = self._open_sharing(full_share)

340 # self.assertEquals(0, secret)

341 # return partial_share

342 # #test_add_macs_preserves_value_of_zero_sharing.skip = "nyi"

343 #

344

345 class TripleTest(BeDOZaTestCase):

346

347 timeout = 25

348

349 @protocol

350 def test_generate_triples_generates_correct_single_triple(self, runtime):

351 p = 17

352 Zp = GF(p)

353 random = Random(574566 + runtime.id)

354 triple_generator = TripleGenerator(runtime, self.security_parameter, p, random)

355 triples = triple_generator._generate_triples(1)

356

357 def check((a, b, c)):

358 self.assertEquals(c, a * b)

359

360 def open(triple):

361 d1 = runtime.open(triple.a)

362 d2 = runtime.open(triple.b)

363 d3 = runtime.open(triple.c)

364 d = gatherResults([d1, d2, d3])

365 runtime.schedule_callback(d, check)

366 return d

367

368 for triple in triples:

369 runtime.schedule_callback(triple, open)

370 return gatherResults(triples)

371

372 @protocol

373 def test_generate_triples_generates_correct_triples(self, runtime):

374 p = 17

375

376 Zp = GF(p)

377

378 random = Random(574566 + runtime.id)

379 triple_generator = TripleGenerator(runtime, self.security_parameter, p, random)

380

381 triples = triple_generator._generate_triples(10)

382

383 def check((a, b, c)):

384 self.assertEquals(c, a * b)

385

386 def open(triple):

387 d1 = runtime.open(triple.a)

388 d2 = runtime.open(triple.b)

389 d3 = runtime.open(triple.c)

390 d = gatherResults([d1, d2, d3])

391 runtime.schedule_callback(d, check)

392 return d

393

394 for triple in triples:

395 runtime.schedule_callback(triple, open)

396 return gatherResults(triples)

397

398 @protocol

399 def test_generate_triple_candidates_generates_correct_triples(self, runtime):

400 p = 17

401

402 Zp = GF(p)

403

404 random = Random(283883)

405 triple_generator = TripleGenerator(runtime, self.security_parameter, p, random)

406

407 triples = triple_generator._generate_triple_candidates(5)

408 def verify(triples):

409 for inx in xrange(len(triples) // 3):

410 self.assertEquals(triples[10 + inx], triples[inx] * triples[5 + inx])

411 opened_shares = []

412 for s in triples:

413 opened_shares.append(runtime.open(s))

414 d = gather_shares(opened_shares)

415 d.addCallback(verify)

416 return d

417

418 class MulTest(BeDOZaTestCase):

419

420 timeout = 10

421

422 @protocol

423 def test_mul_computes_correct_result(self, runtime):

424 p = 17

425

426 random = Random(283883)

427 triple_generator = TripleGenerator(runtime, 32, p, random)

428

429 Zp = GF(p)

430

431 ais = [Zp(6), Zp(6), Zp(6), Zp(6)]

432 b2 = Zp(7)

433 cs = []

434 for ai in ais:

435 cs.append(triple_generator.paillier.encrypt(b2.value, 2))

436

437 n = len(ais)

438

439 if runtime.id == 1:

440 r1 = triple_generator._mul(1, 2, n, ais, cs)

441 def check1(shares):

442 for share in shares:

443 pc = tuple(runtime.program_counter)

444 runtime.protocols[2].sendData(pc, TEXT, str(share.value))

445 return True

446 r1.addCallback(check1)

447 return r1

448 else:

449 r1 = triple_generator._mul(1, 2, n)

450 def check(shares):

451 deferreds = []

452 for share in shares:

453 if runtime.id == 2:

454 def check_additivity(zi, zj):

455 self.assertEquals((Zp(long(zi)) + zj).value, 8)

456 return None

457 d = Deferred()

458 d.addCallback(check_additivity, share.value)

459 runtime._expect_data(1, TEXT, d)

460 deferreds.append(d)

461 else:

462 self.assertEquals(share.value, 0)

463 return gatherResults(deferreds)

464 r1.addCallback(check)

465 return r1

466

467 @protocol

468 def test_mul_same_player_inputs_and_receives(self, runtime):

469 p = 17

470

471 random = Random(283883)

472 triple_generator = TripleGenerator(runtime, self.security_parameter, p, random)

473

474 Zp = GF(p)

475

476 ais = [Zp(6), Zp(6), Zp(6), Zp(6)]

477 b2 = Zp(7)

478 cs = []

479 for ai in ais:

480 cs.append(triple_generator.paillier.encrypt(b2.value, 2))

481

482 n = len(ais)

483

484 r1 = triple_generator._mul(2, 2, n, ais, cs)

485 def check(shares):

486 for share in shares:

487 if runtime.id == 2:

488 self.assertEquals(share.value, 8)

489 return True

490

491 r1.addCallback(check)

492 return r1

493

494

495 class ShareTest(BeDOZaTestCase):

496

497 timeout = 10

498

499 @protocol

500 def test_share_protocol_single(self, runtime):

501 p, k = 17, 5

502 Zp = GF(p)

503 random = Random(3455433 + runtime.id)

504 elms = [Zp(runtime.id)]

505 paillier_random = Random(random.getrandbits(128))

506 zk_random = Random(random.getrandbits(128))

507 paillier = ModifiedPaillier(runtime, paillier_random)

508 partial_shares = generate_partial_share_contents(

509 elms, runtime, paillier, k, zk_random)

510

511 def decrypt(share_contents):

512 self.assertEquals(1, len(share_contents))

513 decrypted_share = paillier.decrypt(

514 share_contents[0].enc_shares[runtime.id - 1])

515 decrypted_shares = _convolute(runtime, decrypted_share)

516 def test_sum(vals):

517 self.assertEquals([Zp(e) for e in [1, 2, 3]], vals)

518 runtime.schedule_callback(decrypted_shares, test_sum)

519

520 runtime.schedule_callback(partial_shares, decrypt)

521 return partial_shares

522

523 @protocol

524 def test_share_protocol_multi(self, runtime):

525 p, k = 17, 5

526 Zp = GF(p)

527 random = Random(345453 + runtime.id)

528 elms = [Zp(runtime.id), Zp(runtime.id * 3)]

529 paillier_random = Random(random.getrandbits(128))

530 zk_random = Random(random.getrandbits(128))

531 paillier = ModifiedPaillier(runtime, paillier_random)

532 partial_shares = generate_partial_share_contents(

533 elms, runtime, paillier, k, zk_random)

534

535 def decrypt(share_contents):

536 self.assertEquals(2, len(share_contents))

537 decrypted_shares = [paillier.decrypt(

538 share_contents[i].enc_shares[runtime.id - 1])

539 for i in range(2)]

540 decrypted_shares = [_convolute(runtime, decrypted_shares[i])

541 for i in range(2)]

542 def test_sum(vals, should_be):

543 self.assertEquals([Zp(e) for e in should_be], vals)

544 runtime.schedule_callback(

545 decrypted_shares[0], test_sum, [1, 2, 3])

546 runtime.schedule_callback(

547 decrypted_shares[1], test_sum, [3, 6, 9])

548

549 runtime.schedule_callback(partial_shares, decrypt)

550 return partial_shares

551

552

553 class FullMulTest(BeDOZaTestCase):

554

555 timeout = 10

556

557 @protocol

558 def test_fullmul_computes_the_correct_result(self, runtime):

559 p = 17

560

561 Zp = GF(p)

562

563 random = Random(283883)

564 triple_generator = TripleGenerator(runtime, self.security_parameter, p, random)

565

566 paillier = triple_generator.paillier

567

568 share_as = []

569 share_bs = []

570 share_as.append(partial_share(random, runtime, GF(p), 6, paillier=paillier))

571 share_bs.append(partial_share(random, runtime, GF(p), 7, paillier=paillier))

572 share_as.append(partial_share(random, runtime, GF(p), 5, paillier=paillier))

573 share_bs.append(partial_share(random, runtime, GF(p), 4, paillier=paillier))

574 share_as.append(partial_share(random, runtime, GF(p), 2, paillier=paillier))

575 share_bs.append(partial_share(random, runtime, GF(p), 3, paillier=paillier))

576

577

578 share_zs = triple_generator._full_mul(share_as, share_bs)

579 def check(shares):

580 def test_sum(ls):

581 self.assertEquals(8, Zp(sum(ls[0])))

582 self.assertEquals(3, Zp(sum(ls[1])))

583 self.assertEquals(6, Zp(sum(ls[2])))

584 values = []

585 for share in shares:

586 value = _convolute(runtime, share.value.value)

587 values.append(value)

588 d = gatherResults(values)

589 runtime.schedule_callback(d, test_sum)

590 return d

591

592 d = gatherResults(share_zs)

593 d.addCallback(check)

594 return d

595

596 @protocol

597 def test_fullmul_encrypted_values_are_the_same_as_the_share(self, runtime):

598 p = 17

599

600 Zp = GF(p)

601

602 random = Random(283883)

603 triple_generator = TripleGenerator(runtime, self.security_parameter, p, random)

604

605 paillier = triple_generator.paillier

606

607 share_as = []

608 share_bs = []

609 share_as.append(partial_share(random, runtime, GF(p), 6, paillier=paillier))

610 share_bs.append(partial_share(random, runtime, GF(p), 7, paillier=paillier))

611 share_as.append(partial_share(random, runtime, GF(p), 5, paillier=paillier))

612 share_bs.append(partial_share(random, runtime, GF(p), 4, paillier=paillier))

613 share_as.append(partial_share(random, runtime, GF(p), 2, paillier=paillier))

614 share_bs.append(partial_share(random, runtime, GF(p), 3, paillier=paillier))

615

616 share_zs = triple_generator._full_mul(share_as, share_bs)

617 def check(shares):

618 all_enc_shares = []

619 for share in shares:

620 def test_enc(enc_shares, value):

621 all_the_same, zi_enc = reduce(lambda x, y: (x[0] and x[1] == y, y), enc_shares, (True, enc_shares[0]))

622 zi_enc = triple_generator.paillier.decrypt(zi_enc)

623 self.assertEquals(value, Zp(zi_enc))

624 return True

625 for inx, enc_share in enumerate(share.enc_shares):

626 d = _convolute(runtime, enc_share)

627 if runtime.id == inx + 1:

628 d.addCallback(test_enc, share.value)

629 all_enc_shares.append(d)

630 return gatherResults(all_enc_shares)

631

632 d = gatherResults(share_zs)

633 d.addCallback(check)

634 return d

635

636

637 skip_if_missing_packages(

638 ShareTest,

639 ModifiedPaillierTest,

640 PartialShareGeneratorTest,

641 TripleTest,

642 DataTransferTest,

643 MulTest,

644 FullMulTest,

645 ShareGeneratorTest,

646 AddMacsTest)