viff

changeset 1471:06b1b7647643

BeDOZa: Moved multiplication functionality into SimpleArithmetic.
author Janus Dam Nielsen <janus.nielsen@alexandra.dk>
date Wed, 07 Jul 2010 15:40:45 +0200
parents f27609bc4831
children 55d2c1692771
files viff/bedoza.py viff/simplearithmetic.py viff/test/test_bedoza_runtime.py
diffstat 3 files changed, 138 insertions(+), 71 deletions(-) [+]
line diff
     1.1 --- a/viff/bedoza.py	Wed Jul 07 14:31:30 2010 +0200
     1.2 +++ b/viff/bedoza.py	Wed Jul 07 15:40:45 2010 +0200
     1.3 @@ -297,11 +297,16 @@
     1.4          return (zi, zks, zms)
     1.5  
     1.6      def _minus_public_right(self, x, c, field):
     1.7 +        (zi, zks, zms) = self._minus_public_right_without_share(x, c, field)
     1.8 +        return BeDOZaShare(self, field, zi, zks, zms)
     1.9 +
    1.10 +    def _minus_public_right_without_share(self, x, c, field):
    1.11          (xi, xks, xms) = x
    1.12          if self.id == 1:
    1.13              xi = xi - c
    1.14          xks.keys[0] = xks.keys[0] + xks.alpha * c
    1.15 -        return BeDOZaShare(self, field, xi, xks, xms)
    1.16 +        return xi, xks, xms
    1.17 +
    1.18  
    1.19      def _minus_public_left(self, x, c, field):
    1.20          y = self._constant_multiply(x, field(-1))
    1.21 @@ -372,69 +377,5 @@
    1.22                  c += share_c.value
    1.23          return [triple_a, triple_b, triple_c]
    1.24  
    1.25 -    def mul(self, share_x, share_y):
    1.26 -        """Multiplication of shares."""
    1.27 -        assert isinstance(share_x, Share) or isinstance(share_y, Share), \
    1.28 -            "At least one of share_x and share_y must be a Share."
    1.29 -
    1.30 -        self.increment_pc()
    1.31 -
    1.32 -        field = getattr(share_x, "field", getattr(share_y, "field", None))
    1.33 -
    1.34 -        triple = self._get_triple(field)
    1.35 -        return self._basic_multiplication(share_x, share_y, *triple)
    1.36 -
    1.37 -    def _basic_multiplication(self, share_x, share_y, triple_a, triple_b, triple_c):
    1.38 -        """Multiplication of shares give a triple.
    1.39 -
    1.40 -        Communication cost: ???.
    1.41 -
    1.42 -        ``d = Open([x] - [a])``
    1.43 -        ``e = Open([y] - [b])``
    1.44 -        ``[z] = e[x] + d[y] - [de] + [c]``
    1.45 -        """
    1.46 -        assert isinstance(share_x, Share) or isinstance(share_y, Share), \
    1.47 -            "At least one of share_x and share_y must be a Share."
    1.48 -
    1.49 -        self.increment_pc()
    1.50 -
    1.51 -        field = getattr(share_x, "field", getattr(share_y, "field", None))
    1.52 -        n = field(0)
    1.53 -
    1.54 -        cmul_result = self._cmul(share_x, share_y, field)
    1.55 -        if cmul_result is  not None:
    1.56 -            return cmul_result
    1.57 -
    1.58 -        def multiply((x, y, c, d, e)):
    1.59 -            # [de]
    1.60 -            de = d * e
    1.61 -            # e[x]
    1.62 -            t1 = self._constant_multiply(x, e)
    1.63 -            # d[y]
    1.64 -            t2 = self._constant_multiply(y, d)
    1.65 -            # d[y] - [de]
    1.66 -            t3 = self._minus_public_right1(t2, de, field)
    1.67 -            # d[y] - [de] + [c]
    1.68 -            t4 = self._plus((t3, c), field)
    1.69 -            # [z] = e[x] + d[y] - [de] + [c]
    1.70 -            zi, zks, zms = self._plus((t1, t4), field)
    1.71 -            return BeDOZaShare(self, field, zi, zks, zms)
    1.72 -
    1.73 -        #d = Open([x] - [a])
    1.74 -        d = self.output(share_x - triple_a)
    1.75 -        # e = Open([y] - [b])
    1.76 -        e = self.output(share_y - triple_b)
    1.77 -        result = gather_shares([share_x, share_y, triple_c, d, e])
    1.78 -        result.addCallbacks(multiply, self.error_handler)
    1.79 -
    1.80 -        # do actual communication
    1.81 -        self.activate_reactor()
    1.82 -
    1.83 -        return result
    1.84 -
    1.85 -    def _minus_public_right1(self, x, c, field):
    1.86 -        (xi, xks, xms) = x
    1.87 -        if self.id == 1:
    1.88 -            xi = xi - c
    1.89 -        xks.keys[0] = xks.keys[0] + xks.alpha * c
    1.90 -        return xi, xks, xms
    1.91 +    def _wrap_in_share(self, (zi, zks, zms), field):
    1.92 +        return BeDOZaShare(self, field, zi, zks, zms)
     2.1 --- a/viff/simplearithmetic.py	Wed Jul 07 14:31:30 2010 +0200
     2.2 +++ b/viff/simplearithmetic.py	Wed Jul 07 15:40:45 2010 +0200
     2.3 @@ -21,12 +21,19 @@
     2.4  class SimpleArithmetic:
     2.5      """Provides methods for addition and subtraction.
     2.6  
     2.7 -    Provides set: {add, sub}.
     2.8 -    Requires set: {self._plus((x,y), field),
     2.9 -                   self._minus((x,y), field),
    2.10 +    Provides set: {add, sub, mul}.
    2.11 +    Requires set: {self._plus((x, y), field),
    2.12 +                   self._minus((x, y), field),
    2.13                     self._plus_public(x, c, field),
    2.14                     self._minus_public_right(x, c, field),
    2.15 -                   self._minus_public_left(x, c, field)}.
    2.16 +                   self._minus_public_left(x, c, field),
    2.17 +                   self._wrap_in_share(x, field),
    2.18 +                   self._get_triple(field),
    2.19 +                   self._constant_multiply(x, c),
    2.20 +                   self._cmul(x, y, field),
    2.21 +                   self.open(x),
    2.22 +                   self.increment_pc(),
    2.23 +                   self.activate_reactor()}.
    2.24      """
    2.25  
    2.26      def add(self, share_a, share_b):
    2.27 @@ -74,3 +81,63 @@
    2.28              result = gather_shares([share_a, share_b])
    2.29              result.addCallbacks(self._minus, self.error_handler, callbackArgs=(field,))
    2.30              return result
    2.31 +
    2.32 +    def mul(self, share_x, share_y):
    2.33 +        """Multiplication of shares."""
    2.34 +        assert isinstance(share_x, Share) or isinstance(share_y, Share), \
    2.35 +            "At least one of share_x and share_y must be a Share."
    2.36 +
    2.37 +        self.increment_pc()
    2.38 +
    2.39 +        field = getattr(share_x, "field", getattr(share_y, "field", None))
    2.40 +
    2.41 +        triple = self._get_triple(field)
    2.42 +        return self._basic_multiplication(share_x, share_y, *triple)
    2.43 +
    2.44 +    def _basic_multiplication(self, share_x, share_y, triple_a, triple_b, triple_c):
    2.45 +        """Multiplication of shares give a triple.
    2.46 +
    2.47 +        Communication cost: ???.
    2.48 +
    2.49 +        ``d = Open([x] - [a])``
    2.50 +        ``e = Open([y] - [b])``
    2.51 +        ``[z] = e[x] + d[y] - [de] + [c]``
    2.52 +        """
    2.53 +        assert isinstance(share_x, Share) or isinstance(share_y, Share), \
    2.54 +            "At least one of share_x and share_y must be a Share."
    2.55 +
    2.56 +        self.increment_pc()
    2.57 +
    2.58 +        field = getattr(share_x, "field", getattr(share_y, "field", None))
    2.59 +        n = field(0)
    2.60 +
    2.61 +        cmul_result = self._cmul(share_x, share_y, field)
    2.62 +        if cmul_result is  not None:
    2.63 +            return cmul_result
    2.64 +
    2.65 +        def multiply((x, y, c, d, e)):
    2.66 +            # [de]
    2.67 +            de = d * e
    2.68 +            # e[x]
    2.69 +            t1 = self._constant_multiply(x, e)
    2.70 +            # d[y]
    2.71 +            t2 = self._constant_multiply(y, d)
    2.72 +            # d[y] - [de]
    2.73 +            t3 = self._minus_public_right_without_share(t2, de, field)
    2.74 +            # d[y] - [de] + [c]
    2.75 +            t4 = self._plus((t3, c), field)
    2.76 +            # [z] = e[x] + d[y] - [de] + [c]
    2.77 +            z = self._plus((t1, t4), field)
    2.78 +            return self._wrap_in_share(z, field)
    2.79 +
    2.80 +        #d = Open([x] - [a])
    2.81 +        d = self.output(share_x - triple_a)
    2.82 +        # e = Open([y] - [b])
    2.83 +        e = self.output(share_y - triple_b)
    2.84 +        result = gather_shares([share_x, share_y, triple_c, d, e])
    2.85 +        result.addCallbacks(multiply, self.error_handler)
    2.86 +
    2.87 +        # do actual communication
    2.88 +        self.activate_reactor()
    2.89 +
    2.90 +        return result
     3.1 --- a/viff/test/test_bedoza_runtime.py	Wed Jul 07 14:31:30 2010 +0200
     3.2 +++ b/viff/test/test_bedoza_runtime.py	Wed Jul 07 15:40:45 2010 +0200
     3.3 @@ -371,3 +371,62 @@
     3.4          d = runtime.open(z2)
     3.5          d.addCallback(check)
     3.6          return d
     3.7 +
     3.8 +    @protocol
     3.9 +    def test_mul_mul(self, runtime):
    3.10 +        """Test multiplication of two numbers."""
    3.11 +
    3.12 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
    3.13 +
    3.14 +        x1 = 6
    3.15 +        y1 = 6
    3.16 +
    3.17 +        def check(v):
    3.18 +            self.assertEquals(v, x1 * y1)
    3.19 +
    3.20 +        x2 = runtime.random_share(self.Zp)
    3.21 +        y2 = runtime.random_share(self.Zp)
    3.22 +
    3.23 +        z2 = x2 * y2
    3.24 +        d = runtime.open(z2)
    3.25 +        d.addCallback(check)
    3.26 +        return d
    3.27 +    @protocol
    3.28 +    def test_basic_multiply_constant_right(self, runtime):
    3.29 +        """Test multiplication of two numbers."""
    3.30 +
    3.31 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
    3.32 +
    3.33 +        x1 = 6
    3.34 +        y1 = 6
    3.35 +
    3.36 +        def check(v):
    3.37 +            self.assertEquals(v, x1 * y1)
    3.38 +
    3.39 +        x2 = runtime.random_share(self.Zp)
    3.40 +
    3.41 +        a, b, c = runtime._get_triple(self.Zp)
    3.42 +        z2 = runtime._basic_multiplication(x2, self.Zp(y1), a, b, c)
    3.43 +        d = runtime.open(z2)
    3.44 +        d.addCallback(check)
    3.45 +        return d
    3.46 +
    3.47 +    @protocol
    3.48 +    def test_basic_multiply_constant_left(self, runtime):
    3.49 +        """Test multiplication of two numbers."""
    3.50 +
    3.51 +        self.Zp = GF(6277101735386680763835789423176059013767194773182842284081)
    3.52 +
    3.53 +        x1 = 6
    3.54 +        y1 = 6
    3.55 +
    3.56 +        def check(v):
    3.57 +            self.assertEquals(v, x1 * y1)
    3.58 +
    3.59 +        x2 = runtime.random_share(self.Zp)
    3.60 +
    3.61 +        a, b, c = runtime._get_triple(self.Zp)
    3.62 +        z2 = runtime._basic_multiplication(self.Zp(y1), x2, a, b, c)
    3.63 +        d = runtime.open(z2)
    3.64 +        d.addCallback(check)
    3.65 +        return d