# 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) 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/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk