viff

changeset 1460:9a4e722f182b

Orlandi: Refactored addition and subtraction into their own mixin.
author Janus Dam Nielsen <janus.nielsen@alexandra.dk>
date Tue, 06 Jul 2010 14:10:13 +0200
parents 007822876664
children 85c41e1f7328
files viff/orlandi.py viff/simplearithmetic.py viff/test/test_orlandi_runtime.py
diffstat 3 files changed, 136 insertions(+), 110 deletions(-) [+]
line diff
     1.1 --- a/viff/orlandi.py	Tue Jul 06 11:01:53 2010 +0200
     1.2 +++ b/viff/orlandi.py	Tue Jul 06 14:10:13 2010 +0200
     1.3 @@ -33,6 +33,8 @@
     1.4  from viff.field import FieldElement
     1.5  from viff.paillier import encrypt_r, decrypt
     1.6  
     1.7 +from viff.simplearithmetic import SimpleArithmetic
     1.8 +
     1.9  from hash_broadcast import HashBroadcastMixin
    1.10  
    1.11  try:
    1.12 @@ -96,7 +98,7 @@
    1.13          Share.__init__(self, runtime, field, (value, rho, commitment))
    1.14  
    1.15  
    1.16 -class OrlandiRuntime(Runtime, HashBroadcastMixin):
    1.17 +class OrlandiRuntime(SimpleArithmetic, Runtime, HashBroadcastMixin):
    1.18      """The Orlandi runtime.
    1.19  
    1.20      The runtime is used for sharing values (:meth:`secret_share` or
    1.21 @@ -423,72 +425,69 @@
    1.22  
    1.23          return s
    1.24  
    1.25 -    def add(self, share_a, share_b):
    1.26 -        """Addition of shares.
    1.27 +    def _convert_public_to_share(self, c, field):
    1.28 +        """Convert a public value to a share.
    1.29 +        
    1.30 +        Any additive constant can be interpreted as:
    1.31 +        ``[c]_1 = (c, 0, Com_ck(c,0))`` and
    1.32 +        ``[c]_i = (0, 0, Com_ck(c,0)) for i != 1``.
    1.33 +        """
    1.34 +        zero = field(0)
    1.35 +        ci = zero
    1.36 +        if self.id == 1:
    1.37 +            ci = c
    1.38 +        return self._constant(ci, c, field)
    1.39  
    1.40 -        Communication cost: none.
    1.41 +    def _constant(self, xi, x, field):
    1.42 +        """Greate a share *xi* with commitment to value *x*."""
    1.43 +        zero = field(0)
    1.44 +        Cx = commitment.commit(x.value, 0, 0)
    1.45 +        return (xi, (zero, zero), Cx)
    1.46  
    1.47 -        Each party ``P_i`` computes::
    1.48 +    def _plus_public(self, x, c, field):
    1.49 +        return self._do_arithmetic_op(x, c, field, self._plus)
    1.50  
    1.51 -          [z]_i = [x]_i + [y]_i
    1.52 -                = (x_i + y_i mod p, rho_xi + rho_yi mod p, C_x * C_y)
    1.53 +    def _plus(self, (x, y), field):
    1.54 +        """Addition of share-tuples *x* and *y*.
    1.55  
    1.56 +        Each party ``P_i`` computes:
    1.57 +        ``[x]_i = (x_i, rho_xi, C_x)``
    1.58 +        ``[y]_i = (y_i, rho_yi, C_y)``
    1.59 +        ``[z]_i = [x]_i + [y]_i
    1.60 +                = (x_i + y_i mod p, rho_xi + rho_yi mod p, C_x * C_y)``.
    1.61          """
    1.62 -        def is_share(s, field):
    1.63 -            if not isinstance(s, Share):
    1.64 -                if not isinstance(s, FieldElement):
    1.65 -                    s = field(s)
    1.66 -                (v, rhov, Cv) = self._additive_constant(field(0), s)
    1.67 -                return OrlandiShare(self, field, v, rhov, Cv)
    1.68 -            return s
    1.69 +        (xi, (rhoxi1, rhoxi2), Cx) = x
    1.70 +        (yi, (rhoyi1, rhoyi2), Cy) = y
    1.71 +        zi = xi + yi
    1.72 +        rhozi1 = rhoxi1 + rhoyi1
    1.73 +        rhozi2 = rhoxi2 + rhoyi2
    1.74 +        Cz = Cx * Cy
    1.75 +        return (zi, (rhozi1, rhozi2), Cz)
    1.76  
    1.77 -        # Either share_a or share_b must have an attribute called "field".
    1.78 -        field = share_a.field
    1.79 +    def _minus_public(self, x, c, field):
    1.80 +        return self._do_arithmetic_op(x, c, field, self._minus)
    1.81  
    1.82 -        share_b = is_share(share_b, field)
    1.83 +    def _do_arithmetic_op(self, x, c, field, op):
    1.84 +        y = self._convert_public_to_share(c, field)
    1.85 +        (zi, (rhozi1, rhozi2), Cz) = op((x, y), field)
    1.86 +        return OrlandiShare(self, field, zi, (rhozi1, rhozi2), Cz)
    1.87  
    1.88 -        # Add rho_xi and rho_yi and compute the commitment.
    1.89 -        def compute_sums((x, y)):
    1.90 -            (zi, (rhozi1, rhozi2), Cz) = self._plus(x, y)
    1.91 -            return OrlandiShare(self, field, zi, (rhozi1, rhozi2), Cz)
    1.92 +    def _minus(self, (x, y), field):
    1.93 +        """Subtraction of share-tuples *x* and *y*.
    1.94  
    1.95 -        result = gather_shares([share_a, share_b])
    1.96 -        result.addCallbacks(compute_sums, self.error_handler)
    1.97 -        return result
    1.98 -
    1.99 -    def sub(self, share_a, share_b):
   1.100 -        """Subtraction of shares.
   1.101 -
   1.102 -        Communication cost: none.
   1.103 -
   1.104 -        Each party ``P_i`` computes::
   1.105 -
   1.106 -          [z]_i = [x]_i - [y]_i
   1.107 -                = (x_i - y_i mod p, rho_x,i - rho_y,i mod p, C_x * C_y)
   1.108 -
   1.109 +        Each party ``P_i`` computes:
   1.110 +        ``[x]_i = (x_i, rho_x,i, C_x)``
   1.111 +        ``[y]_i = (y_i, rho_y,i, C_y)``
   1.112 +        ``[z]_i = [x]_i - [y]_i
   1.113 +                = (x_i - y_i mod p, rho_x,i - rho_y,i mod p, C_x / C_y)``.
   1.114          """
   1.115 -        def is_share(s, field):
   1.116 -            if not isinstance(s, Share):
   1.117 -                if not isinstance(s, FieldElement):
   1.118 -                    s = field(s)
   1.119 -                (v, rhov, Cv) = self._additive_constant(field(0), s)
   1.120 -                return OrlandiShare(self, field, v, rhov, Cv)
   1.121 -            return s
   1.122 -
   1.123 -        # Either share_a or share_b must have an attribute called "field".
   1.124 -        field = getattr(share_a, "field", getattr(share_b, "field", None))
   1.125 -
   1.126 -        share_a = is_share(share_a, field)
   1.127 -        share_b = is_share(share_b, field)
   1.128 -
   1.129 -        # Subtract xi and yi, rhoxi and rhoyi, and compute the commitment
   1.130 -        def compute_subs((x, y)):
   1.131 -            zi, (rhozi1, rhozi2), Cz = self._minus(x, y)
   1.132 -            return OrlandiShare(self, field, zi, (rhozi1, rhozi2), Cz)
   1.133 -
   1.134 -        result = gather_shares([share_a, share_b])
   1.135 -        result.addCallbacks(compute_subs, self.error_handler)
   1.136 -        return result
   1.137 +        xi, (rhoxi1, rhoxi2), Cx = x
   1.138 +        yi, (rhoyi1, rhoyi2), Cy = y
   1.139 +        zi = xi - yi
   1.140 +        rhozi1 = rhoxi1 - rhoyi1
   1.141 +        rhozi2 = rhoxi2 - rhoyi2
   1.142 +        Cz = Cx / Cy
   1.143 +        return (zi, (rhozi1, rhozi2), Cz)
   1.144  
   1.145      def input(self, inputters, field, number=None):
   1.146          """Input *number* to the computation.
   1.147 @@ -587,53 +586,6 @@
   1.148              triple = [Share(self, field, i) for i in triple]
   1.149          return self._basic_multiplication(share_x, share_y, *triple)
   1.150  
   1.151 -    def _additive_constant(self, zero, field_element):
   1.152 -        """Greate an additive constant.
   1.153 -
   1.154 -        Any additive constant can be interpreted as:
   1.155 -        ``[c]_1 = (c, 0, Com_ck(c,0))`` and
   1.156 -        ``[c]_i = (0, 0, Com_ck(c,0)) for i != 1``.
   1.157 -        """
   1.158 -        v = zero
   1.159 -        if self.id == 1:
   1.160 -            v = field_element
   1.161 -        Cx = commitment.commit(field_element.value, zero.value, zero.value)
   1.162 -        return (v, (zero, zero), Cx)
   1.163 -
   1.164 -    def _plus(self, x, y):
   1.165 -        """Addition of share-tuples *x* and *y*.
   1.166 -
   1.167 -        Each party ``P_i`` computes:
   1.168 -        ``[x]_i = (x_i, rho_xi, C_x)``
   1.169 -        ``[y]_i = (y_i, rho_yi, C_y)``
   1.170 -        ``[z]_i = [x]_i + [y]_i
   1.171 -                = (x_i + y_i mod p, rho_xi + rho_yi mod p, C_x * C_y)``.
   1.172 -        """
   1.173 -        (xi, (rhoxi1, rhoxi2), Cx) = x
   1.174 -        (yi, (rhoyi1, rhoyi2), Cy) = y
   1.175 -        zi = xi + yi
   1.176 -        rhozi1 = rhoxi1 + rhoyi1
   1.177 -        rhozi2 = rhoxi2 + rhoyi2
   1.178 -        Cz = Cx * Cy
   1.179 -        return (zi, (rhozi1, rhozi2), Cz)
   1.180 -
   1.181 -    def _minus(self, x, y):
   1.182 -        """Subtraction of share-tuples *x* and *y*.
   1.183 -
   1.184 -        Each party ``P_i`` computes:
   1.185 -        ``[x]_i = (x_i, rho_x,i, C_x)``
   1.186 -        ``[y]_i = (y_i, rho_y,i, C_y)``
   1.187 -        ``[z]_i = [x]_i - [y]_i
   1.188 -                = (x_i - y_i mod p, rho_x,i - rho_y,i mod p, C_x / C_y)``.
   1.189 -        """
   1.190 -        xi, (rhoxi1, rhoxi2), Cx = x
   1.191 -        yi, (rhoyi1, rhoyi2), Cy = y
   1.192 -        zi = xi - yi
   1.193 -        rhozi1 = rhoxi1 - rhoyi1
   1.194 -        rhozi2 = rhoxi2 - rhoyi2
   1.195 -        Cz = Cx / Cy
   1.196 -        return (zi, (rhozi1, rhozi2), Cz)
   1.197 -
   1.198      def _cmul(self, share_x, share_y, field):
   1.199          """Multiplication of a share with a constant.
   1.200  
   1.201 @@ -685,7 +637,7 @@
   1.202          self.random_triple(field, 1)[0].addCallbacks(chain, self.error_handler,
   1.203                                                       (results,))
   1.204          return results
   1.205 -
   1.206 +    
   1.207      def _basic_multiplication(self, share_x, share_y, triple_a, triple_b, triple_c):
   1.208          """Multiplication of shares give a triple.
   1.209  
   1.210 @@ -711,17 +663,17 @@
   1.211              d = ds[0]
   1.212              e = ds[1]
   1.213              # [de]
   1.214 -            de = self._additive_constant(field(0), d * e)
   1.215 +            de = self._convert_public_to_share(d * e, field)
   1.216              # e[x]
   1.217              t1 = self._const_mul(e.value, x)
   1.218              # d[y]
   1.219              t2 = self._const_mul(d.value, y)
   1.220              # d[y] - [de]
   1.221 -            t3 = self._minus(t2, de)
   1.222 +            t3 = self._minus((t2, de), field)
   1.223              # d[y] - [de] + [c]
   1.224 -            t4 = self._plus(t3, c)
   1.225 +            t4 = self._plus((t3, c), field)
   1.226              # [z] = e[x] + d[y] - [de] + [c]
   1.227 -            zi, rhoz, Cz = self._plus(t1, t4)
   1.228 +            zi, rhoz, Cz = self._plus((t1, t4), field)
   1.229              return OrlandiShare(self, field, zi, rhoz, Cz)
   1.230  
   1.231          # d = Open([x] - [a])
   1.232 @@ -815,7 +767,7 @@
   1.233              # [F_j] = [x] + SUM_i=1^d [f_i]*j^i
   1.234              # and
   1.235              # [G_j] = [y] + SUM_i=1^d [g_i]*j^i
   1.236 -            h0i, rhoh0, Ch0 = self._additive_constant(field(0), n)
   1.237 +            h0i, rhoh0, Ch0 = self._convert_public_to_share(n, field)
   1.238              H0 = OrlandiShare(self, field, h0i, rhoh0, Ch0)
   1.239              xi, (rhoxi1, rhoxi2), Cx = x
   1.240              yi, (rhoyi1, rhoyi2), Cy = y
     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/viff/simplearithmetic.py	Tue Jul 06 14:10:13 2010 +0200
     2.3 @@ -0,0 +1,58 @@
     2.4 +# Copyright 2010 VIFF Development Team.
     2.5 +#
     2.6 +# This file is part of VIFF, the Virtual Ideal Functionality Framework.
     2.7 +#
     2.8 +# VIFF is free software: you can redistribute it and/or modify it
     2.9 +# under the terms of the GNU Lesser General Public License (LGPL) as
    2.10 +# published by the Free Software Foundation, either version 3 of the
    2.11 +# License, or (at your option) any later version.
    2.12 +#
    2.13 +# VIFF is distributed in the hope that it will be useful, but WITHOUT
    2.14 +# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
    2.15 +# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
    2.16 +# Public License for more details.
    2.17 +#
    2.18 +# You should have received a copy of the GNU Lesser General Public
    2.19 +# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
    2.20 +
    2.21 +from viff.runtime import Share, gather_shares
    2.22 +from viff.field import FieldElement
    2.23 +
    2.24 +class SimpleArithmetic:
    2.25 +    """Provides methods for addition and subtraction.
    2.26 +
    2.27 +    Provides set: {add, sub}.
    2.28 +    Requires set: {self._plus((x,y), field), self._minus((x,y), field),
    2.29 +                   self._convert_public_to_share_and_do(operation)}.
    2.30 +    """
    2.31 +
    2.32 +    def add(self, share_a, share_b):
    2.33 +        """Addition of shares.
    2.34 +
    2.35 +        share_a is assumed to be an instance of Share.
    2.36 +        If share_b is also an instance of Share then self._plus gets called.
    2.37 +        If not then self._add_public get called.
    2.38 +        """
    2.39 +        return self.both_shares(share_a, share_b, self._plus_public, self._plus)
    2.40 +
    2.41 +    def sub(self, share_a, share_b):
    2.42 +        """Subtraction of shares.
    2.43 +
    2.44 +        share_a is assumed to be an instance of Share.
    2.45 +        If share_b is also an instance of Share then self._minus gets called.
    2.46 +        If not then self._sub_public get called.
    2.47 +        """
    2.48 +        return self.both_shares(share_a, share_b, self._minus_public, self._minus)
    2.49 +
    2.50 +
    2.51 +    def both_shares(self, share_a, share_b, if_not, if_so):
    2.52 +        field = share_a.field
    2.53 +        if not isinstance(share_b, Share):
    2.54 +            if not isinstance(share_b, FieldElement):
    2.55 +                share_b = field(share_b)
    2.56 +            share_a.addCallbacks(if_not, self.error_handler, callbackArgs=(share_b, field))
    2.57 +            return share_a
    2.58 +        else:
    2.59 +            result = gather_shares([share_a, share_b])
    2.60 +            result.addCallbacks(if_so, self.error_handler, callbackArgs=(field,))
    2.61 +            return result
     3.1 --- a/viff/test/test_orlandi_runtime.py	Tue Jul 06 11:01:53 2010 +0200
     3.2 +++ b/viff/test/test_orlandi_runtime.py	Tue Jul 06 14:10:13 2010 +0200
     3.3 @@ -140,6 +140,22 @@
     3.4          return d
     3.5  
     3.6      @protocol
     3.7 +    def test_plus(self, runtime):
     3.8 +        """Test addition of two numbers."""
     3.9 +
    3.10 +        Zp = GF(6277101735386680763835789423176059013767194773182842284081)
    3.11 +
    3.12 +        Cx = commitment.commit(7, 4, 5)
    3.13 +        x = (Zp(2), (Zp(2), Zp(2)), Cx)
    3.14 +        y = (Zp(2), (Zp(2), Zp(2)), Cx)
    3.15 +        zi, (rho1, rho2), Cz = runtime._plus((x, y), Zp)
    3.16 +        self.assertEquals(zi, Zp(4))
    3.17 +        self.assertEquals(rho1, 4)
    3.18 +        self.assertEquals(rho2, 4)
    3.19 +        self.assertEquals(Cz, Cx * Cx) 
    3.20 +        return zi
    3.21 +
    3.22 +    @protocol
    3.23      def test_sum(self, runtime):
    3.24          """Test addition of two numbers."""
    3.25