[PATCH] New passive multiplication protocol

[Martin Geisler]

# HG changeset patch
# User Martin Geisler <***@daimi.au.dk>
# Date 1223419886 -7200
# Node ID f991be62408ed1b4e28e2bce6544743a7f6e0c38
# Parent f4de7f56103eeb450c3277ddfd9dda2e366b92a0
New passive multiplication protocol.

The protocol lets a random (but consistent) subset of 2t+1 players do
the resharing -- the remaining players can skip the local
multiplication and resharing in addition to the network traffic.

diff --git a/viff/runtime.py b/viff/runtime.py
--- a/viff/runtime.py
+++ b/viff/runtime.py
@@ -39,7 +39,7 @@
from collections import deque

from viff import shamir
-from viff.prss import prss, prss_lsb, prss_zero
+from viff.prss import prss, prss_lsb, prss_zero, generate_subsets
from viff.field import GF256, FieldElement
from viff.util import wrapper, rand

@@ -703,6 +703,17 @@
def __init__(self, player, threshold, options=None):
"""Initialize runtime."""
BasicRuntime.__init__(self, player, threshold, options)
+ self.subsets = {}
+
+ def select_subset(self, size):
+ """Select *size* players IDs based on current program counter."""
+ try:
+ subsets = self.subsets[size]
+ except KeyError:
+ players = frozenset(range(1, self.num_players+1))
+ subsets = list(generate_subsets(players, size))
+ self.subsets[size] = subsets
+ return subsets[hash(tuple(self.program_counter)) % len(subsets)]

@increment_pc
def open(self, share, receivers=None, threshold=None):
@@ -811,25 +822,39 @@
return result

# At this point both share_a and share_b must be Share
- # objects. So we wait on them, multiply and reshare.
+ # objects which imply that we must do network communication.
+ field = share_a.field
+ threshold = 2 * self.threshold + 1
+ senders = self.select_subset(threshold)

- def share_recombine(number):
- shares = shamir.share(number, self.threshold, self.num_players)
+ if self.id in senders:
+ # We have to wait on share_a and share_b, do a local
+ # multiplication and send shares to the others.

- exchanged_shares = []
- for peer_id, share in shares:
- d = self._exchange_shares(peer_id.value, share)
- d.addCallback(lambda share, peer_id: (peer_id, share), peer_id)
- exchanged_shares.append(d)
+ def share(number):
+ pc = tuple(self.program_counter)
+ shares = shamir.share(number, self.threshold, self.num_players)
+ received = []
+ for peer_id, field_element in shares:
+ if peer_id == self.id:
+ received.append(Share(self, field_element.field, field_element))
+ else:
+ self.protocols[peer_id.value].sendShare(pc, field_element)
+ if peer_id.value in senders:
+ received.append(self._expect_share(peer_id.value, field))
+ return received

- # Recombine the first 2t+1 shares.
- result = gather_shares(exchanged_shares[:2*self.threshold+1])
- result.addCallback(shamir.recombine)
- return result
+ result = gather_shares([share_a, share_b])
+ result.addCallback(lambda (a, b): a * b)
+ self.schedule_callback(result, share)
+ else:
+ # We simply expect 2t+1 shares from the senders.
+ received_shares = [self._expect_share(s, field) for s in senders]
+ result = gather_shares(received_shares)

- result = gather_shares([share_a, share_b])
- result.addCallback(lambda (a, b): a * b)
- self.schedule_callback(result, share_recombine)
+ # Recombine the first 2t+1 shares.
+ result.addCallback(lambda shares: zip(map(field, senders), shares))
+ result.addCallback(shamir.recombine)
return result

@increment_pc