Re: [viff-devel] [Marc Makkes] Homomorphic encryption
Hi Marc, We generally use Paillier as a part of secure multiparty computation protocols, where each party has his own secret key and knows the public keys of the other players. The ciphertexts are generally multiplied a substantial number of times. Can you give me the background of this application? You should checkout the Paillier runtime in viff/paillier.py in VIFF. I think it is a classical example of what we want to do. Also I am working on an implementation of another runtime, where Paillier is used. It is not yet complete but I will spend some time today to get it into VIFF. It should also provide you with some inspiration. I will let you know when it is available in the VIFF repository. Also, i don't see any problems adapting for python. Creating a python binding should easy to make. Do you have time frame for when you are going to use the paillier implementation? Or is it already running? Our current Paillier runtime will certainly already now benefit from a fast implementation of Paillier. My main interest is using the implementation for the other runtime mentioned above. And I currently estimate that I am 3 to 4 weeks from completing it. Janus Dam Nielsen RD SCIENTIST, PhD. CENTRE FOR IT-SECURITY THE ALEXANDRA INSTITUTE LTD. T +45 42 22 93 56 E janus.niel...@alexandra.dk W alexandra.dk ___ 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
# HG changeset patch
# User Janus Dam Nielsen janus.niel...@alexandra.dk
# 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 http://www.gnu.org/licenses/.
+
+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 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
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
[viff-devel] [PATCH 04 of 12] Implementation of random share command
# HG changeset patch
# User Janus Dam Nielsen janus.niel...@alexandra.dk
# 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 07 of 12] Implementation of input and shift commands
# HG changeset patch
# User Janus Dam Nielsen janus.niel...@alexandra.dk
# 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 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
@@ -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
# HG changeset patch
# User Janus Dam Nielsen janus.niel...@alexandra.dk
# 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 06 of 12] Implementation of subtraction command
# HG changeset patch
# User Janus Dam Nielsen janus.niel...@alexandra.dk
# 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 12 of 12] importeret rettelse triple_test.patch
# HG changeset patch # User Janus Dam Nielsen janus.niel...@alexandra.dk # 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
# HG changeset patch
# User Janus Dam Nielsen janus.niel...@alexandra.dk
# 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)
Re: [viff-devel] [PATCH 03 of 12] Implementation of the open command
Janus Dam Nielsen janus.niel...@alexandra.dk 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 10 of 12] Added a variant of the encryption method which takes a random value as argument
Janus Dam Nielsen janus.niel...@alexandra.dk writes: # HG changeset patch # User Janus Dam Nielsen janus.niel...@alexandra.dk # 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 00 of 12] Partial implementation of the Orlandi runtime.
Janus Dam Nielsen janus.niel...@alexandra.dk 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
