Discussion:
[PATCH 15 of 20] importeret rettelse triple_test.patch
Janus Dam Nielsen
2009-10-06 08:10:05 UTC
Permalink
# HG changeset patch
# User Janus Dam Nielsen <***@alexandra.dk>
# Date 1254816324 -7200
# Node ID 04d228359cee302716040a5eebee38c46980a1b3
# Parent db2d970885f44d2cf18608c81f8422e87d97af8c
importeret rettelse triple_test.patch

diff --git a/viff/orlandi.py b/viff/orlandi.py
--- a/viff/orlandi.py
+++ b/viff/orlandi.py
@@ -964,7 +964,46 @@
self.schedule_callback(result, step2ab, ai, (r1, r2), alpha_randomness)
result.addErrback(self.error_handler)
return result
-
+
+ def triple_test(self, field):
+ """Generate a triple ``(a, b, c)`` where ``c = a * b``.
+
+ The triple ``(a, b, c)`` is checked against the
+ triple ``(x, y, z)`` and a random value ``r``.
+
+ """
+ triple1 = self.triple_gen(field)
+ triple2 = self.triple_gen(field)
+ r = self.open(self.random_share(field))
+
+ def check((v, oa, ob, oc, ox, oy, oz), a, b, c, ec):
+ if v is 0:
+ return None
+ return (a, b, c, ec)
+
+ def compute_value(((a, b, c, ec), (x, y, z, _), r)):
+ oa = self.open(a)
+ ob = self.open(b)
+ oc = self.open(c)
+ ox = self.open(x)
+ oy = self.open(y)
+ oz = self.open(z)
+ l = self._cmul(r, x, field)
+ m = self._cmul(r, y, field)
+ n = self._cmul(r*r, z, field)
+ d = c - self._basic_multiplication(a, b, l, m, n)
+ r = gather_shares([d, oa, ob, oc, ox, oy, oz])
+ r.addCallbacks(check, self.error_handler, callbackArgs=(a, b, c, ec))
+ return r
+
+ result = gatherResults([triple1, triple2, r])
+ self.schedule_callback(result, compute_value)
+ result.addErrback(self.error_handler)
+
+ # do actual communication
+ self.activate_reactor()
+
+ return result

def error_handler(self, ex):
print "Error: ", ex
diff --git a/viff/test/test_orlandi_runtime.py b/viff/test/test_orlandi_runtime.py
--- a/viff/test/test_orlandi_runtime.py
+++ b/viff/test/test_orlandi_runtime.py
@@ -624,3 +624,24 @@
d = gatherResults([t1, t2])
d.addCallbacks(open, runtime.error_handler)
return d
+
+
+ @protocol
+ def test_tripleTest(self, runtime):
+ """Test the triple_test command."""
+
+ self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
+
+ def check((a, b, c)):
+ self.assertEquals(c, a * b)
+
+ def open((a, b, c, _)):
+ d1 = runtime.open(a)
+ d2 = runtime.open(b)
+ d3 = runtime.open(c)
+ d = gatherResults([d1, d2, d3])
+ d.addCallback(check)
+ return d
+ d = runtime.triple_test(self.Zp)
+ d.addCallbacks(open, runtime.error_handler)
+ return d
Janus Dam Nielsen
2009-10-06 08:09:58 UTC
Permalink
# HG changeset patch
# User Janus Dam Nielsen <***@alexandra.dk>
# Date 1254816324 -7200
# Node ID bb9566f09d3faebe29cb9a689051dad7da3a61e5
# Parent 7ed324dff36bceac194528fd00f43dd572254bc8
Implementation of random share command.

diff --git a/viff/orlandi.py b/viff/orlandi.py
--- a/viff/orlandi.py
+++ b/viff/orlandi.py
@@ -269,6 +269,53 @@
if self.id in receivers:
return result

+ def random_share(self, field):
+ """Generate a random share in the field, field.
+
+ To generate a share of a random element ``r in Z_p``, party ``P_i``
+ chooses at random ``r_i, rho_ri in Z_p X (Z_p)^2`` and
+ broadcast ``C_r^i = Com_ck(r_i, rho_ri)``.
+
+ Every party computes ``C_r = PRODUCT_i=1^n C_r^i = Com_ck(r, rho_r)``,
+ where ``r_i = SUM_i=1^n r_i and rho_r = SUM_i=1^n rho_ri``.
+
+ Party ``P_i sets [r]_i = (r_i, rho_ri, C_r)``.
+
+ """
+ self.program_counter[-1] += 1
+
+ # P_i chooses at random r_i, rho_ri in Z_p x (Z_p)^2
+ ri = field(rand.randint(0, field.modulus - 1))
+ rhoi1 = field(rand.randint(0, field.modulus - 1))
+ rhoi2 = field(rand.randint(0, field.modulus - 1))
+
+ # compute C_r^i = Com_ck(r_i, rho_ri).
+ Cri = commitment.commit(ri.value, rhoi1, rhoi2)
+
+ # Broadcast C_r^i.
+ sls = gatherResults(self.broadcast(self.players.keys(), self.players.keys(), repr(Cri)))
+
+ def compute_commitment(ls):
+ Cr = ls.pop()
+ for Cri in ls:
+ Cr = Cr * Cri
+ return OrlandiShare(self, field, ri, (rhoi1, rhoi2), Cr)
+
+ def deserialize(ls):
+ return [ commitment.deserialize(x) for x in ls ]
+
+ sls.addCallbacks(deserialize, self.error_handler)
+ sls.addCallbacks(compute_commitment, self.error_handler)
+
+ s = Share(self, field)
+ # We add the result to the chains in triple.
+ sls.chainDeferred(s)
+
+ # do actual communication
+ self.activate_reactor()
+
+ return s
+
def error_handler(self, ex):
print "Error: ", ex
return ex
diff --git a/viff/runtime.py b/viff/runtime.py
--- a/viff/runtime.py
+++ b/viff/runtime.py
@@ -327,20 +327,13 @@

key = (program_counter, data_type)

