Package viff :: Module orlandi
[hide private]
[frames] | no frames]

Source Code for Module viff.orlandi

   1  # Copyright 2009 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  from twisted.internet.defer import Deferred, DeferredList, gatherResults 
  19   
  20  from viff.runtime import Runtime, Share, ShareList, gather_shares, preprocess 
  21  from viff.util import rand 
  22  from viff.constants import TEXT, PAILLIER 
  23  from viff.field import FieldElement 
  24  from viff.paillier import encrypt_r, decrypt 
  25   
  26  from hash_broadcast import HashBroadcastMixin 
  27   
  28  try: 
  29      import commitment 
  30      commitment.set_reference_string(23434347834783478783478L, 
  31                                      489237823478234783478020L) 
  32  except ImportError: 
33 # The commitment module is not public, so we cannot expect the 34 # import to work. Catching the ImportError here allows the 35 # benchmark and tests to import viff.orlandi without blowing up. 36 # It is only if the OrlandiRuntime is used that things blow up. 37 pass 38 39 # import logging 40 # LOG_FILENAME = 'logging_example.out' 41 # logging.basicConfig(filename=LOG_FILENAME,level=logging.DEBUG,) 42 43 -class OrlandiException(Exception):
44 pass
45
46 -class OrlandiShare(Share):
47 """A share in the Orlandi runtime. 48 49 A share in the Orlandi runtime is a 3-tuple ``(x_i, rho_i, Cr_i)`` of: 50 51 - A share of a number, ``x_i`` 52 - A tuple of two random numbers, ``rho_i = (rho_i1, rho_i2)`` 53 - A commitment to the number and the random numbers, ``Cr_i`` 54 55 The :class:`Runtime` operates on shares, represented by this class. 56 Shares are asynchronous in the sense that they promise to attain a 57 value at some point in the future. 58 59 Shares overload the arithmetic operations so that ``x = a + b`` 60 will create a new share *x*, which will eventually contain the 61 sum of *a* and *b*. Each share is associated with a 62 :class:`Runtime` and the arithmetic operations simply call back to 63 that runtime. 64 """ 65
66 - def __init__(self, runtime, field, value=None, rho=None, commitment=None):
67 self.share = value 68 self.rho = rho 69 self.commitment = commitment 70 Share.__init__(self, runtime, field, (value, rho, commitment))
71
72 73 -class OrlandiRuntime(Runtime, HashBroadcastMixin):
74 """The Orlandi runtime. 75 76 The runtime is used for sharing values (:meth:`secret_share` or 77 :meth:`shift`) into :class:`OrlandiShare` object and opening such 78 shares (:meth:`open`) again. Calculations on shares is normally 79 done through overloaded arithmetic operations, but it is also 80 possible to call :meth:`add`, :meth:`mul`, etc. directly if one 81 prefers. 82 83 Each player in the protocol uses a :class:`Runtime` object. To 84 create an instance and connect it correctly with the other 85 players, please use the :func:`create_runtime` function instead of 86 instantiating a Runtime directly. The :func:`create_runtime` 87 function will take care of setting up network connections and 88 return a :class:`Deferred` which triggers with the 89 :class:`Runtime` object when it is ready. 90 """ 91
92 - def __init__(self, player, threshold=None, options=None):
93 """Initialize runtime.""" 94 Runtime.__init__(self, player, threshold, options) 95 self.threshold = self.num_players - 1 96 self.s = 1 97 self.d = 0 98 self.s_lambda = 1
99
100 - def compute_delta(self, d):
101 def product(j): 102 pt = 1 103 pn = 1 104 for k in xrange(1, 2 * d + 2): 105 if k != j: 106 pt *= k 107 pn *= k - j 108 return pt // pn
109 110 delta = [] 111 for j in xrange(1, 2 * d + 2): 112 delta.append(product(j)) 113 return delta
114
115 - def output(self, share, receivers=None, threshold=None):
116 return self.open(share, receivers, threshold)
117
118 - def _send_orlandi_share(self, other_id, pc, xi, rhoi, Cx):
119 """Send the share *xi*, *rhoi*, and the commitment *Cx* to 120 party *other_id*.""" 121 self.protocols[other_id].sendShare(pc, xi) 122 self.protocols[other_id].sendShare(pc, rhoi[0]) 123 self.protocols[other_id].sendShare(pc, rhoi[1]) 124 self.protocols[other_id].sendData(pc, TEXT, repr(Cx))
125
126 - def _expect_orlandi_share(self, peer_id, field):
127 """Waits for a number ``x``, ``rho``, and the commitment for 128 ``x``.""" 129 xi = self._expect_share(peer_id, field) 130 Cx = Deferred() 131 rhoi1 = self._expect_share(peer_id, field) 132 rhoi2 = self._expect_share(peer_id, field) 133 self._expect_data(peer_id, TEXT, Cx) 134 sls = ShareList([xi, rhoi1, rhoi2, Cx]) 135 def combine(ls): 136 expected_num = 4; 137 if len(ls) is not expected_num: 138 raise OrlandiException("Cannot share number, trying to create a share," 139 " expected %s components got %s." 140 % (expected_num, len(ls))) 141 s1, xi = ls[0] 142 s2, rhoi1 = ls[1] 143 s3, rhoi2 = ls[2] 144 s4, Cx = ls[3] 145 Cxx = commitment.deserialize(Cx) 146 if not (s1 and s2 and s3 and s4): 147 raise OrlandiException("Cannot share number, trying to create share," 148 " but a component did arrive properly.") 149 return OrlandiShare(self, field, xi, (rhoi1, rhoi2), Cxx)
150 sls.addCallbacks(combine, self.error_handler) 151 return sls 152
153 - def _expect_orlandi_share_xi_rhoi(self, peer_id, field):
154 xi = self._expect_share(peer_id, field) 155 rhoi1 = self._expect_share(peer_id, field) 156 rhoi2 = self._expect_share(peer_id, field) 157 sls = ShareList([xi, rhoi1, rhoi2]) 158 def combine(ls): 159 expected_num = 3; 160 if len(ls) is not expected_num: 161 raise OrlandiException("Cannot share number, trying to create a share," 162 " expected %s components got %s." 163 % (expected_num, len(ls))) 164 165 s1, xi = ls[0] 166 s2, rhoi1 = ls[1] 167 s3, rhoi2 = ls[2] 168 if not (s1 and s2 and s3): 169 raise OrlandiException("Cannot share number, trying to create share " 170 "but a component did arrive properly.") 171 return OrlandiShare(self, field, xi, (rhoi1, rhoi2))
172 sls.addCallbacks(combine, self.error_handler) 173 return sls 174
175 - def secret_share(self, inputters, field, number=None, threshold=None):
176 """Share the value *number* among all the parties using 177 additive sharing. 178 179 To share an element ``x in Z_p``, choose random ``x_1, ..., 180 x_n-1 in Z_p``, define ``x_n = x - SUM_i=1^n-1 x_i mod p``. 181 182 Choose random values ``rho_x1, ..., rho_xn in (Z_p)^2``, 183 define ``rho_x = SUM_i=1^n rho_x,i`` and ``C_x = Com_ck(x, 184 p_x)``. 185 186 Send ``[x]_i = (x_i, rho_xi, C_x)`` to party ``P_i``. 187 """ 188 assert number is None or self.id in inputters 189 self.threshold = self.num_players - 1 190 191 self.program_counter[-1] += 1 192 193 def additive_shares_with_rho(x): 194 """Returns a tuple of a list of tuples (player id, share, 195 rho) and rho. 196 197 Chooses random elements ``x_1, ..., x_n-1`` in field and 198 ``x_n`` st. ``x_n = x - Sum_i=1^n-1 x_i``. 199 200 Chooses random pair of elements ``rho_1, ..., rho_n in 201 Z_p^2`` and define ``rho_n = Sum_i=1^n rho_i``. 202 203 Returns a pair of ``((player id, x_i, rho_i), rho)``. 204 """ 205 shares = [] 206 rhos = [] 207 sum = 0 208 rho1 = 0 209 rho2 = 0 210 for i in xrange(1, self.num_players): 211 xi = field(rand.randint(0, field.modulus - 1)) 212 rhoi1 = field(rand.randint(0, field.modulus - 1)) 213 rhoi2 = field(rand.randint(0, field.modulus - 1)) 214 sum += xi 215 rho1 += rhoi1 216 rho2 += rhoi2 217 shares.append((i, xi, (rhoi1, rhoi2))) 218 xn = field(x) - sum 219 rhon1 = field(rand.randint(0, field.modulus - 1)) 220 rhon2 = field(rand.randint(0, field.modulus - 1)) 221 shares.append((self.num_players, xn, (rhon1, rhon2))) 222 rho1 += rhon1 223 rho2 += rhon2 224 return shares, (rho1, rho2)
225 226 # Send ``[x]_i = (x_i, rho_x,i, C_x)`` to party ``P_i``. 227 results = [] 228 for peer_id in inputters: 229 if peer_id == self.id: 230 pc = tuple(self.program_counter) 231 shares, rho = additive_shares_with_rho(number) 232 Cx = commitment.commit(number, rho[0].value, rho[1].value) 233 # Distribute the shares 234 the_others = [] 235 for other_id, xi, rhoi in shares: 236 if other_id == self.id: 237 results.append(OrlandiShare(self, field, xi, rhoi, Cx)) 238 else: 239 # Send ``xi``, ``rhoi``, and commitment 240 self._send_orlandi_share(other_id, pc, xi, rhoi, Cx) 241 else: 242 # Expect ``xi``, ``rhoi``, and commitment 243 results.append(self._expect_orlandi_share(peer_id, field)) 244 # do actual communication 245 self.activate_reactor() 246 # Unpack a singleton list. 247 if len(results) == 1: 248 return results[0] 249 return results 250
251 - def open(self, share, receivers=None, threshold=None):
252 """Share reconstruction. 253 254 Every partyi broadcasts a share pair ``(x_i', rho_x,i')``. 255 256 The parties compute the sums ``x'``, ``rho_x'`` and check 257 ``Com_ck(x',rho_x' = C_x``. 258 259 If yes, return ``x = x'``, else else return :const:`None`. 260 """ 261 assert isinstance(share, Share) 262 # all players receive result by default 263 if receivers is None: 264 receivers = self.players.keys() 265 assert threshold is None 266 threshold = self.num_players - 1 267 268 field = share.field 269 270 self.program_counter[-1] += 1 271 272 def recombine_value(shares, Cx): 273 x = 0 274 rho1 = 0 275 rho2 = 0 276 for xi, rhoi1, rhoi2 in shares: 277 x += xi 278 rho1 += rhoi1 279 rho2 += rhoi2 280 Cx1 = commitment.commit(x.value, rho1.value, rho2.value) 281 if Cx1 == Cx: 282 return x 283 else: 284 #return x 285 raise OrlandiException("Wrong commitment for value %s, %s, %s, found %s expected %s." % 286 (x, rho1, rho2, Cx1, Cx))
287 288 def deserialize(ls): 289 shares = [(field(long(x)), field(long(rho1)), field(long(rho2))) 290 for x, rho1, rho2 in map(self.list_str, ls)] 291 return shares 292 293 def exchange((xi, (rhoi1, rhoi2), Cx), receivers): 294 # Send share to all receivers. 295 ds = self.broadcast(self.players.keys(), receivers, 296 str((str(xi.value), 297 str(rhoi1.value), 298 str(rhoi2.value)))) 299 300 if self.id in receivers: 301 result = gatherResults(ds) 302 result.addCallbacks(deserialize, self.error_handler) 303 result.addCallbacks(recombine_value, self.error_handler, 304 callbackArgs=(Cx,)) 305 return result 306 307 result = share.clone() 308 self.schedule_callback(result, exchange, receivers) 309 result.addErrback(self.error_handler) 310 311 # do actual communication 312 self.activate_reactor() 313 314 if self.id in receivers: 315 return result 316
317 - def random_share(self, field):
318 """Generate a random share in the field, field. 319 320 To generate a share of a random element ``r in Z_p``, party 321 ``P_i`` chooses at random ``r_i, rho_ri in Z_p X (Z_p)^2`` and 322 broadcast ``C_r^i = Com_ck(r_i, rho_ri)``. 323 324 Every party computes ``C_r = PRODUCT_i=1^n C_r^i = Com_ck(r, 325 rho_r)``, where ``r_i = SUM_i=1^n r_i and rho_r = SUM_i=1^n 326 rho_ri``. 327 328 Party ``P_i sets [r]_i = (r_i, rho_ri, C_r)``. 329 """ 330 self.program_counter[-1] += 1 331 332 # P_i chooses at random r_i, rho_ri in Z_p x (Z_p)^2 333 ri = field(rand.randint(0, field.modulus - 1)) 334 rhoi1 = field(rand.randint(0, field.modulus - 1)) 335 rhoi2 = field(rand.randint(0, field.modulus - 1)) 336 337 # compute C_r^i = Com_ck(r_i, rho_ri). 338 Cri = commitment.commit(ri.value, rhoi1, rhoi2) 339 340 # Broadcast C_r^i. 341 sls = gatherResults(self.broadcast(self.players.keys(), self.players.keys(), repr(Cri))) 342 343 def compute_commitment(ls): 344 Cr = ls.pop() 345 for Cri in ls: 346 Cr = Cr * Cri 347 return OrlandiShare(self, field, ri, (rhoi1, rhoi2), Cr)
348 349 def deserialize(ls): 350 return [ commitment.deserialize(x) for x in ls ] 351 352 sls.addCallbacks(deserialize, self.error_handler) 353 sls.addCallbacks(compute_commitment, self.error_handler) 354 355 s = Share(self, field) 356 # We add the result to the chains in triple. 357 sls.chainDeferred(s) 358 359 # do actual communication 360 self.activate_reactor() 361 362 return s 363
364 - def add(self, share_a, share_b):
365 """Addition of shares. 366 367 Communication cost: none. 368 369 Each party ``P_i`` computes:: 370 371 [z]_i = [x]_i + [y]_i 372 = (x_i + y_i mod p, rho_xi + rho_yi mod p, C_x * C_y) 373 374 """ 375 def is_share(s, field): 376 if not isinstance(s, Share): 377 if not isinstance(s, FieldElement): 378 s = field(s) 379 (v, rhov, Cv) = self._additive_constant(field(0), s) 380 return OrlandiShare(self, field, v, rhov, Cv) 381 return s
382 383 # Either share_a or share_b must have an attribute called "field". 384 field = getattr(share_a, "field", getattr(share_b, "field", None)) 385 386 share_a = is_share(share_a, field) 387 share_b = is_share(share_b, field) 388 389 # Add rho_xi and rho_yi and compute the commitment. 390 def compute_sums((x, y)): 391 (zi, (rhozi1, rhozi2), Cz) = self._plus(x, y) 392 return OrlandiShare(self, field, zi, (rhozi1, rhozi2), Cz) 393 394 result = gather_shares([share_a, share_b]) 395 result.addCallbacks(compute_sums, self.error_handler) 396 return result 397
398 - def sub(self, share_a, share_b):
399 """Subtraction of shares. 400 401 Communication cost: none. 402 403 Each party ``P_i`` computes:: 404 405 [z]_i = [x]_i - [y]_i 406 = (x_i - y_i mod p, rho_x,i - rho_y,i mod p, C_x * C_y) 407 408 """ 409 def is_share(s, field): 410 if not isinstance(s, Share): 411 if not isinstance(s, FieldElement): 412 s = field(s) 413 (v, rhov, Cv) = self._additive_constant(field(0), s) 414 return OrlandiShare(self, field, v, rhov, Cv) 415 return s
416 417 # Either share_a or share_b must have an attribute called "field". 418 field = getattr(share_a, "field", getattr(share_b, "field", None)) 419 420 share_a = is_share(share_a, field) 421 share_b = is_share(share_b, field) 422 423 # Subtract xi and yi, rhoxi and rhoyi, and compute the commitment 424 def compute_subs((x, y)): 425 zi, (rhozi1, rhozi2), Cz = self._minus(x, y) 426 return OrlandiShare(self, field, zi, (rhozi1, rhozi2), Cz) 427 428 result = gather_shares([share_a, share_b]) 429 result.addCallbacks(compute_subs, self.error_handler) 430 return result 431
432 - def input(self, inputters, field, number=None, threshold=None):
433 """Input *number* to the computation. 434 435 The input is shared using the :meth:`shift` method. 436 """ 437 return self.shift(inputters, field, number)
438 439
440 - def shift(self, inputters, field, number=None):
441 """Shift of a share. 442 443 Useful for input. 444 445 Communication cost: ???. 446 447 Assume the parties are given a random share ``[r]`` by a 448 trusted dealer. Then we denote the following protocol but 449 ``[x] = Shift(P_i, x, [r])``. 450 451 1. ``r = OpenTo(P_i, [r]`` 452 453 2. ``P_i broadcasts Delta = r - x`` 454 455 3. ``[x] = [r] - Delta`` 456 """ 457 # TODO: Communitcation costs? 458 assert (self.id in inputters and number != None) or (self.id not in inputters) 459 460 self.program_counter[-1] += 1 461 462 results = [] 463 def hack(_, peer_id): 464 # Assume the parties are given a random share [r] by a 465 # trusted dealer. 466 share_r = self.random_share(field) 467 # 1. r = OpenTo(P_i, [r]) 468 open_r = self.open(share_r, [peer_id]) 469 def subtract_delta(delta, share_r): 470 delta = field(long(delta)) 471 x = self.sub(share_r, delta) 472 return x
473 if peer_id == self.id: 474 def g(r, x): 475 delta = r - x 476 delta = self.broadcast([peer_id], self.players.keys(), 477 str(delta.value)) 478 self.schedule_callback(delta, subtract_delta, share_r) 479 delta.addErrback(self.error_handler) 480 return delta 481 self.schedule_callback(open_r, g, number) 482 open_r.addErrback(self.error_handler) 483 return open_r 484 else: 485 d = Deferred() 486 def g(_, peer_id, share_r): 487 delta = self.broadcast([peer_id], self.players.keys()) 488 self.schedule_callback(delta, subtract_delta, share_r) 489 delta.addErrback(self.error_handler) 490 return delta 491 self.schedule_callback(d, g, peer_id, share_r) 492 d.addErrback(self.error_handler) 493 d.callback(None) 494 return d 495 496 for peer_id in inputters: 497 s = Share(self, field) 498 self.schedule_callback(s, hack, peer_id) 499 s.addErrback(self.error_handler) 500 s.callback(None) 501 results.append(s) 502 503 # do actual communication 504 self.activate_reactor() 505 506 if len(results) == 1: 507 return results[0] 508 return results 509
510 - def mul(self, share_x, share_y):
511 """Multiplication of shares. 512 513 Communication cost: ???. 514 """ 515 # TODO: Communication cost? 516 assert isinstance(share_x, Share) or isinstance(share_y, Share), \ 517 "At least one of share_x and share_y must be a Share." 518 519 self.program_counter[-1] += 1 520 521 field = getattr(share_x, "field", getattr(share_y, "field", None)) 522 523 def finish_mul((a, b, c)): 524 return self._basic_multiplication(share_x, share_y, a, b, c)
525 526 # This will be the result, a Share object. 527 result = Share(self, share_x.field) 528 # This is the Deferred we will do processing on. 529 triple = self._get_triple(field) 530 triple = self.schedule_complex_callback(triple, finish_mul) 531 # We add the result to the chains in triple. 532 triple.chainDeferred(result) 533 return result 534
535 - def _additive_constant(self, zero, field_element):
536 """Greate an additive constant. 537 538 Any additive constant can be interpreted as: 539 ``[c]_1 = (c, 0, Com_ck(c,0))`` and 540 ``[c]_i = (0, 0, Com_ck(c,0)) for i != 1``. 541 """ 542 v = zero 543 if self.id == 1: 544 v = field_element 545 Cx = commitment.commit(field_element.value, zero.value, zero.value) 546 return (v, (zero, zero), Cx)
547
548 - def _plus(self, x, y):
549 """Addition of share-tuples *x* and *y*. 550 551 Each party ``P_i`` computes: 552 ``[x]_i = (x_i, rho_xi, C_x)`` 553 ``[y]_i = (y_i, rho_yi, C_y)`` 554 ``[z]_i = [x]_i + [y]_i 555 = (x_i + y_i mod p, rho_xi + rho_yi mod p, C_x * C_y)``. 556 """ 557 (xi, (rhoxi1, rhoxi2), Cx) = x 558 (yi, (rhoyi1, rhoyi2), Cy) = y 559 zi = xi + yi 560 rhozi1 = rhoxi1 + rhoyi1 561 rhozi2 = rhoxi2 + rhoyi2 562 Cz = Cx * Cy 563 return (zi, (rhozi1, rhozi2), Cz)
564
565 - def _minus(self, x, y):
566 """Subtraction of share-tuples *x* and *y*. 567 568 Each party ``P_i`` computes: 569 ``[x]_i = (x_i, rho_x,i, C_x)`` 570 ``[y]_i = (y_i, rho_y,i, C_y)`` 571 ``[z]_i = [x]_i - [y]_i 572 = (x_i - y_i mod p, rho_x,i - rho_y,i mod p, C_x / C_y)``. 573 """ 574 xi, (rhoxi1, rhoxi2), Cx = x 575 yi, (rhoyi1, rhoyi2), Cy = y 576 zi = xi - yi 577 rhozi1 = rhoxi1 - rhoyi1 578 rhozi2 = rhoxi2 - rhoyi2 579 Cz = Cx / Cy 580 return (zi, (rhozi1, rhozi2), Cz)
581
582 - def _cmul(self, share_x, share_y, field):
583 """Multiplication of a share with a constant. 584 585 Either share_x or share_y must be an OrlandiShare but not 586 both. Returns None if both share_x and share_y are 587 OrlandiShares. 588 """ 589 def constant_multiply(x, c): 590 assert(isinstance(c, FieldElement)) 591 zi, rhoz, Cx = self._const_mul(c.value, x) 592 return OrlandiShare(self, field, zi, rhoz, Cx)
593 if not isinstance(share_x, Share): 594 # Then share_y must be a Share => local multiplication. We 595 # clone first to avoid changing share_y. 596 assert isinstance(share_y, Share), \ 597 "At least one of the arguments must be a share." 598 result = share_y.clone() 599 result.addCallback(constant_multiply, share_x) 600 return result 601 if not isinstance(share_y, Share): 602 # Likewise when share_y is a constant. 603 assert isinstance(share_x, Share), \ 604 "At least one of the arguments must be a share." 605 result = share_x.clone() 606 result.addCallback(constant_multiply, share_y) 607 return result 608 return None 609
610 - def _const_mul(self, c, x):
611 """Multiplication of a share-tuple with a constant c.""" 612 assert(isinstance(c, long) or isinstance(c, int)) 613 xi, (rhoi1, rhoi2), Cx = x 614 zi = xi * c 615 rhoz = (rhoi1 * c, rhoi2 * c) 616 Cz = Cx**c 617 return (zi, rhoz, Cz)
618
619 - def _get_share(self, field, value):
620 Cc = commitment.commit(value * 3, 0, 0) 621 c = OrlandiShare(self, field, field(value), (field(0), field(0)), Cc) 622 return c
623 624 @preprocess("random_triple")
625 - def _get_triple(self, field):
626 c, d = self.random_triple(field, 1) 627 def f(ls): 628 return ls[0]
629 d.addCallbacks(f, self.error_handler) 630 return d 631
632 - def _basic_multiplication(self, share_x, share_y, triple_a, triple_b, triple_c):
633 """Multiplication of shares give a triple. 634 635 Communication cost: ???. 636 637 ``d = Open([x] - [a])`` 638 ``e = Open([y] - [b])`` 639 ``[z] = e[x] + d[y] - [de] + [c]`` 640 """ 641 assert isinstance(share_x, Share) or isinstance(share_y, Share), \ 642 "At least one of share_x and share_y must be a Share." 643 644 self.program_counter[-1] += 1 645 646 field = getattr(share_x, "field", getattr(share_y, "field", None)) 647 n = field(0) 648 649 cmul_result = self._cmul(share_x, share_y, field) 650 if cmul_result is not None: 651 return cmul_result 652 653 def multiply((x, y, d, e, c)): 654 # [de] 655 de = self._additive_constant(field(0), d * e) 656 # e[x] 657 t1 = self._const_mul(e.value, x) 658 # d[y] 659 t2 = self._const_mul(d.value, y) 660 # d[y] - [de] 661 t3 = self._minus(t2, de) 662 # d[y] - [de] + [c] 663 t4 = self._plus(t3, c) 664 # [z] = e[x] + d[y] - [de] + [c] 665 zi, rhoz, Cz = self._plus(t1, t4) 666 return OrlandiShare(self, field, zi, rhoz, Cz)
667 668 # d = Open([x] - [a]) 669 d = self.open(share_x - triple_a) 670 # e = Open([y] - [b]) 671 e = self.open(share_y - triple_b) 672 result = gather_shares([share_x, share_y, d, e, triple_c]) 673 result.addCallbacks(multiply, self.error_handler) 674 675 # do actual communication 676 self.activate_reactor() 677 678 return result 679
680 - def sum_poly(self, j, ls):
681 exp = j 682 fj, (rhoj1, rhoj2), Cfj = ls[0] 683 x = fj*exp 684 rho1 = rhoj1 * exp 685 rho2 = rhoj2 * exp 686 Cx = Cfj**exp 687 exp *= j 688 689 for (fj, (rhoj1, rhoj2), Cfj) in ls[1:]: 690 x += fj * exp 691 rho1 += rhoj1 * exp 692 rho2 += rhoj2 * exp 693 Cx = Cx * (Cfj**exp) 694 exp *= j 695 return x, (rho1, rho2), Cx
696
697 - def leak_tolerant_mul(self, share_x, share_y, M):
698 """Leak tolerant multiplication of shares. 699 700 Communication cost: ???. 701 702 Assuming a set of multiplicative triples: 703 ``M = ([a_i], [b_i], [c_i]) for 1 <= i <= 2d + 1``. 704 705 1. ``for i = 1, ..., d do [f_i] = rand(), [g_i] = rand()`` 706 707 2. Compute:: 708 709 for j = 1, ..., 2d+1 do 710 [F_j] = [x] + SUM_i=1^d [f_i]*j^i 711 and 712 [G_j] = [y] + SUM_i=1^d [g_i]*j^i 713 714 3. ``for j = 1, ..., 2d+1 do [H_j] = Mul([F_j], [G_j], [a_j], 715 [b_j], [c_j])`` 716 717 4. compute ``[H_0] = SUM_j=1^2d+1 delta_j[H_j]`` where 718 ``delta_j = PRODUCT_k=1, k!=j^2d+1 k/(k-j)`` 719 720 5. output ``[z] = [H_0]`` 721 """ 722 assert isinstance(share_x, Share) or isinstance(share_y, Share), \ 723 "At least one of share_x and share_y must be a Share." 724 725 self.program_counter[-1] += 1 726 727 field = getattr(share_x, "field", getattr(share_y, "field", None)) 728 n = field(0) 729 730 cmul_result = self._cmul(share_x, share_y, field) 731 if cmul_result is not None: 732 return cmul_result 733 734 # 1. for i = 1, ..., d do [f_i] = rand(), [g_i] = rand() 735 d = (len(M) - 1) // 2 736 deltas = self.compute_delta(d) 737 f = [] 738 g = [] 739 for x in xrange(d): 740 f.append(self.random_share(field)) 741 g.append(self.random_share(field)) 742 743 def compute_polynomials(t): 744 x, y = t[0] 745 f = [] 746 g = [] 747 if 1 in t: 748 f = t[1] 749 if 2 in t: 750 g = t[2] 751 # print "==> poly", self.id 752 # print "x:", x 753 # print "y:", y 754 # print "f:", f 755 # print "g:", g 756 # 2) for j = 1, ..., 2d+1 do 757 # [F_j] = [x] + SUM_i=1^d [f_i]*j^i 758 # and 759 # [G_j] = [y] + SUM_i=1^d [g_i]*j^i 760 h0i, rhoh0, Ch0 = self._additive_constant(field(0), n) 761 H0 = OrlandiShare(self, field, h0i, rhoh0, Ch0) 762 xi, (rhoxi1, rhoxi2), Cx = x 763 yi, (rhoyi1, rhoyi2), Cy = y 764 765 for j in xrange(1, 2*d + 2): 766 Fji = xi 767 rho1_Fji = rhoxi1 768 rho2_Fji = rhoxi2 769 C_Fji = Cx 770 if f != []: 771 # SUM_i=1^d [f_i]*j^i 772 vi, (rhovi1, rhovi2), Cv = self.sum_poly(j, f) 773 # [F_j] = [x] + SUM_i=1^d [f_i]*j^i 774 Fji += vi 775 rho1_Fji += rhovi1 776 rho2_Fji += rhovi2 777 C_Fji *= Cv 778 Gji = yi 779 rho1_Gji = rhoyi1 780 rho2_Gji = rhoyi2 781 C_Gji = Cy 782 if g != []: 783 # SUM_i=1^d [g_i]*j^i 784 wi, (rhowi1, rhowi2), Cw = self.sum_poly(j, g) 785 # [G_j] = [y] + SUM_i=1^d [g_i]*j^i 786 Gji += wi 787 rho1_Gji += rhowi1 788 rho2_Gji += rhowi2 789 C_Gji *= Cw 790 Fj = OrlandiShare(self, field, Fji, (rho1_Fji, rho2_Fji), C_Fji) 791 Gj = OrlandiShare(self, field, Gji, (rho1_Gji, rho2_Gji), C_Gji) 792 a, b, c = M.pop(0) 793 794 # [H_j] = Mul([F_j], [G_j], [a_j], [b_j], [c_j]) 795 Hj = self._basic_multiplication(Fj, Gj, a, b, c) 796 dj = self._cmul(field(deltas[j - 1]), Hj, field) 797 H0 = H0 + dj 798 # 5) output [z] = [H_0] 799 return H0
800 801 ls = [gather_shares([share_x, share_y])] 802 if g: 803 ls.append(gather_shares(g)) 804 if f: 805 ls.append(gather_shares(f)) 806 result = gather_shares(ls) 807 self.schedule_callback(result, compute_polynomials) 808 result.addErrback(self.error_handler) 809 810 # do actual communication 811 self.activate_reactor() 812 813 return result 814
815 - def triple_gen(self, field):
816 """Generate a triple ``a, b, c`` s.t. ``c = a * b``. 817 818 1. Every party ``P_i`` chooses random values ``a_i, r_i in Z_p 819 X (Z_p)^2``, compute ``alpha_i = Enc_eki(a_i)`` and ``Ai = 820 Com_ck(a_i, r_i)``, and broadcast them. 821 822 2. Every party ``P_j`` does: 823 824 a. choose random ``b_j, s_j in Z_p X (Z_p)^2``. 825 826 b. compute ``B_j = ``Com_ck(b_j, s_j)`` and broadcast it. 827 828 c. ``P_j`` do towards every other party: 829 830 i. choose random ``d_ij in Z_p^3`` 831 832 ii. compute and send 833 ``gamma_ij = alpha_i^b_j Enc_ek_i(1;1)^d_ij`` to ``P_i``. 834 835 836 3. Every party ``P_i`` does: 837 838 a. compute ``c_i = SUM_j Dec_sk_i(gamma_ij) - SUM_j d_ij mod p`` 839 840 b. pick random ``t_i in (Z_p)^2``, compute and 841 broadcast ``C_i = Com_ck(c_i, t_i)`` 842 843 4. Everyone computes: 844 ``(A, B, C) = (PRODUCT_i A_i, PRODUCT_i B_i, PRODUCT_i C_i)`` 845 846 5. Every party ``P_i`` outputs shares ``[a_i] = (a_i, r_i, A)``, 847 ``[b_i] = (b_i, s_i, B)``, and ``[c_i] = (c_i, t_i, C)``. 848 849 """ 850 self.program_counter[-1] += 1 851 852 def random_number(p): 853 return field(rand.randint(0, p - 1))
854 855 def product(ls): 856 """Compute the product of the elements in the list *ls*.""" 857 b = commitment.deserialize(ls[0]) 858 for x in ls[1:]: 859 b *= commitment.deserialize(x) 860 return b 861 862 def sum(ls): 863 """Compute the sum of the elements in the list *ls*.""" 864 b = field(0) 865 for x in ls: 866 b += x 867 return b 868 869 def step45(Cs, alphas, gammas, alpha_randomness, 870 As, Bs, ai, bi, ci, r, s, t, dijs): 871 """4) Everyone computes: 872 ``A = PRODUCT_i A_i`` 873 ``B = PRODUCT_i B_i`` 874 ``C = PRODUCT_i C_i`` 875 876 5) Every party ``P_i`` outputs shares ``[a_i] = (a_i, r_i, A)``, 877 ``[b_i] = (b_i, s_i, B)``, and ``[c_i] = (c_i, t_i, C)``. 878 """ 879 A = product(As) 880 B = product(Bs) 881 C = product(Cs) 882 a = OrlandiShare(self, field, ai, r, A) 883 b = OrlandiShare(self, field, bi, s, B) 884 c = OrlandiShare(self, field, ci, t, C) 885 return (a, b, c, (alphas, alpha_randomness, gammas, dijs)) 886 887 def decrypt_gammas(ls): 888 """Decrypt all the elements of the list *ls*.""" 889 rs = [] 890 for x in ls: 891 rs.append(field(decrypt(x, self.players[self.id].seckey))) 892 return rs 893 894 def step3(gammas, alphas, alpha_randomness, As, Bs, ai, bi, r, s, dijs): 895 """3) Every party ``P_i`` does: 896 (a) compute 897 ``c_i = SUM_j Dec_sk_i(gamma_ij) - SUM_j d_ji mod p`` 898 899 (b) pick random ``t_i in (Z_p)^2``, compute and 900 broadcast ``C_i = Com_ck(c_i, t_i)`` 901 """ 902 # c_i = SUM_j Dec_sk_i(gamma_ij) - SUM_j d_ji mod p. 903 ls = decrypt_gammas(gammas) 904 ci = sum(ls) - sum(dijs) 905 # (b) pick random t_i in (Z_p)^2. 906 t1 = random_number(field. modulus) 907 t2 = random_number(field. modulus) 908 t = (t1, t2) 909 # C_i = Com_ck(c_i, t_i). 910 Ci = commitment.commit(ci.value, t1.value, t2.value) 911 912 # Broadcast Ci. 913 Cs = self.broadcast(self.players.keys(), self.players.keys(), 914 repr(Ci)) 915 result = gatherResults(Cs) 916 result.addCallbacks(step45, self.error_handler, 917 callbackArgs=(alphas, gammas, alpha_randomness, 918 As, Bs, ai, bi, ci, r, s, t, dijs)) 919 return result 920 921 def step2c(Bs, As, alphas, alpha_randomness, ai, bj, r, s): 922 """(c) P_j do, towards every other party: 923 i. choose random d_i,j in Z_p^3 924 ii. compute and send 925 gamma_ij = alpha_i^b_j Enc_ek_i(1;1)^d_ij to P_i. 926 """ 927 928 # (c) P_j do, towards every other party: 929 dijs = [None] * len(self.players.keys()) 930 results = [None] * len(self.players.keys()) 931 pc = tuple(self.program_counter) 932 for pi in self.players.keys(): 933 n = self.players[pi].pubkey[0] 934 nsq = n * n 935 # choose random d_i,j in Z_p^3 936 dij = random_number(field.modulus**3) 937 # Enc_ek_i(1;1)^d_ij 938 enc = encrypt_r(1, 1, self.players[pi].pubkey) 939 t1 = pow(enc, dij.value, nsq) 940 # alpha_i^b_j. 941 t2 = pow(alphas[pi - 1], bj.value, nsq) 942 # gamma_ij = alpha_i^b_j Enc_ek_i(1;1)^d_ij 943 gammaij = (t2) * (t1) % nsq 944 # Broadcast gamma_ij 945 if pi != self.id: 946 self.protocols[pi].sendData(pc, PAILLIER, str(gammaij)) 947 d = Deferred() 948 d.addCallbacks(lambda value: long(value), self.error_handler) 949 self._expect_data(pi, PAILLIER, d) 950 else: 951 d = Deferred() 952 d.callback(gammaij) 953 dijs[pi - 1] = dij 954 results[pi - 1] = d 955 result = gatherResults(results) 956 self.schedule_callback(result, step3, alphas, alpha_randomness, 957 As, Bs, ai, bj, r, s, dijs) 958 result.addErrback(self.error_handler) 959 return result 960 961 def step2ab((alphas, As), ai, r, alpha_randomness): 962 """2) Every party P_j does: 963 (a) choose random b_j, s_j in Z_p X (Z_p)^2. 964 965 (b) compute B_j = Com_ck(b_j, s_j) and broadcast it. 966 """ 967 # (a) choose random b_j, s_j in Z_p X (Z_p)^2. 968 bj = random_number(field.modulus) 969 s1 = random_number(field.modulus) 970 s2 = random_number(field.modulus) 971 # (b) compute B_j = Com_ck(b_j, s_j). 972 Bj = commitment.commit(bj.value, s1.value, s2.value) 973 974 # Broadcast B_j. 975 results = self.broadcast(self.players.keys(), self.players.keys(), repr(Bj)) 976 result = gatherResults(results) 977 self.schedule_callback(result, step2c, As, alphas, alpha_randomness, 978 ai, bj, r, (s1, s2)) 979 result.addErrback(self.error_handler) 980 return result 981 982 # 1) Every party P_i chooses random values a_i, r_i in Z_p X (Z_p)^2, 983 # compute alpha_i = Enc_eki(a_i) and Ai = Com_ck(a_i, r_i), and 984 # broadcast them. 985 986 # Every party P_i chooses random values a_i, r_i in Z_p X (Z_p)^2 987 ai = random_number(field.modulus) 988 r1 = random_number(field.modulus) 989 r2 = random_number(field.modulus) 990 991 # compute alpha_i = Enc_eki(a_i) 992 n, g = self.players[self.id].pubkey 993 alpha_randomness = rand.randint(1, long(n)) 994 alphai = encrypt_r(ai.value, alpha_randomness, (n, g)) 995 # and A_i = Com_ck(a_i, r_i). 996 Ai = commitment.commit(ai.value, r1.value, r2.value) 997 998 # broadcast alpha_i and A_i. 999 ds = self.broadcast(sorted(self.players.keys()), 1000 sorted(self.players.keys()), 1001 str(alphai) + ":" + repr(Ai)) 1002 1003 result = gatherResults(ds) 1004 def split_alphas_and_As(ls): 1005 alphas = [] 1006 As = [] 1007 for x in ls: 1008 alpha, Ai = x.split(':') 1009 alphas.append(long(alpha)) 1010 As.append(Ai) 1011 return alphas, As 1012 self.schedule_callback(result, split_alphas_and_As) 1013 self.schedule_callback(result, step2ab, ai, (r1, r2), alpha_randomness) 1014 result.addErrback(self.error_handler) 1015 return result 1016
1017 - def triple_test(self, field):
1018 """Generate a triple ``(a, b, c)`` where ``c = a * b``. 1019 1020 The triple ``(a, b, c)`` is checked against the 1021 triple ``(x, y, z)`` and a random value ``r``. 1022 1023 """ 1024 triple1 = self.triple_gen(field) 1025 triple2 = self.triple_gen(field) 1026 r = self.open(self.random_share(field)) 1027 1028 def check((v, oa, ob, oc, ox, oy, oz), a, b, c, ec): 1029 if v is 0: 1030 return None 1031 return (a, b, c, ec)
1032 1033 def compute_value(((a, b, c, ec), (x, y, z, _), r)): 1034 oa = self.open(a) 1035 ob = self.open(b) 1036 oc = self.open(c) 1037 ox = self.open(x) 1038 oy = self.open(y) 1039 oz = self.open(z) 1040 l = self._cmul(r, x, field) 1041 m = self._cmul(r, y, field) 1042 n = self._cmul(r*r, z, field) 1043 d = c - self._basic_multiplication(a, b, l, m, n) 1044 r = gather_shares([d, oa, ob, oc, ox, oy, oz]) 1045 r.addCallbacks(check, self.error_handler, callbackArgs=(a, b, c, ec)) 1046 return r 1047 1048 result = gatherResults([triple1, triple2, r]) 1049 self.schedule_callback(result, compute_value) 1050 result.addErrback(self.error_handler) 1051 1052 # do actual communication 1053 self.activate_reactor() 1054 1055 return result 1056
1057 - def random_triple(self, field, quantity=1):
1058 """Generate a list of triples ``(a, b, c)`` where ``c = a * b``. 1059 1060 The triple ``(a, b, c)`` is secure in the Fcrs-hybrid model. 1061 1062 """ 1063 self.program_counter[-1] += 1 1064 1065 M = [] 1066 1067 # print "Generating %i triples... relax, have a break..." % ((1 + self.s_lambda) * (2 * self.d + 1) * quantity) 1068 1069 for x in xrange((1 + self.s_lambda) * (2 * self.d + 1) * quantity): 1070 M.append(self.triple_test(field)) 1071 1072 def step3(ls): 1073 """Coin-flip a subset test_set of M of size lambda(2d + 1)M.""" 1074 size = self.s_lambda * (2 * self.d + 1) * quantity 1075 inx = 0 1076 p_half = field.modulus // 2 1077 def coin_flip(v, ls, test_set): 1078 candidate = ls.pop(0) 1079 if p_half > v: 1080 test_set.append(candidate) 1081 else: 1082 ls.append(candidate) 1083 if size > len(test_set): 1084 r = self.random_share(field) 1085 r = self.output(r) 1086 self.schedule_callback(r, coin_flip, ls, test_set) 1087 r.addErrback(self.error_handler) 1088 return r 1089 return ls, test_set
1090 r = self.random_share(field) 1091 r = self.output(r) 1092 self.schedule_callback(r, coin_flip, ls, []) 1093 r.addErrback(self.error_handler) 1094 return r 1095 1096 def step45(lists): 1097 """For all i in test_set the parties reveal 1098 the randomness used for TripleTest() and checks that 1099 the randomness is consistent with the actual values.""" 1100 M_without_test_set = lists[0] 1101 T = lists[1] 1102 1103 def defer_share(xi, (rho1, rho2), commitment): 1104 d1 = Deferred() 1105 d2 = Deferred() 1106 d3 = Deferred() 1107 d4 = Deferred() 1108 d1.callback(xi) 1109 d2.callback(rho1) 1110 d3.callback(rho2) 1111 d4.callback(commitment) 1112 return gatherResults([d1, d2, d3, d4]) 1113 1114 def get_share(x, ls): 1115 share = ls[x * 4] 1116 rho1 = ls[x * 4 + 1] 1117 rho2 = ls[x * 4 + 2] 1118 commitment = ls[x * 4 + 3] 1119 return (share, rho1, rho2, commitment) 1120 1121 def send_share(player_id, pc, a): 1122 self._send_orlandi_share(player_id, pc, a.share, a.rho, a.commitment) 1123 1124 def receive_shares(player_id): 1125 Cx = Deferred() 1126 xi = self._expect_share(player_id, field) 1127 rho1 = self._expect_share(player_id, field) 1128 rho2 = self._expect_share(player_id, field) 1129 self._expect_data(player_id, TEXT, Cx) 1130 Cx.addCallbacks(lambda Cx: commitment.deserialize(Cx), 1131 self.error_handler) 1132 return gatherResults([xi, rho1, rho2, Cx]) 1133 1134 def send_long(player_id, pc, l): 1135 self.protocols[player_id].sendData(pc, TEXT, str(l)) 1136 1137 def receive_long(player_id): 1138 l = Deferred() 1139 self._expect_data(player_id, TEXT, l) 1140 l.addCallbacks(lambda x: long(x), self.error_handler) 1141 return l 1142 1143 def defer_value(l): 1144 d = Deferred() 1145 d.callback(l) 1146 return d 1147 1148 def check((ais, bis, cis, alpha_randomness, dijs), alphas, gammas): 1149 """So if B receives ai, bi, dij, ri, si, and the 1150 randomness used in the computation of alpha, he then 1151 checks that: 1152 1153 1) the alpha_i he received is equals to the encryption 1154 of ai and the commitment he received, Ai, is equal 1155 to the commitment of ai and ri 1156 1157 2) the commitment he received, Bj, is equal to the 1158 commitment of bj and sj 1159 1160 3) the gammaij he received is equal to the gammaij he 1161 now computes based on the values he reveives 1162 1163 4) a, b, c is a triple, a * b = c 1164 1165 5) ai, bi < p and dij < p^3 1166 """ 1167 a = 0 1168 a_rho1 = 0 1169 a_rho2 = 0 1170 b = 0 1171 b_rho1 = 0 1172 b_rho2 = 0 1173 c = 0 1174 c_rho1 = 0 1175 c_rho2 = 0 1176 1177 for x in xrange(len(ais)): 1178 (ai, a_rhoi1, a_rhoi2, A) = ais[x] 1179 (bi, b_rhoi1, b_rhoi2, B) = bis[x] 1180 (ci, c_rhoi1, c_rhoi2, C) = cis[x] 1181 # 5) ai, bi < p... 1182 if ai >= field.modulus: 1183 raise OrlandiException("Inconsistent share ai, ai >= p: %i" % ai) 1184 if bi >= field.modulus: 1185 raise OrlandiException("Inconsistent share bi, bi >= p: %i" % bi) 1186 a += ai 1187 a_rho1 += a_rhoi1 1188 a_rho2 += a_rhoi2 1189 b += bi 1190 b_rho1 += b_rhoi1 1191 b_rho2 += b_rhoi2 1192 c += ci 1193 c_rho1 += c_rhoi1 1194 c_rho2 += c_rhoi2 1195 # 1) the alpha_i he received is equals to the encryption of ai... 1196 alphai = encrypt_r(ai.value, alpha_randomness[x], 1197 self.players[x + 1].pubkey) 1198 if not(alphas[x] == alphai): 1199 raise OrlandiException("Inconsistent alpha from player %i, %i, %i" % (x + 1, alphas[x], alphai)) 1200 1201 A1 = commitment.commit(a.value, a_rho1.value, a_rho2.value) 1202 B1 = commitment.commit(b.value, b_rho1.value, b_rho2.value) 1203 C1 = commitment.commit(c.value, c_rho1.value, c_rho2.value) 1204 1205 # 1) ... and the commitment he received, Ai, is equal 1206 # to the commitment of ai and ri. 1207 if A1 != A: 1208 raise OrlandiException("Inconsistent commitment for value %s, found %s expected %s." % (a, A1, A)) 1209 # 2) the commitment he received, Bj, is equal to the 1210 # commitment of bj and sj. 1211 if B1 != B: 1212 raise OrlandiException("Inconsistent commitment for value %s, found %s expected %s." % (b, B1, B)) 1213 if C1 != C: 1214 raise OrlandiException("Inconsistent commitment for value %s, found %s expected %s." % (c, C1, C)) 1215 # 4) a, b, c is a triple, a * b = c 1216 if a * b != c: 1217 raise OrlandiException("Inconsistent triple, %i * %i does not equals %i." % (a, b, c)) 1218 1219 1220 # 3) the gammaij he received is equal to the gammaij 1221 # he now computes based on the values he reveives 1222 for j in xrange(len(ais)): 1223 n = self.players[self.id].pubkey[0] 1224 nsq = n * n 1225 dij = dijs[j] 1226 # 5) ... and dij < p^3. 1227 if dij >= (field.modulus**3): 1228 raise OrlandiException("Inconsistent random value dij %i from player %i" % (dij, j + 1)) 1229 # Enc_ek_i(1;1)^d_ij 1230 enc = encrypt_r(1, 1, self.players[self.id].pubkey) 1231 t1 = pow(enc, dij.value, nsq) 1232 # alpha_i^b_j. 1233 t2 = pow(alphas[self.id - 1], bis[j][0].value, nsq) 1234 # gamma_ij = alpha_i^b_j Enc_ek_i(1;1)^d_ij 1235 gammaij = (t2) * (t1) % nsq 1236 if gammaij != gammas[j]: 1237 raise OrlandiException("Inconsistent gammaij, %i, %i" % (gammaij, gammas[j])) 1238 1239 return True 1240 1241 dls_all = [] 1242 for (a, b, c, (alphas, alpha_randomness, gammas, dijs)) in T: 1243 ds_a = [None] * len(self.players) 1244 ds_b = [None] * len(self.players) 1245 ds_c = [None] * len(self.players) 1246 ds_alpha_randomness = [None] * len(self.players) 1247 ds_dijs = [None] * len(self.players) 1248 pc = tuple(self.program_counter) 1249 1250 for player_id in xrange(1, len(self.players.keys()) + 1): 1251 if player_id == self.id: 1252 ds_a[player_id - 1] = defer_share(a.share, a.rho, a.commitment) 1253 ds_b[player_id - 1] = defer_share(b.share, b.rho, b.commitment) 1254 ds_c[player_id - 1] = defer_share(c.share, c.rho, c.commitment) 1255 ds_alpha_randomness[player_id - 1] = defer_value(alpha_randomness) 1256 ds_dijs[player_id - 1] = defer_value(dijs[player_id - 1]) 1257 # Receive and recombine shares if this player is a 1258 # receiver. 1259 else: 1260 send_share(player_id, pc, a) 1261 send_share(player_id, pc, b) 1262 send_share(player_id, pc, c) 1263 send_long(player_id, pc, alpha_randomness) 1264 self.protocols[player_id].sendShare(pc, dijs[player_id - 1]) 1265 1266 ds_a[player_id - 1] = receive_shares(player_id) 1267 ds_b[player_id - 1] = receive_shares(player_id) 1268 ds_c[player_id - 1] = receive_shares(player_id) 1269 ds_alpha_randomness[player_id - 1] = receive_long(player_id) 1270 ds_dijs[player_id - 1] = self._expect_share(player_id, field) 1271 dls_a = gatherResults(ds_a) 1272 dls_b = gatherResults(ds_b) 1273 dls_c = gatherResults(ds_c) 1274 dls_dijs = gatherResults(ds_dijs) 1275 dls_alpha_randomness = gatherResults(ds_alpha_randomness) 1276 1277 dls = gatherResults([dls_a, dls_b, dls_c, dls_alpha_randomness, dls_dijs]) 1278 dls.addCallbacks(check, self.error_handler, callbackArgs=[alphas, gammas]) 1279 dls_all.append(dls) 1280 1281 def result(x): 1282 ls = [] 1283 for a, b, c, _ in M_without_test_set: 1284 ls.append((a, b, c)) 1285 return ls 1286 1287 dls_all = gatherResults(dls_all) 1288 dls_all.addCallbacks(result, self.error_handler) 1289 return dls_all 1290 1291 def step6(M_without_test_set): 1292 """Partition M without test_set in quantity random subsets 1293 M_i of size (2d + 1). 1294 """ 1295 subsets = [] 1296 size = 2 * self.d + 1 1297 for x in xrange(quantity): 1298 subsets.append([]) 1299 1300 def put_in_set(v, M_without_test_set, subsets): 1301 if 0 == len(M_without_test_set): 1302 return subsets 1303 v = v.value % quantity 1304 if size > len(subsets[v]): 1305 subsets[v].append(M_without_test_set.pop(0)) 1306 r = self.random_share(field) 1307 r = self.output(r) 1308 self.schedule_callback(r, put_in_set, M_without_test_set, subsets) 1309 r.addErrback(self.error_handler) 1310 return r 1311 r = self.random_share(field) 1312 r = self.output(r) 1313 self.schedule_callback(r, put_in_set, M_without_test_set, subsets) 1314 r.addErrback(self.error_handler) 1315 return r 1316 1317 1318 def step7(Msets): 1319 """For i = 1,...,M do: 1320 a) [a] <- Fpp(rand,...), [b] <- Fpp(rand,...) 1321 b) [r] <- Fpp(rand,...), 1322 c) [c] <- LTMUL([a], [b], M_i) 1323 d) Open([c] + [r]) 1324 """ 1325 ds = [] 1326 for Mi in Msets: 1327 a = self.random_share(field) 1328 b = self.random_share(field) 1329 r = self.random_share(field) 1330 c = self.leak_tolerant_mul(a, b, Mi) 1331 d = self.open(c + r) 1332 def return_abc(x, a, b, c): 1333 return a, b, c 1334 d.addCallbacks(return_abc, self.error_handler, callbackArgs=(a, b, c)) 1335 ds.append(d) 1336 result = gather_shares(ds) 1337 def triples(ls): 1338 return ls 1339 result.addCallbacks(triples, self.error_handler) 1340 return result 1341 1342 result = gatherResults(M) 1343 self.schedule_callback(result, step3) 1344 result.addErrback(self.error_handler) 1345 self.schedule_callback(result, step45) 1346 self.schedule_callback(result, step6) 1347 self.schedule_callback(result, step7) 1348 1349 # do actual communication 1350 self.activate_reactor() 1351 1352 s = Share(self, field) 1353 # We add the result to the chains in result. 1354 result.chainDeferred(s) 1355 1356 return quantity, s 1357
1358 - def error_handler(self, ex):
1359 print "Error: ", ex 1360 return ex
1361
1362 - def set_args(self, args):
1363 """args is a dictionary.""" 1364 self.s = args['s'] 1365 self.d = args['d'] 1366 self.s_lambda = args['lambda']
1367