changeset 1459:007822876664

BeDOZa: Implemented addition.
author Janus Dam Nielsen <janus.nielsen@alexandra.dk>
date Tue, 06 Jul 2010 11:01:53 +0200
parents 1daa218516f8
children 9a4e722f182b
files viff/bedoza.py viff/test/test_bedoza_runtime.py
diffstat 2 files changed, 130 insertions(+), 1 deletions(-) [+]
line wrap: on
line diff
--- a/viff/bedoza.py	Tue Jul 06 11:01:34 2010 +0200
+++ b/viff/bedoza.py	Tue Jul 06 11:01:53 2010 +0200
@@ -19,7 +19,8 @@
 
 from twisted.internet.defer import Deferred, gatherResults, succeed
 
-from viff.runtime import Runtime, Share, ShareList
+from viff.runtime import Runtime, Share, ShareList, gather_shares
+from viff.field import FieldElement
 
 from hash_broadcast import HashBroadcastMixin
 
@@ -253,3 +254,50 @@
 
     def get_alpha(self):
         return self.keys[0]
+        
+    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, {xk^{i}_{j} + yk^{i}_{j} mod p}_{j=0}^{j=n}, {xm^{i}_{j} + ym^{i}_{j} mod p}_{j=0}^{j=n})
+
+        """
+        # Either share_a or share_b must have an attribute called "field".
+        field = share_a.field
+        if not isinstance(share_b, Share):
+            if not isinstance(share_b, FieldElement):
+                share_b = field(share_b)
+            share_a.addCallbacks(self._add_public, self.error_handler, callbackArgs=(share_b, field))
+            return share_a
+        else:
+            result = gather_shares([share_a, share_b])
+            result.addCallbacks(self._plus, self.error_handler, callbackArgs=(field,))
+            return result
+
+    def _add_public(self, x, y, field):
+        """Greate an additive constant."""
+        (xi, xks, xms) = x
+        if self.id == 1:
+            xi = xi + y
+        xks.keys[0] = xks.keys[0] - xks.alpha * y
+        return BeDOZaShare(self, field, xi, xks, xms)
+
+    def _plus(self, (x, y), field):
+        """Addition of share-tuples *x* and *y*.
+
+        Each party ``P_i`` computes:
+        ``[x]_i = (x_i, xk, xm)``
+        ``[y]_i = (y_i, yk, ym)``
+        ``[z]_i = [x]_i + [y]_i
+                = (x_i + y_i mod p, {xk^{i}_{j} + yk^{i}_{j} mod p}_{j=0}^{j=n}, {xm^{i}_{j} + ym^{i}_{j} mod p}_{j=0}^{j=n})
+        """
+        (xi, xks, xms) = x
+        (yi, yks, yms) = y
+        zi = xi + yi
+        zks = xks + yks
+        zms = xms + yms
+        return (zi, zks, zms)
--- a/viff/test/test_bedoza_runtime.py	Tue Jul 06 11:01:34 2010 +0200
+++ b/viff/test/test_bedoza_runtime.py	Tue Jul 06 11:01:53 2010 +0200
@@ -130,3 +130,84 @@
         d.addCallback(check)
         return d
 
+    @protocol
+    def test_plus(self, runtime):
+        """Test addition of two numbers."""
+
+        Zp = GF(6277101735386680763835789423176059013767194773182842284081)
+       
+        x = (Zp(2), BeDOZaKeyList(Zp(23), [Zp(3), Zp(4), Zp(1)]), BeDOZaMessageList([Zp(2), Zp(74), Zp(23), Zp(2)]))
+        y = (Zp(2), BeDOZaKeyList(Zp(23), [Zp(5), Zp(2), Zp(7)]), BeDOZaMessageList([Zp(2), Zp(74), Zp(23), Zp(2)]))
+        zi, zks, zms = runtime._plus((x, y), Zp)
+        self.assertEquals(zi, Zp(4))
+        self.assertEquals(zks, BeDOZaKeyList(Zp(23), [Zp(8), Zp(6), Zp(8)]))
+        self.assertEquals(zms, BeDOZaMessageList([Zp(4), Zp(148), Zp(46), Zp(4)]))
+        return zi
+
+    @protocol
+    def test_sum(self, runtime):
+        """Test addition of two numbers."""
+
+        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
+
+        def check(v):
+            self.assertEquals(v, 12)
+
+        x2 = runtime.random_share(self.Zp)
+        y2 = runtime.random_share(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."""
+
+        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
+
+        def check(v):
+            self.assertEquals(v, 12)
+
+        x2 = runtime.random_share(self.Zp)
+        y2 = runtime.random_share(self.Zp)
+        z2 = x2 + y2
+        d = runtime.open(z2)
+        d.addCallback(check)
+        return d
+
+    @protocol
+    def test_sum_constant_right(self, runtime):
+        """Test addition of secret shared number and a public number."""
+
+        self.Zp = GF(31)
+
+        x1 = 42
+        y1 = 7
+
+        def check(v):
+            self.assertEquals(v, 13)
+
+        x2 = runtime.random_share(self.Zp)
+        z2 = x2 + y1
+        d = runtime.open(z2)
+        d.addCallback(check)
+        return d
+
+    @protocol
+    def test_sum_constant_left(self, runtime):
+        """Test addition of a public number and secret shared number."""
+
+        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
+
+        x1 = 42
+        y1 = 7
+
+        def check(v):
+            self.assertEquals(v, 13)
+
+        x2 = runtime.random_share(self.Zp)
+        z2 = y1 + x2
+        d = runtime.open(z2)
+        d.addCallback(check)
+        return d