-# print "Player %s has received data %s from %s with pc: %s" % (str(self.factory.runtime.id),
-# str(data),
-# str(self.peer_id),
-# str(key))
-
if key in self.waiting_deferreds:
-# print "A deferred was waiting"
deq = self.waiting_deferreds[key]
deferred = deq.popleft()
if not deq:
del self.waiting_deferreds[key]
self.factory.runtime.handle_deferred_data(deferred, data)
else:
-# print "A deferred is not waiting, lets put the data on the shelf"
deq = self.incoming_data.setdefault(key, deque())
deq.append(data)
except struct.error, e:
@@ -399,12 +392,6 @@
"""
try:
key = (program_counter, data_type)
-
-# print self
-# print "Player %s has received data %s from %s with pc: %s" % (str(self.factory.runtime.id),
-# str(data),
-# str(self.peer_id),
-# program_counter)

if key in self.waiting_deferreds:
deq = self.waiting_deferreds[key]
@@ -754,7 +741,6 @@
else:
# We have not yet received anything from the other side.
deq = self.protocols[peer_id].waiting_deferreds.setdefault(key, deque())
-# print "The deferred %s is waiting on data from %i with key: %s" % (str(deferred), peer_id, str(key))
deq.append(deferred)

def _exchange_shares(self, peer_id, field_element):
@@ -869,6 +855,7 @@
def handle_deferred_data(self, deferred, data):
"""Put deferred and data into the queue if the ViffReactor is running.
Otherwise, just execute the callback."""
+
if self.using_viff_reactor:
self.deferred_queue.append((deferred, data))
else:
diff --git a/viff/test/test_orlandi_runtime.py b/viff/test/test_orlandi_runtime.py
--- a/viff/test/test_orlandi_runtime.py
+++ b/viff/test/test_orlandi_runtime.py
@@ -71,3 +71,18 @@
d.addCallback(check)
return d

+ @protocol
+ def test_random_share(self, runtime):
+ """Test creation of a random shared number."""
+
+ self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
+
+ def check(v):
+ self.assertEquals(True, True)
+
+ x = runtime.random_share(self.Zp)
+ d = runtime.open(x)
+ d.addCallback(check)
+ return d
+
+
Janus Dam Nielsen
2009-10-06 08:10:08 UTC
Permalink
# HG changeset patch
# User Janus Dam Nielsen <***@alexandra.dk>
# Date 1254816324 -7200
# Node ID 9d6c0fe2f0d6d4b6c481842689e5d5f917512255
# Parent 2704f20bab087cc127acb0961acba98768a0123c
We skippe the tests because the commit module is not currently included in VIFF.

diff --git a/viff/test/test_orlandi_runtime.py b/viff/test/test_orlandi_runtime.py
--- a/viff/test/test_orlandi_runtime.py
+++ b/viff/test/test_orlandi_runtime.py
@@ -26,7 +26,7 @@

from viff.util import rand

-import commitment
+# import commitment


def _get_triple(runtime, field):
@@ -68,6 +68,8 @@
share.addCallback(check)
return share

+ test_secret_share.skip = "Commitment module is not included in VIFF."
+
@protocol
def test_open_secret_share(self, runtime):
"""Test sharing and open of a number."""
@@ -85,6 +87,8 @@
d.addCallback(check)
return d

+ test_open_secret_share.skip = "Commitment module is not included in VIFF."
+
@protocol
def test_random_share(self, runtime):
"""Test creation of a random shared number."""
@@ -99,6 +103,7 @@
d.addCallback(check)
return d

+ test_random_share.skip = "Commitment module is not included in VIFF."

@protocol
def test_sum(self, runtime):
@@ -127,6 +132,8 @@
d.addCallback(check)
return d

+ test_sum.skip = "Commitment module is not included in VIFF."
+
@protocol
def test_sum_plus(self, runtime):
"""Test addition of two numbers."""
@@ -154,6 +161,8 @@
d.addCallback(check)
return d

+ test_sum_plus.skip = "Commitment module is not included in VIFF."
+
@protocol
def test_sum_constant(self, runtime):
"""Test addition of two numbers."""
@@ -176,6 +185,8 @@
d.addCallback(check)
return d

+ test_sum_constant.skip = "Commitment module is not included in VIFF."
+
@protocol
def test_sub(self, runtime):
"""Test subtration of two numbers."""
@@ -203,6 +214,8 @@
d.addCallback(check)
return d

+ test_sub.skip = "Commitment module is not included in VIFF."
+
@protocol
def test_sub_minus(self, runtime):
"""Test subtration of two numbers."""
@@ -230,6 +243,8 @@
d.addCallback(check)
return d

+ test_sub_minus.skip = "Commitment module is not included in VIFF."
+
@protocol
def test_sub_constant(self, runtime):
"""Test subtration of two numbers."""
@@ -252,6 +267,7 @@
d.addCallback(check)
return d

+ test_sub_constant.skip = "Commitment module is not included in VIFF."

class OrlandiAdvancedCommandsTest(RuntimeTestCase):
"""Test for advanced commands."""
@@ -277,6 +293,8 @@
d.addCallback(check)
return d

+ test_shift.skip = "Commitment module is not included in VIFF."
+
@protocol
def test_shift_two_inputters(self, runtime):
"""Test addition of the shift command."""
@@ -293,6 +311,8 @@
d2.addCallback(check)
return DeferredList([d1, d2])

+ test_shift_two_inputters.skip = "Commitment module is not included in VIFF."
+
@protocol
def test_shift_two_consequtive_inputters(self, runtime):
"""Test addition of the shift command."""
@@ -309,6 +329,8 @@
r.addCallback(r1)
return r

+ test_shift_two_consequtive_inputters.skip = "Commitment module is not included in VIFF."
+
@protocol
def test_shift_two_consequtive_inputters2(self, runtime):
"""Test addition of the shift command."""
@@ -328,6 +350,8 @@
r.addCallback(r1)
return r

+ test_shift_two_consequtive_inputters2.skip = "Commitment module is not included in VIFF."
+
@protocol
def test_input(self, runtime):
"""Test of many uses of the input command."""
@@ -350,6 +374,8 @@
shares_ready = gather_shares(a_shares + b_shares)
return shares_ready

+ test_input.skip = "Commitment module is not included in VIFF."
+
@protocol
def test_basic_multiply(self, runtime):
"""Test multiplication of two numbers."""
@@ -371,6 +397,8 @@
d.addCallback(check)
return d

+ test_basic_multiply.skip = "Commitment module is not included in VIFF."
+
@protocol
def test_mul_mul(self, runtime):
"""Test multiplication of two numbers."""
@@ -391,6 +419,8 @@
d.addCallback(check)
return d

+ test_mul_mul.skip = "Commitment module is not included in VIFF."
+
@protocol
def test_basic_multiply_constant_right(self, runtime):
"""Test multiplication of two numbers."""
@@ -411,6 +441,8 @@
d.addCallback(check)
return d

+ test_basic_multiply_constant_right.skip = "Commitment module is not included in VIFF."
+
@protocol
def test_basic_multiply_constant_left(self, runtime):
"""Test multiplication of two numbers."""
@@ -431,6 +463,8 @@
d.addCallback(check)
return d

+ test_basic_multiply_constant_left.skip = "Commitment module is not included in VIFF."
+
@protocol
def test_constant_multiplication_constant_left(self, runtime):
"""Test multiplication of two numbers."""
@@ -450,6 +484,8 @@
d.addCallback(check)
return d

+ test_constant_multiplication_constant_left.skip = "Commitment module is not included in VIFF."
+
@protocol
def test_constant_multiplication_constant_right(self, runtime):
"""Test multiplication of two numbers."""
@@ -469,6 +505,8 @@
d.addCallback(check)
return d

+ test_constant_multiplication_constant_right.skip = "Commitment module is not included in VIFF."
+
@protocol
def test_constant_multiplication_constant_None(self, runtime):
"""Test multiplication of two numbers."""
@@ -481,6 +519,8 @@
x2 = runtime.shift([1], self.Zp, x1)
y2 = runtime.shift([1], self.Zp, y1)

+ test_constant_multiplication_constant_None.skip = "Commitment module is not included in VIFF."
+
@protocol
def test_sum_poly(self, runtime):
"""Test implementation of sum_poly."""
@@ -498,6 +538,8 @@
self.assertEquals(rho2, 29)
self.assertEquals(Cx, 29)
return x
+
+ test_sum_poly.skip = "Commitment module is not included in VIFF."

@protocol
def test_sum_poly(self, runtime):
@@ -521,6 +563,8 @@
self.assertEquals(Cx, Cf1**3 * Cf2**9 * Cf3**27)
return x

+ test_sum_poly.skip = "Commitment module is not included in VIFF."
+
@protocol
def test_delta(self, runtime):
"""Test implementation of compute_delta."""
@@ -538,6 +582,8 @@

return delta

+ test_delta.skip = "Commitment module is not included in VIFF."
+
@protocol
def test_leak_mul(self, runtime):
"""Test leaktolerant multiplication of two numbers."""
@@ -570,6 +616,7 @@
self.assertEquals(z2, None)
return z2

+ test_leak_mul.skip = "Commitment module is not included in VIFF."

class TripleGenTest(RuntimeTestCase):
"""Test for generation of triples."""
@@ -601,6 +648,8 @@
d.addCallbacks(open, runtime.error_handler)
return d

+ test_tripleGen.skip = "Commitment module is not included in VIFF."
+
@protocol
def test_tripleGen2(self, runtime):
"""Test the triple_gen command."""
@@ -627,6 +676,7 @@
d.addCallbacks(open, runtime.error_handler)
return d

+ test_tripleGen2.skip = "Commitment module is not included in VIFF."

@protocol
def test_tripleTest(self, runtime):
@@ -648,6 +698,8 @@
d.addCallbacks(open, runtime.error_handler)
return d

+ test_tripleTest.skip = "Commitment module is not included in VIFF."
+
@protocol
def test_random_triple(self, runtime):
"""Test the triple_combiner command."""
@@ -678,6 +730,8 @@
d.addCallbacks(open, runtime.error_handler)
return d

+ test_random_triple.skip = "Commitment module is not included in VIFF."
+
@protocol
def test_random_triple3_parallel(self, runtime):
"""Test the triple_combiner command."""
@@ -711,6 +765,8 @@
d.addCallbacks(open, runtime.error_handler)
return d

+ test_random_triple3_parallel.skip = "Commitment module is not included in VIFF."
+
@protocol
def test_random_triple_parallel(self, runtime):
"""Test the triple_combiner command."""
@@ -766,3 +822,5 @@

runtime.schedule_callback(shares_ready, cont)
return shares_ready
+
+ test_random_triple_parallel.skip = "Commitment module is not included in VIFF."
Janus Dam Nielsen
2009-10-06 08:09:54 UTC
Permalink
# HG changeset patch
# User Janus Dam Nielsen <***@alexandra.dk>
# Date 1254816324 -7200
# Node ID 53d198cdf14cb85d81d6e6cf1ec75a16773dfbec
# Parent 5a815629d825c6eae85cacfe821e8945a232ebcd
An implementation of a broadcast mixin based on hashing of the received messages.

diff --git a/viff/constants.py b/viff/constants.py
--- a/viff/constants.py
+++ b/viff/constants.py
@@ -25,3 +25,10 @@
READY = 2
SEND = 3
PAILLIER = 4
+TEXT = 5
+
+# Used by the HashBroadcastMixin
+INCONSISTENTHASH = 6
+OK = 7
+HASH = 8
+SIGNAL = 9
diff --git a/viff/hash_broadcast.py b/viff/hash_broadcast.py
new file mode 100644
--- /dev/null
+++ b/viff/hash_broadcast.py
@@ -0,0 +1,166 @@
+#!/usr/bin/env python
+
+# Copyright 2009 VIFF Development Team.
+#
+# This file is part of VIFF, the Virtual Ideal Functionality Framework.
+#
+# VIFF is free software: you can redistribute it and/or modify it
+# under the terms of the GNU Lesser General Public License (LGPL) as
+# published by the Free Software Foundation, either version 3 of the
+# License, or (at your option) any later version.
+#
+# VIFF is distributed in the hope that it will be useful, but WITHOUT
+# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
+# Public License for more details.
+#
+# You should have received a copy of the GNU Lesser General Public
+# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
+
+from twisted.internet.defer import gatherResults, Deferred, DeferredList
+
+from hashlib import sha1
+from viff.constants import TEXT, INCONSISTENTHASH, OK, HASH, SIGNAL
+
+error_msg = "Player %i, has received an inconsistent hash %s."
+
+class InconsistentHashException(Exception):
+ pass
+
+class HashBroadcastMixin:
+ """A non-consistent broadcast scheme mainly useful for full threshold security.
+
+ A value is send using `send_value` and when received a hash is generated and
+ exchanged among the receivers. If a receiver receives a hash which is not equal
+ to the one he generated, then he sends an error signal to the others and
+ they stop the computation. Else he sends an ok signal and the computation continues."""
+
+ def _send_message(self, pc, sender, receivers, message):
+ for peer_id in receivers:
+ self.protocols[peer_id].sendData(pc, TEXT, message)
+
+ def _receive_broadcast(self, pc, unique_pc, sender, receivers):
+ # The result.
+ result = Deferred()
+ # The message store.
+ message = []
+ # The hash store
+ g_hashes = {}
+ # The signal store
+ signals = {}
+
+ def signal_received(signal, peer_id, message, num_receivers, hashes, signals):
+ # Store the signal.
+ signals[peer_id] = long(signal)
+ # If all signals are received then check if they are OK or INCONSISTENTHASH.
+ if num_receivers == len(signals.keys()):
+ s = reduce(lambda x, y: OK if OK == y else INCONSISTENTHASH, signals.values())
+ if OK == s:
+ # Make the result ready.
+ result.callback(message[0])
+ else:
+ raise InconsistentHashException(error_msg % (self.id, hashes))
+
+ def hash_received(h, unique_pc, peer_id, receivers, a_hashes):
+ # Store the hash.
+ a_hashes[peer_id] = h
+ # If we have received a hash from everybody, then compute the signal and send it.
+ if len(receivers) == len(a_hashes.keys()):
+ signal = OK
+ # First we check if the hashes we received are equal to the hash we computed ourselves.
+ for peer_id in receivers:
+ signal = signal if a_hashes[peer_id] == a_hashes[self.id] else INCONSISTENTHASH
+ # Then we send the SAME signal to everybody.
+ for peer_id in receivers:
+ self.protocols[peer_id].sendData(unique_pc, SIGNAL, str(signal))
+ # The return value does not matter.
+ return None
+
+ def message_received(m, unique_pc, message, receivers, hashes):
+ # Store the message.
+ message.append(m)
+ # Compute hash of message.
+ h = sha1(m).hexdigest()
+ # Store hash.
+ hashes[self.id] = h
+ # Send the hash to all receivers.
+ for peer_id in receivers:
+ self.protocols[peer_id].sendData(unique_pc, HASH, str(h))
+
+ # Set up receivers for hashes and signals.
+ # Note, we use the unique_pc to avoid data to cross method invocation boundaries.
+ for peer_id in receivers:
+ d_hash = Deferred().addCallbacks(hash_received,
+ self.error_handler,
+ callbackArgs=(unique_pc, peer_id, receivers, g_hashes))
+ self._expect_data_with_pc(unique_pc, peer_id, HASH, d_hash)
+ d_signal = Deferred().addCallbacks(signal_received,
+ self.error_handler,
+ callbackArgs=(peer_id, message, len(receivers), g_hashes, signals))
+ self._expect_data_with_pc(unique_pc, peer_id, SIGNAL, d_signal)
+
+ # Set up receiving of the message.
+ d_message = Deferred().addCallbacks(message_received,
+ self.error_handler,
+ callbackArgs=(unique_pc, message, receivers, g_hashes))
+ self._expect_data(sender, TEXT, d_message)
+ return result
+
+
+ def broadcast(self, senders, receivers, message=None):
+ """Broadcast the messeage from senders to receivers.
+
+ Returns a list of deferreds if the calling player is among
+ the receivers and there are multiple senders.
+ Returns a single element if there is only on sender, or the
+ calling player is among the senders only.
+
+ The order of the resulting list is guaranteed to be the same order
+ as the list of senders.
+
+ Senders and receivers should be lists containing the id of the senders
+ and receivers, respectively.
+
+ Note: You send implicitly to your self."""
+ assert message is None or self.id in senders
+
+ self.program_counter[-1] += 1
+
+ pc = tuple(self.program_counter)
+ if (self.id in receivers or self.id in senders):
+ results = [None] * len(senders)
+ else:
+ results = []
+
+ if self.id in senders:
+ self._send_message(pc, self.id, receivers, message)
+
+ if self.id in receivers:
+ for x in xrange(len(senders)):
+ sender = senders[x]
+ new_pc = list(self.program_counter)
+ new_pc.append(x)
+ results[x] = self._receive_broadcast(pc, tuple(new_pc), sender, receivers)
+
+ if self.id in senders and self.id not in receivers:
+ d = Deferred()
+ d.callback(message)
+ results = [d]
+
+ self.program_counter[-1] += 1
+
+ if len(results) == 1:
+ return results[0]
+
+ return results
+
+ def list_str(self, s):
+ ls = []
+ for x in s[1:-1].split(','):
+ x = x.strip()
+ ls.append(str(x)[1:-1])
+ return ls
+
+ def error_handler(self, ex):
+ print "Error: ", ex
+ return ex
diff --git a/viff/test/test_hash_broadcast.py b/viff/test/test_hash_broadcast.py
new file mode 100644
--- /dev/null
+++ b/viff/test/test_hash_broadcast.py
@@ -0,0 +1,181 @@
+# Copyright 2009 VIFF Development Team.
+#
+# This file is part of VIFF, the Virtual Ideal Functionality Framework.
+#
+# VIFF is free software: you can redistribute it and/or modify it
+# under the terms of the GNU Lesser General Public License (LGPL) as
+# published by the Free Software Foundation, either version 3 of the
+# License, or (at your option) any later version.
+#
+# VIFF is distributed in the hope that it will be useful, but WITHOUT
+# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
+# Public License for more details.
+#
+# You should have received a copy of the GNU Lesser General Public
+# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
+
+from twisted.internet.defer import gatherResults, Deferred, DeferredList
+
+from viff.test.util import RuntimeTestCase, protocol
+from viff.field import GF
+from viff.runtime import Share
+
+from viff.comparison import Toft05Runtime
+from viff.hash_broadcast import HashBroadcastMixin
+
+class BroadcastRuntime(Toft05Runtime, HashBroadcastMixin):
+ """Mix of :class:`Toft05Runtime` and
+ :class:`HashBroadcastRuntime`."""
+ pass
+
+class HashBroadcastTest(RuntimeTestCase):
+ """Test for the hash broadcast mixin."""
+
+ # Number of players.
+ num_players = 3
+
+ runtime_class = BroadcastRuntime
+
+ timeout = 10
+ @protocol
+ def test_send(self, runtime):
+ """Test of send a value."""
+ self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
+
+ value = 42
+
+ receivers = [2, 3]
+ if 1 == runtime.id:
+ d = runtime.broadcast([1], receivers, str(value))
+ else:
+ d = runtime.broadcast([1], receivers)
+ def check(x):
+ self.assertEquals(int(x), 42)
+ d.addCallback(check)
+ return d
+
+
+ @protocol
+ def test_send_two_senders_in_parallel(self, runtime):
+ """Test of send a value."""
+ self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
+
+ def check(ls):
+ for s, x in ls:
+ self.assertEquals(int(x), 42)
+ return ls
+
+ value = 42
+
+ receivers = [2, 3]
+ if 1 == runtime.id:
+ d1 = runtime.broadcast([1], receivers, str(value))
+ else:
+ d1 = runtime.broadcast([1], receivers)
+
+ if 2 == runtime.id:
+ d2 = runtime.broadcast([2], [3], str(value))
+ else:
+ d2 = runtime.broadcast([2], [3])
+
+ ds = [d1]
+ if [] != d2:
+ ds.append(d2)
+ dls = DeferredList(ds)
+ dls.addCallback(check)
+ return dls
+
+ @protocol
+ def test_send_multiple_senders_in_one_burst(self, runtime):
+ """Test of send a value."""
+ self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
+
+ value = 42
+ if 1 == runtime.id:
+ value = 7
+
+ if 1 == runtime.id or 3 == runtime.id:
+ ds = runtime.broadcast([1, 3], [2], str(value))
+
+ if 2 == runtime.id:
+ ds = runtime.broadcast([1, 3], [2])
+ dls = DeferredList(ds)
+ def check(ls):
+ self.assertEquals(int(ls[0][1]), 7)
+ self.assertEquals(int(ls[1][1]), 42)
+ return ls
+ dls.addCallback(check)
+ return dls
+ return None
+
+
+ @protocol
+ def test_sender_in_receivers(self, runtime):
+ """Test of send a value."""
+ self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
+
+ value = 42
+ if 1 == runtime.id:
+ d = runtime.broadcast([1], [1, 2, 3], str(value))
+ else:
+ d = runtime.broadcast([1], [1, 2, 3])
+
+ def check(x):
+ self.assertEquals(int(x), 42)
+ return x
+ d.addCallback(check)
+ return d
+
+ @protocol
+ def test_complex(self, runtime):
+ def check(ls):
+ for x, v in ls:
+ self.assertEquals(runtime.list_str(v), ['7', '9', '13'])
+
+ receivers = [1, 2, 3]
+ def exchange((xi, rhoi1, rhoi2)):
+ # Send share to all receivers.
+ ds = runtime.broadcast(receivers, receivers, str((str(xi), str(rhoi1), str(rhoi2))))
+ dls = DeferredList(ds)
+ dls.addCallbacks(check, runtime.error_handler)
+ return dls
+
+ result = Deferred()
+ result.addCallbacks(exchange, runtime.error_handler)
+ result.callback((7, 9, 13))
+ return result
+
+ @protocol
+ def test_complex2(self, runtime):
+ def check(ls):
+ if (2 == runtime.id) or (1 == runtime.id):
+ self.assertEquals(ls[0][1], "V1")
+ self.assertEquals(ls[1][1], "V1")
+ self.assertEquals(ls[2][1], "V1")
+ self.assertEquals(ls[3][1], "V2")
+ else:
+ self.assertEquals(ls[0][1], "V1")
+ self.assertEquals(ls[1][1], "V1")
+ self.assertEquals(ls[2][1], "V1")
+ self.assertEquals(ls[3][1], "V2")
+ self.assertEquals(ls[4][1], "V2")
+ field = self.Zp
+ results = []
+ results += runtime.broadcast(runtime.players.keys(), runtime.players.keys(), "V1")
+ if runtime.id in [1, 2]:
+ v = runtime.broadcast([1, 2], [3], "V2")
+ if isinstance(v, list):
+ results += v
+ else:
+ results.append(v)
+ else:
+ results += runtime.broadcast([1, 2], [3])
+ if 3 == runtime.id:
+ results += [runtime.broadcast([3], runtime.players.keys(), str(7))]
+ else:
+ results += [runtime.broadcast([3], runtime.players.keys())]
+ dls = DeferredList(results)
+ runtime.schedule_callback(dls, check)
+ dls.addErrback(runtime.error_handler)
+ return dls
Janus Dam Nielsen
2009-10-06 08:09:59 UTC
Permalink
# HG changeset patch
# User Janus Dam Nielsen <***@alexandra.dk>
# Date 1254816324 -7200
# Node ID 94086392cb3c34db1672660c9711cbd4941c991f
# Parent bb9566f09d3faebe29cb9a689051dad7da3a61e5
Implementation of addition command.

diff --git a/viff/orlandi.py b/viff/orlandi.py
--- a/viff/orlandi.py
+++ b/viff/orlandi.py
@@ -20,6 +20,7 @@
from viff.runtime import Runtime, Share, ShareList, gather_shares
from viff.util import rand
from viff.constants import TEXT
+from viff.field import FieldElement

from hash_broadcast import HashBroadcastMixin

@@ -315,6 +316,69 @@
self.activate_reactor()

return s
+
+ def add(self, share_a, share_b):
+ """Addition of shares.
+
+ Communication cost: none.
+
+ Each party ``P_i`` computes:
+ ``[z]_i = [x]_i + [y]_i
+ = (x_i + y_i mod p, rho_xi + rho_yi mod p, C_x * C_y)``.
+
+ """
+ def is_share(s, field):
+ if not isinstance(s, Share):
+ if not isinstance(s, FieldElement):
+ s = field(s)
+ (v, rhov, Cv) = self._additive_constant(field(0), s)
+ return OrlandiShare(self, field, v, rhov, Cv)
+ return s
+
+ # Either share_a or share_b must have an attribute called "field".
+ field = getattr(share_a, "field", getattr(share_b, "field", None))
+
+ share_a = is_share(share_a, field)
+ share_b = is_share(share_b, field)
+
+ # Add rho_xi and rho_yi and compute the commitment.
+ def compute_sums((x, y)):
+ (zi, (rhozi1, rhozi2), Cz) = self._plus(x, y)
+ return OrlandiShare(self, field, zi, (rhozi1, rhozi2), Cz)
+
+ result = gather_shares([share_a, share_b])
+ result.addCallbacks(compute_sums, self.error_handler)
+ return result
+
+ def _additive_constant(self, zero, field_element):
+ """Greate an additive constant.
+
+ Any additive constant can be interpreted as:
+ ``[c]_1 = (c, 0, Com_ck(c,0))`` and
+ ``[c]_i = (0, 0, Com_ck(c,0)) for i != 1``.
+ """
+ v = zero
+ if self.id == 1:
+ v = field_element
+ Cx = commitment.commit(field_element.value, zero.value, zero.value)
+ return (v, (zero, zero), Cx)
+
+ def _plus(self, x, y):
+ """Addition of share-tuples *x* and *y*.
+
+ Each party ``P_i`` computes:
+ ``[x]_i = (x_i, rho_xi, C_x)``
+ ``[y]_i = (y_i, rho_yi, C_y)``
+ ``[z]_i = [x]_i + [y]_i
+ = (x_i + y_i mod p, rho_xi + rho_yi mod p, C_x * C_y)``.
+ """
+ (xi, (rhoxi1, rhoxi2), Cx) = x
+ (yi, (rhoyi1, rhoyi2), Cy) = y
+ zi = xi + yi
+ rhozi1 = rhoxi1 + rhoyi1
+ rhozi2 = rhoxi2 + rhoyi2
+ Cz = Cx * Cy
+ return (zi, (rhozi1, rhozi2), Cz)

def error_handler(self, ex):
print "Error: ", ex
diff --git a/viff/test/test_orlandi_runtime.py b/viff/test/test_orlandi_runtime.py
--- a/viff/test/test_orlandi_runtime.py
+++ b/viff/test/test_orlandi_runtime.py
@@ -75,7 +75,7 @@
def test_random_share(self, runtime):
"""Test creation of a random shared number."""

- self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
+ self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)

def check(v):
self.assertEquals(True, True)
@@ -86,3 +86,78 @@
return d


+ @protocol
+ def test_sum(self, runtime):
+ """Test addition of two numbers."""
+
+ self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
+
+ x1 = 42
+ y1 = 7
+
+ def check(v):
+ self.assertEquals(v, x1 + y1)
+
+ if 1 == runtime.id:
+ x2 = runtime.secret_share([1], self.Zp, x1)
+ else:
+ x2 = runtime.secret_share([1], self.Zp)
+
+ if 3 == runtime.id:
+ y2 = runtime.secret_share([3], self.Zp, y1)
+ else:
+ y2 = runtime.secret_share([3], self.Zp)
+
+ z2 = runtime.add(x2, y2)
+ d = runtime.open(z2)
+ d.addCallback(check)
+ return d
+
+ @protocol
+ def test_sum_plus(self, runtime):
+ """Test addition of two numbers."""
+
+ self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
+
+ x1 = 42
+ y1 = 7
+
+ def check(v):
+ self.assertEquals(v, x1 + y1)
+
+ if 1 == runtime.id:
+ x2 = runtime.secret_share([1], self.Zp, x1)
+ else:
+ x2 = runtime.secret_share([1], self.Zp)
+
+ if 3 == runtime.id:
+ y2 = runtime.secret_share([3], self.Zp, y1)
+ else:
+ y2 = runtime.secret_share([3], self.Zp)
+
+ z2 = x2 + y2
+ d = runtime.open(z2)
+ d.addCallback(check)
+ return d
+
+ @protocol
+ def test_sum_constant(self, runtime):
+ """Test addition of two numbers."""
+
+ self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
+
+ x1 = 42
+ y1 = 7
+
+ def check(v):
+ self.assertEquals(v, x1 + y1)
+
+ if 1 == runtime.id:
+ x2 = runtime.secret_share([1], self.Zp, x1)
+ else:
+ x2 = runtime.secret_share([1], self.Zp)
+
+ z2 = x2 + y1
+ d = runtime.open(z2)
+ d.addCallback(check)
+ return d
Janus Dam Nielsen
2009-10-06 08:09:57 UTC
Permalink
# HG changeset patch
# User Janus Dam Nielsen <***@alexandra.dk>
# Date 1254816324 -7200
# Node ID 7ed324dff36bceac194528fd00f43dd572254bc8
# Parent 42d95e56edf626b2a2c8535e5bfbe856a1e82a3b
Implementation of the open command.

diff --git a/viff/orlandi.py b/viff/orlandi.py
--- a/viff/orlandi.py
+++ b/viff/orlandi.py
@@ -15,12 +15,14 @@
# You should have received a copy of the GNU Lesser General Public
# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.

-from twisted.internet.defer import Deferred
+from twisted.internet.defer import Deferred, gatherResults

from viff.runtime import Runtime, Share, ShareList, gather_shares
from viff.util import rand
from viff.constants import TEXT

+from hash_broadcast import HashBroadcastMixin
+
import commitment
commitment.set_reference_string(23434347834783478783478L, 489237823478234783478020L)

@@ -54,7 +56,7 @@
Share.__init__(self, runtime, field, (value, rho, commitment))


-class OrlandiRuntime(Runtime):
+class OrlandiRuntime(Runtime, HashBroadcastMixin):
"""The Orlandi runtime.

