viff

changeset 1226:94086392cb3c

Implementation of addition command.
author Janus Dam Nielsen <janus.nielsen@alexandra.dk>
date Tue, 06 Oct 2009 10:05:24 +0200
parents bb9566f09d3f
children 5636b02c6bef
files viff/orlandi.py viff/test/test_orlandi_runtime.py
diffstat 2 files changed, 140 insertions(+), 1 deletions(-) [+]
line diff
     1.1 --- a/viff/orlandi.py	Tue Oct 06 10:05:24 2009 +0200
     1.2 +++ b/viff/orlandi.py	Tue Oct 06 10:05:24 2009 +0200
     1.3 @@ -20,6 +20,7 @@
     1.4  from viff.runtime import Runtime, Share, ShareList, gather_shares
     1.5  from viff.util import rand
     1.6  from viff.constants import TEXT
     1.7 +from viff.field import FieldElement
     1.8  
     1.9  from hash_broadcast import HashBroadcastMixin
    1.10  
    1.11 @@ -315,6 +316,69 @@
    1.12          self.activate_reactor()
    1.13  
    1.14          return s
    1.15 +    
    1.16 +    def add(self, share_a, share_b):
    1.17 +        """Addition of shares.
    1.18 +
    1.19 +        Communication cost: none.
    1.20 +
    1.21 +        Each party ``P_i`` computes:
    1.22 +        ``[z]_i = [x]_i + [y]_i
    1.23 +                = (x_i + y_i mod p, rho_xi + rho_yi mod p, C_x * C_y)``.
    1.24 +
    1.25 +        """
    1.26 +        def is_share(s, field):
    1.27 +            if not isinstance(s, Share):
    1.28 +                if not isinstance(s, FieldElement):
    1.29 +                    s = field(s)
    1.30 +                (v, rhov, Cv) = self._additive_constant(field(0), s)
    1.31 +                return OrlandiShare(self, field, v, rhov, Cv)
    1.32 +            return s
    1.33 +
    1.34 +        # Either share_a or share_b must have an attribute called "field". 
    1.35 +        field = getattr(share_a, "field", getattr(share_b, "field", None))
    1.36 +
    1.37 +        share_a = is_share(share_a, field)
    1.38 +        share_b = is_share(share_b, field)
    1.39 +
    1.40 +        # Add rho_xi and rho_yi and compute the commitment.
    1.41 +        def compute_sums((x, y)):
    1.42 +            (zi, (rhozi1, rhozi2), Cz) = self._plus(x, y)
    1.43 +            return OrlandiShare(self, field, zi, (rhozi1, rhozi2), Cz)
    1.44 +
    1.45 +        result = gather_shares([share_a, share_b])
    1.46 +        result.addCallbacks(compute_sums, self.error_handler)
    1.47 +        return result
    1.48 +
    1.49 +    def _additive_constant(self, zero, field_element):
    1.50 +        """Greate an additive constant.
    1.51 +
    1.52 +        Any additive constant can be interpreted as:
    1.53 +        ``[c]_1 = (c, 0, Com_ck(c,0))`` and
    1.54 +        ``[c]_i = (0, 0, Com_ck(c,0)) for i != 1``.
    1.55 +        """
    1.56 +        v = zero
    1.57 +        if self.id == 1:
    1.58 +            v = field_element
    1.59 +        Cx = commitment.commit(field_element.value, zero.value, zero.value)
    1.60 +        return (v, (zero, zero), Cx)
    1.61 +
    1.62 +    def _plus(self, x, y):
    1.63 +        """Addition of share-tuples *x* and *y*.
    1.64 +
    1.65 +        Each party ``P_i`` computes:
    1.66 +        ``[x]_i = (x_i, rho_xi, C_x)``
    1.67 +        ``[y]_i = (y_i, rho_yi, C_y)``
    1.68 +        ``[z]_i = [x]_i + [y]_i
    1.69 +                = (x_i + y_i mod p, rho_xi + rho_yi mod p, C_x * C_y)``.
    1.70 +        """
    1.71 +        (xi, (rhoxi1, rhoxi2), Cx) = x
    1.72 +        (yi, (rhoyi1, rhoyi2), Cy) = y
    1.73 +        zi = xi + yi
    1.74 +        rhozi1 = rhoxi1 + rhoyi1
    1.75 +        rhozi2 = rhoxi2 + rhoyi2
    1.76 +        Cz = Cx * Cy
    1.77 +        return (zi, (rhozi1, rhozi2), Cz)
    1.78  
    1.79      def error_handler(self, ex):
    1.80          print "Error: ", ex
     2.1 --- a/viff/test/test_orlandi_runtime.py	Tue Oct 06 10:05:24 2009 +0200
     2.2 +++ b/viff/test/test_orlandi_runtime.py	Tue Oct 06 10:05:24 2009 +0200
     2.3 @@ -75,7 +75,7 @@
     2.4      def test_random_share(self, runtime):
     2.5          """Test creation of a random shared number."""
     2.6  
     2.7 -        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)        
     2.8 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
     2.9  
    2.10          def check(v):
    2.11              self.assertEquals(True, True)           
    2.12 @@ -86,3 +86,78 @@
    2.13          return d
    2.14   
    2.15  
    2.16 +    @protocol
    2.17 +    def test_sum(self, runtime):
    2.18 +        """Test addition of two numbers."""
    2.19 +
    2.20 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
    2.21 + 
    2.22 +        x1 = 42
    2.23 +        y1 = 7
    2.24 +
    2.25 +        def check(v):
    2.26 +            self.assertEquals(v, x1 + y1)
    2.27 +
    2.28 +        if 1 == runtime.id:
    2.29 +            x2 = runtime.secret_share([1], self.Zp, x1)
    2.30 +        else:
    2.31 +            x2 = runtime.secret_share([1], self.Zp)
    2.32 +
    2.33 +        if 3 == runtime.id:
    2.34 +            y2 = runtime.secret_share([3], self.Zp, y1)
    2.35 +        else:
    2.36 +            y2 = runtime.secret_share([3], self.Zp)
    2.37 +
    2.38 +        z2 = runtime.add(x2, y2)
    2.39 +        d = runtime.open(z2)
    2.40 +        d.addCallback(check)
    2.41 +        return d
    2.42 +
    2.43 +    @protocol
    2.44 +    def test_sum_plus(self, runtime):
    2.45 +        """Test addition of two numbers."""
    2.46 +
    2.47 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
    2.48 +
    2.49 +        x1 = 42
    2.50 +        y1 = 7
    2.51 +
    2.52 +        def check(v):
    2.53 +            self.assertEquals(v, x1 + y1)
    2.54 +
    2.55 +        if 1 == runtime.id:
    2.56 +            x2 = runtime.secret_share([1], self.Zp, x1)
    2.57 +        else:
    2.58 +            x2 = runtime.secret_share([1], self.Zp)
    2.59 +
    2.60 +        if 3 == runtime.id:
    2.61 +            y2 = runtime.secret_share([3], self.Zp, y1)
    2.62 +        else:
    2.63 +            y2 = runtime.secret_share([3], self.Zp)
    2.64 +
    2.65 +        z2 = x2 + y2
    2.66 +        d = runtime.open(z2)
    2.67 +        d.addCallback(check)
    2.68 +        return d
    2.69 +
    2.70 +    @protocol
    2.71 +    def test_sum_constant(self, runtime):
    2.72 +        """Test addition of two numbers."""
    2.73 +
    2.74 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
    2.75 +
    2.76 +        x1 = 42
    2.77 +        y1 = 7
    2.78 +
    2.79 +        def check(v):
    2.80 +            self.assertEquals(v, x1 + y1)
    2.81 +
    2.82 +        if 1 == runtime.id:
    2.83 +            x2 = runtime.secret_share([1], self.Zp, x1)
    2.84 +        else:
    2.85 +            x2 = runtime.secret_share([1], self.Zp)
    2.86 +
    2.87 +        z2 = x2 + y1
    2.88 +        d = runtime.open(z2)
    2.89 +        d.addCallback(check)
    2.90 +        return d