viff

changeset 1460:9a4e722f182b

Orlandi: Refactored addition and subtraction into their own mixin.
author Janus Dam Nielsen Tue, 06 Jul 2010 14:10:13 +0200 007822876664 85c41e1f7328 viff/orlandi.py viff/simplearithmetic.py viff/test/test_orlandi_runtime.py 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.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.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.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.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.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.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.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.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.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.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
```