# HG changeset patch
# User Janus Dam Nielsen <[email protected]>
# 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)
self.assertEquals(z2, None)
return z2
+
+ @protocol
+ def test_sum_poly(self, runtime):
+ """Test implementation of sum_poly."""
+
+ f = []
+ f.append((self.Zp(7), (self.Zp(7), self.Zp(7)), self.Zp(7)))
+ f.append((self.Zp(9), (self.Zp(9), self.Zp(9)), self.Zp(9)))
+ f.append((self.Zp(13), (self.Zp(13), self.Zp(13)), self.Zp(13)))
+
+ x, (rho1, rho2), Cx = runtime.sum_poly(1, f)
+ self.assertEquals(x, 29)
+ self.assertEquals(rho1, 29)
+ self.assertEquals(rho2, 29)
+ self.assertEquals(Cx, 29)
+ return x
+
+ @protocol
+ def test_sum_poly(self, runtime):
+ """Test implementation of sum_poly."""
+
+ 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(3, f)
+ self.assertEquals(x, 453)
+ self.assertEquals(rho1, 453)
+ self.assertEquals(rho2, 453)
+ self.assertEquals(Cx, 453)
+ return x
+
+ @protocol
+ def test_delta(self, runtime):
+ """Test implementation of compute_delta."""
+
+ delta = runtime.compute_delta(3)
+ self.assertEquals(delta[0], 7)
+ self.assertEquals(delta[1], -21)
+ self.assertEquals(delta[2], 35)
+ self.assertEquals(delta[3], -35)
+ self.assertEquals(delta[4], 21)
+ self.assertEquals(delta[5], -7)
+ self.assertEquals(delta[6], 1)
+
+ return delta
+
+ @protocol
+ def test_leak_mul(self, runtime):
+ """Test leaktolerant multiplication of two numbers."""
+
+ x1 = 42
+ y1 = 7
+
+ def check(v):
+ self.assertEquals(v, x1 * y1)
+
+
+ x2 = runtime.shift([1], self.Zp, x1)
+ y2 = runtime.shift([2], self.Zp, y1)
+
+ z2 = x2 * y1
+ z2 = runtime.leak_tolerant_mul(x2, y2)
+ d = runtime.open(z2)
+ d.addCallback(check)
+ return d
_______________________________________________
viff-devel mailing list (http://viff.dk/)
[email protected]
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
