gmane.comp.cryptography.viff.patches
http://blog.gmane.org/gmane.comp.cryptography.viff.patches
hourly11901-01-01T00:00+00:00Gmanehttp://gmane.org/img/gmane-25t.png
http://gmane.org
[Fwd: [PATCH 1 of 1] Added computation-id option]
http://permalink.gmane.org/gmane.comp.cryptography.viff.patches/161
<pre>
-------- Original Message --------
Subject: [PATCH 1 of 1] Added computation-id option
Date: Wed, 04 Aug 2010 12:17:43 -0000
From: Thomas P Jakobsen <tpj< at >cs.au.dk>
To: mkeller< at >cs.au.dk
CC: ttoft< at >cs.au.dk
References: <patchbomb.1280924262< at >dhcp-11-67-32.daimi.au.dk>
# HG changeset patch
# User Tomas Toft <ttoft< at >cs.au.dk>
# Date 1280227043 -7200
# Node ID 7c45463151f482ff75bbd877dad3509e8f9cb3c9
# Parent e7b2fe7eb75319e2f60cc292b0d68fe568d394ab
Added computation-id option.
This changeset adds a command line option to VIFF allowing users to
specify a computation id.
Prior to this changeset, any computation involving pseudo-random
secret sharing (which for the time being boils down to computations
done with the PassiveRuntime) could only be run one time using the
same set of VIFF player configuration files. If more than one
computation was executed with the same set of configuration files, the
security of the system would be broken.
With this changeset, multiple computations can be run securely with
the same set of configuration files as long as each computation is run
with a unique computation id.
diff -r e7b2fe7eb753 -r 7c45463151f4 viff/runtime.py
--- a/viff/runtime.pyThu Jul 29 15:58:52 2010 +0200
+++ b/viff/runtime.pyTue Jul 27 12:37:23 2010 +0200
< at >< at > -536,6 +536,10 < at >< at >
"multiple times on the command line; the
first will "
"override host and port of player 1, the
second that "
"of player 2, and so forth.")
+ group.add_option("--computation-id", type="int", metavar="ID",
+ help="Set the (positive, integer) ID for this "
+ "computation. Must be unique to ensure "
+ "security.")
try:
# Using __import__ since we do not use the module, we are
< at >< at > -551,7 +555,8 < at >< at >
deferred_debug=False,
profile=False,
track_memory=False,
- statistics=False)
+ statistics=False,
+ computation_id=None)
def __init__(self, player, threshold, options=None):
"""Initialize runtime.
< at >< at > -585,7 +590,12 < at >< at >
self._needed_data = {}
#: Current program counter.
- self.program_counter = [0]
+ __comp_id = self.options.computation_id
+ if __comp_id is None:
+ __comp_id = 0
+ else:
+ assert __comp_id >0, "Non-positive ID: %d." % __comp_id
+ self.program_counter = [__comp_id, 0]
#: Connections to the other players.
#:
</pre>Marcel Keller2010-08-04T12:28:21[PATCH 1 of 1] Added command line option for playerhost and port
http://permalink.gmane.org/gmane.comp.cryptography.viff.patches/160
<pre># HG changeset patch
# User Thomas P Jakobsen <tpj< at >cs.au.dk>
# Date 1271181869 -7200
# Node ID 4a6c97b250725bb5a2bdf219ae00aa8e85b0d083
# Parent 6d838b2d24a22835782d71704c9ab5c7f22eac06
Added command line option for player host and port.
Sometimes it is more convenient to specify host and port numbers of
the players as command line arguments when running VIFF itself, rather
than by editing the configuration files.
This revision enables users to override host and port numbers
specified in the configuration files by command line arguments.
diff -r 6d838b2d24a2 -r 4a6c97b25072 viff/runtime.py
--- a/viff/runtime.pyTue Mar 30 11:34:39 2010 +0200
+++ b/viff/runtime.pyTue Apr 13 20:04:29 2010 +0200
< at >< at > -530,6 +530,12 < at >< at >
group.add_option("--no-socket-retry", action="store_true",
default=False, help="Fail rather than keep retrying "
"to connect if port is already in use.")
+ group.add_option("--host", metavar="HOST:PORT", action="append",
+ help="Override host and port of players as specified "
+ "in the configuration file. You can use this option "
+ "multiple times on the command line; the first will "
+ "override host and port of player 1, the second that "
+ "of player 2, and so forth.")
try:
# Using __import__ since we do not use the module, we are
< at >< at > -998,6 +1004,11 < at >< at >
from viff.passive import PassiveRuntime
runtime_class = PassiveRuntime
+ if options and options.host:
+ for i in range(len(options.host)):
+ players[i + 1].host, port_str = options.host[i].rsplit(":")
+ players[i + 1].port = int(port_str)
+
if options and options.profile:
# To collect profiling information we monkey patch reactor.run
# to do the collecting. It would be nicer to simply start the
</pre>Thomas P Jakobsen2010-04-13T18:15:23[PATCH 0 of 1] Command line arguments for host andport.
http://permalink.gmane.org/gmane.comp.cryptography.viff.patches/159
<pre>Here's a patch that allows users to specify player host and port
numbers via the command line.
If theres no objections, I'll push this change into VIFF in a couple
of days.
Regards,
Thomas
</pre>Thomas P Jakobsen2010-04-13T18:15:22Re: [PATCH] Added option to avoid retrying toconnect if socket isalready in use
http://permalink.gmane.org/gmane.comp.cryptography.viff.patches/158
<pre>
Nice, please put it in yourself! :-)
</pre>Martin Geisler2010-01-20T11:26:57[PATCH] Added option to avoid retrying to connect ifsocket isalready in use
http://permalink.gmane.org/gmane.comp.cryptography.viff.patches/157
<pre># HG changeset patch
# User Thomas P Jakobsen <tpj< at >cs.au.dk>
# Date 1263974081 -3600
# Node ID 2324d01c74e2c35b5bb6cb4d7bda1304a376b066
# Parent efa1983063d62a8115949a7e63d5ad4e5a23a791
Added option to avoid retrying to connect if socket is already in use.
In some situations it turns out to be more convenient to have VIFF
throw an exception rather than keep retrying to connect to a socket
with exponentially increasing delays. This is now possible using the
new command line parameter --no-socket-retry.
diff -r efa1983063d6 -r 2324d01c74e2 viff/runtime.py
--- a/viff/runtime.pyThu Jan 14 11:36:13 2010 +0100
+++ b/viff/runtime.pyWed Jan 20 08:54:41 2010 +0100
< at >< at > -525,6 +525,9 < at >< at >
help="Collect and print profiling information.")
group.add_option("--track-memory", action="store_true",
help="Track memory usage over time.")
+ group.add_option("--no-socket-retry", action="store_true",
+ default=False, help="Fail rather than keep retrying "
+ "to connect if port is already in use.")
try:
# Using __import__ since we do not use the module, we are
< at >< at > -1068,6 +1071,8 < at >< at >
try:
runtime.port = listen(port)
except CannotListenError, e:
+ if options and options.no_socket_retry:
+ raise
delay *= 1 + rand.random()
print "Error listening on port %d: %s" % (port, e.socketError[1])
print "Will try again in %d seconds" % delay
</pre>Thomas P Jakobsen2010-01-20T07:56:34Re: [PATCH] Added option to avoid retrying toconnect if socket is already in use
http://permalink.gmane.org/gmane.comp.cryptography.viff.patches/156
<pre>
You're right. I'll send a modified patch soon.
Regards,
Thomas
</pre>Thomas P Jakobsen2010-01-20T07:56:15Re: [PATCH] Added option to avoid retrying toconnect if socket isalready in use
http://permalink.gmane.org/gmane.comp.cryptography.viff.patches/155
<pre>_______________________________________________
viff-patches mailing list
viff-patches< at >viff.dk
http://lists.viff.dk/listinfo.cgi/viff-patches-viff.dk
</pre>Martin Geisler2010-01-19T23:11:52[PATCH] Added option to avoid retrying to connect ifsocket isalready in use
http://permalink.gmane.org/gmane.comp.cryptography.viff.patches/154
<pre># HG changeset patch
# User Thomas P Jakobsen <tpj< at >cs.au.dk>
# Date 1263939336 -3600
# Node ID 0b1e6cf3f57efe5a3b320897da636a6e2ebb2bdf
# Parent efa1983063d62a8115949a7e63d5ad4e5a23a791
Added option to avoid retrying to connect if socket is already in use.
In some situations it turns out to be more convenient to have VIFF
throw an exception rather than keep retrying to connect to a socket
with exponentially increasing delays. This is now possible using the
new command line parameter --no-socket-retry.
diff -r efa1983063d6 -r 0b1e6cf3f57e viff/runtime.py
--- a/viff/runtime.pyThu Jan 14 11:36:13 2010 +0100
+++ b/viff/runtime.pyTue Jan 19 23:15:36 2010 +0100
< at >< at > -525,6 +525,10 < at >< at >
help="Collect and print profiling information.")
group.add_option("--track-memory", action="store_true",
help="Track memory usage over time.")
+ group.add_option("--no-socket-retry", action="store_false",
+ dest="socket_retry", default=True,
+ help="Fail rather than keep retrying to connect "
+ "if port is already in use.")
try:
# Using __import__ since we do not use the module, we are
< at >< at > -1060,18 +1064,21 < at >< at >
connect = lambda host, port: reactor.connectTCP(host, port, factory)
port = players[id].port
- runtime.port = None
- delay = 2
- while runtime.port is None:
- # We keep trying to listen on the port, but with an
- # exponentially increasing delay between each attempt.
- try:
- runtime.port = listen(port)
- except CannotListenError, e:
- delay *= 1 + rand.random()
- print "Error listening on port %d: %s" % (port, e.socketError[1])
- print "Will try again in %d seconds" % delay
- time.sleep(delay)
+ if options and options.socket_retry:
+ runtime.port = None
+ delay = 2
+ while runtime.port is None:
+ # We keep trying to listen on the port, but with an
+ # exponentially increasing delay between each attempt.
+ try:
+ runtime.port = listen(port)
+ except CannotListenError, e:
+ delay *= 1 + rand.random()
+ print "Error listening on port %d: %s" % (port, e.socketError[1])
+ print "Will try again in %d seconds" % delay
+ time.sleep(delay)
+ else:
+ runtime.port = listen(port)
print "Listening on port %d" % port
for peer_id, player in players.iteritems():
</pre>Thomas P Jakobsen2010-01-19T22:18:59[PATCH 16 of 20] importeret rettelsetriple_combiner.patch
http://permalink.gmane.org/gmane.comp.cryptography.viff.patches/153
<pre># HG changeset patch
# User Janus Dam Nielsen <janus.nielsen< at >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
< at >< at > -55,6 +55,9 < at >< at >
"""
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))
< at >< at > -81,6 +84,9 < at >< at >
"""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):
< at >< at > -1005,6 +1011,293 < at >< at >
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
< at >< at > -548,8 +548,8 < at >< at >
x1 = 42
y1 = 7
- d = 4
-
+ runtime.d = 2
+
def check(v):
self.assertEquals(v, x1 * y1)
< at >< at > -557,7 +557,7 < at >< at >
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)
< at >< at > -577,7 +577,7 < at >< at >
runtime_class = OrlandiRuntime
- timeout = 240
+ timeout = 1600
< at >protocol
def test_tripleGen(self, runtime):
< at >< at > -645,3 +645,34 < at >< at >
d = runtime.triple_test(self.Zp)
d.addCallbacks(open, runtime.error_handler)
return d
+
+ < at >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
+
</pre>Janus Dam Nielsen2009-10-06T08:10:06[PATCH 20 of 20] importeret rettelseautopreprocessing.patch
http://permalink.gmane.org/gmane.comp.cryptography.viff.patches/152
<pre># HG changeset patch
# User Janus Dam Nielsen <janus.nielsen< at >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
< at >< at > -63,6 +63,7 < at >< at >
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, \
< at >< at > -87,12 +88,13 < at >< at >
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]),
< at >< at > -116,7 +118,7 < at >< at >
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")
< at >< at > -138,7 +140,7 < at >< at >
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.
< at >< at > -174,53 +176,43 < at >< at >
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 = []
< at >< at > -234,43 +226,49 < at >< at >
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:
< at >< at > -280,24 +278,30 < at >< at >
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
< at >< at > -378,11 +378,11 < at >< at >
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 =
< at >< at > -423,11 +423,11 < at >< at >
< at >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
< at >< at > -475,17 +475,21 < at >< at >
"""
def preprocess_decorator(method):
-
< at >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
< at >< at > -808,6 +812,9 < at >< at >
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
</pre>Janus Dam Nielsen2009-10-06T08:10:10[PATCH 14 of 20] Implementation of the TripleGenprotocol
http://permalink.gmane.org/gmane.comp.cryptography.viff.patches/151
<pre># HG changeset patch
# User Janus Dam Nielsen <janus.nielsen< at >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
< at >< at > -19,8 +19,9 < at >< at >
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
< at >< at > -771,6 +772,200 < at >< at >
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
< at >< at > -567,3 +567,60 < at >< at >
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
+
+ < at >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
+
+ < at >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
</pre>Janus Dam Nielsen2009-10-06T08:10:04[PATCH 12 of 20] Implementation of the basicmultiplication command
http://permalink.gmane.org/gmane.comp.cryptography.viff.patches/150
<pre># HG changeset patch
# User Janus Dam Nielsen <janus.nielsen< at >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
< at >< at > -459,6 +459,22 < at >< at >
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.
< at >< at > -506,6 +522,102 < at >< at >
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
< at >< at > -19,7 +19,7 < at >< at >
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
< at >< at > -28,6 +28,18 < at >< at >
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."""
< at >< at > -281,7 +293,6 < at >< at >
d2.addCallback(check)
return DeferredList([d1, d2])
-
< at >protocol
def test_shift_two_consequtive_inputters(self, runtime):
"""Test addition of the shift command."""
< at >< at > -339,3 +350,137 < at >< at >
shares_ready = gather_shares(a_shares + b_shares)
return shares_ready
+ < at >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
+
+ < at >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
+
+ < at >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
+
+ < at >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
+
+ < at >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
+
+ < at >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
+
+ < at >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
</pre>Janus Dam Nielsen2009-10-06T08:10:02[PATCH 17 of 20] Replace the current implementationof _get_triplewith a call to random triple
http://permalink.gmane.org/gmane.comp.cryptography.viff.patches/149
<pre># HG changeset patch
# User Janus Dam Nielsen <janus.nielsen< at >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
< at >< at > -495,8 +495,17 < at >< at >
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.
< at >< at > -588,14 +597,11 < at >< at >
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.
< at >< at > -1011,7 +1017,7 < at >< at >
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.
< at >< at > -1019,15 +1025,16 < at >< at >
"""
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):
< at >< at > -1235,18 +1242,18 < at >< at >
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)
< at >< at > -1295,8 +1302,11 < at >< at >
# 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
< at >< at > -261,7 +261,7 < at >< at >
runtime_class = OrlandiRuntime
- timeout = 60
+ timeout = 800
< at >protocol
def test_shift(self, runtime):
< at >< at > -556,13 +556,15 < at >< at >
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)
< at >< at > -672,7 +674,95 < at >< at >
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
+ < at >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
+
+ < at >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
</pre>Janus Dam Nielsen2009-10-06T08:10:07[PATCH 05 of 20] Boilerplate code for theimplementation of theOrlandi runtime
http://permalink.gmane.org/gmane.comp.cryptography.viff.patches/148
<pre># HG changeset patch
# User Janus Dam Nielsen <janus.nielsen< at >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
< at >< at > -0,0 +1,69 < at >< at >
+# 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
< at >< at > -0,0 +1,33 < at >< at >
+# 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
</pre>Janus Dam Nielsen2009-10-06T08:09:55[PATCH 06 of 20] Implemented secret sharing command
http://permalink.gmane.org/gmane.comp.cryptography.viff.patches/147
<pre># HG changeset patch
# User Janus Dam Nielsen <janus.nielsen< at >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
< at >< at > -15,8 +15,18 < at >< at >
# 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
< at >< at > -67,3 +77,115 < at >< at >
"""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
< at >< at > -21,9 +21,11 < at >< at >
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."""
< at >< at > -31,3 +33,23 < at >< at >
num_players = 3
runtime_class = OrlandiRuntime
+
+ < at >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
</pre>Janus Dam Nielsen2009-10-06T08:09:56[PATCH 11 of 20] Implementation of input and shiftcommands
http://permalink.gmane.org/gmane.comp.cryptography.viff.patches/146
<pre># HG changeset patch
# User Janus Dam Nielsen <janus.nielsen< at >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
< at >< at > -96,7 +96,8 < at >< at >
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
< at >< at > -15,7 +15,7 < at >< at >
# 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
< at >< at > -383,6 +383,82 < at >< at >
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
< at >< at > -15,15 +15,17 < at >< at >
# 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):
< at >< at > -239,3 +241,101 < at >< at >
return d
+class OrlandiAdvancedCommandsTest(RuntimeTestCase):
+ """Test for advanced commands."""
+
+ # Number of players.
+ num_players = 3
+
+ runtime_class = OrlandiRuntime
+
+ timeout = 60
+
+ < at >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
+
+ < at >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])
+
+
+ < at >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
+
+ < at >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
+
+ < at >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
+
</pre>Janus Dam Nielsen2009-10-06T08:10:01[PATCH 02 of 20] Constants used in communication isrefactored to anew file
http://permalink.gmane.org/gmane.comp.cryptography.viff.patches/145
<pre># HG changeset patch
# User Janus Dam Nielsen <janus.nielsen< at >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
< at >< at > -28,7 +28,7 < at >< at >
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
< at >< at > -0,0 +1,27 < at >< at >
+# -*- 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
< at >< at > -28,7 +28,7 < at >< at >
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
< at >< at > -41,6 +41,7 < at >< at >
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
< at >< at > -51,13 +52,6 < at >< at >
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
< at >< at > -30,7 +30,8 < at >< at >
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
</pre>Janus Dam Nielsen2009-10-06T08:09:52[PATCH 13 of 20] Implementation of the leak tolerantmultiplicationcommand
http://permalink.gmane.org/gmane.comp.cryptography.viff.patches/144
<pre># HG changeset patch
# User Janus Dam Nielsen <janus.nielsen< at >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
< at >< at > -81,6 +81,21 < at >< at >
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)
< at >< at > -243,8 +258,9 < at >< at >
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)]
< at >< at > -559,6 +575,11 < at >< at >
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)
< at >< at > -617,6 +638,139 < at >< at >
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
< at >< at > -334,7 +334,7 < at >< at >
self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
- count = 20
+ count = 9
a_shares = []
b_shares = []
< at >< at > -481,6 +481,89 < at >< at >
x2 = runtime.shift([1], self.Zp, x1)
y2 = runtime.shift([1], self.Zp, y1)
+ < at >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
+
+ < at >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
+
+ < at >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
+
+ < at >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
</pre>Janus Dam Nielsen2009-10-06T08:10:03[PATCH 10 of 20] Implementation of subtractioncommand
http://permalink.gmane.org/gmane.comp.cryptography.viff.patches/143
<pre># HG changeset patch
# User Janus Dam Nielsen <janus.nielsen< at >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
< at >< at > -350,6 +350,39 < at >< at >
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.
< at >< at > -380,6 +413,23 < at >< at >
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
< at >< at > -161,3 +161,81 < at >< at >
d = runtime.open(z2)
d.addCallback(check)
return d
+
+ < at >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
+
+ < at >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
+
+ < at >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
+
+
</pre>Janus Dam Nielsen2009-10-06T08:10:00[PATCH 01 of 20] It is now possible to send data toyour self
http://permalink.gmane.org/gmane.comp.cryptography.viff.patches/142
<pre># HG changeset patch
# User Janus Dam Nielsen <janus.nielsen< at >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
< at >< at > -382,6 +382,65 < at >< at >
"""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."""
< at >< at > -535,7 +594,9 < at >< at >
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()
< at >< at > -551,9 +612,7 < at >< at >
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.
< at >< at > -670,7 +729,6 < at >< at >
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
< at >< at > -27,10 +27,10 < at >< at >
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
< at >< at > -191,6 +191,49 < at >< at >
return gatherResults([opened_a, opened_b, opened_c])
+ < at >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
+
+ < at >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
< at >< at > -22,7 +22,7 < at >< at >
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
< at >< at > -220,7 +220,13 < at >< at >
# 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.
</pre>Janus Dam Nielsen2009-10-06T08:09:51[PATCH 00 of 20] Implementation of the Orlandiruntime
http://permalink.gmane.org/gmane.comp.cryptography.viff.patches/141
<pre>Hi friends of VIFF,
This pathcbomb contains three contributions
1) I have made it possible for a player to send and expect data from him self. This simplifies the implementation of the broadcast protocol I have implemented for the Orlandi runtime
2) An implementation of the Orlandi runtime. I have decided not to include the code for the commitment scheme yet, since it uses propriatary code
3) A refactoring and improvement of the benchmark.py application
Please review the code.
--
Janus
</pre>Janus Dam Nielsen2009-10-06T08:09:50Search EngineSearch the mailing list at Gmanequery
http://search.gmane.org/?group=$group=gmane.comp.cryptography.viff.patches