The runtime is used for sharing values (:meth:`secret_share` or
@@ -113,6 +115,27 @@
sls.addCallbacks(combine, self.error_handler)
return sls

+ def _expect_orlandi_share_xi_rhoi(self, peer_id, field):
+ xi = self._expect_share(peer_id, field)
+ rhoi1 = self._expect_share(peer_id, field)
+ rhoi2 = self._expect_share(peer_id, field)
+ sls = ShareList([xi, rhoi1, rhoi2])
+ def combine(ls):
+ expected_num = 3;
+ if len(ls) is not expected_num:
+ raise OrlandiException("Cannot share number, trying to create a share,"
+ " expected %s components got %s." % (expected_num, len(ls)))
+
+ s1, xi = ls[0]
+ s2, rhoi1 = ls[1]
+ s3, rhoi2 = ls[2]
+ if not (s1 and s2 and s3):
+ raise OrlandiException("Cannot share number, trying to create share "
+ "but a component did arrive properly.")
+ return OrlandiShare(self, field, xi, (rhoi1, rhoi2))
+ sls.addCallbacks(combine, self.error_handler)
+ return sls
+
def secret_share(self, inputters, field, number=None, threshold=None):
"""Share the value, number, among all the parties using additive shareing.

@@ -186,6 +209,66 @@
return results[0]
return results

+ def open(self, share, receivers=None, threshold=None):
+ """Share reconstruction.
+
+ Every partyi broadcasts a share pair ``(x_i', rho_x,i')``.
+
+ The parties compute the sums ``x'``, ``rho_x'`` and
+ check ``Com_ck(x',rho_x' = C_x``.
+
+ If yes, return ``x = x'``, else else return :const:`None`.
+ """
+ assert isinstance(share, Share)
+ # all players receive result by default
+ if receivers is None:
+ receivers = self.players.keys()
+ assert threshold is None
+ threshold = self.num_players - 1
+
+ field = share.field
+
+ self.program_counter[-1] += 1
+
+ def recombine_value(shares, Cx):
+ x = 0
+ rho1 = 0
+ rho2 = 0
+ for xi, rhoi1, rhoi2 in shares:
+ x += xi
+ rho1 += rhoi1
+ rho2 += rhoi2
+ Cx1 = commitment.commit(x.value, rho1.value, rho2.value)
+ if Cx1 == Cx:
+ return x
+ else:
+ raise OrlandiException("Wrong commitment for value %s, found %s expected %s." %
+ (x, Cx1, Cx))
+
+ def deserialize(ls):
+ shares = [(field(long(x)), field(long(rho1)), field(long(rho2))) for x, rho1, rho2 in map(self.list_str, ls)]
+ return shares
+
+ def exchange((xi, (rhoi1, rhoi2), Cx), receivers):
+ # Send share to all receivers.
+ ds = self.broadcast(self.players.keys(), receivers, str((str(xi.value), str(rhoi1.value), str(rhoi2.value))))
+
+ if self.id in receivers:
+ result = gatherResults(ds)
+ result.addCallbacks(deserialize, self.error_handler)
+ result.addCallbacks(recombine_value, self.error_handler, callbackArgs=(Cx,))
+ return result
+
+ result = share.clone()
+ self.schedule_callback(result, exchange, receivers)
+ result.addErrback(self.error_handler)
+
+ # do actual communication
+ self.activate_reactor()
+
+ if self.id in receivers:
+ return result
+
def error_handler(self, ex):
print "Error: ", ex
return ex
diff --git a/viff/runtime.py b/viff/runtime.py
--- a/viff/runtime.py
+++ b/viff/runtime.py
@@ -327,13 +327,20 @@

key = (program_counter, data_type)

+# print "Player %s has received data %s from %s with pc: %s" % (str(self.factory.runtime.id),
+# str(data),
+# str(self.peer_id),
+# str(key))
+
if key in self.waiting_deferreds:
+# print "A deferred was waiting"
deq = self.waiting_deferreds[key]
deferred = deq.popleft()
if not deq:
del self.waiting_deferreds[key]
self.factory.runtime.handle_deferred_data(deferred, data)
else:
+# print "A deferred is not waiting, lets put the data on the shelf"
deq = self.incoming_data.setdefault(key, deque())
deq.append(data)
except struct.error, e:
@@ -392,7 +399,13 @@
"""
try:
key = (program_counter, data_type)
-
+
+# print self
+# print "Player %s has received data %s from %s with pc: %s" % (str(self.factory.runtime.id),
+# str(data),
+# str(self.peer_id),
+# program_counter)
+
if key in self.waiting_deferreds:
deq = self.waiting_deferreds[key]
deferred = deq.popleft()
@@ -741,6 +754,7 @@
else:
# We have not yet received anything from the other side.
deq = self.protocols[peer_id].waiting_deferreds.setdefault(key, deque())
+# print "The deferred %s is waiting on data from %i with key: %s" % (str(deferred), peer_id, str(key))
deq.append(deferred)

def _exchange_shares(self, peer_id, field_element):
@@ -855,7 +869,6 @@
def handle_deferred_data(self, deferred, data):
"""Put deferred and data into the queue if the ViffReactor is running.
Otherwise, just execute the callback."""
-
if self.using_viff_reactor:
self.deferred_queue.append((deferred, data))
else:
diff --git a/viff/test/test_orlandi_runtime.py b/viff/test/test_orlandi_runtime.py
--- a/viff/test/test_orlandi_runtime.py
+++ b/viff/test/test_orlandi_runtime.py
@@ -53,3 +53,21 @@
share = runtime.secret_share([1], self.Zp)
share.addCallback(check)
return share
+
+ @protocol
+ def test_open_secret_share(self, runtime):
+ """Test sharing and open of a number."""
+
+ self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
+
+ def check(v):
+ self.assertEquals(v, 42)
+
+ if 1 == runtime.id:
+ x = runtime.secret_share([1], self.Zp, 42)
+ else:
+ x = runtime.secret_share([1], self.Zp)
+ d = runtime.open(x)
+ d.addCallback(check)
+ return d
+
Janus Dam Nielsen
2009-10-06 08:10:09 UTC
Permalink
# HG changeset patch
# User Janus Dam Nielsen <***@alexandra.dk>
# Date 1254816324 -7200
# Node ID 2dabe8c91e557603cbfeb84d39f892f6bf4e773f
# Parent 9d6c0fe2f0d6d4b6c481842689e5d5f917512255
Refactored options to be more generic in terms of supported runtimes and mixins.

diff --git a/apps/benchmark.py b/apps/benchmark.py
--- a/apps/benchmark.py
+++ b/apps/benchmark.py
@@ -94,18 +94,30 @@
print "Time per %s operation: %.0f ms" % (what, 1000*(stop-start) / count)
print "*" * 6

+operations = {"mul": (operator.mul,[]),
+ "compToft05": (operator.ge, [ComparisonToft05Mixin]),
+ "compToft07": (operator.ge, [ComparisonToft07Mixin]),
+ "eq": (operator.eq, [ProbabilisticEqualityMixin])}

-operations = ["mul", "compToft05", "compToft07", "eq"]
+runtimes = {"PassiveRuntime": PassiveRuntime,
+ "PaillierRuntime": PaillierRuntime,
+ "BasicActiveRuntime": BasicActiveRuntime}
+
+mixins = {"TriplesHyperinvertibleMatricesMixin" : TriplesHyperinvertibleMatricesMixin,
+ "TriplesPRSSMixin": TriplesPRSSMixin,
+ "ComparisonToft05Mixin": ComparisonToft05Mixin,
+ "ComparisonToft07Mixin": ComparisonToft07Mixin,
+ "ProbabilisticEqualityMixin": ProbabilisticEqualityMixin}

parser = OptionParser(usage="Usage: %prog [options] config_file")
parser.add_option("-m", "--modulus",
help="lower limit for modulus (can be an expression)")
-parser.add_option("-a", "--active", action="store_true",
- help="use actively secure runtime")
-parser.add_option("--passive", action="store_false", dest="active",
- help="use passively secure runtime")
-parser.add_option("-2", "--twoplayer", action="store_true",
- help="use twoplayer runtime")
+parser.add_option("-r", "--runtime", type="choice", choices=runtimes.keys(),
+ help="the name of the basic runtime to test")
+parser.add_option("-n", "--num_players", action="store_true", dest="num_players",
+ help="number of players")
+parser.add_option("--mixins", type="choice", choices=mixins.keys(),
+ help="operation to benchmark")
parser.add_option("--prss", action="store_true",
help="use PRSS for preprocessing")
parser.add_option("--hyper", action="store_false", dest="prss",
@@ -114,7 +126,7 @@
help="corruption threshold")
parser.add_option("-c", "--count", type="int",
help="number of operations")
-parser.add_option("-o", "--operation", type="choice", choices=operations,
+parser.add_option("-o", "--operation", type="choice", choices=operations.keys(),
help="operation to benchmark")
parser.add_option("-p", "--parallel", action="store_true",
help="execute operations in parallel")
@@ -122,10 +134,12 @@
help="execute operations in sequence")
parser.add_option("-f", "--fake", action="store_true",
help="skip local computations using fake field elements")
+parser.add_option("--args", type="string",
+ help="additional arguments to the runtime, the format is a comma separated list of id=value pairs e.g. --args s=1,d=0,lambda=1")

parser.set_defaults(modulus=2**65, threshold=1, count=10,
- active=False, twoplayer=False, prss=True,
- operation=operations[0], parallel=True, fake=False)
+ runtime=runtimes.keys()[0], mixins=mixins.keys(), num_players=2, prss=True,
+ operation=operations.keys()[0], parallel=True, fake=False)

# Add standard VIFF options.
Runtime.add_options(parser)
@@ -285,41 +299,26 @@
record_stop(None, "sequential test")
self.finished(None)

-mixins = []
-if options.twoplayer:
- # Then there is just one possible runtime:
- operation = operator.mul
- base_runtime_class = PaillierRuntime
-else:
- # There are several options for a multiplayer runtime:
- if options.active:
- base_runtime_class = BasicActiveRuntime
- if options.prss:
- mixins.append(TriplesPRSSMixin)
- else:
- mixins.append(TriplesHyperinvertibleMatricesMixin)
- else:
- base_runtime_class = PassiveRuntime
+# Identify the base runtime class.
+base_runtime_class = runtimes[options.runtime]

- if options.operation == "mul":
- operation = operator.mul
- elif options.operation == "compToft05":
- operation = operator.ge
- mixins.append(ComparisonToft05Mixin)
- elif options.operation == "compToft07":
- operation = operator.ge
- mixins.append(ComparisonToft07Mixin)
- elif options.operation == "eq":
- operation = operator.eq
- mixins.append(ProbabilisticEqualityMixin)
+# Identify the additional mixins.
+actual_mixins = []
+if options.mixins != "":
+ actual_mixins = [mixins[mixin] for mixin in options.mixins.split(',')]
+
+
+# Identify the operation and it mixin dependencies.
+operation = operations[options.operation][0]
+actual_mixins += operations[options.operation][1]

print "Using the base runtime: %s." % base_runtime_class
-if mixins:
+if actual_mixins:
print "With the following mixins:"
- for mixin in mixins:
+ for mixin in actual_mixins:
print "- %s" % mixin

-runtime_class = make_runtime_class(base_runtime_class, mixins)
+runtime_class = make_runtime_class(base_runtime_class, actual_mixins)

if options.parallel:
benchmark = ParallelBenchmark
@@ -328,6 +327,19 @@

pre_runtime = create_runtime(id, players, options.threshold,
options, runtime_class)
+
+def update_args(runtime, options):
+ args = {}
+ if options.args != "":
+ for arg in options.args.split(','):
+ id, value = arg.split('=')
+ args[id] = long(value)
+ runtime.setArgs(args)
+ return runtime
+
+
+pre_runtime.addCallback(update_args, options)
+
pre_runtime.addCallback(benchmark, operation)

print "#### Starting reactor ###"
Janus Dam Nielsen
2009-10-06 08:09:53 UTC
Permalink
# HG changeset patch
# User Janus Dam Nielsen <***@alexandra.dk>
# Date 1254816324 -7200
# Node ID 5a815629d825c6eae85cacfe821e8945a232ebcd
# Parent 8a5eb65501118b57550a57504450ea6ae406d077
Added method for expecting data on the network using a specified programcounter.

diff --git a/viff/runtime.py b/viff/runtime.py
--- a/viff/runtime.py
+++ b/viff/runtime.py
@@ -726,6 +726,9 @@
# Convert self.program_counter to a hashable value in order to
# use it as a key in self.protocols[peer_id].incoming_data.
pc = tuple(self.program_counter)
+ return self._expect_data_with_pc(pc, peer_id, data_type, deferred)
+
+ def _expect_data_with_pc(self, pc, peer_id, data_type, deferred):
key = (pc, data_type)

if key in self.protocols[peer_id].incoming_data:
Janus Dam Nielsen
2009-10-06 08:09:51 UTC
Permalink
# HG changeset patch
# User Janus Dam Nielsen <***@alexandra.dk>
# Date 1254816260 -7200
# Node ID c43b0e520aba3d9c7de29e494e0ff16d0f66cd37
# Parent 80125f56beaa186cda5d520c6f4b04da598e71bb
It is now possible to send data to your self.

The sendData and _expect_data primitives now accepts and transmits data send from a player to himself.

diff --git a/viff/runtime.py b/viff/runtime.py
--- a/viff/runtime.py
+++ b/viff/runtime.py
@@ -382,6 +382,65 @@
"""Disconnect this protocol instance."""
self.transport.loseConnection()

+class SelfShareExchanger(ShareExchanger):
+
+ def __init__(self, id, factory):
+ ShareExchanger.__init__(self)
+ self.peer_id = id
+ self.factory = factory
+
+ def stringReceived(self, program_counter, data_type, data):
+ """Called when a share is received.
+
+ The string received is unpacked into the program counter, and
+ a data part. The data is passed the appropriate Deferred in
+ :class:`self.incoming_data`.
+ """
+ try:
+ key = (program_counter, data_type)
+
+ if key in self.waiting_deferreds:
+ deq = self.waiting_deferreds[key]
+ deferred = deq.popleft()
+ if not deq:
+ del self.waiting_deferreds[key]
+ self.factory.runtime.handle_deferred_data(deferred, data)
+ else:
+ deq = self.incoming_data.setdefault(key, deque())
+ deq.append(data)
+ except struct.error, e:
+ self.factory.runtime.abort(self, e)
+
+ def sendData(self, program_counter, data_type, data):
+ """Send data to the self.id."""
+ self.stringReceived(program_counter, data_type, data)
+
+ def loseConnection(self):
+ """Disconnect this protocol instance."""
+ self.lost_connection.callback(self)
+ return None
+
+
+class SelfShareExchangerFactory(ReconnectingClientFactory, ServerFactory):
+ """Factory for creating SelfShareExchanger protocols."""
+
+ protocol = SelfShareExchanger
+ maxDelay = 3
+ factor = 1.234567 # About half of the Twisted default
+
+ def __init__(self, runtime):
+ """Initialize the factory."""
+ self.runtime = runtime
+
+ def identify_peer(self, protocol):
+ raise Exception("Is identify_peer necessary?")
+
+ def clientConnectionLost(self, connector, reason):
+ reason.trap(ConnectionDone)
+
+class FakeTransport(object):
+ def close(self):
+ return True

class ShareExchangerFactory(ReconnectingClientFactory, ServerFactory):
"""Factory for creating ShareExchanger protocols."""
@@ -535,7 +594,9 @@
self.players = {}
# Add ourselves, but with no protocol since we wont be
# communicating with ourselves.
- self.add_player(player, None)
+ protocol = SelfShareExchanger(self.id, SelfShareExchangerFactory(self))
+ protocol.transport = FakeTransport()
+ self.add_player(player, protocol)

#: Queue of deferreds and data.
self.deferred_queue = deque()
@@ -551,9 +612,7 @@
def add_player(self, player, protocol):
self.players[player.id] = player
self.num_players = len(self.players)
- # There is no protocol for ourselves, so we wont add that:
- if protocol is not None:
- self.protocols[player.id] = protocol
+ self.protocols[player.id] = protocol

def shutdown(self):
"""Shutdown the runtime.
@@ -670,7 +729,6 @@
return result

def _expect_data(self, peer_id, data_type, deferred):
- assert peer_id != self.id, "Do not expect data from yourself!"
# Convert self.program_counter to a hashable value in order to
# use it as a key in self.protocols[peer_id].incoming_data.
pc = tuple(self.program_counter)
diff --git a/viff/test/test_runtime.py b/viff/test/test_runtime.py
--- a/viff/test/test_runtime.py
+++ b/viff/test/test_runtime.py
@@ -27,10 +27,10 @@
from random import Random
import operator

-from twisted.internet.defer import gatherResults
+from twisted.internet.defer import gatherResults, Deferred, DeferredList

from viff.field import GF256
-from viff.runtime import Share
+from viff.runtime import Share, SHARE
from viff.comparison import Toft05Runtime
from viff.test.util import RuntimeTestCase, BinaryOperatorTestCase, protocol

@@ -191,6 +191,49 @@

return gatherResults([opened_a, opened_b, opened_c])

+ @protocol
+ def test_send_receive_self(self, runtime):
+ """Test send and receive of values."""
+ value = 42
+
+ pc = tuple(runtime.program_counter)
+ runtime.protocols[runtime.id].sendData(pc, SHARE, str(value))
+
+ d = Deferred()
+ runtime._expect_data(runtime.id, SHARE, d)
+ def check(x):
+ self.assertEquals(int(x), value)
+ return x
+ d.addCallback(check)
+ return d
+
+ @protocol
+ def test_send_receive_self2(self, runtime):
+ """Test send and receive of values."""
+ value = 42
+
+ pc = tuple(runtime.program_counter)
+ for peer_id in runtime.players:
+ data = str(value)
+ runtime.protocols[peer_id].sendData(pc, SHARE, data)
+
+ ds = []
+ for peer_id in runtime.players:
+ d = Deferred()
+ runtime._expect_data(peer_id, SHARE, d)
+ ds.append(d)
+
+ dls = DeferredList(ds)
+ def check(ls):
+ for s, x in ls:
+ self.assertEquals(int(x), value)
+ return ls
+
+ dls.addCallback(check)
+ return dls
+
+
+

class ConvertBitShareTest(RuntimeTestCase):
runtime_class = Toft05Runtime
diff --git a/viff/test/util.py b/viff/test/util.py
--- a/viff/test/util.py
+++ b/viff/test/util.py
@@ -22,7 +22,7 @@
from twisted.internet import reactor

from viff.passive import PassiveRuntime
-from viff.runtime import Share, ShareExchanger, ShareExchangerFactory
+from viff.runtime import Share, ShareExchanger, ShareExchangerFactory, SelfShareExchanger, SelfShareExchangerFactory, FakeTransport
from viff.field import GF
from viff.config import generate_configs, load_config
from viff.util import rand
@@ -220,7 +220,13 @@
# fire.
sentinel = loopbackAsync(server, client)
self.close_sentinels.append(sentinel)
-
+ else:
+ protocol = SelfShareExchanger(id, SelfShareExchangerFactory(runtime))
+ protocol.transport = FakeTransport()
+ # Keys for when we are the client and when we are the server.
+ server_key = (id, id)
+ # Store a protocol used when we are the server.
+ self.protocols[server_key] = protocol

class BinaryOperatorTestCase:
"""Test a binary operator.
Janus Dam Nielsen
2009-10-06 08:10:00 UTC
Permalink
# HG changeset patch
# User Janus Dam Nielsen <***@alexandra.dk>
# Date 1254816324 -7200
# Node ID 5636b02c6beffac287fc05f62b87b3b03c01e116
# Parent 94086392cb3c34db1672660c9711cbd4941c991f
Implementation of subtraction command.

diff --git a/viff/orlandi.py b/viff/orlandi.py
--- a/viff/orlandi.py
+++ b/viff/orlandi.py
@@ -350,6 +350,39 @@
result.addCallbacks(compute_sums, self.error_handler)
return result

+ def sub(self, share_a, share_b):
+ """Subtraction of shares.
+
+ Communication cost: none.
+
+ Each party ``P_i`` computes:
+ ``[z]_i = [x]_i - [y]_i
+ = (x_i - y_i mod p, rho_x,i - rho_y,i mod p, C_x * C_y)``.
+
+ """
+ def is_share(s, field):
+ if not isinstance(s, Share):
+ if not isinstance(s, FieldElement):
+ s = field(s)
+ (v, rhov, Cv) = self._additive_constant(field(0), s)
+ return OrlandiShare(self, field, v, rhov, Cv)
+ return s
+
+ # Either share_a or share_b must have an attribute called "field".
+ field = getattr(share_a, "field", getattr(share_b, "field", None))
+
+ share_a = is_share(share_a, field)
+ share_b = is_share(share_b, field)
+
+ # Subtract xi and yi, rhoxi and rhoyi, and compute the commitment
+ def compute_subs((x, y)):
+ zi, (rhozi1, rhozi2), Cz = self._minus(x, y)
+ return OrlandiShare(self, field, zi, (rhozi1, rhozi2), Cz)
+
+ result = gather_shares([share_a, share_b])
+ result.addCallbacks(compute_subs, self.error_handler)
+ return result
+
def _additive_constant(self, zero, field_element):
"""Greate an additive constant.

@@ -380,6 +413,23 @@
Cz = Cx * Cy
return (zi, (rhozi1, rhozi2), Cz)

+ def _minus(self, x, y):
+ """Subtraction of share-tuples *x* and *y*.
+
+ Each party ``P_i`` computes:
+ ``[x]_i = (x_i, rho_x,i, C_x)``
+ ``[y]_i = (y_i, rho_y,i, C_y)``
+ ``[z]_i = [x]_i - [y]_i
+ = (x_i - y_i mod p, rho_x,i - rho_y,i mod p, C_x / C_y)``.
+ """
+ xi, (rhoxi1, rhoxi2), Cx = x
+ yi, (rhoyi1, rhoyi2), Cy = y
+ zi = xi - yi
+ rhozi1 = rhoxi1 - rhoyi1
+ rhozi2 = rhoxi2 - rhoyi2
+ Cz = Cx / Cy
+ return (zi, (rhozi1, rhozi2), Cz)
+
def error_handler(self, ex):
print "Error: ", ex
return ex
diff --git a/viff/test/test_orlandi_runtime.py b/viff/test/test_orlandi_runtime.py
--- a/viff/test/test_orlandi_runtime.py
+++ b/viff/test/test_orlandi_runtime.py
@@ -161,3 +161,81 @@
d = runtime.open(z2)
d.addCallback(check)
return d
+
+ @protocol
+ def test_sub(self, runtime):
+ """Test subtration of two numbers."""
+
+ self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
+
+ x1 = 42
+ y1 = 7
+
+ def check(v):
+ self.assertEquals(v, x1 - y1)
+
+ if 1 == runtime.id:
+ x2 = runtime.secret_share([1], self.Zp, x1)
+ else:
+ x2 = runtime.secret_share([1], self.Zp)
+
+ if 3 == runtime.id:
+ y2 = runtime.secret_share([3], self.Zp, y1)
+ else:
+ y2 = runtime.secret_share([3], self.Zp)
+
+ z2 = runtime.sub(x2, y2)
+ d = runtime.open(z2)
+ d.addCallback(check)
+ return d
+
+ @protocol
+ def test_sub_minus(self, runtime):
+ """Test subtration of two numbers."""
+
+ self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
+
+ x1 = 42
+ y1 = 7
+
+ def check(v):
+ self.assertEquals(v, x1 - y1)
+
+ if 1 == runtime.id:
+ x2 = runtime.secret_share([1], self.Zp, x1)
+ else:
+ x2 = runtime.secret_share([1], self.Zp)
+
+ if 3 == runtime.id:
+ y2 = runtime.secret_share([3], self.Zp, y1)
+ else:
+ y2 = runtime.secret_share([3], self.Zp)
+
+ z2 = x2 - y2
+ d = runtime.open(z2)
+ d.addCallback(check)
+ return d
+
+ @protocol
+ def test_sub_constant(self, runtime):
+ """Test subtration of two numbers."""
+
+ self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
+
+ x1 = 42
+ y1 = 7
+
+ def check(v):
+ self.assertEquals(v, x1 - y1)
+
+ if 1 == runtime.id:
+ x2 = runtime.secret_share([1], self.Zp, x1)
+ else:
+ x2 = runtime.secret_share([1], self.Zp)
+
+ z2 = x2 - y1
+ d = runtime.open(z2)
+ d.addCallback(check)
+ return d
+
+
Janus Dam Nielsen
2009-10-06 08:10:03 UTC
Permalink
# HG changeset patch
# User Janus Dam Nielsen <***@alexandra.dk>
# Date 1254816324 -7200
# Node ID 86e0c7d54f2220bf03da45cf4269c88a7e6b777c
# Parent eb0443115206dc4a50bfea300c5582613d26326a
Implementation of the leak tolerant multiplication command.

diff --git a/viff/orlandi.py b/viff/orlandi.py
--- a/viff/orlandi.py
+++ b/viff/orlandi.py
@@ -81,6 +81,21 @@
Runtime.__init__(self, player, threshold, options)
self.threshold = self.num_players - 1

+ def compute_delta(self, d):
+ def product(j):
+ pt = 1
+ pn = 1
+ for k in xrange(1, 2 * d + 2):
+ if k != j:
+ pt *= k
+ pn *= k - j
+ return pt // pn
+
+ delta = []
+ for j in xrange(1, 2 * d + 2):
+ delta.append(product(j))
+ return delta
+
def output(self, share, receivers=None, threshold=None):
return self.open(share, receivers, threshold)

@@ -243,8 +258,9 @@
if Cx1 == Cx:
return x
else:
- raise OrlandiException("Wrong commitment for value %s, found %s expected %s." %
- (x, Cx1, Cx))
+ #return x
+ raise OrlandiException("Wrong commitment for value %s, %s, %s, found %s expected %s." %
+ (x, rho1, rho2, Cx1, Cx))

def deserialize(ls):
shares = [(field(long(x)), field(long(rho1)), field(long(rho2))) for x, rho1, rho2 in map(self.list_str, ls)]
@@ -559,6 +575,11 @@
Cz = Cx**c
return (zi, rhoz, Cz)

+ def _get_share(self, field, value):
+ Cc = commitment.commit(value * 3, 0, 0)
+ c = OrlandiShare(self, field, field(value), (field(0), field(0)), Cc)
+ return c
+
def _get_triple(self, field):
n = field(0)
Ca = commitment.commit(6, 0, 0)
@@ -617,6 +638,139 @@

return result

+ def sum_poly(self, j, ls):
+ exp = j
+ fj, (rhoj1, rhoj2), Cfj = ls[0]
+ x = fj*exp
+ rho1 = rhoj1 * exp
+ rho2 = rhoj2 * exp
+ Cx = Cfj**exp
+ exp *= j
+
+ for (fj, (rhoj1, rhoj2), Cfj) in ls[1:]:
+ x += fj * exp
+ rho1 += rhoj1 * exp
+ rho2 += rhoj2 * exp
+ Cx = Cx * (Cfj**exp)
+ exp *= j
+ return x, (rho1, rho2), Cx
+
+ def leak_tolerant_mul(self, share_x, share_y, M):
+ """Leak tolerant multiplication of shares.
+
+ Communication cost: ???.
+
+ Assuming a set of multiplicative triples:
+ ``M = ([a_i], [b_i], [c_i]) for 1 <= i <= 2d + 1``.
+
+ 1) ``for i = 1, ..., d do [f_i] = rand(), [g_i] = rand()``
+
+ 2) ``for j = 1, ..., 2d+1 do
+ [F_j] = [x] + SUM_i=1^d [f_i]*j^i
+ and
+ [G_j] = [y] + SUM_i=1^d [g_i]*j^i``
+
+ 3) for j = 1, ..., 2d+1 do [H_j] = Mul([F_j], [G_j], [a_j], [b_j], [c_j])
+
+ 4) compute [H_0] = SUM_j=1^2d+1 delta_j[H_j]
+
+ 5) output [z] = [H_0]
+
+ delta_j = PRODUCT_k=1, k!=j^2d+1 k/(k-j).
+ """
+ assert isinstance(share_x, Share) or isinstance(share_y, Share), \
+ "At least one of share_x and share_y must be a Share."
+
+ self.program_counter[-1] += 1
+
+ field = getattr(share_x, "field", getattr(share_y, "field", None))
+ n = field(0)
+
+ cmul_result = self._cmul(share_x, share_y, field)
+ if cmul_result is not None:
+ return cmul_result
+
+ # 1) for i = 1, ..., d do [f_i] = rand(), [g_i] = rand()
+ d = (len(M) - 1) // 2
+ deltas = self.compute_delta(d)
+ f = []
+ g = []
+ for x in xrange(d):
+ f.append(self.random_share(field))
+ g.append(self.random_share(field))
+
+ def compute_polynomials(t):
+ x, y = t[0]
+ f = []
+ g = []
+ if 1 in t:
+ f = t[1]
+ if 2 in t:
+ g = t[2]
+# print "==> poly", self.id
+# print "x:", x
+# print "y:", y
+# print "f:", f
+# print "g:", g
+ # 2) for j = 1, ..., 2d+1 do
+ # [F_j] = [x] + SUM_i=1^d [f_i]*j^i
+ # and
+ # [G_j] = [y] + SUM_i=1^d [g_i]*j^i
+ h0i, rhoh0, Ch0 = self._additive_constant(field(0), n)
+ H0 = OrlandiShare(self, field, h0i, rhoh0, Ch0)
+ xi, (rhoxi1, rhoxi2), Cx = x
+ yi, (rhoyi1, rhoyi2), Cy = y
+
+ for j in xrange(1, 2*d + 2):
+ Fji = xi
+ rho1_Fji = rhoxi1
+ rho2_Fji = rhoxi2
+ C_Fji = Cx
+ if f != []:
+ # SUM_i=1^d [f_i]*j^i
+ vi, (rhovi1, rhovi2), Cv = self.sum_poly(j, f)
+ # [F_j] = [x] + SUM_i=1^d [f_i]*j^i
+ Fji += vi
+ rho1_Fji += rhovi1
+ rho2_Fji += rhovi2
+ C_Fji *= Cv
+ Gji = yi
+ rho1_Gji = rhoyi1
+ rho2_Gji = rhoyi2
+ C_Gji = Cy
+ if g != []:
+ # SUM_i=1^d [g_i]*j^i
+ wi, (rhowi1, rhowi2), Cw = self.sum_poly(j, g)
+ # [G_j] = [y] + SUM_i=1^d [g_i]*j^i
+ Gji += wi
+ rho1_Gji += rhowi1
+ rho2_Gji += rhowi2
+ C_Gji *= Cw
+ Fj = OrlandiShare(self, field, Fji, (rho1_Fji, rho2_Fji), C_Fji)
+ Gj = OrlandiShare(self, field, Gji, (rho1_Gji, rho2_Gji), C_Gji)
+ a, b, c = M.pop(0)
+
+ # [H_j] = Mul([F_j], [G_j], [a_j], [b_j], [c_j])
+ Hj = self._basic_multiplication(Fj, Gj, a, b, c)
+ dj = self._cmul(field(deltas[j - 1]), Hj, field)
+ H0 = H0 + dj
+ # 5) output [z] = [H_0]
+ return H0
+
+ ls = [gather_shares([share_x, share_y])]
+ if g:
+ ls.append(gather_shares(g))
+ if f:
+ ls.append(gather_shares(f))
+ result = gather_shares(ls)
+ self.schedule_callback(result, compute_polynomials)
+ result.addErrback(self.error_handler)
+
+ # do actual communication
+ self.activate_reactor()
+
+ return result
+
def error_handler(self, ex):
print "Error: ", ex
return ex
diff --git a/viff/test/test_orlandi_runtime.py b/viff/test/test_orlandi_runtime.py
--- a/viff/test/test_orlandi_runtime.py
+++ b/viff/test/test_orlandi_runtime.py
@@ -334,7 +334,7 @@

self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)

- count = 20
+ count = 9

a_shares = []
b_shares = []
@@ -481,6 +481,89 @@
x2 = runtime.shift([1], self.Zp, x1)
y2 = runtime.shift([1], self.Zp, y1)

+ @protocol
+ def test_sum_poly(self, runtime):
+ """Test implementation of sum_poly."""
+
+ self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
+
+ f = []
+ f.append((self.Zp(7), (self.Zp(7), self.Zp(7)), self.Zp(7)))
+ f.append((self.Zp(9), (self.Zp(9), self.Zp(9)), self.Zp(9)))
+ f.append((self.Zp(13), (self.Zp(13), self.Zp(13)), self.Zp(13)))
+
+ x, (rho1, rho2), Cx = runtime.sum_poly(1, f)
+ self.assertEquals(x, 29)
+ self.assertEquals(rho1, 29)
+ self.assertEquals(rho2, 29)
+ self.assertEquals(Cx, 29)
+ return x
+
+ @protocol
+ def test_sum_poly(self, runtime):
+ """Test implementation of sum_poly."""
+
+ self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
+
+ Cf1 = commitment.commit(21, 21, 21)
+ Cf2 = commitment.commit(27, 27, 27)
+ Cf3 = commitment.commit(39, 39, 39)
+
+ f = []
+ f.append((self.Zp(7), (self.Zp(7), self.Zp(7)), Cf1))
+ f.append((self.Zp(9), (self.Zp(9), self.Zp(9)), Cf2))
+ f.append((self.Zp(13), (self.Zp(13), self.Zp(13)), Cf3))
+
+ x, (rho1, rho2), Cx = runtime.sum_poly(3, f)
+ self.assertEquals(x, 453)
+ self.assertEquals(rho1, 453)
+ self.assertEquals(rho2, 453)
+ self.assertEquals(Cx, Cf1**3 * Cf2**9 * Cf3**27)
+ return x
+
+ @protocol
+ def test_delta(self, runtime):
+ """Test implementation of compute_delta."""
+
+ self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
+
+ delta = runtime.compute_delta(3)
+ self.assertEquals(delta[0], 7)
+ self.assertEquals(delta[1], -21)
+ self.assertEquals(delta[2], 35)
+ self.assertEquals(delta[3], -35)
+ self.assertEquals(delta[4], 21)
+ self.assertEquals(delta[5], -7)
+ self.assertEquals(delta[6], 1)
+
+ return delta
+
+ @protocol
+ def test_leak_mul(self, runtime):
+ """Test leaktolerant multiplication of two numbers."""
+ commitment.set_reference_string(long(2), long(6))
+
+ self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
+
+ x1 = 42
+ y1 = 7
+
+ d = 4
+
+ def check(v):
+ self.assertEquals(v, x1 * y1)
+
+ x2 = runtime.shift([1], self.Zp, x1)
+ y2 = runtime.shift([2], self.Zp, y1)
+
+ M = []
+ for j in xrange(1, 2*d + 2):
+ M.append(_get_triple(self, self.Zp))
+ z2 = runtime.leak_tolerant_mul(x2, y2, M)
+ d = runtime.open(z2)
+ d.addCallback(check)
+ return d
+
z2 = runtime._cmul(y2, x2, self.Zp)
self.assertEquals(z2, None)
return z2
Janus Dam Nielsen
2009-10-06 08:09:52 UTC
Permalink
# HG changeset patch
# User Janus Dam Nielsen <***@alexandra.dk>
# Date 1254816276 -7200
# Node ID 8a5eb65501118b57550a57504450ea6ae406d077
# Parent c43b0e520aba3d9c7de29e494e0ff16d0f66cd37
Constants used in communication is refactored to a new file.

diff --git a/viff/active.py b/viff/active.py
--- a/viff/active.py
+++ b/viff/active.py
@@ -28,7 +28,7 @@
from viff.matrix import Matrix, hyper
from viff.passive import PassiveRuntime
from viff.runtime import Share, preprocess, gather_shares
-from viff.runtime import ECHO, READY, SEND
+from viff.constants import ECHO, READY, SEND


class BrachaBroadcastMixin:
diff --git a/viff/constants.py b/viff/constants.py
new file mode 100644
--- /dev/null
+++ b/viff/constants.py
@@ -0,0 +1,27 @@
+# -*- coding: utf-8 -*-
+#
+# Copyright 2009 VIFF Development Team.
+#
+# This file is part of VIFF, the Virtual Ideal Functionality Framework.
+#
+# VIFF is free software: you can redistribute it and/or modify it
+# under the terms of the GNU Lesser General Public License (LGPL) as
+# published by the Free Software Foundation, either version 3 of the
+# License, or (at your option) any later version.
+#
+# VIFF is distributed in the hope that it will be useful, but WITHOUT
+# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
+# Public License for more details.
+#
+# You should have received a copy of the GNU Lesser General Public
+# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
+
+__docformat__ = "restructuredtext"
+
+# Constants used for communication.
+SHARE = 0
+ECHO = 1
+READY = 2
+SEND = 3
+PAILLIER = 4
diff --git a/viff/paillier.py b/viff/paillier.py
--- a/viff/paillier.py
+++ b/viff/paillier.py
@@ -28,7 +28,7 @@
import gmpy

from viff.runtime import Runtime, Share, gather_shares
-from viff.runtime import PAILLIER
+from viff.constants import PAILLIER
from viff.util import rand, find_random_prime

def L(u, n):
diff --git a/viff/runtime.py b/viff/runtime.py
--- a/viff/runtime.py
+++ b/viff/runtime.py
@@ -41,6 +41,7 @@

from viff.field import GF256, FieldElement
from viff.util import wrapper, rand, deep_wait, track_memory_usage, begin, end
+from viff.constants import SHARE
import viff.reactor

from twisted.internet import reactor
@@ -51,13 +52,6 @@
from twisted.internet.protocol import ReconnectingClientFactory, ServerFactory
from twisted.protocols.basic import Int16StringReceiver

-# Constants used by ShareExchanger.
-SHARE = 0
-ECHO = 1
-READY = 2
-SEND = 3
-PAILLIER = 4
-

class Share(Deferred):
"""A shared number.
diff --git a/viff/test/test_runtime.py b/viff/test/test_runtime.py
--- a/viff/test/test_runtime.py
+++ b/viff/test/test_runtime.py
@@ -30,7 +30,8 @@
from twisted.internet.defer import gatherResults, Deferred, DeferredList

