Re: [viff-devel] [PATCH 00 of 12] Partial implementation of the Orlandi runtime.

[Martin Geisler]

Janus Dam Nielsen  writes:

> This patchbomb contains partial implementation of the Orlandi runtime.

Wow, cool! I've just looked through the first couple of patches and even
though I had some style-complaints, I think this is great!

If I've understood things correctly, then this gives us an actively
secure protocol for full threshold scenarios, right?

> The patches implements the basic and advanced commands along with the
> triple_gen and triple_test commands.
>
> The patches are partial implementations in the sense that the
> commitments are not implemented correctly, pending an implementation
> of Elliptic Curves.

Maybe you should publish the patches as a tree on hg.viff.dk like Marcel
has done -- and then let me know when you're happy with it and want me
to pull it into the main tree.

-- 
Martin Geisler

VIFF (Virtual Ideal Functionality Framework) brings easy and efficient
SMPC (Secure Multiparty Computation) to Python. See: http://viff.dk/.


pgpzxNWt1MBsU.pgp
Description: PGP signature
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] [PATCH 10 of 12] Added a variant of the encryption method which takes a random value as argument

[Martin Geisler]

Janus Dam Nielsen  writes:

> # HG changeset patch
> # User Janus Dam Nielsen 
> # Date 1245395100 -7200
> # Node ID ad19cc189a5bf04ba37c0a9e25600040585cc1e9
> # Parent  cd787f04de1f3be2e7c969e963ed7bcd94f81305
> Added a variant of the encryption method which takes a random value as 
> argument.

Thanks, pushed as revision c1259ceebc55!

-- 
Martin Geisler

VIFF (Virtual Ideal Functionality Framework) brings easy and efficient
SMPC (Secure Multiparty Computation) to Python. See: http://viff.dk/.


pgpmv8UmRd5yi.pgp
Description: PGP signature
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] [PATCH 03 of 12] Implementation of the open command

[Martin Geisler]

Janus Dam Nielsen  writes:

> +@increment_pc
> +def open(self, share, receivers=None, threshold=None):
> +"""Share reconstruction.
> +
> +Every parti broadcasts a share pair (x_{i}^{'}, rho_{x,i}^{'}).

Typo: "parti" -> "party". Also, the prime (') should not be put as a
superscript in LaTeX.

> +
> +The parties compute the sums x^{'}, rho_{x}^{'} and 
> +check Com_{ck}(x^{'},rho_{x}^{'} = C_{x}.
> +
> +If yes, output x = x^{'}, else output x = _|_.

Heh, I though it was only in Haskell that they write the bottom symbol
like that... :-) You really mean "else return :const:`None`", right?

> +"""
> +assert isinstance(share, Share)
> +# all players receive result by default
> +if receivers is None:
> +receivers = self.players.keys()
> +assert threshold is None
> +threshold = self.num_players - 1
> +
> +def recombine_value(shares, Cx):
> +x = share.field(0)
> +rho1 = share.field(0)
> +rho2 = share.field(0)

Due to automagic coercion you can actually initialize the values to 0.

> +for xi, (rhoi1, rhoi2), c in shares:
> +x += xi
> +rho1 += rhoi1
> +rho2 += rhoi2
> +assert c is None, "A commitment is found."
> +return self.check_commitment(x, (rho1, rho2), Cx)

-- 
Martin Geisler

VIFF (Virtual Ideal Functionality Framework) brings easy and efficient
SMPC (Secure Multiparty Computation) to Python. See: http://viff.dk/.


pgpP8XozoAFcu.pgp
Description: PGP signature
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] [PATCH 02 of 12] Implemented secret sharing command

[Martin Geisler]

Janus Dam Nielsen  writes:

> # HG changeset patch
> # User Janus Dam Nielsen 
> # Date 1245394849 -7200
> # Node ID f780a9ea514acb7de9d70022a8845938599696c8
> # Parent  15c0283f7cb6dad3d7a41e9095bb4fd18a30d909
> Implemented secret sharing command.
>
> diff --git a/viff/orlandi.py b/viff/orlandi.py
> --- a/viff/orlandi.py
> +++ b/viff/orlandi.py
> @@ -67,3 +67,112 @@
>  """Initialize runtime."""
>  Runtime.__init__(self, player, threshold, options)
>  self.threshold = self.num_players - 1
> +
> +def _Com(self, x, rho):

This name is bad Python Python style, could we please call it _commit
instead? I'm sure it's called Com in the paper, but still.

> +return self.open(share, receivers, threshold)
> +
> +def _send_orlandi_share(self, other_id, pc, xi, rhoi, Cx):
> +"""Send the share xim, rhoi, and the commitment Cx to party 
> other_id."""

The arguments should be as such (and xim looks like a typo):

 +"""Send the share *xi*, *rhoi*, and the commitment *Cx* to party 
*other_id*."""

> +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)
> +rhoi1 = self._expect_share(peer_id, field)
> +rhoi2 = self._expect_share(peer_id, field)
> +Cx = self._expect_share(peer_id, field)
> +sls = ShareList([xi, rhoi1, rhoi2, Cx])
> +def combine(ls):
> +if len(ls) is not 4:
> +raise OrlandiException("Cannot share number, trying to 
> create share," + \
> +   " but there are too few or too 
> many components.")

Please don't use backslashes to continue statements when they are inside
parenthesis. Also, adjacent strings are merged just like in C, so it
should be:

 +raise OrlandiException("Cannot share number, trying to create 
share, "
 +   "but there are too few or too many 
components.")

Also, there will always be 4 elements in the list.

> +s1, xi = ls[0]
> +s2, rhoi1 = ls[1]
> +s3, rhoi2 = ls[2]
> +s4, Cx = ls[3]
> +if not (s1 and s2 and s3 and s4):
> +raise OrlandiException("Cannot share number, trying to 
> create share," + \
> +   " but a component did arrive 
> properly.")

Same problem as above with the backslashes. Also, I think we talked
about this, but it looks like gather_shares would be better than
ShareList since you must have all four shares anyway.

> +@increment_pc
> +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_{x,1}, ..., rho_{x,n} in (Z_{p})^2, define 
> +rho_x = SUM_{i=1}^{n} rho_{x,i} and C_{x} = Com_{ck}(x, p_{x}).

Docstrings should use a blank like to separate paragraphs -- or be
wordwrapped correctly. Ad-hoc newlines like these wont be preserved.

-- 
Martin Geisler

VIFF (Virtual Ideal Functionality Framework) brings easy and efficient
SMPC (Secure Multiparty Computation) to Python. See: http://viff.dk/.


pgp9FvHRwXFFW.pgp
Description: PGP signature
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] [PATCH 01 of 12] importeret rettelse orlandi_implementation.patch

[Martin Geisler]

Janus Dam Nielsen  writes:

> # HG changeset patch
> # User Janus Dam Nielsen 
> # Date 1245394848 -7200
> # Node ID 15c0283f7cb6dad3d7a41e9095bb4fd18a30d909
> # Parent  8ec45943c12ab91430d03a8895aabc6f64fe7a37
> importeret rettelse orlandi_implementation.patch

Missing commit message :-)

> diff --git a/viff/orlandi.py b/viff/orlandi.py
> new file mode 100644
> --- /dev/null
> +++ b/viff/orlandi.py
> @@ -0,0 +1,69 @@
> +# Copyright 2008 VIFF Development Team.

The copyright dates are off by one :-)

> [...]
> +
> +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:

Have you tried running Sphinx on these docstrings? I would wrap the
tuples in ``...`` and drop the curly parenthesis around the subscripts.

-- 
Martin Geisler

VIFF (Virtual Ideal Functionality Framework) brings easy and efficient
SMPC (Secure Multiparty Computation) to Python. See: http://viff.dk/.


pgpYu7u73FuM2.pgp
Description: PGP signature
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

[viff-devel] [PATCH 08 of 12] Implementation of the basic multiplication command

[Janus Dam Nielsen]

# HG changeset patch
# User Janus Dam Nielsen 
# Date 1245395036 -7200
# Node ID a07740da4582869d11ead0f56ae055965aa2b4b0
# Parent  07a8329e75322d482dae15186422dd75e9ddb653
Implementation of the basic multiplication command.

diff --git a/viff/orlandi.py b/viff/orlandi.py
--- a/viff/orlandi.py
+++ b/viff/orlandi.py
@@ -15,6 +15,8 @@
 # You should have received a copy of the GNU Lesser General Public
 # License along with VIFF. If not, see .
 
+from twisted.internet.defer import DeferredList, gatherResults
+
 from viff.runtime import Runtime, increment_pc, Share, ShareList, gather_shares
 from viff.util import rand, dprint
 
@@ -442,6 +444,21 @@
  return results[0]
 return results   
 
+@increment_pc
+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."
+
+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.
 
@@ -488,6 +505,97 @@
 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):
