viff

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 diff
     1.1 --- a/viff/bedoza.py	Tue Jul 06 11:01:34 2010 +0200
     1.2 +++ b/viff/bedoza.py	Tue Jul 06 11:01:53 2010 +0200
     1.3 @@ -19,7 +19,8 @@
     1.4  
     1.5  from twisted.internet.defer import Deferred, gatherResults, succeed
     1.6  
     1.7 -from viff.runtime import Runtime, Share, ShareList
     1.8 +from viff.runtime import Runtime, Share, ShareList, gather_shares
     1.9 +from viff.field import FieldElement
    1.10  
    1.11  from hash_broadcast import HashBroadcastMixin
    1.12  
    1.13 @@ -253,3 +254,50 @@
    1.14  
    1.15      def get_alpha(self):
    1.16          return self.keys[0]
    1.17 +        
    1.18 +    def add(self, share_a, share_b):
    1.19 +        """Addition of shares.
    1.20 +
    1.21 +        Communication cost: none.
    1.22 +
    1.23 +        Each party ``P_i`` computes::
    1.24 +
    1.25 +          [z]_i = [x]_i + [y]_i
    1.26 +                = (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})
    1.27 +
    1.28 +        """
    1.29 +        # Either share_a or share_b must have an attribute called "field".
    1.30 +        field = share_a.field
    1.31 +        if not isinstance(share_b, Share):
    1.32 +            if not isinstance(share_b, FieldElement):
    1.33 +                share_b = field(share_b)
    1.34 +            share_a.addCallbacks(self._add_public, self.error_handler, callbackArgs=(share_b, field))
    1.35 +            return share_a
    1.36 +        else:
    1.37 +            result = gather_shares([share_a, share_b])
    1.38 +            result.addCallbacks(self._plus, self.error_handler, callbackArgs=(field,))
    1.39 +            return result
    1.40 +
    1.41 +    def _add_public(self, x, y, field):
    1.42 +        """Greate an additive constant."""
    1.43 +        (xi, xks, xms) = x
    1.44 +        if self.id == 1:
    1.45 +            xi = xi + y
    1.46 +        xks.keys[0] = xks.keys[0] - xks.alpha * y
    1.47 +        return BeDOZaShare(self, field, xi, xks, xms)
    1.48 +
    1.49 +    def _plus(self, (x, y), field):
    1.50 +        """Addition of share-tuples *x* and *y*.
    1.51 +
    1.52 +        Each party ``P_i`` computes:
    1.53 +        ``[x]_i = (x_i, xk, xm)``
    1.54 +        ``[y]_i = (y_i, yk, ym)``
    1.55 +        ``[z]_i = [x]_i + [y]_i
    1.56 +                = (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})
    1.57 +        """
    1.58 +        (xi, xks, xms) = x
    1.59 +        (yi, yks, yms) = y
    1.60 +        zi = xi + yi
    1.61 +        zks = xks + yks
    1.62 +        zms = xms + yms
    1.63 +        return (zi, zks, zms)
     2.1 --- a/viff/test/test_bedoza_runtime.py	Tue Jul 06 11:01:34 2010 +0200
     2.2 +++ b/viff/test/test_bedoza_runtime.py	Tue Jul 06 11:01:53 2010 +0200
     2.3 @@ -130,3 +130,84 @@
     2.4          d.addCallback(check)
     2.5          return d
     2.6  
     2.7 +    @protocol
     2.8 +    def test_plus(self, runtime):
     2.9 +        """Test addition of two numbers."""
    2.10 +
    2.11 +        Zp = GF(6277101735386680763835789423176059013767194773182842284081)
    2.12 +       
    2.13 +        x = (Zp(2), BeDOZaKeyList(Zp(23), [Zp(3), Zp(4), Zp(1)]), BeDOZaMessageList([Zp(2), Zp(74), Zp(23), Zp(2)]))
    2.14 +        y = (Zp(2), BeDOZaKeyList(Zp(23), [Zp(5), Zp(2), Zp(7)]), BeDOZaMessageList([Zp(2), Zp(74), Zp(23), Zp(2)]))
    2.15 +        zi, zks, zms = runtime._plus((x, y), Zp)
    2.16 +        self.assertEquals(zi, Zp(4))
    2.17 +        self.assertEquals(zks, BeDOZaKeyList(Zp(23), [Zp(8), Zp(6), Zp(8)]))
    2.18 +        self.assertEquals(zms, BeDOZaMessageList([Zp(4), Zp(148), Zp(46), Zp(4)]))
    2.19 +        return zi
    2.20 +
    2.21 +    @protocol
    2.22 +    def test_sum(self, runtime):
    2.23 +        """Test addition of two numbers."""
    2.24 +
    2.25 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
    2.26 +
    2.27 +        def check(v):
    2.28 +            self.assertEquals(v, 12)
    2.29 +
    2.30 +        x2 = runtime.random_share(self.Zp)
    2.31 +        y2 = runtime.random_share(self.Zp)
    2.32 +        z2 = runtime.add(x2, y2)
    2.33 +        d = runtime.open(z2)
    2.34 +        d.addCallback(check)
    2.35 +        return d
    2.36 +
    2.37 +    @protocol
    2.38 +    def test_sum_plus(self, runtime):
    2.39 +        """Test addition of two numbers."""
    2.40 +
    2.41 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
    2.42 +
    2.43 +        def check(v):
    2.44 +            self.assertEquals(v, 12)
    2.45 +
    2.46 +        x2 = runtime.random_share(self.Zp)
    2.47 +        y2 = runtime.random_share(self.Zp)
    2.48 +        z2 = x2 + y2
    2.49 +        d = runtime.open(z2)
    2.50 +        d.addCallback(check)
    2.51 +        return d
    2.52 +
    2.53 +    @protocol
    2.54 +    def test_sum_constant_right(self, runtime):
    2.55 +        """Test addition of secret shared number and a public number."""
    2.56 +
    2.57 +        self.Zp = GF(31)
    2.58 +
    2.59 +        x1 = 42
    2.60 +        y1 = 7
    2.61 +
    2.62 +        def check(v):
    2.63 +            self.assertEquals(v, 13)
    2.64 +
    2.65 +        x2 = runtime.random_share(self.Zp)
    2.66 +        z2 = x2 + y1
    2.67 +        d = runtime.open(z2)
    2.68 +        d.addCallback(check)
    2.69 +        return d
    2.70 +
    2.71 +    @protocol
    2.72 +    def test_sum_constant_left(self, runtime):
    2.73 +        """Test addition of a public number and secret shared number."""
    2.74 +
    2.75 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
    2.76 +
    2.77 +        x1 = 42
    2.78 +        y1 = 7
    2.79 +
    2.80 +        def check(v):
    2.81 +            self.assertEquals(v, 13)
    2.82 +
    2.83 +        x2 = runtime.random_share(self.Zp)
    2.84 +        z2 = y1 + x2
    2.85 +        d = runtime.open(z2)
    2.86 +        d.addCallback(check)
    2.87 +        return d