# [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
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])
+
+        # 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)