+zi, rhoz, Cx = self._const_mul(c, 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."""
+xi, (rhoi1, rhoi2), Cx = x
+zi = xi * c
+rhoz = (rhoi1 * c, rhoi2 * c)
+Cz = Cx # TODO: exponentiation
+return (zi, rhoz, Cx)
+
+
+def _get_triple(self, field):
+n = field(0)
+a = OrlandiShare(self, field, field(2), (n, n), n)
+b = OrlandiShare(self, field, field(4), (n, n), n)
+c = OrlandiShare(self, field, field(24), (n, n), n)
+return (a, b, c)
+
+@increment_pc
+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."
+
+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, x)
+# d[y]
+t2 = self._const_mul(d, 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

[viff-devel] [PATCH 12 of 12] importeret rettelse triple_test.patch

[Janus Dam Nielsen]

# HG changeset patch
# User Janus Dam Nielsen 
# Date 1245395107 -7200
# Node ID 57f6d76d82e375b77293bcc6d54eeb6242686079
# Parent  4c46e8eeb719682da1a91b7ad96e7e902363e204
importeret rettelse triple_test.patch

diff --git a/viff/orlandi.py b/viff/orlandi.py
--- a/viff/orlandi.py
+++ b/viff/orlandi.py
@@ -932,7 +932,39 @@
 self.schedule_callback(result, step2ab, ai, (r1, r2))
 result.addErrback(self.error_handler)
 return result
-
+
+def triple_test(self, field):
+triple1 = self.triple_gen(field)
+triple2 = self.triple_gen(field)
+r = self.open(self.random_share(field))
+
+def check((v, oa, ob, oc, ox, oy, oz), a, b, c):
+if v is 0:
+return None
+return (a, b, c)
+
+def compute_value(((a, b, c), (x, y, z), r)):
+oa = self.open(a)
+ob = self.open(b)
+oc = self.open(c)
+ox = self.open(x)
+oy = self.open(y)
+oz = self.open(z)
+l = self._cmul(r, x, field)
+m = self._cmul(r, y, field)
+n = self._cmul(r*r, z, field)
+d = c - self._basic_multiplication(a, b, l, m, n)
+r = gather_shares([d, oa, ob, oc, ox, oy, oz])
+r.addCallbacks(check, self.error_handler, callbackArgs=(a, b, c))
+return r
+
+result = gatherResults([triple1, triple2, r])
+result.addCallbacks(compute_value, self.error_handler)
+
+# do actual communication
+self.activate_reactor()
+
+return result
 
 def error_handler(self, ex):
 print "Error: ", ex
diff --git a/viff/test/test_orlandi_runtime.py 
b/viff/test/test_orlandi_runtime.py
--- a/viff/test/test_orlandi_runtime.py
+++ b/viff/test/test_orlandi_runtime.py
@@ -494,4 +494,21 @@
 d = gatherResults([t1, t2])
 d.addCallbacks(open, runtime.error_handler)
 return d
-
+
+@protocol
+def test_tripleTest(self, runtime):
+"""Test the triple_test command."""
+
+def check((a, b, c)):
+self.assertEquals(c, a * b)
+
+def open((a, b, c)):
+d1 = runtime.open(a)
+d2 = runtime.open(b)
+d3 = runtime.open(c)
+d = gatherResults([d1, d2, d3])
+d.addCallback(check)
+return d
+d = runtime.triple_test(self.Zp)
+d.addCallbacks(open, runtime.error_handler)
+return d
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

[viff-devel] [PATCH 09 of 12] Implementation of the leak tolerant multiplication command

[Janus Dam Nielsen]

# HG changeset patch
# User Janus Dam Nielsen 
# Date 1245395070 -7200
# Node ID cd787f04de1f3be2e7c969e963ed7bcd94f81305
# Parent  a07740da4582869d11ead0f56ae055965aa2b4b0
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
@@ -75,6 +75,23 @@
 """Initialize runtime."""
 Runtime.__init__(self, player, threshold, options)
 self.threshold = self.num_players - 1
+self.d = 3
+self.delta = self.compute_delta(self.d)
+
+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 * self.d + 2):
+delta.append(product(j))
+return delta
 
 def _Com(self, x, rho):
 return x + rho[0] + rho[1]
@@ -595,6 +612,107 @@
 
 return result
 
+def sum_poly(self, j, ls):
+x = 0
+rho1 = 0
+rho2 = 0
+Cx = 0
+exp = j
+for (fj, (rhoj1, rhoj2), Cfj) in ls:
+x += fj * exp
+rho1 += rhoj1 * exp
+rho2 += rhoj2 * exp
+Cx += Cfj * exp
+exp *= j
+return x, (rho1, rho2), Cx
+
+@increment_pc
+def leak_tolerant_mul(self, share_x, share_y):
+"""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."
+
+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()
+f = []
+g = []
+for x in xrange(self.d):
+f.append(self.random_share(field))
+g.append(self.random_share(field))
+
+def compute_polynomials(((x, y), f, g)):
+# 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*self.d + 2):
+# SUM_{i=1}^{d} [f_{i}]*j^{i} 
+vi, (rhovi1, rhovi2), Cv = self.sum_poly(j, f)
+# SUM_{i=1}^{d} [g_{i}]*j^{i} 
+wi, (rhowi1, rhowi2), Cw = self.sum_poly(j, g)
+# [F_{j}] = [x] + SUM_{i=1}^{d} [f_{i}]*j^{i} 
+# [G_{j}] = [y] + SUM_{i=1}^{d} [g_{i}]*j^{i} 
+Fji = xi + vi
+Gji = yi + wi
+Fj = OrlandiShare(self, field, Fji, (rhovi1, rhovi2), Cv)
+Gj = OrlandiShare(self, field, Gji, (rhowi1, rhowi2), Cw)
+
+a, b, c = self._get_triple(field)
+
+# [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(self.delta[j - 1], Hj, field)
+H0 = H0 + dj
+# 5) output [z] = [H_{0}]
+return H0
+
+result1 = gather_shares([share_x, share_y])
+result2 = gather_shares(f)
+result3 = gather_shares(g)
+result = gather_shares([result1, result2, result3])
+result.addCallbacks(compute_polynomials, 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
@@ -375,3 +375,70 @@
 z2 = runtime._cmul(y2, x2, self.Zp)
  

[viff-devel] [PATCH 11 of 12] Implementation of the TripleGen protocol

[Janus Dam Nielsen]

# HG changeset patch
# User Janus Dam Nielsen 
# Date 1245395102 -7200
# Node ID 4c46e8eeb719682da1a91b7ad96e7e902363e204
# Parent  ad19cc189a5bf04ba37c0a9e25600040585cc1e9
Implementation of the TripleGen protocol.

diff --git a/viff/orlandi.py b/viff/orlandi.py
--- a/viff/orlandi.py
+++ b/viff/orlandi.py
@@ -15,10 +15,11 @@
 # You should have received a copy of the GNU Lesser General Public
 # License along with VIFF. If not, see .
 
-from twisted.internet.defer import DeferredList, gatherResults
+from twisted.internet.defer import Deferred, DeferredList, gatherResults
 
-from viff.runtime import Runtime, increment_pc, Share, ShareList, gather_shares
+from viff.runtime import Runtime, increment_pc, Share, ShareList, 
gather_shares, PAILLIER
 from viff.util import rand, dprint
+from viff.paillier import encrypt, encrypt_r, decrypt
 
 class OrlandiException(Exception):
 pass
@@ -713,6 +714,226 @@
 
 return result
 
+@increment_pc
+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_{i,j} in Z_{p^{3}}
+   ii. compute and send 
+   gamma_{i,j} = alpha_{i}^{b_{j}} Enc_{ek_{i}}(1;1)^{d_{i, 
j}} to P_{i}.
+
+3) Every party P_{i} does:
+   (a) compute c_{i} = SUM_{j} Dec_{sk_{i}}(gamma_{i,j}) - SUM_{j} 
d_{i,j} 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).
+
+"""
+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 = field(1)
+for x in ls:
+b *= 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, As, Bs, ai, bi, ci, r, s, t):
+"""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)
+
+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, As, Bs, ai, bi, r, s, dijs):
+"""3) Every party P_{i} does:
+  (a) compute 
+  c_{i} = SUM_{j} Dec_{sk_{i}}(gamma_{i,j}) - SUM_{j} d_{j,i} 
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_{i,j}) - SUM_{j} d_{j,i} 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 = self._Com(ci, t)
+
+# Broadcast Ci.
+Cs = [None] * len(self.players)
+pc = tuple(self.program_counter)
+for peer_id in self.players:
+if peer_id != self.id:
+self.protocols[peer_id].sendShare(pc, Ci)
+d = self._expect_share(peer_id, field)
+else:
+d = Deferred()
+d.callback(Ci)
+Cs[peer_id - 1] = d
+result = gatherResults(Cs)
+result.addCallback(step45, As, Bs, ai, bi, ci, r, s, t)
+

[viff-devel] [PATCH 10 of 12] Added a variant of the encryption method which takes a random value as argument

[Janus Dam Nielsen]

# HG changeset patch
# User Janus Dam Nielsen 
# Date 1245395100 -7200
# Node ID ad19cc189a5bf04ba37c0a9e25600040585cc1e9
# Parent  cd787f04de1f3be2e7c969e963ed7bcd94f81305
Added a variant of the encryption method which takes a random value as argument.

diff --git a/viff/paillier.py b/viff/paillier.py
--- a/viff/paillier.py
+++ b/viff/paillier.py
@@ -56,6 +56,9 @@
 
 def encrypt(m, (n, g)):
 r = rand.randint(1, long(n))
+return encrypt_r(m, r, (n, g))
+
+def encrypt_r(m, r, (n, g)):
 nsq = n*n
 return (pow(g, m, nsq)*pow(r, n, nsq)) % nsq
 
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

[viff-devel] [PATCH 06 of 12] Implementation of subtraction command

[Janus Dam Nielsen]

# HG changeset patch
# User Janus Dam Nielsen 
# Date 1245394917 -7200
# Node ID 4c4228af583fc965fb0722c5b051ffa213152f62
# Parent  85ae7883768d8367baf57cf3b6647707cb1d9b1d
Implementation of subtraction command.

diff --git a/viff/orlandi.py b/viff/orlandi.py
--- a/viff/orlandi.py
+++ b/viff/orlandi.py
@@ -347,6 +347,37 @@
 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):
+(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.
 
@@ -376,6 +407,23 @@
 Cz = Cx * Cy
 return (zi, (rhozi1, rhozi2), Cz)
 
+def _minus(self, x, y):
+"""Subtraction of share-tuples x and y.
+
+Each party P_{i} computes:
+[x]_{i} = (x_{i}, rho_{x,i}, C_{x})
+[y]_{i} = (y_{i}, rho_{y,i}, C_{y})
+[z]_{i} = [x]_{i} - [y]_{i}
+= (x_{i} - y_{i} mod p, rho_{x,i} - rho_{y,i} mod p, C_{x} * 
C_{y}).
+"""
+xi, (rhoxi1, rhoxi2), Cx = x
+yi, (rhoyi1, rhoyi2), Cy = y
+zi = xi - yi
+rhozi1 = rhoxi1 - rhoyi1
+rhozi2 = rhoxi2 - rhoyi2
+Cz = Cx * Cy
+return (zi, (rhozi1, rhozi2), Cz)
+
 def error_handler(self, ex):
 print "Error: ", ex
 return ex
diff --git a/viff/test/test_orlandi_runtime.py 
b/viff/test/test_orlandi_runtime.py
--- a/viff/test/test_orlandi_runtime.py
+++ b/viff/test/test_orlandi_runtime.py
@@ -147,5 +147,74 @@
 d.addCallback(check)
 return d
 
+@protocol
+def test_sub(self, runtime):
+"""Test subtration of two numbers."""
 
+x1 = 42
+y1 = 7
 
+def check(v):
+self.assertEquals(v, x1 + y1)
+
+if 1 == runtime.id:
+x2 = runtime.secret_share([1], self.Zp, x1)
+else:
+x2 = runtime.secret_share([1], self.Zp)
+
+if 3 == runtime.id:
+y2 = runtime.secret_share([3], self.Zp, y1)
+else:
+y2 = runtime.secret_share([3], self.Zp)
+
+z2 = runtime.add(x2, y2)
+d = runtime.open(z2)
+d.addCallback(check)
+return d
+
+@protocol
+def test_sub_minus(self, runtime):
+"""Test subtration of two numbers."""
+
+x1 = 42
+y1 = 7
+
+def check(v):
+self.assertEquals(v, x1 - y1)
+
+if 1 == runtime.id:
+x2 = runtime.secret_share([1], self.Zp, x1)
+else:
+x2 = runtime.secret_share([1], self.Zp)
+
+if 3 == runtime.id:
+y2 = runtime.secret_share([3], self.Zp, y1)
+else:
+y2 = runtime.secret_share([3], self.Zp)
+
+z2 = x2 - y2
+d = runtime.open(z2)
+d.addCallback(check)
+return d
+
+@protocol
+def test_sub_constant(self, runtime):
+"""Test subtration of two numbers."""
+
+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
+
+
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

[viff-devel] [PATCH 07 of 12] Implementation of input and shift commands

[Janus Dam Nielsen]

# HG changeset patch
# User Janus Dam Nielsen 
# Date 1245394940 -7200
# Node ID 07a8329e75322d482dae15186422dd75e9ddb653
# Parent  4c4228af583fc965fb0722c5b051ffa213152f62
Implementation of input and shift commands.

diff --git a/viff/orlandi.py b/viff/orlandi.py
--- a/viff/orlandi.py
+++ b/viff/orlandi.py
@@ -43,6 +43,12 @@
 def __init__(self, runtime, field, value=None, rho=None, commitment=None):
 Share.__init__(self, runtime, field, (value, rho, commitment))
 
+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)
 
 class OrlandiRuntime(Runtime):
 """The Orlandi runtime.
@@ -378,6 +384,64 @@
 result.addCallbacks(compute_subs, self.error_handler)
 return result
 
+@increment_pc
+def shift(self, inputters, field, number):
+"""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?
+results = []
+for peer_id in inputters:
+# 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])
+if peer_id == self.id:
+# I am an inputter, send delta
+pc = tuple(self.program_counter)
+def f(r, share_r, pc):
+my_delta = None
+# 2) P_{i} broadcasts Delta = r - x
+for other_id in self.players:
+delta = r - number
+if not (other_id == self.id):
+self.protocols[other_id].sendShare(pc, delta)
+else:
+# 3) [x] = [r] - Delta
+my_delta = self.sub(share_r, delta)
+return my_delta
+open_r.addCallback(f, share_r, pc)
+open_r.addErrback(self.error_handler)
+results.append(open_r)
+else:
+# I am not an inputter, wait for a delta
+d = self._expect_share(peer_id, field)
+def f(delta, share_r):
+# 3) [x] = [r] - Delta
+return self.sub(share_r, delta)
+d.addCallback(f, share_r)
+results.append(d)
+
+# do actual communication
+self.activate_reactor()
+
+if len(results) == 1:
+ return results[0]
+return results   
+
 def _additive_constant(self, zero, field_element):
 """Greate an additive constant.
 
diff --git a/viff/test/test_orlandi_runtime.py 
b/viff/test/test_orlandi_runtime.py
--- a/viff/test/test_orlandi_runtime.py
+++ b/viff/test/test_orlandi_runtime.py
@@ -15,7 +15,7 @@
 # You should have received a copy of the GNU Lesser General Public
 # License along with VIFF. If not, see .
 
-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
@@ -218,3 +218,37 @@
 return d
 
 
+class OrlandiAdvancedCommandsTest(RuntimeTestCase):
+"""Test for advanced commands."""
+
+# Number of players.
+num_players = 3
+ 
+runtime_class = OrlandiRuntime
+ 
+@protocol
+def test_shift(self, runtime):
+"""Test addition of the shift command."""
+
+def check(v):
+self.assertEquals(v, 42)
+ 
+x = runtime.shift([2], self.Zp, 42)
+d = runtime.open(x)
+d.addCallback(check)
+return d
+
+@protocol
+def test_shift_two_inputters(self, runtime):
+"""Test addition of the shift command."""
+
+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])
+
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

[viff-devel] [PATCH 05 of 12] Implementation of addition command

[Janus Dam Nielsen]

# HG changeset patch
# User Janus Dam Nielsen 
# Date 1245394853 -7200
# Node ID 85ae7883768d8367baf57cf3b6647707cb1d9b1d
# Parent  1eb98ef76446e9ef06d8d94e31748fe5cfd2ba82
Implementation of addition command.

diff --git a/viff/orlandi.py b/viff/orlandi.py
--- a/viff/orlandi.py
+++ b/viff/orlandi.py
@@ -316,6 +316,66 @@
 
 return sls
 