from viff.field import GF256
-from viff.runtime import Share, SHARE
+from viff.runtime import Share
+from viff.constants import SHARE
from viff.comparison import Toft05Runtime
from viff.test.util import RuntimeTestCase, BinaryOperatorTestCase, protocol
Janus Dam Nielsen
2009-10-06 08:10:01 UTC
Permalink
# HG changeset patch
# User Janus Dam Nielsen <***@alexandra.dk>
# Date 1254816324 -7200
# Node ID a62e12c9947a9499dd293e2dce91992950505fee
# Parent 5636b02c6beffac287fc05f62b87b3b03c01e116
Implementation of input and shift commands.

diff --git a/viff/hash_broadcast.py b/viff/hash_broadcast.py
--- a/viff/hash_broadcast.py
+++ b/viff/hash_broadcast.py
@@ -96,7 +96,8 @@
self._expect_data_with_pc(unique_pc, peer_id, HASH, d_hash)
d_signal = Deferred().addCallbacks(signal_received,
self.error_handler,
- callbackArgs=(peer_id, message, len(receivers), g_hashes, signals))
+ callbackArgs=(peer_id, message, len(receivers),
+ g_hashes, signals))
self._expect_data_with_pc(unique_pc, peer_id, SIGNAL, d_signal)

# Set up receiving of the message.
diff --git a/viff/orlandi.py b/viff/orlandi.py
--- a/viff/orlandi.py
+++ b/viff/orlandi.py
@@ -15,7 +15,7 @@
# You should have received a copy of the GNU Lesser General Public
# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.

-from twisted.internet.defer import Deferred, gatherResults
+from twisted.internet.defer import Deferred, DeferredList, gatherResults

from viff.runtime import Runtime, Share, ShareList, gather_shares
from viff.util import rand
@@ -383,6 +383,82 @@
result.addCallbacks(compute_subs, self.error_handler)
return result

+ def input(self, inputters, field, number=None, threshold=None):
+ """Input *number* to the computation.
+
+ The input is shared using the :meth:`shift` method.
+ """
+ return self.shift(inputters, field, number)
+
+
+ def shift(self, inputters, field, number=None):
+ """Shift of a share.
+
+ Useful for input.
+
+ Communication cost: ???.
+
+ Assume the parties are given a random share ``[r]`` by a trusted dealer.
+ Then we denote the following protocol but ``[x] = Shift(P_i, x, [r])``.
+
+ 1) ``r = OpenTo(P_i, [r]``
+
+ 2) ``P_i broadcasts Delta = r - x``
+
+ 3) ``[x] = [r] - Delta``
+
+ """
+ # TODO: Communitcation costs?
+ assert (self.id in inputters and number != None) or (self.id not in inputters)
+
+ self.program_counter[-1] += 1
+
+ results = []
+ def hack(_, peer_id):
+ # Assume the parties are given a random share [r] by a trusted dealer.
+ share_r = self.random_share(field)
+ # 1) r = OpenTo(P_i, [r])
+ open_r = self.open(share_r, [peer_id])
+ def subtract_delta(delta, share_r):
+ delta = field(long(delta))
+ x = self.sub(share_r, delta)
+ return x
+ if peer_id == self.id:
+ def g(r, x):
+ delta = r - x
+ delta = self.broadcast([peer_id], self.players.keys(), str(delta.value))
+ self.schedule_callback(delta, subtract_delta, share_r)
+ delta.addErrback(self.error_handler)
+ return delta
+ self.schedule_callback(open_r, g, number)
+ open_r.addErrback(self.error_handler)
+ return open_r
+ else:
+ d = Deferred()
+ def g(_, peer_id, share_r):
+ delta = self.broadcast([peer_id], self.players.keys())
+ self.schedule_callback(delta, subtract_delta, share_r)
+ delta.addErrback(self.error_handler)
+ return delta
+ self.schedule_callback(d, g, peer_id, share_r)
+ d.addErrback(self.error_handler)
+ d.callback(None)
+ return d
+
+ for peer_id in inputters:
+ s = Share(self, field)
+ self.schedule_callback(s, hack, peer_id)
+ s.addErrback(self.error_handler)
+ s.callback(None)
+ results.append(s)
+
+ # do actual communication
+ self.activate_reactor()
+
+ if len(results) == 1:
+ return results[0]
+ return results
+
def _additive_constant(self, zero, field_element):
"""Greate an additive constant.

diff --git a/viff/test/test_orlandi_runtime.py b/viff/test/test_orlandi_runtime.py
--- a/viff/test/test_orlandi_runtime.py
+++ b/viff/test/test_orlandi_runtime.py
@@ -15,15 +15,17 @@
# You should have received a copy of the GNU Lesser General Public
# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.

-from twisted.internet.defer import gatherResults
+from twisted.internet.defer import gatherResults, DeferredList

from viff.test.util import RuntimeTestCase, protocol, BinaryOperatorTestCase
-from viff.runtime import Share
+from viff.runtime import Share, gather_shares
from viff.orlandi import OrlandiRuntime

from viff.field import FieldElement, GF
from viff.passive import PassiveRuntime

+from viff.util import rand
+
import commitment

class OrlandiBasicCommandsTest(RuntimeTestCase):
@@ -239,3 +241,101 @@
return d


+class OrlandiAdvancedCommandsTest(RuntimeTestCase):
+ """Test for advanced commands."""
+
+ # Number of players.
+ num_players = 3
+
+ runtime_class = OrlandiRuntime
+
+ timeout = 60
+
+ @protocol
+ def test_shift(self, runtime):
+ """Test addition of the shift command."""
+
+ self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
+
+ def check(v):
+ self.assertEquals(v, 42)
+
+ x = runtime.shift([2], self.Zp, 42)
+ d = runtime.open(x)
+ d.addCallback(check)
+ return d
+
+ @protocol
+ def test_shift_two_inputters(self, runtime):
+ """Test addition of the shift command."""
+
+ self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
+
+ def check(v):
+ self.assertEquals(v, 42)
+
+ x, y = runtime.shift([1,3], self.Zp, 42)
+ d1 = runtime.open(x)
+ d1.addCallback(check)
+ d2 = runtime.open(y)
+ d2.addCallback(check)
+ return DeferredList([d1, d2])
+
+
+ @protocol
+ def test_shift_two_consequtive_inputters(self, runtime):
+ """Test addition of the shift command."""
+
+ self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
+
+ def r1(ls):
+ x, y = ls
+ self.assertEquals(runtime.program_counter, [4])
+
+ x = runtime.shift([1], self.Zp, 42)
+ y = runtime.shift([2], self.Zp, 42)
+ r = gather_shares([x, y])
+ r.addCallback(r1)
+ return r
+
+ @protocol
+ def test_shift_two_consequtive_inputters2(self, runtime):
+ """Test addition of the shift command."""
+
+ self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
+
+ def check(v):
+ self.assertEquals(v, 42)
+
+ def r1((x, y)):
+ self.assertEquals(x, 42)
+ self.assertEquals(y, 42)
+
+ x = runtime.shift([1], self.Zp, 42)
+ y = runtime.shift([2], self.Zp, 42)
+ r = gather_shares([runtime.open(x), runtime.open(y)])
+ r.addCallback(r1)
+ return r
+
+ @protocol
+ def test_input(self, runtime):
+ """Test of many uses of the input command."""
+
+ self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
+
+ count = 20
+
+ a_shares = []
+ b_shares = []
+ for i in range(count):
+ inputter = (i % len(runtime.players)) + 1
+ if inputter == runtime.id:
+ a = rand.randint(0, self.Zp.modulus)
+ b = rand.randint(0, self.Zp.modulus)
+ else:
+ a, b = None, None
+ a_shares.append(runtime.input([inputter], self.Zp, a))
+ b_shares.append(runtime.input([inputter], self.Zp, b))
+ shares_ready = gather_shares(a_shares + b_shares)
+ return shares_ready
+
Janus Dam Nielsen
2009-10-06 08:09:56 UTC
Permalink
# HG changeset patch
# User Janus Dam Nielsen <***@alexandra.dk>
# Date 1254816324 -7200
# Node ID 42d95e56edf626b2a2c8535e5bfbe856a1e82a3b
# Parent 7fe8f5835b61c495be6eb807cae043f6aa1fd908
Implemented secret sharing command.

diff --git a/viff/orlandi.py b/viff/orlandi.py
--- a/viff/orlandi.py
+++ b/viff/orlandi.py
@@ -15,8 +15,18 @@
# You should have received a copy of the GNU Lesser General Public
# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.

+from twisted.internet.defer import Deferred
+
from viff.runtime import Runtime, Share, ShareList, gather_shares
from viff.util import rand
+from viff.constants import TEXT
+
+import commitment
+commitment.set_reference_string(23434347834783478783478L, 489237823478234783478020L)
+
+# import logging
+# LOG_FILENAME = 'logging_example.out'
+# logging.basicConfig(filename=LOG_FILENAME,level=logging.DEBUG,)

class OrlandiException(Exception):
pass
@@ -67,3 +77,115 @@
"""Initialize runtime."""
Runtime.__init__(self, player, threshold, options)
self.threshold = self.num_players - 1
+
+ def output(self, share, receivers=None, threshold=None):
+ return self.open(share, receivers, threshold)
+
+ def _send_orlandi_share(self, other_id, pc, xi, rhoi, Cx):
+ """Send the share *xi*, *rhoi*, and the commitment *Cx* to party *other_id*."""
+ self.protocols[other_id].sendShare(pc, xi)
+ self.protocols[other_id].sendShare(pc, rhoi[0])
+ self.protocols[other_id].sendShare(pc, rhoi[1])
+ self.protocols[other_id].sendData(pc, TEXT, repr(Cx))
+
+ def _expect_orlandi_share(self, peer_id, field):
+ """Waits for a number ``x``, ``rho``, and the commitment for ``x``."""
+ xi = self._expect_share(peer_id, field)
+ Cx = Deferred()
+ rhoi1 = self._expect_share(peer_id, field)
+ rhoi2 = self._expect_share(peer_id, field)
+ self._expect_data(peer_id, TEXT, Cx)
+ sls = ShareList([xi, rhoi1, rhoi2, Cx])
+ def combine(ls):
+ expected_num = 4;
+ if len(ls) is not expected_num:
+ raise OrlandiException("Cannot share number, trying to create a share,"
+ " expected %s components got %s." % (expected_num, len(ls)))
+ s1, xi = ls[0]
+ s2, rhoi1 = ls[1]
+ s3, rhoi2 = ls[2]
+ s4, Cx = ls[3]
+ Cxx = commitment.deserialize(Cx)
+ if not (s1 and s2 and s3 and s4):
+ raise OrlandiException("Cannot share number, trying to create share,"
+ " but a component did arrive properly.")
+ return OrlandiShare(self, field, xi, (rhoi1, rhoi2), Cxx)
+ sls.addCallbacks(combine, self.error_handler)
+ return sls
+
+ def secret_share(self, inputters, field, number=None, threshold=None):
+ """Share the value, number, among all the parties using additive shareing.
+
+ To share an element ``x in Z_p``, choose random ``x_1, ..., x_n-1 in Z_p``,
+ define ``x_n = x - SUM_i=1^n-1 x_i mod p``.
+
+ Choose random values ``rho_x1, ..., rho_xn in (Z_p)^2``, define
+ ``rho_x = SUM_i=1^n rho_x,i`` and ``C_x = Com_ck(x, p_x)``.
+
+ Send ``[x]_i = (x_i, rho_xi, C_x)`` to party ``P_i``.
+ """
+ assert number is None or self.id in inputters
+ self.threshold = self.num_players - 1
+
+ self.program_counter[-1] += 1
+
+ def additive_shares_with_rho(x):
+ """Returns a tuple of a list of tuples (player id, share, rho) and rho.
+
+ Chooses random elements ``x_1, ..., x_n-1`` in field and ``x_n`` st.
+ ``x_n = x - Sum_i=1^n-1 x_i``.
+
+ Chooses random pair of elements ``rho_1, ..., rho_n in Z_p^2``
+ and define ``rho_n = Sum_i=1^n rho_i``.
+
+ Returns a pair of ``((player id, x_i, rho_i), rho)``.
+ """
+ shares = []
+ rhos = []
+ sum = 0
+ rho1 = 0
+ rho2 = 0
+ for i in xrange(1, self.num_players):
+ xi = field(rand.randint(0, field.modulus - 1))
+ rhoi1 = field(rand.randint(0, field.modulus - 1))
+ rhoi2 = field(rand.randint(0, field.modulus - 1))
+ sum += xi
+ rho1 += rhoi1
+ rho2 += rhoi2
+ shares.append((i, xi, (rhoi1, rhoi2)))
+ xn = field(x) - sum
+ rhon1 = field(rand.randint(0, field.modulus - 1))
+ rhon2 = field(rand.randint(0, field.modulus - 1))
+ shares.append((self.num_players, xn, (rhon1, rhon2)))
+ rho1 += rhon1
+ rho2 += rhon2
+ return shares, (rho1, rho2)
+
+ # Send ``[x]_i = (x_i, rho_x,i, C_x)`` to party ``P_i``.
+ results = []
+ for peer_id in inputters:
+ if peer_id == self.id:
+ pc = tuple(self.program_counter)
+ shares, rho = additive_shares_with_rho(number)
+ Cx = commitment.commit(number, rho[0].value, rho[1].value)
+ # Distribute the shares
+ the_others = []
+ for other_id, xi, rhoi in shares:
+ if other_id == self.id:
+ results.append(OrlandiShare(self, field, xi, rhoi, Cx))
+ else:
+ # Send ``xi``, ``rhoi``, and commitment
+ self._send_orlandi_share(other_id, pc, xi, rhoi, Cx)
+ else:
+ # Expect ``xi``, ``rhoi``, and commitment
+ results.append(self._expect_orlandi_share(peer_id, field))
+ # do actual communication
+ self.activate_reactor()
+ # Unpack a singleton list.
+ if len(results) == 1:
+ return results[0]
+ return results
+
+ def error_handler(self, ex):
+ print "Error: ", ex
+ return ex
diff --git a/viff/test/test_orlandi_runtime.py b/viff/test/test_orlandi_runtime.py
--- a/viff/test/test_orlandi_runtime.py
+++ b/viff/test/test_orlandi_runtime.py
@@ -21,9 +21,11 @@
from viff.runtime import Share
from viff.orlandi import OrlandiRuntime

-from viff.field import FieldElement
+from viff.field import FieldElement, GF
from viff.passive import PassiveRuntime

+import commitment
+
class OrlandiBasicCommandsTest(RuntimeTestCase):
"""Test for basic commands."""

@@ -31,3 +33,23 @@
num_players = 3

runtime_class = OrlandiRuntime
+
+ @protocol
+ def test_secret_share(self, runtime):
+ """Test sharing of random numbers."""
+
+ self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
+
+ def check((xi, (rho1, rho2), Cr)):
+ # Check that we got the expected number of shares.
+ self.assert_type(xi, FieldElement)
+ self.assert_type(rho1, FieldElement)
+ self.assert_type(rho2, FieldElement)
+ self.assert_type(Cr, commitment.Commitment)
+
+ if 1 == runtime.id:
+ share = runtime.secret_share([1], self.Zp, 42)
+ else:
+ share = runtime.secret_share([1], self.Zp)
+ share.addCallback(check)
+ return share
Janus Dam Nielsen
2009-10-06 08:09:55 UTC
Permalink
# HG changeset patch
# User Janus Dam Nielsen <***@alexandra.dk>
# Date 1254816324 -7200
# Node ID 7fe8f5835b61c495be6eb807cae043f6aa1fd908
# Parent 53d198cdf14cb85d81d6e6cf1ec75a16773dfbec
Boilerplate code for the implementation of the Orlandi runtime.

diff --git a/viff/orlandi.py b/viff/orlandi.py
new file mode 100644
--- /dev/null
+++ b/viff/orlandi.py
@@ -0,0 +1,69 @@
+# Copyright 2009 VIFF Development Team.
+#
+# This file is part of VIFF, the Virtual Ideal Functionality Framework.
+#
+# VIFF is free software: you can redistribute it and/or modify it
+# under the terms of the GNU Lesser General Public License (LGPL) as
+# published by the Free Software Foundation, either version 3 of the
+# License, or (at your option) any later version.
+#
+# VIFF is distributed in the hope that it will be useful, but WITHOUT
+# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
+# Public License for more details.
+#
+# You should have received a copy of the GNU Lesser General Public
+# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
+
+from viff.runtime import Runtime, Share, ShareList, gather_shares
+from viff.util import rand
+
+class OrlandiException(Exception):
+ pass
+
+class OrlandiShare(Share):
+ """A share in the Orlandi runtime.
+
+ A share in the Orlandi runtime is a 3-tuple ``(x_i, rho_i, Cr_i)`` of:
+ - A share of a number, ``x_i``
+ - A tuple of two random numbers, ``rho_i = (rho_i1, rho_i2)``
+ - A commitment to the number and the random numbers, ``Cr_i``
+
+ The :class:`Runtime` operates on shares, represented by this class.
+ Shares are asynchronous in the sense that they promise to attain a
+ value at some point in the future.
+
+ Shares overload the arithmetic operations so that ``x = a + b``
+ will create a new share *x*, which will eventually contain the
+ sum of *a* and *b*. Each share is associated with a
+ :class:`Runtime` and the arithmetic operations simply call back to
+ that runtime.
+ """
+
+ def __init__(self, runtime, field, value=None, rho=None, commitment=None):
+ Share.__init__(self, runtime, field, (value, rho, commitment))
+
+
+class OrlandiRuntime(Runtime):
+ """The Orlandi runtime.
+
+ The runtime is used for sharing values (:meth:`secret_share` or
+ :meth:`shift`) into :class:`OrlandiShare` object and opening such
+ shares (:meth:`open`) again. Calculations on shares is normally
+ done through overloaded arithmetic operations, but it is also
+ possible to call :meth:`add`, :meth:`mul`, etc. directly if one
+ prefers.
+
+ Each player in the protocol uses a :class:`Runtime` object. To
+ create an instance and connect it correctly with the other
+ players, please use the :func:`create_runtime` function instead of
+ instantiating a Runtime directly. The :func:`create_runtime`
+ function will take care of setting up network connections and
+ return a :class:`Deferred` which triggers with the
+ :class:`Runtime` object when it is ready.
+ """
+
+ def __init__(self, player, threshold=None, options=None):
+ """Initialize runtime."""
+ Runtime.__init__(self, player, threshold, options)
+ self.threshold = self.num_players - 1
diff --git a/viff/test/test_orlandi_runtime.py b/viff/test/test_orlandi_runtime.py
new file mode 100644
--- /dev/null
+++ b/viff/test/test_orlandi_runtime.py
@@ -0,0 +1,33 @@
+# Copyright 2009 VIFF Development Team.
+#
+# This file is part of VIFF, the Virtual Ideal Functionality Framework.
+#
+# VIFF is free software: you can redistribute it and/or modify it
+# under the terms of the GNU Lesser General Public License (LGPL) as
+# published by the Free Software Foundation, either version 3 of the
+# License, or (at your option) any later version.
+#
+# VIFF is distributed in the hope that it will be useful, but WITHOUT
+# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
+# Public License for more details.
+#
+# You should have received a copy of the GNU Lesser General Public
+# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
+
+from twisted.internet.defer import gatherResults
+
+from viff.test.util import RuntimeTestCase, protocol, BinaryOperatorTestCase
+from viff.runtime import Share
+from viff.orlandi import OrlandiRuntime
+
+from viff.field import FieldElement
+from viff.passive import PassiveRuntime
+
+class OrlandiBasicCommandsTest(RuntimeTestCase):
+ """Test for basic commands."""
+
+ # Number of players.
+ num_players = 3
+
+ runtime_class = OrlandiRuntime
Janus Dam Nielsen
2009-10-06 08:10:07 UTC
Permalink
# HG changeset patch
# User Janus Dam Nielsen <***@alexandra.dk>
# Date 1254816324 -7200
# Node ID 2704f20bab087cc127acb0961acba98768a0123c
# Parent abe7f8ef29b1620b69666ff34bae3e8cdb469f8a
Replace the current implementation of _get_triple with a call to random triple.

Implement the preprocessing interface.

diff --git a/viff/orlandi.py b/viff/orlandi.py
--- a/viff/orlandi.py
+++ b/viff/orlandi.py
@@ -495,8 +495,17 @@

field = getattr(share_x, "field", getattr(share_y, "field", None))

- a, b, c = self._get_triple(field)
- return self._basic_multiplication(share_x, share_y, a, b, c)
+ def finish_mul((a, b, c)):
+ return self._basic_multiplication(share_x, share_y, a, b, c)
+
+ # This will be the result, a Share object.
+ result = Share(self, share_x.field)
+ # This is the Deferred we will do processing on.
+ triple = self._get_triple(field)
+ triple = self.schedule_complex_callback(triple, finish_mul)
+ # We add the result to the chains in triple.
+ triple.chainDeferred(result)
+ return result

def _additive_constant(self, zero, field_element):
"""Greate an additive constant.
@@ -588,14 +597,11 @@
return c

def _get_triple(self, field):
- n = field(0)
- Ca = commitment.commit(6, 0, 0)
- a = OrlandiShare(self, field, field(2), (n, n), Ca)
- Cb = commitment.commit(12, 0, 0)
- b = OrlandiShare(self, field, field(4), (n, n), Cb)
- Cc = commitment.commit(72, 0, 0)
- c = OrlandiShare(self, field, field(24), (n, n), Cc)
- return (a, b, c)
+ c, d = self.random_triple(field, 1)
+ def f(ls):
+ return ls[0]
+ d.addCallbacks(f, self.error_handler)
+ return d

def _basic_multiplication(self, share_x, share_y, triple_a, triple_b, triple_c):
"""Multiplication of shares give a triple.
@@ -1011,7 +1017,7 @@

return result

- def random_triple(self, field):
+ def random_triple(self, field, number_of_requested_triples):
"""Generate a list of triples ``(a, b, c)`` where ``c = a * b``.

The triple ``(a, b, c)`` is secure in the Fcrs-hybrid model.
@@ -1019,15 +1025,16 @@
"""
self.program_counter[-1] += 1

- number_of_multiplications = 1
M = []
-
- for x in xrange((1 + self.s_lambda) * (2 * self.d + 1) * number_of_multiplications):
+
+# print "Generating %i triples... relax, have a brak..." % ((1 + self.s_lambda) * (2 * self.d + 1) * number_of_requested_triples)
+
+ for x in xrange((1 + self.s_lambda) * (2 * self.d + 1) * number_of_requested_triples):
M.append(self.triple_test(field))

def step3(ls):
"""Coin-flip a subset test_set of M of size lambda(2d + 1)M."""
- size = self.s_lambda * (2 * self.d + 1) * number_of_multiplications
+ size = self.s_lambda * (2 * self.d + 1) * number_of_requested_triples
inx = 0
p_half = field.modulus // 2
def coin_flip(v, ls, test_set):
@@ -1235,18 +1242,18 @@
return dls_all

def step6(M_without_test_set):
- """Partition M without test_set in number_of_multiplications
+ """Partition M without test_set in number_of_requested_triples
random subsets M_i of size (2d + 1).
"""
subsets = []
size = 2 * self.d + 1
- for x in xrange(number_of_multiplications):
+ for x in xrange(number_of_requested_triples):
subsets.append([])

def put_in_set(v, M_without_test_set, subsets):
if 0 == len(M_without_test_set):
return subsets
- v = v.value % number_of_multiplications
+ v = v.value % number_of_requested_triples
if size > len(subsets[v]):
subsets[v].append(M_without_test_set.pop(0))
r = self.random_share(field)
@@ -1295,8 +1302,11 @@
# do actual communication
self.activate_reactor()

- return result
-
+ s = Share(self, field)
+ def f(ls, s):
+ s.callback(ls)
+ result.addCallbacks(f, self.error_handler, callbackArgs=(s,))
+ return number_of_requested_triples, s

def error_handler(self, ex):
print "Error: ", ex
diff --git a/viff/test/test_orlandi_runtime.py b/viff/test/test_orlandi_runtime.py
--- a/viff/test/test_orlandi_runtime.py
+++ b/viff/test/test_orlandi_runtime.py
@@ -261,7 +261,7 @@

runtime_class = OrlandiRuntime

- timeout = 60
+ timeout = 800

@protocol
def test_shift(self, runtime):
@@ -556,13 +556,15 @@
x2 = runtime.shift([1], self.Zp, x1)
y2 = runtime.shift([2], self.Zp, y1)

- M = []
- for j in xrange(1, 2*runtime.d + 2):
- M.append(_get_triple(self, self.Zp))
- z2 = runtime.leak_tolerant_mul(x2, y2, M)
- d = runtime.open(z2)
- d.addCallback(check)
- return d
+ c, sls = runtime.random_triple(self.Zp, 2*runtime.d + 1)
+
+ def cont(M):
+ z2 = runtime.leak_tolerant_mul(x2, y2, M)
+ d = runtime.open(z2)
+ d.addCallback(check)
+ return d
+ sls.addCallbacks(cont, runtime.error_handler)
+ return sls

z2 = runtime._cmul(y2, x2, self.Zp)
self.assertEquals(z2, None)
@@ -672,7 +674,95 @@
d = gatherResults(ds)
d.addCallback(check)
return d
- d = runtime.random_triple(self.Zp)
+ c, d = runtime.random_triple(self.Zp, 1)
d.addCallbacks(open, runtime.error_handler)
return d

+ @protocol
+ def test_random_triple3_parallel(self, runtime):
+ """Test the triple_combiner command."""
+
+ self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
+
+ def check(ls):
+ for x in xrange(len(ls) // 3):
+ a = ls[x * 3]
+ b = ls[x * 3 + 1]
+ c = ls[x * 3 + 2]
+ self.assertEquals(c, a * b)
+
+ def open(ls):
+ ds = []
+ for [(a, b, c)] in ls:
+ d1 = runtime.open(a)
+ d2 = runtime.open(b)
+ d3 = runtime.open(c)
+ ds.append(d1)
+ ds.append(d2)
+ ds.append(d3)
+
+ d = gatherResults(ds)
+ d.addCallback(check)
+ return d
+ ac, a = runtime.random_triple(self.Zp, 1)
+ bc, b = runtime.random_triple(self.Zp, 1)
+ cc, c = runtime.random_triple(self.Zp, 1)
+ d = gather_shares([a, b, c])
+ d.addCallbacks(open, runtime.error_handler)
+ return d
+
+ @protocol
+ def test_random_triple_parallel(self, runtime):
+ """Test the triple_combiner command."""
+
+ self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
+
+ def check(ls):
+ for x in xrange(len(ls) // 3):
+ a = ls[x * 3]
+ b = ls[x * 3 + 1]
+ c = ls[x * 3 + 2]
+ self.assertEquals(c, a * b)
+
+ def open(ls):
+ ds = []
+ for [(a, b, c)] in ls:
+ d1 = runtime.open(a)
+ d2 = runtime.open(b)
+ d3 = runtime.open(c)
+ ds.append(d1)
+ ds.append(d2)
+ ds.append(d3)
+
+ d = gatherResults(ds)
+ d.addCallback(check)
+ return d
+
+ a_shares = []
+ b_shares = []
+ c_shares = []
+
+ def cont(x):
+ while a_shares and b_shares:
+ a = a_shares.pop()
+ b = b_shares.pop()
+ print "computing..."
+ c_shares.append(runtime.mul(a, b))
+ done = gather_shares(c_shares)
+ return done
+
+ count = 5
+
+ for i in range(count):
+ inputter = (i % len(runtime.players)) + 1
+ if inputter == runtime.id:
+ a = rand.randint(0, self.Zp.modulus)
+ b = rand.randint(0, self.Zp.modulus)
+ else:
+ a, b = None, None
+ a_shares.append(runtime.input([inputter], self.Zp, a))
+ b_shares.append(runtime.input([inputter], self.Zp, b))
+ shares_ready = gather_shares(a_shares + b_shares)
+
+ runtime.schedule_callback(shares_ready, cont)
+ return shares_ready
Janus Dam Nielsen
2009-10-06 08:10:02 UTC
Permalink
# HG changeset patch
# User Janus Dam Nielsen <***@alexandra.dk>
# Date 1254816324 -7200
# Node ID eb0443115206dc4a50bfea300c5582613d26326a
# Parent a62e12c9947a9499dd293e2dce91992950505fee
Implementation of the basic multiplication command.

diff --git a/viff/orlandi.py b/viff/orlandi.py
--- a/viff/orlandi.py
+++ b/viff/orlandi.py
@@ -459,6 +459,22 @@
return results[0]
return results

+ def mul(self, share_x, share_y):
+ """Multiplication of shares.
+
+ Communication cost: ???.
+ """
+ # TODO: Communication cost?
+ assert isinstance(share_x, Share) or isinstance(share_y, Share), \
+ "At least one of share_x and share_y must be a Share."
+
+ self.program_counter[-1] += 1
+
+ field = getattr(share_x, "field", getattr(share_y, "field", None))
+
+ a, b, c = self._get_triple(field)
+ return self._basic_multiplication(share_x, share_y, a, b, c)
+
def _additive_constant(self, zero, field_element):
"""Greate an additive constant.

@@ -506,6 +522,102 @@
Cz = Cx / Cy
return (zi, (rhozi1, rhozi2), Cz)

+ def _cmul(self, share_x, share_y, field):
+ """Multiplication of a share with a constant.
+
+ Either share_x or share_y must be an OrlandiShare but not both.
+ Returns None if both share_x and share_y are OrlandiShares.
+
+ """
+ def constant_multiply(x, c):
+ assert(isinstance(c, FieldElement))
+ zi, rhoz, Cx = self._const_mul(c.value, x)
+ return OrlandiShare(self, field, zi, rhoz, Cx)
+ if not isinstance(share_x, Share):
+ # Then share_y must be a Share => local multiplication. We
+ # clone first to avoid changing share_y.
+ assert isinstance(share_y, Share), \
+ "At least one of the arguments must be a share."
+ result = share_y.clone()
+ result.addCallback(constant_multiply, share_x)
+ return result
+ if not isinstance(share_y, Share):
+ # Likewise when share_y is a constant.
+ assert isinstance(share_x, Share), \
+ "At least one of the arguments must be a share."
+ result = share_x.clone()
+ result.addCallback(constant_multiply, share_y)
+ return result
+ return None
+
+ def _const_mul(self, c, x):
+ """Multiplication of a share-tuple with a constant c."""
+ assert(isinstance(c, long) or isinstance(c, int))
+ xi, (rhoi1, rhoi2), Cx = x
+ zi = xi * c
+ rhoz = (rhoi1 * c, rhoi2 * c)
+ Cz = Cx**c
+ return (zi, rhoz, Cz)
+
+ def _get_triple(self, field):
+ n = field(0)
+ Ca = commitment.commit(6, 0, 0)
+ a = OrlandiShare(self, field, field(2), (n, n), Ca)
+ Cb = commitment.commit(12, 0, 0)
+ b = OrlandiShare(self, field, field(4), (n, n), Cb)
+ Cc = commitment.commit(72, 0, 0)
+ c = OrlandiShare(self, field, field(24), (n, n), Cc)
+ return (a, b, c)
+
+ def _basic_multiplication(self, share_x, share_y, triple_a, triple_b, triple_c):
+ """Multiplication of shares give a triple.
+
+ Communication cost: ???.
+
+ ``d = Open([x] - [a])``
+ ``e = Open([y] - [b])``
+ ``[z] = e[x] + d[y] - [de] + [c]``
+ """
+ assert isinstance(share_x, Share) or isinstance(share_y, Share), \
+ "At least one of share_x and share_y must be a Share."
+
+ self.program_counter[-1] += 1
+
+ field = getattr(share_x, "field", getattr(share_y, "field", None))
+ n = field(0)
+
+ cmul_result = self._cmul(share_x, share_y, field)
+ if cmul_result is not None:
+ return cmul_result
+
+ def multiply((x, y, d, e, c)):
+ # [de]
+ de = self._additive_constant(field(0), d * e)
+ # e[x]
+ t1 = self._const_mul(e.value, x)
+ # d[y]
+ t2 = self._const_mul(d.value, y)
+ # d[y] - [de]
+ t3 = self._minus(t2, de)
+ # d[y] - [de] + [c]
+ t4 = self._plus(t3, c)
+ # [z] = e[x] + d[y] - [de] + [c]
+ zi, rhoz, Cz = self._plus(t1, t4)
+ return OrlandiShare(self, field, zi, rhoz, Cz)
+
+ # d = Open([x] - [a])
+ d = self.open(share_x - triple_a)
+ # e = Open([y] - [b])
+ e = self.open(share_y - triple_b)
+ result = gather_shares([share_x, share_y, d, e, triple_c])
+ result.addCallbacks(multiply, self.error_handler)
+
+ # do actual communication
+ self.activate_reactor()
+
+ return result
+
def error_handler(self, ex):
print "Error: ", ex
return ex
+
diff --git a/viff/test/test_orlandi_runtime.py b/viff/test/test_orlandi_runtime.py
--- a/viff/test/test_orlandi_runtime.py
+++ b/viff/test/test_orlandi_runtime.py
@@ -19,7 +19,7 @@

from viff.test.util import RuntimeTestCase, protocol, BinaryOperatorTestCase
from viff.runtime import Share, gather_shares
-from viff.orlandi import OrlandiRuntime
+from viff.orlandi import OrlandiRuntime, OrlandiShare

from viff.field import FieldElement, GF
from viff.passive import PassiveRuntime
@@ -28,6 +28,18 @@

import commitment

+
+def _get_triple(runtime, field):
+ n = field(0)
+ Ca = commitment.commit(6, 0, 0)
+ a = OrlandiShare(runtime, field, field(2), (n, n), Ca)
+ Cb = commitment.commit(12, 0, 0)
+ b = OrlandiShare(runtime, field, field(4), (n, n), Cb)
+ Cc = commitment.commit(72, 0, 0)
+ c = OrlandiShare(runtime, field, field(24), (n, n), Cc)
+ return (a, b, c)
+
+
class OrlandiBasicCommandsTest(RuntimeTestCase):
"""Test for basic commands."""

@@ -281,7 +293,6 @@
d2.addCallback(check)
return DeferredList([d1, d2])

-
@protocol
def test_shift_two_consequtive_inputters(self, runtime):
"""Test addition of the shift command."""
@@ -339,3 +350,137 @@
shares_ready = gather_shares(a_shares + b_shares)
return shares_ready

+ @protocol
+ def test_basic_multiply(self, runtime):
+ """Test multiplication of two numbers."""
+
+ self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
+
+ x1 = 42
+ y1 = 7
+
+ def check(v):
+ self.assertEquals(v, x1 * y1)
+
+ x2 = runtime.shift([2], self.Zp, x1)
+ y2 = runtime.shift([3], self.Zp, y1)
+
+ a, b, c = _get_triple(self, self.Zp)
+ z2 = runtime._basic_multiplication(x2, y2, a, b, c)
+ d = runtime.open(z2)
+ d.addCallback(check)
+ return d
+
+ @protocol
+ def test_mul_mul(self, runtime):
+ """Test multiplication of two numbers."""
+
+ self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
+
+ x1 = 42
+ y1 = 7
+
+ def check(v):
+ self.assertEquals(v, x1 * y1)
+
+ x2 = runtime.shift([2], self.Zp, x1)
+ y2 = runtime.shift([3], self.Zp, y1)
+
+ z2 = x2 * y2
+ d = runtime.open(z2)
+ d.addCallback(check)
+ return d
+
+ @protocol
+ def test_basic_multiply_constant_right(self, runtime):
+ """Test multiplication of two numbers."""
+
+ self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
+
+ x1 = 42
+ y1 = 7
+
+ def check(v):
+ self.assertEquals(v, x1 * y1)
+
+ x2 = runtime.shift([1], self.Zp, x1)
+
+ a, b, c = _get_triple(self, self.Zp)
+ z2 = runtime._basic_multiplication(x2, self.Zp(y1), a, b, c)
+ d = runtime.open(z2)
+ d.addCallback(check)
+ return d
+
+ @protocol
+ def test_basic_multiply_constant_left(self, runtime):
+ """Test multiplication of two numbers."""
+
+ self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
+
+ x1 = 42
+ y1 = 7
+
+ def check(v):
+ self.assertEquals(v, x1 * y1)
+
+ x2 = runtime.shift([1], self.Zp, x1)
+
+ a, b, c = _get_triple(self, self.Zp)
+ z2 = runtime._basic_multiplication(self.Zp(y1), x2, a, b, c)
+ d = runtime.open(z2)
+ d.addCallback(check)
+ return d
+
+ @protocol
+ def test_constant_multiplication_constant_left(self, runtime):
+ """Test multiplication of two numbers."""
+
+ self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
+
+ x1 = 42
+ y1 = 7
+
+ def check(v):
+ self.assertEquals(v, x1 * y1)
+
+ x2 = runtime.shift([1], self.Zp, x1)
+
+ z2 = runtime._cmul(self.Zp(y1), x2, self.Zp)
+ d = runtime.open(z2)
+ d.addCallback(check)
+ return d
+
+ @protocol
+ def test_constant_multiplication_constant_right(self, runtime):
+ """Test multiplication of two numbers."""
+
+ self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
+
+ x1 = 42
+ y1 = 7
+
+ def check(v):
+ self.assertEquals(v, x1 * y1)
+
+ x2 = runtime.shift([1], self.Zp, x1)
+
+ z2 = runtime._cmul(x2, self.Zp(y1), self.Zp)
+ d = runtime.open(z2)
+ d.addCallback(check)
+ return d
+
+ @protocol
+ def test_constant_multiplication_constant_None(self, runtime):
+ """Test multiplication of two numbers."""
+
+ self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
+
+ x1 = 42
+ y1 = 7
+
+ x2 = runtime.shift([1], self.Zp, x1)
+ y2 = runtime.shift([1], self.Zp, y1)
+
+ z2 = runtime._cmul(y2, x2, self.Zp)
+ self.assertEquals(z2, None)
+ return z2
Janus Dam Nielsen
2009-10-06 08:10:04 UTC
Permalink
# HG changeset patch
# User Janus Dam Nielsen <***@alexandra.dk>
# Date 1254816324 -7200
# Node ID db2d970885f44d2cf18608c81f8422e87d97af8c
# Parent 86e0c7d54f2220bf03da45cf4269c88a7e6b777c
Implementation of the TripleGen protocol.

diff --git a/viff/orlandi.py b/viff/orlandi.py
--- a/viff/orlandi.py
+++ b/viff/orlandi.py
@@ -19,8 +19,9 @@

from viff.runtime import Runtime, Share, ShareList, gather_shares
from viff.util import rand
-from viff.constants import TEXT
+from viff.constants import TEXT, PAILLIER
from viff.field import FieldElement
+from viff.paillier import encrypt_r, decrypt

from hash_broadcast import HashBroadcastMixin

@@ -771,6 +772,200 @@

return result

+ def triple_gen(self, field):
+ """Generate a triple ``a, b, c`` s.t. ``c = a * b``.
+
+ 1) Every party ``P_i`` chooses random values ``a_i, r_i in Z_p X (Z_p)^2``,
+ compute ``alpha_i = Enc_eki(a_i)`` and ``Ai = Com_ck(a_i, r_i)``, and
+ broadcast them.
+
+ 2) Every party ``P_j`` does:
+ (a) choose random ``b_j, s_j in Z_p X (Z_p)^2``.
+
+ (b) compute ``B_j = ``Com_ck(b_j, s_j)`` and broadcast it.
+
+ (c) ``P_j`` do towards every other party:
+ i. choose random ``d_ij in Z_p^3``
+ ii. compute and send
+ ``gamma_ij = alpha_i^b_j Enc_ek_i(1;1)^d_ij`` to ``P_i``.
+
+ 3) Every party ``P_i`` does:
+ (a) compute ``c_i = SUM_j Dec_sk_i(gamma_ij) - SUM_j d_ij mod p``
+
+ (b) pick random ``t_i in (Z_p)^2``, compute and
+ broadcast ``C_i = Com_ck(c_i, t_i)``
+
+ 4) Everyone computes:
+ ``(A, B, C) = (PRODUCT_i A_i, PRODUCT_i B_i, PRODUCT_i C_i)``
+
+ 5) Every party ``P_i`` outputs shares ``[a_i] = (a_i, r_i, A)``,
+ ``[b_i] = (b_i, s_i, B)``, and ``[c_i] = (c_i, t_i, C)``.
+
+ """
+ self.program_counter[-1] += 1
+
+ def random_number(p):
+ return field(rand.randint(0, p - 1))
+
+ def product(ls):
+ """Compute the product of the elements in the list *ls*."""
+ b = commitment.deserialize(ls[0])
+ for x in ls[1:]:
+ b *= commitment.deserialize(x)
+ return b
+
+ def sum(ls):
+ """Compute the sum of the elements in the list *ls*."""
+ b = field(0)
+ for x in ls:
+ b += x
+ return b
+
+ def step45(Cs, alphas, gammas, alpha_randomness,
+ As, Bs, ai, bi, ci, r, s, t, dijs):
+ """4) Everyone computes:
+ ``A = PRODUCT_i A_i``
+ ``B = PRODUCT_i B_i``
+ ``C = PRODUCT_i C_i``
+
+ 5) Every party ``P_i`` outputs shares ``[a_i] = (a_i, r_i, A)``,
+ ``[b_i] = (b_i, s_i, B)``, and ``[c_i] = (c_i, t_i, C)``.
+ """
+ A = product(As)
+ B = product(Bs)
+ C = product(Cs)
+ a = OrlandiShare(self, field, ai, r, A)
+ b = OrlandiShare(self, field, bi, s, B)
+ c = OrlandiShare(self, field, ci, t, C)
+ return (a, b, c, (alphas, alpha_randomness, gammas, dijs))
+
+ def decrypt_gammas(ls):
+ """Decrypt all the elements of the list *ls*."""
+ rs = []
+ for x in ls:
+ rs.append(field(decrypt(x, self.players[self.id].seckey)))
+ return rs
+
+ def step3(gammas, alphas, alpha_randomness, As, Bs, ai, bi, r, s, dijs):
+ """3) Every party ``P_i`` does:
+ (a) compute
+ ``c_i = SUM_j Dec_sk_i(gamma_ij) - SUM_j d_ji mod p``
+
+ (b) pick random ``t_i in (Z_p)^2``, compute and
+ broadcast ``C_i = Com_ck(c_i, t_i)``
+ """
+ # c_i = SUM_j Dec_sk_i(gamma_ij) - SUM_j d_ji mod p.
+ ls = decrypt_gammas(gammas)
+ ci = sum(ls) - sum(dijs)
+ # (b) pick random t_i in (Z_p)^2.
+ t1 = random_number(field. modulus)
+ t2 = random_number(field. modulus)
+ t = (t1, t2)
+ # C_i = Com_ck(c_i, t_i).
+ Ci = commitment.commit(ci.value, t1.value, t2.value)
+
+ # Broadcast Ci.
+ Cs = self.broadcast(self.players.keys(), self.players.keys(), repr(Ci))
+ result = gatherResults(Cs)
+ result.addCallbacks(step45, self.error_handler, callbackArgs=(alphas, gammas, alpha_randomness,
+ As, Bs, ai, bi, ci, r, s, t, dijs))
+ return result
+
+ def step2c(Bs, As, alphas, alpha_randomness, ai, bj, r, s):
+ """(c) P_j do, towards every other party:
+ i. choose random d_i,j in Z_p^3
+ ii. compute and send
+ gamma_ij = alpha_i^b_j Enc_ek_i(1;1)^d_ij to P_i.
+ """
+
+ # (c) P_j do, towards every other party:
+ dijs = [None] * len(self.players.keys())
+ results = [None] * len(self.players.keys())
+ pc = tuple(self.program_counter)
+ for pi in self.players.keys():
+ n = self.players[pi].pubkey[0]
+ nsq = n * n
+ # choose random d_i,j in Z_p^3
+ dij = random_number(field.modulus**3)
+ # Enc_ek_i(1;1)^d_ij
+ enc = encrypt_r(1, 1, self.players[pi].pubkey)
+ t1 = pow(enc, dij.value, nsq)
+ # alpha_i^b_j.
+ t2 = pow(alphas[pi - 1], bj.value, nsq)
+ # gamma_ij = alpha_i^b_j Enc_ek_i(1;1)^d_ij
+ gammaij = (t2) * (t1) % nsq
+ # Broadcast gamma_ij
+ if pi != self.id:
+ self.protocols[pi].sendData(pc, PAILLIER, str(gammaij))
+ d = Deferred()
+ d.addCallbacks(lambda value: long(value), self.error_handler)
+ self._expect_data(pi, PAILLIER, d)
+ else:
+ d = Deferred()
+ d.callback(gammaij)
+ dijs[pi - 1] = dij
+ results[pi - 1] = d
+ result = gatherResults(results)
+ self.schedule_callback(result, step3, alphas, alpha_randomness,
+ As, Bs, ai, bj, r, s, dijs)
+ result.addErrback(self.error_handler)
+ return result
+
+ def step2ab((alphas, As), ai, r, alpha_randomness):
+ """2) Every party P_j does:
+ (a) choose random b_j, s_j in Z_p X (Z_p)^2.
+
+ (b) compute B_j = Com_ck(b_j, s_j) and broadcast it.
+ """
+ # (a) choose random b_j, s_j in Z_p X (Z_p)^2.
+ bj = random_number(field.modulus)
+ s1 = random_number(field.modulus)
+ s2 = random_number(field.modulus)
+ # (b) compute B_j = Com_ck(b_j, s_j).
+ Bj = commitment.commit(bj.value, s1.value, s2.value)
+
+ # Broadcast B_j.
+ results = self.broadcast(self.players.keys(), self.players.keys(), repr(Bj))
+ result = gatherResults(results)
+ self.schedule_callback(result, step2c, As, alphas, alpha_randomness,
+ ai, bj, r, (s1, s2))
+ result.addErrback(self.error_handler)
+ return result
+
+ # 1) Every party P_i chooses random values a_i, r_i in Z_p X (Z_p)^2,
+ # compute alpha_i = Enc_eki(a_i) and Ai = Com_ck(a_i, r_i), and
+ # broadcast them.
+
+ # Every party P_i chooses random values a_i, r_i in Z_p X (Z_p)^2
+ ai = random_number(field.modulus)
+ r1 = random_number(field.modulus)
+ r2 = random_number(field.modulus)
+
+ # compute alpha_i = Enc_eki(a_i)
+ n, g = self.players[self.id].pubkey
+ alpha_randomness = rand.randint(1, long(n))
+ alphai = encrypt_r(ai.value, alpha_randomness, (n, g))
+ # and A_i = Com_ck(a_i, r_i).
+ Ai = commitment.commit(ai.value, r1.value, r2.value)
+
+ # broadcast alpha_i and A_i.
+ ds = self.broadcast(sorted(self.players.keys()), sorted(self.players.keys()), str(alphai) + ":" + repr(Ai))
+
+ result = gatherResults(ds)
+ def split_alphas_and_As(ls):
+ alphas = []
+ As = []
+ for x in ls:
+ alpha, Ai = x.split(':')
+ alphas.append(long(alpha))
+ As.append(Ai)
+ return alphas, As
+ self.schedule_callback(result, split_alphas_and_As)
+ self.schedule_callback(result, step2ab, ai, (r1, r2), alpha_randomness)
+ result.addErrback(self.error_handler)
+ return result
+
+
def error_handler(self, ex):
print "Error: ", ex
return ex
diff --git a/viff/test/test_orlandi_runtime.py b/viff/test/test_orlandi_runtime.py
--- a/viff/test/test_orlandi_runtime.py
+++ b/viff/test/test_orlandi_runtime.py
@@ -567,3 +567,60 @@
z2 = runtime._cmul(y2, x2, self.Zp)
self.assertEquals(z2, None)
return z2
+
+
+class TripleGenTest(RuntimeTestCase):
+ """Test for generation of triples."""
+
+ # Number of players.
+ num_players = 3
+
+ runtime_class = OrlandiRuntime
+
+ timeout = 240
+
+ @protocol
+ def test_tripleGen(self, runtime):
+ """Test the triple_gen command."""
+
+ self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
+
+ def check((a, b, c)):
+ self.assertEquals(c, a * b)
+
+ def open((a, b, c, _)):
+ d1 = runtime.open(a)
+ d2 = runtime.open(b)
+ d3 = runtime.open(c)
+ d = gatherResults([d1, d2, d3])
+ d.addCallback(check)
+ return d
+ d = runtime.triple_gen(self.Zp)
+ d.addCallbacks(open, runtime.error_handler)
+ return d
+
+ @protocol
+ def test_tripleGen2(self, runtime):
+ """Test the triple_gen command."""
+
+ self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
+
+ def check((a, b, c, dx, dy, dz)):
+ self.assertEquals(c, a * b)
+ self.assertEquals(dz, dx * dy)
+
+ def open(((a, b, c, control), (x, y, z, _))):
+ d1 = runtime.open(a)
+ d2 = runtime.open(b)
+ d3 = runtime.open(c)
+ dx = runtime.open(x)
+ dy = runtime.open(y)
+ dz = runtime.open(z)
+ d = gatherResults([d1, d2, d3, dx, dy, dz])
+ d.addCallback(check)
+ return d
+ t1 = runtime.triple_gen(self.Zp)
+ t2 = runtime.triple_gen(self.Zp)
+ d = gatherResults([t1, t2])
+ d.addCallbacks(open, runtime.error_handler)
+ return d
Janus Dam Nielsen
2009-10-06 08:10:10 UTC
Permalink
# HG changeset patch
# User Janus Dam Nielsen <***@alexandra.dk>
# Date 1254816324 -7200
# Node ID dd15e514cbb0a59f8cf06caa55064cccde3f9b41
# Parent 2dabe8c91e557603cbfeb84d39f892f6bf4e773f
importeret rettelse autopreprocessing.patch

diff --git a/apps/benchmark.py b/apps/benchmark.py
--- a/apps/benchmark.py
+++ b/apps/benchmark.py
@@ -63,6 +63,7 @@
import viff.reactor
viff.reactor.install()
from twisted.internet import reactor
+from twisted.internet.defer import Deferred

from viff.field import GF, GF256, FakeGF
from viff.runtime import Runtime, create_runtime, gather_shares, \
@@ -87,12 +88,13 @@
print "Started", what


-def record_stop(_, what):
+def record_stop(x, what):
stop = time.time()
print
print "Total time used: %.3f sec" % (stop-start)
print "Time per %s operation: %.0f ms" % (what, 1000*(stop-start) / count)
print "*" * 6
+ return x

operations = {"mul": (operator.mul,[]),
"compToft05": (operator.ge, [ComparisonToft05Mixin]),
@@ -116,7 +118,7 @@
help="the name of the basic runtime to test")
parser.add_option("-n", "--num_players", action="store_true", dest="num_players",
help="number of players")
-parser.add_option("--mixins", type="choice", choices=mixins.keys(),
+parser.add_option("--mixins", type="string",
help="operation to benchmark")
parser.add_option("--prss", action="store_true",
help="use PRSS for preprocessing")
@@ -138,7 +140,7 @@
help="additional arguments to the runtime, the format is a comma separated list of id=value pairs e.g. --args s=1,d=0,lambda=1")

parser.set_defaults(modulus=2**65, threshold=1, count=10,
- runtime=runtimes.keys()[0], mixins=mixins.keys(), num_players=2, prss=True,
+ runtime=runtimes.keys()[0], mixins="", num_players=2, prss=True,
operation=operations.keys()[0], parallel=True, fake=False)

# Add standard VIFF options.
@@ -174,53 +176,43 @@
def __init__(self, rt, operation):
self.rt = rt
self.operation = operation
- self.sync_preprocess()
-
- def sync_preprocess(self):
- print "Synchronizing preprocessing"
+ self.pc = None
sys.stdout.flush()
sync = self.rt.synchronize()
+ self.doTest(sync, lambda x: x)
self.rt.schedule_callback(sync, self.preprocess)
+ self.doTest(sync, lambda x: self.rt.shutdown())
+
+# def sync_preprocess(self):
+# print "Synchronizing preprocessing"
+# sys.stdout.flush()
+# sync = self.rt.synchronize()
+# self.rt.schedule_callback(sync, self.preprocess)

- def preprocess(self, _):
- program_desc = {}
-
- if isinstance(self.rt, BasicActiveRuntime):
- # TODO: Make this optional and maybe automatic. The
- # program descriptions below were found by carefully
- # studying the output reported when the benchmarks were
- # run with no preprocessing. So they are quite brittle.
- if self.operation == operator.mul:
- key = ("generate_triples", (Zp,))
- desc = [(i, 1, 0) for i in range(3, 3 + count)]
- program_desc.setdefault(key, []).extend(desc)
- elif isinstance(self.rt, ComparisonToft05Mixin):
- key = ("generate_triples", (GF256,))
- desc = sum([[(c, 64, i, 1, 1, 0) for i in range(2, 33)] +
- [(c, 64, i, 3, 1, 0) for i in range(17, 33)]
- for c in range(3 + 2*count, 3 + 3*count)],
- [])
- program_desc.setdefault(key, []).extend(desc)
- elif isinstance(self.rt, ComparisonToft07Mixin):
- key = ("generate_triples", (Zp,))
- desc = sum([[(c, 2, 4, i, 2, 1, 0) for i in range(1, 33)] +
- [(c, 2, 4, 99, 2, 1, 0)] +
- [(c, 2, 4, i, 1, 0) for i in range(65, 98)]
- for c in range(3 + 2*count, 3 + 3*count)],
- [])
- program_desc.setdefault(key, []).extend(desc)
-
- if program_desc:
+ def preprocess(self, needed_data):
+ print "Preprocess", needed_data
+ if needed_data:
print "Starting preprocessing"
record_start("preprocessing")
- preproc = self.rt.preprocess(program_desc)
+ preproc = self.rt.preprocess(needed_data)
preproc.addCallback(record_stop, "preprocessing")
- self.rt.schedule_callback(preproc, self.begin)
+ return preproc
else:
print "Need no preprocessing"
- self.begin(None)
+ return None
+
+ def doTest(self, d, termination_function):
+ print "doTest", self.rt.program_counter
+ self.rt.schedule_callback(d, self.begin)
+ self.rt.schedule_callback(d, self.sync_test)
+# self.rt.schedule_callback(d, self.countdown, 3)
+ self.rt.schedule_callback(d, self.run_test)
+ self.rt.schedule_callback(d, self.sync_test)
+ self.rt.schedule_callback(d, self.finished, termination_function)
+ return d

def begin(self, _):
+ print "begin", self.rt.program_counter
print "Runtime ready, generating shares"
self.a_shares = []
self.b_shares = []
@@ -234,43 +226,49 @@
self.a_shares.append(self.rt.input([inputter], Zp, a))
self.b_shares.append(self.rt.input([inputter], Zp, b))
shares_ready = gather_shares(self.a_shares + self.b_shares)
- self.rt.schedule_callback(shares_ready, self.sync_test)
+ return shares_ready

- def sync_test(self, _):
+ def sync_test(self, x):
print "Synchronizing test start."
sys.stdout.flush()
sync = self.rt.synchronize()
- self.rt.schedule_callback(sync, self.countdown, 3)
+ self.rt.schedule_callback(sync, lambda y: x)
+ return sync

- def countdown(self, _, seconds):
- if seconds > 0:
- print "Starting test in %d" % seconds
- sys.stdout.flush()
- reactor.callLater(1, self.countdown, None, seconds - 1)
- else:
- print "Starting test now"
- sys.stdout.flush()
- self.run_test(None)
+# def countdown(self, _, seconds):
+# if seconds > 0:
+# print "Starting test in %d" % seconds
+# sys.stdout.flush()
+# reactor.callLater(1, self.countdown, None, seconds - 1)
+# else:
+# print "Starting test now"
+# sys.stdout.flush()
+# self.run_test(None)

def run_test(self, _):
raise NotImplemented("Override this abstract method in a sub class.")

- def finished(self, _):
+ def finished(self, needed_data, termination_function):
sys.stdout.flush()

if self.rt._needed_data:
print "Missing pre-processed data:"
- for (func, args), pcs in self.rt._needed_data.iteritems():
+ for (func, args), pcs in needed_data.iteritems():
print "* %s%s:" % (func, args)
print " " + pformat(pcs).replace("\n", "\n ")

- self.rt.shutdown()
+ return termination_function(needed_data)

# This class implements a benchmark where run_test executes all
# operations in parallel.
class ParallelBenchmark(Benchmark):

- def run_test(self, _):
+ def run_test(self, shares):
+ print "rt", self.rt.program_counter, self.pc
+ if self.pc != None:
+ self.rt.program_counter = self.pc
+ else:
+ self.pc = list(self.rt.program_counter)
c_shares = []
record_start("parallel test")
while self.a_shares and self.b_shares:
@@ -280,24 +278,30 @@

done = gather_shares(c_shares)
done.addCallback(record_stop, "parallel test")
- self.rt.schedule_callback(done, self.finished)
+ def f(x):
+ needed_data = self.rt._needed_data
+ self.rt._needed_data = {}
+ return needed_data
+ done.addCallback(f)
+ return done
+

# A benchmark where the operations are executed one after each other.
class SequentialBenchmark(Benchmark):

- def run_test(self, _):
+ def run_test(self, _, termination_function, d):
record_start("sequential test")
- self.single_operation(None)
+ self.single_operation(None, termination_function)

- def single_operation(self, _):
+ def single_operation(self, _, termination_function):
if self.a_shares and self.b_shares:
a = self.a_shares.pop()
b = self.b_shares.pop()
c = self.operation(a, b)
- self.rt.schedule_callback(c, self.single_operation)
+ self.rt.schedule_callback(c, self.single_operation, termination_function)
else:
record_stop(None, "sequential test")
- self.finished(None)
+ self.finished(None, termination_function)

# Identify the base runtime class.
base_runtime_class = runtimes[options.runtime]
diff --git a/viff/active.py b/viff/active.py
--- a/viff/active.py
+++ b/viff/active.py
@@ -378,11 +378,11 @@
def get_triple(self, field):
# This is a waste, but this function is only called if there
# are no pre-processed triples left.
- count, result = self.generate_triples(field)
+ count, result = self.generate_triples(field, None)
result.addCallback(lambda triples: triples[0])
return result

- def generate_triples(self, field):
+ def generate_triples(self, field, number_of_requested_triples):
"""Generate multiplication triples.

These are random numbers *a*, *b*, and *c* such that ``c =
@@ -423,11 +423,11 @@

@preprocess("generate_triples")
def get_triple(self, field):
- count, result = self.generate_triples(field)
+ count, result = self.generate_triples(field, None)
result.addCallback(lambda triples: triples[0])
return result

- def generate_triples(self, field):
+ def generate_triples(self, field, number_of_requested_triples):
"""Generate a multiplication triple using PRSS.

These are random numbers *a*, *b*, and *c* such that ``c =
diff --git a/viff/runtime.py b/viff/runtime.py
--- a/viff/runtime.py
+++ b/viff/runtime.py
@@ -475,17 +475,21 @@
"""

def preprocess_decorator(method):
-
@wrapper(method)
def preprocess_wrapper(self, *args, **kwargs):
pc = tuple(self.program_counter)
try:
+ self.program_counter[-1] += 1
return self._pool[pc]
except KeyError:
- key = (generator, args)
- pcs = self._needed_data.setdefault(key, [])
- pcs.append(pc)
- return method(self, *args, **kwargs)
+ try:
+ key = (generator, args)
+ pcs = self._needed_data.setdefault(key, [])
+ pcs.append(pc)
+ self.program_counter.append(0)
+ return method(self, *args, **kwargs)
+ finally:
+ self.program_counter.pop()

return preprocess_wrapper
return preprocess_decorator
@@ -808,6 +812,9 @@
func = getattr(self, generator)
results = []
items = 0
+ args = list(args)
+ args.append(len(program_counters))
+ args = tuple(args)
while items < len(program_counters):
item_count, result = func(*args)
items += item_count
Janus Dam Nielsen
2009-10-06 08:10:06 UTC
Permalink
# HG changeset patch
# User Janus Dam Nielsen <***@alexandra.dk>
# Date 1254816324 -7200
# Node ID abe7f8ef29b1620b69666ff34bae3e8cdb469f8a
# Parent 04d228359cee302716040a5eebee38c46980a1b3
importeret rettelse triple_combiner.patch

diff --git a/viff/orlandi.py b/viff/orlandi.py
--- a/viff/orlandi.py
+++ b/viff/orlandi.py
@@ -55,6 +55,9 @@
"""

def __init__(self, runtime, field, value=None, rho=None, commitment=None):
+ self.share = value
+ self.rho = rho
+ self.commitment = commitment
Share.__init__(self, runtime, field, (value, rho, commitment))


@@ -81,6 +84,9 @@
"""Initialize runtime."""
Runtime.__init__(self, player, threshold, options)
self.threshold = self.num_players - 1
+ self.s = 1
+ self.d = 0
+ self.s_lambda = 1

def compute_delta(self, d):
def product(j):
@@ -1005,6 +1011,293 @@

return result

+ def random_triple(self, field):
+ """Generate a list of triples ``(a, b, c)`` where ``c = a * b``.
+
+ The triple ``(a, b, c)`` is secure in the Fcrs-hybrid model.
+
+ """
+ self.program_counter[-1] += 1
+
+ number_of_multiplications = 1
+ M = []
+
+ for x in xrange((1 + self.s_lambda) * (2 * self.d + 1) * number_of_multiplications):
+ M.append(self.triple_test(field))
+
+ def step3(ls):
+ """Coin-flip a subset test_set of M of size lambda(2d + 1)M."""
+ size = self.s_lambda * (2 * self.d + 1) * number_of_multiplications
+ inx = 0
+ p_half = field.modulus // 2
+ def coin_flip(v, ls, test_set):
+ candidate = ls.pop(0)
+ if p_half > v:
+ test_set.append(candidate)
+ else:
+ ls.append(candidate)
+ if size > len(test_set):
+ r = self.random_share(field)
+ r = self.output(r)
+ self.schedule_callback(r, coin_flip, ls, test_set)
+ r.addErrback(self.error_handler)
+ return r
+ return ls, test_set
+ r = self.random_share(field)
+ r = self.output(r)
+ self.schedule_callback(r, coin_flip, ls, [])
+ r.addErrback(self.error_handler)
+ return r
+
+ def step45(lists):
+ """For all i in test_set the parties reveal
+ the randomness used for TripleTest() and checks that
+ the randomness is consistent with the actual values."""
+ M_without_test_set = lists[0]
+ T = lists[1]
+
+ def defer_share(xi, (rho1, rho2), commitment):
+ d1 = Deferred()
+ d2 = Deferred()
+ d3 = Deferred()
+ d4 = Deferred()
+ d1.callback(xi)
+ d2.callback(rho1)
+ d3.callback(rho2)
+ d4.callback(commitment)
+ return gatherResults([d1, d2, d3, d4])
+
+ def get_share(x, ls):
+ share = ls[x * 4]
+ rho1 = ls[x * 4 + 1]
+ rho2 = ls[x * 4 + 2]
+ commitment = ls[x * 4 + 3]
+ return (share, rho1, rho2, commitment)
+
+ def send_share(player_id, pc, a):
+ self._send_orlandi_share(player_id, pc, a.share, a.rho, a.commitment)
+
+ def receive_shares(player_id):
+ Cx = Deferred()
+ xi = self._expect_share(player_id, field)
+ rho1 = self._expect_share(player_id, field)
+ rho2 = self._expect_share(player_id, field)
+ self._expect_data(player_id, TEXT, Cx)
+ Cx.addCallbacks(lambda Cx: commitment.deserialize(Cx),
+ self.error_handler)
+ return gatherResults([xi, rho1, rho2, Cx])
+
+ def send_long(player_id, pc, l):
+ self.protocols[player_id].sendData(pc, TEXT, str(l))
+
+ def receive_long(player_id):
+ l = Deferred()
+ self._expect_data(player_id, TEXT, l)
+ l.addCallbacks(lambda x: long(x), self.error_handler)
+ return l
+
+ def defer_value(l):
+ d = Deferred()
+ d.callback(l)
+ return d
+
+ def check((ais, bis, cis, alpha_randomness, dijs), alphas, gammas):
+ """So if B receives ai, bi, dij, ri, si, and the randomness used in the
+ computation of alpha, he then checks that:
+ 1) the alpha_i he received is equals to the encryption of ai and the
+ commitment he received, Ai, is equal to the commitment of ai and ri
+ 2) the commitment he received, Bj, is equal to the commitment of bj and sj
+ 3) the gammaij he received is equal to the gammaij he now computes based on
+ the values he reveives
+ 4) a, b, c is a triple, a * b = c
+ 5) ai, bi < p and dij < p^3
+ """
+ a = 0
+ a_rho1 = 0
+ a_rho2 = 0
+ b = 0
+ b_rho1 = 0
+ b_rho2 = 0
+ c = 0
+ c_rho1 = 0
+ c_rho2 = 0
+
+ for x in xrange(len(ais)):
+ (ai, a_rhoi1, a_rhoi2, A) = ais[x]
+ (bi, b_rhoi1, b_rhoi2, B) = bis[x]
+ (ci, c_rhoi1, c_rhoi2, C) = cis[x]
+ # 5) ai, bi < p...
+ if ai >= field.modulus:
+ raise OrlandiException("Inconsistent share ai, ai >= p: %i" % ai)
+ if bi >= field.modulus:
+ raise OrlandiException("Inconsistent share bi, bi >= p: %i" % bi)
+ a += ai
+ a_rho1 += a_rhoi1
+ a_rho2 += a_rhoi2
+ b += bi
+ b_rho1 += b_rhoi1
+ b_rho2 += b_rhoi2
+ c += ci
+ c_rho1 += c_rhoi1
+ c_rho2 += c_rhoi2
+ # 1) the alpha_i he received is equals to the encryption of ai...
+ alphai = encrypt_r(ai.value, alpha_randomness[x],
+ self.players[x + 1].pubkey)
+ if not(alphas[x] == alphai):
+ raise OrlandiException("Inconsistent alpha from player %i, %i, %i" % (x + 1, alphas[x], alphai))
+
+ A1 = commitment.commit(a.value, a_rho1.value, a_rho2.value)
+ B1 = commitment.commit(b.value, b_rho1.value, b_rho2.value)
+ C1 = commitment.commit(c.value, c_rho1.value, c_rho2.value)
+
+ # 1) ... and the commitment he received, Ai, is equal
+ # to the commitment of ai and ri.
+ if A1 != A:
+ raise OrlandiException("Inconsistent commitment for value %s, found %s expected %s." % (a, A1, A))
+ # 2) the commitment he received, Bj, is equal to the commitment of bj and sj.
+ if B1 != B:
+ raise OrlandiException("Inconsistent commitment for value %s, found %s expected %s." % (b, B1, B))
+ if C1 != C:
+ raise OrlandiException("Inconsistent commitment for value %s, found %s expected %s." % (c, C1, C))
+ # 4) a, b, c is a triple, a * b = c
+ if a * b != c:
+ raise OrlandiException("Inconsistent triple, %i * %i does not equals %i." % (a, b, c))
+
+
+ # 3) the gammaij he received is equal to the gammaij he now computes based on
+ # the values he reveives
+ for j in xrange(len(ais)):
+ n = self.players[self.id].pubkey[0]
+ nsq = n * n
+ dij = dijs[j]
+ # 5) ... and dij < p^3.
+ if dij >= (field.modulus**3):
+ raise OrlandiException("Inconsistent random value dij %i from player %i" % (dij, j + 1))
+ # Enc_ek_i(1;1)^d_ij
+ enc = encrypt_r(1, 1, self.players[self.id].pubkey)
+ t1 = pow(enc, dij.value, nsq)
+ # alpha_i^b_j.
+ t2 = pow(alphas[self.id - 1], bis[j][0].value, nsq)
+ # gamma_ij = alpha_i^b_j Enc_ek_i(1;1)^d_ij
+ gammaij = (t2) * (t1) % nsq
+ if gammaij != gammas[j]:
+ raise OrlandiException("Inconsistent gammaij, %i, %i" % (gammaij, gammas[j]))
+
+ return True
+
+ dls_all = []
+ for (a, b, c, (alphas, alpha_randomness, gammas, dijs)) in T:
+ ds_a = [None] * len(self.players)
+ ds_b = [None] * len(self.players)
+ ds_c = [None] * len(self.players)
+ ds_alpha_randomness = [None] * len(self.players)
+ ds_dijs = [None] * len(self.players)
+ pc = tuple(self.program_counter)
+
+ for player_id in xrange(1, len(self.players.keys()) + 1):
+ if player_id == self.id:
+ ds_a[player_id - 1] = defer_share(a.share, a.rho, a.commitment)
+ ds_b[player_id - 1] = defer_share(b.share, b.rho, b.commitment)
+ ds_c[player_id - 1] = defer_share(c.share, c.rho, c.commitment)
+ ds_alpha_randomness[player_id - 1] = defer_value(alpha_randomness)
+ ds_dijs[player_id - 1] = defer_value(dijs[player_id - 1])
+ # Receive and recombine shares if this player is a receiver.
+ else:
+ send_share(player_id, pc, a)
+ send_share(player_id, pc, b)
+ send_share(player_id, pc, c)
+ send_long(player_id, pc, alpha_randomness)
+ self.protocols[player_id].sendShare(pc, dijs[player_id - 1])
+
+ ds_a[player_id - 1] = receive_shares(player_id)
+ ds_b[player_id - 1] = receive_shares(player_id)
+ ds_c[player_id - 1] = receive_shares(player_id)
+ ds_alpha_randomness[player_id - 1] = receive_long(player_id)
+ ds_dijs[player_id - 1] = self._expect_share(player_id, field)
+ dls_a = gatherResults(ds_a)
+ dls_b = gatherResults(ds_b)
+ dls_c = gatherResults(ds_c)
+ dls_dijs = gatherResults(ds_dijs)
+ dls_alpha_randomness = gatherResults(ds_alpha_randomness)
+
+ dls = gatherResults([dls_a, dls_b, dls_c, dls_alpha_randomness, dls_dijs])
+ dls.addCallbacks(check, self.error_handler, callbackArgs=[alphas, gammas])
+ dls_all.append(dls)
+
+ def result(x):
+ ls = []
+ for a, b, c, _ in M_without_test_set:
+ ls.append((a, b, c))
+ return ls
+
+ dls_all = gatherResults(dls_all)
+ dls_all.addCallbacks(result, self.error_handler)
+ return dls_all
+
+ def step6(M_without_test_set):
+ """Partition M without test_set in number_of_multiplications
+ random subsets M_i of size (2d + 1).
+ """
+ subsets = []
+ size = 2 * self.d + 1
+ for x in xrange(number_of_multiplications):
+ subsets.append([])
+
+ def put_in_set(v, M_without_test_set, subsets):
+ if 0 == len(M_without_test_set):
+ return subsets
+ v = v.value % number_of_multiplications
+ if size > len(subsets[v]):
+ subsets[v].append(M_without_test_set.pop(0))
+ r = self.random_share(field)
+ r = self.output(r)
+ self.schedule_callback(r, put_in_set, M_without_test_set, subsets)
+ r.addErrback(self.error_handler)
+ return r
+ r = self.random_share(field)
+ r = self.output(r)
+ self.schedule_callback(r, put_in_set, M_without_test_set, subsets)
+ r.addErrback(self.error_handler)
+ return r
+
+
+ def step7(Msets):
+ """For i = 1,...,M do:
+ a) [a] <- Fpp(rand,...), [b] <- Fpp(rand,...)
+ b) [r] <- Fpp(rand,...),
+ c) [c] <- LTMUL([a], [b], M_i)
+ d) Open([c] + [r])
+ """
+ ds = []
+ for Mi in Msets:
+ a = self.random_share(field)
+ b = self.random_share(field)
+ r = self.random_share(field)
+ c = self.leak_tolerant_mul(a, b, Mi)
+ d = self.open(c + r)
+ def return_abc(x, a, b, c):
+ return a, b, c
+ d.addCallbacks(return_abc, self.error_handler, callbackArgs=(a, b, c))
+ ds.append(d)
+ result = gather_shares(ds)
+ def triples(ls):
+ return ls
+ result.addCallbacks(triples, self.error_handler)
+ return result
+
+ result = gatherResults(M)
+ self.schedule_callback(result, step3)
+ result.addErrback(self.error_handler)
+ self.schedule_callback(result, step45)
+ self.schedule_callback(result, step6)
+ self.schedule_callback(result, step7)
+
+ # do actual communication
+ self.activate_reactor()
+
+ return result
+
+
def error_handler(self, ex):
print "Error: ", ex
return ex
diff --git a/viff/test/test_orlandi_runtime.py b/viff/test/test_orlandi_runtime.py
--- a/viff/test/test_orlandi_runtime.py
+++ b/viff/test/test_orlandi_runtime.py
@@ -548,8 +548,8 @@
x1 = 42
y1 = 7

- d = 4
-
+ runtime.d = 2
+
def check(v):
self.assertEquals(v, x1 * y1)

@@ -557,7 +557,7 @@
y2 = runtime.shift([2], self.Zp, y1)

M = []
- for j in xrange(1, 2*d + 2):
+ for j in xrange(1, 2*runtime.d + 2):
M.append(_get_triple(self, self.Zp))
z2 = runtime.leak_tolerant_mul(x2, y2, M)
d = runtime.open(z2)
@@ -577,7 +577,7 @@

runtime_class = OrlandiRuntime

- timeout = 240
+ timeout = 1600

@protocol
def test_tripleGen(self, runtime):
@@ -645,3 +645,34 @@
d = runtime.triple_test(self.Zp)
d.addCallbacks(open, runtime.error_handler)
return d
+
+ @protocol
+ def test_random_triple(self, runtime):
+ """Test the triple_combiner command."""
+
+ self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
+
+ def check(ls):
+ for x in xrange(len(ls) // 3):
+ a = ls[x * 3]
+ b = ls[x * 3 + 1]
+ c = ls[x * 3 + 2]
+ self.assertEquals(c, a * b)
+
+ def open(ls):
+ ds = []
+ for (a, b, c) in ls:
+ d1 = runtime.open(a)
+ d2 = runtime.open(b)
+ d3 = runtime.open(c)
+ ds.append(d1)
+ ds.append(d2)
+ ds.append(d3)
+
+ d = gatherResults(ds)
+ d.addCallback(check)
+ return d
+ d = runtime.random_triple(self.Zp)
+ d.addCallbacks(open, runtime.error_handler)
+ return d
+

Loading...