+def add(self, share_a, share_b):
+"""Addition of shares.
+
+Communication cost: none.
+
+Each party P_{i} computes:
+[z]_{i} = [x]_{i} + [y]_{i}
+= (x_{i} + y_{i} mod p, rho_{x,i} + rho_{y,i} mod p, C_{x} * 
C_{y}).
+
+"""
+def is_share(s, field):
+if not isinstance(s, Share):
+(v, rhov, Cv) = self._additive_constant(field(0), s)
+return OrlandiShare(self, field, v, rhov, Cv)
+return s
+
+# Either share_a or share_b must have an attribute called "field". 
+field = getattr(share_a, "field", getattr(share_b, "field", None))
+
+share_a = is_share(share_a, field)
+share_b = is_share(share_b, field)
+
+# Add rho_{x,i} and rho_{y,i} and compute the commitment.
+def compute_sums((x, y)):
+(zi, (rhozi1, rhozi2), Cz) = self._plus(x, y)
+return OrlandiShare(self, field, zi, (rhozi1, rhozi2), Cz)
+
+result = gather_shares([share_a, share_b])
+result.addCallbacks(compute_sums, self.error_handler)
+return result
+
+def _additive_constant(self, zero, field_element):
+"""Greate an additive constant.
+
+Any additive constant can be interpreted as:
+[c]_{1} = (c, 0, Com_{ck}(c,0)) and
+[c]_{i} = (0, 0, Com_{ck}(c,0)) for i != 1.
+"""
+v = zero
+if self.id == 1:
+v = field_element
+return (v, (zero, zero), self._Com(field_element, (zero, zero)))
+
+def _plus(self, x, y):
+"""Addition 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
@@ -77,4 +77,75 @@
 d.addCallback(check)
 return d
 
+@protocol
+def test_sum(self, runtime):
+"""Test addition of two numbers."""
 
+x1 = 42
+y1 = 7
+
+def check(v):
+self.assertEquals(v, x1 + y1)
+
+if 1 == runtime.id:
+x2 = runtime.secret_share([1], self.Zp, x1)
+else:
+x2 = runtime.secret_share([1], self.Zp)
+
+if 3 == runtime.id:
+y2 = runtime.secret_share([3], self.Zp, y1)
+else:
+y2 = runtime.secret_share([3], self.Zp)
+
+z2 = runtime.add(x2, y2)
+d = runtime.open(z2)
+d.addCallback(check)
+return d
+
+@protocol
+def test_sum_plus(self, runtime):
+"""Test addition of two numbers."""
+
+x1 = 42
+y1 = 7
+
+def check(v):
+self.assertEquals(v, x1 + y1)
+
+if 1 == runtime.id:
+x2 = runtime.secret_share([1], self.Zp, x1)
+else:
+x2 = runtime.secret_share([1], self.Zp)
+
+if 3 == runtime.id:
+y2 = runtime.secret_share([3], self.Zp, y1)
+else:
+y2 = runtime.secret_share([3], self.Zp)
+
+z2 = x2 + y2
+d = runtime.open(z2)
+d.addCallback(check)
+return d
+
+@protocol
+def test_sum_constant(self, runtime):
+"""Test addition of two numbers."""
+
+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
+
+
+
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

[viff-devel] [PATCH 02 of 12] Implemented secret sharing command

[Janus Dam Nielsen]

# HG changeset patch
# User Janus Dam Nielsen 
# Date 1245394849 -7200
# Node ID f780a9ea514acb7de9d70022a8845938599696c8
# Parent  15c0283f7cb6dad3d7a41e9095bb4fd18a30d909
Implemented secret sharing command.

diff --git a/viff/orlandi.py b/viff/orlandi.py
--- a/viff/orlandi.py
+++ b/viff/orlandi.py
@@ -67,3 +67,112 @@
 """Initialize runtime."""
 Runtime.__init__(self, player, threshold, options)
 self.threshold = self.num_players - 1
+
+def _Com(self, x, rho):
+return x + rho[0] + rho[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 xim, 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].sendShare(pc, 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)
+rhoi1 = self._expect_share(peer_id, field)
+rhoi2 = self._expect_share(peer_id, field)
+Cx = self._expect_share(peer_id, field)
+sls = ShareList([xi, rhoi1, rhoi2, Cx])
+def combine(ls):
+if len(ls) is not 4:
+raise OrlandiException("Cannot share number, trying to create 
share," + \
+   " but there are too few or too many 
components.")
+s1, xi = ls[0]
+s2, rhoi1 = ls[1]
+s3, rhoi2 = ls[2]
+s4, Cx = ls[3]
+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), Cx)
+sls.addCallbacks(combine, self.error_handler)
+return sls
+
+@increment_pc
+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_{x,1}, ..., rho_{x,n} 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_{x,i}, C_{x}) to party P_{i}.
+"""
+assert number is None or self.id in inputters
+self.threshold = self.num_players - 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 field_{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 = field(0)
+rho1 = field(0)
+rho2 = field(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 = self._Com(number, rho)
+# Distribute the shares
+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 ac

[viff-devel] [PATCH 03 of 12] Implementation of the open command

[Janus Dam Nielsen]

# HG changeset patch
# User Janus Dam Nielsen 
# Date 1245394850 -7200
# Node ID 29c28d1a8e5f5647fe97d7b01f5924f3ef006301
# Parent  f780a9ea514acb7de9d70022a8845938599696c8
Implementation of the open command.

diff --git a/viff/orlandi.py b/viff/orlandi.py
--- a/viff/orlandi.py
+++ b/viff/orlandi.py
@@ -103,6 +103,26 @@
 sls.addCallbacks(combine, self.error_handler)
 return sls
 
+def _expect_orlandi_share_xi_rhoi(self, peer_id, field):
+xi = self._expect_share(peer_id, field)
+rhoi1 = self._expect_share(peer_id, field)
+rhoi2 = self._expect_share(peer_id, field)
+sls = ShareList([xi, rhoi1, rhoi2])
+def combine(ls):
+if len(ls) is not 3:
+raise OrlandiException("Cannot share number, trying to create 
" + \
+   "share but there are too few or too 
" + \
+   "many components.")
+s1, xi = ls[0]
+s2, rhoi1 = ls[1]
+s3, rhoi2 = ls[2]
+if not (s1 and s2 and s3):
+raise OrlandiException("Cannot share number, trying to create 
share " + \
+   "but a component did arrive 
properly.")
+return OrlandiShare(self, field, xi, (rhoi1, rhoi2))
+sls.addCallbacks(combine, self.error_handler)
+return sls
+
 @increment_pc
 def secret_share(self, inputters, field, number=None, threshold=None):
 """Share the value, number, among all the parties using additive 
shareing.
@@ -173,6 +193,83 @@
 return results[0]
 return results
 
+def check_commitment(self, x, rho, Cx):
+"""Check if Cx is a commitment to x and rho."""
+Cx1 = self._Com(x, rho)
+# if Cx1 == Cx:
+return x
+raise OrlandiException("Wrong commitment for value %s, found %s 
expected %s." % 
+   (x, Cx1, Cx))
+
+@increment_pc
+def open(self, share, receivers=None, threshold=None):
+"""Share reconstruction.
+
+Every parti broadcasts a share pair (x_{i}^{'}, rho_{x,i}^{'}).
+
+The parties compute the sums x^{'}, rho_{x}^{'} and 
+check Com_{ck}(x^{'},rho_{x}^{'} = C_{x}.
+
+If yes, output x = x^{'}, else output x = _|_.
+"""
+assert isinstance(share, Share)
+# all players receive result by default
+if receivers is None:
+receivers = self.players.keys()
+assert threshold is None
+threshold = self.num_players - 1
+
+def recombine_value(shares, Cx):
+x = share.field(0)
+rho1 = share.field(0)
+rho2 = share.field(0)
+for xi, (rhoi1, rhoi2), c in shares:
+x += xi
+rho1 += rhoi1
+rho2 += rhoi2
+assert c is None, "A commitment is found."
+return self.check_commitment(x, (rho1, rho2), Cx)
+
+def recombine(shares, Cx):
+assert len(shares) == threshold + 1
+result = gather_shares(shares)
+result.addCallback(recombine_value, Cx)
+result.addErrback(self.error_handler)
+return result
+
+def exchange((xi, (rhoi1, rhoi2), Cx)):
+# Send share to all receivers.
+for peer_id in receivers:
+if peer_id != self.id:
+pc = tuple(self.program_counter)
+# Send xi, rhoi
+self.protocols[peer_id].sendShare(pc, xi)
+self.protocols[peer_id].sendShare(pc, rhoi1)
+self.protocols[peer_id].sendShare(pc, rhoi2)
+# Receive and recombine shares if this player is a receiver.
+if self.id in receivers:
+deferreds = []
+for peer_id in self.players:
+# Expect xi and rhoi
+if peer_id == self.id:
+d = OrlandiShare(self, 
+ share.field, 
+ xi,
+ (rhoi1, rhoi2))
+else:
+d = self._expect_orlandi_share_xi_rhoi(peer_id, 
share.field)
+deferreds.append(d)
+return recombine(deferreds, Cx)
+
+result = share.clone()
+self.schedule_callback(result, exchange)
+
+# do actual communication
+self.activate_reactor()
+
+if self.id in receivers:
+return result
+
 def error_handler(self, ex):
 print "Error: ", ex
 return ex
diff --git a/viff/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
@@ -49,3 +49,19 @@
 share = runtime.secret_share([1], self.Zp)
 share.addCallback(check)
 re

[viff-devel] [PATCH 04 of 12] Implementation of random share command

[Janus Dam Nielsen]

# HG changeset patch
# User Janus Dam Nielsen 
# Date 1245394852 -7200
# Node ID 1eb98ef76446e9ef06d8d94e31748fe5cfd2ba82
# Parent  29c28d1a8e5f5647fe97d7b01f5924f3ef006301
Implementation of random share command.

diff --git a/viff/orlandi.py b/viff/orlandi.py
--- a/viff/orlandi.py
+++ b/viff/orlandi.py
@@ -270,6 +270,52 @@
 if self.id in receivers:
 return result
 
+@increment_pc
+def random_share(self, field):
+"""Generate a random share in the field, field.
+
+To generate a share of a random element r in Z_{p}, party P_{i} 
+chooses at random r_{i}, rho_{r,i} in Z_{p} x (Z_{p})^2 and
+broadcast C_{r}^{i} = Com_{ck}(r_{i}, rho_{r, i}).
+Every party computes C_{r} = PRODUCT_{i=1}^{n} C_{r}^{i} = Com_{ck}(r, 
rho_{r}),
+where r_{i} = SUM_{i=1}^{n} r_{i} and rho_{r} = SUM_{i=1}^{n} 
rho_{r,i}.
+
+Party P_{i} sets [r]_{i} = (r_{i}, rho_{r,i}, C_{r}).
+
+"""
+# P_{i} chooses at random r_{i}, rho_{r,i} in Z_{p} x (Z_{p})^2
+ri = field(rand.randint(0, field.modulus - 1)) 
+rhoi1 = field(rand.randint(0, field.modulus - 1))
+rhoi2 = field(rand.randint(0, field.modulus - 1))
+# compute C_{r}^{i} = Com_{ck}(r_{i}, rho_{r, i}).
+Cri = self._Com(ri, (rhoi1, rhoi2))
+# Broadcast C_{r}^{i}.
+shares = []
+for peer_id in self.players:
+if peer_id == self.id:
+# Broadcast C_{r}^{i}
+d = Share(self, field, Cri)
+else:
+# Recieve C_{r}^{i}
+pc = tuple(self.program_counter)
+self.protocols[peer_id].sendShare(pc, Cri)
+d = self._expect_share(peer_id, field)
+shares.append(d)
+
+def compute_commitment(ls):
+Cr = field(1)
+for s, v in ls:
+Cr *= v
+return OrlandiShare(self, field, ri, (rhoi1, rhoi2), Cr)
+
+sls = ShareList(shares)
+sls.addCallbacks(compute_commitment, self.error_handler)
+
+# do actual communication
+self.activate_reactor()
+
+return sls
+
 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
@@ -65,3 +65,16 @@
 d.addCallback(check)
 return d
 
+@protocol
+def test_random_share(self, runtime):
+"""Test creation of a random shared number."""
+
+def check(v):
+self.assertEquals(True, True)
+
+x = runtime.random_share(self.Zp)
+d = runtime.open(x)
+d.addCallback(check)
+return d
+
+
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

[viff-devel] [PATCH 00 of 12] Partial implementation of the Orlandi runtime.

[Janus Dam Nielsen]

This patchbomb contains partial implementation of the Orlandi runtime.

The patches implements the basic and advanced commands along with the 
triple_gen and triple_test commands.
The patches are partial implementations in the sense that the commitments are 
not implemented correctly, pending an implementation of Elliptic Curves.
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

[viff-devel] [PATCH 01 of 12] importeret rettelse orlandi_implementation.patch

[Janus Dam Nielsen]

# HG changeset patch
# User Janus Dam Nielsen 
# Date 1245394848 -7200
# Node ID 15c0283f7cb6dad3d7a41e9095bb4fd18a30d909
# Parent  8ec45943c12ab91430d03a8895aabc6f64fe7a37
importeret rettelse orlandi_implementation.patch

diff --git a/viff/orlandi.py b/viff/orlandi.py
new file mode 100644
--- /dev/null
+++ b/viff/orlandi.py
@@ -0,0 +1,69 @@
+# Copyright 2008 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 .
+
+from viff.runtime import Runtime, increment_pc, Share, ShareList, gather_shares
+from viff.util import rand, dprint
+
+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_{i}_{1}, rho_{i}_{2})
+- A commitment to the number and the random numbers, Cr_{i}
+
+The :class:`Runtime` operates on shares, represented by this class.
+Shares are asynchronous in the sense that they promise to attain a
+value at some point in the future.
+
+Shares overload the arithmetic operations so that ``x = a + b``
+will create a new share *x*, which will eventually contain the
+sum of *a* and *b*. Each share is associated with a
+:class:`Runtime` and the arithmetic operations simply call back to
+that runtime.
+"""
+
+def __init__(self, runtime, field, value=None, rho=None, commitment=None):
+Share.__init__(self, runtime, field, (value, rho, commitment))
+
+
+class OrlandiRuntime(Runtime):
+"""The Orlandi runtime.
+
+The runtime is used for sharing values (:meth:`secret_share` or
+:meth:`shift`) into :class:`OrlandiShare` object and opening such
+shares (:meth:`open`) again. Calculations on shares is normally
+done through overloaded arithmetic operations, but it is also
+possible to call :meth:`add`, :meth:`mul`, etc. directly if one
+prefers.
+
+Each player in the protocol uses a :class:`Runtime` object. To
+create an instance and connect it correctly with the other
+players, please use the :func:`create_runtime` function instead of
+instantiating a Runtime directly. The :func:`create_runtime`
+function will take care of setting up network connections and
+return a :class:`Deferred` which triggers with the
+:class:`Runtime` object when it is ready.
+"""
+
+def __init__(self, player, threshold=None, options=None):
+"""Initialize runtime."""
+Runtime.__init__(self, player, threshold, options)
+self.threshold = self.num_players - 1
diff --git a/viff/test/test_orlandi_runtime.py 
b/viff/test/test_orlandi_runtime.py
new file mode 100644
--- /dev/null
+++ b/viff/test/test_orlandi_runtime.py
@@ -0,0 +1,33 @@
+# Copyright 2008 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 .
+
+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
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk