viff

changeset 918:83c89640a6ee

Probabilistic equality mixin.
author Sigurd Meldgaard <stm@daimi.au.dk>
date Tue, 16 Sep 2008 16:09:25 +0200
parents efa3a7721e4a
children 6d14c1d7c92d
files viff/equality.py
diffstat 1 files changed, 107 insertions(+), 0 deletions(-) [+]
line diff
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/viff/equality.py	Tue Sep 16 16:09:25 2008 +0200
     1.3 @@ -0,0 +1,107 @@
     1.4 +# Copyright 2008 VIFF Development Team.
     1.5 +#
     1.6 +# This file is part of VIFF, the Virtual Ideal Functionality Framework.
     1.7 +#
     1.8 +# VIFF is free software: you can redistribute it and/or modify it
     1.9 +# under the terms of the GNU Lesser General Public License (LGPL) as
    1.10 +# published by the Free Software Foundation, either version 3 of the
    1.11 +# License, or (at your option) any later version.
    1.12 +#
    1.13 +# VIFF is distributed in the hope that it will be useful, but WITHOUT
    1.14 +# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
    1.15 +# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
    1.16 +# Public License for more details.
    1.17 +#
    1.18 +# You should have received a copy of the GNU Lesser General Public
    1.19 +# License along with VIFF. If not, see <http://www.gnu.org/licenses/>.
    1.20 +
    1.21 +"""Equality protocol. The mixin class defined here provide an
    1.22 +:meth:`equal` method to the :class:`Runtime <viff.runtime.Runtime>` it
    1.23 +is mixed with.
    1.24 +"""
    1.25 +
    1.26 +from viff.runtime import increment_pc
    1.27 +
    1.28 +class ProbabilisticEqualityMixin:
    1.29 +    """This class implements probabilistic constant-round secure
    1.30 +    equality-testing of secret shared numbers."""
    1.31 +
    1.32 +    @increment_pc
    1.33 +    def equal(self, share_x, share_y):
    1.34 +        """Equality testing with secret shared result.
    1.35 +
    1.36 +        Assumes p = 3 mod 4, returns a secret sharing of 1 if share_x
    1.37 +        == share_y and 0 otherwise.
    1.38 +
    1.39 +        This is the probabilistic method based on quadratic
    1.40 +        reciprocity described in: "Constant-Round Multiparty
    1.41 +        Computation for Interval Test, Equality Test, and Comparison"
    1.42 +        by Takashi Nishide and Kazuo Ohta, and fails with probability
    1.43 +        1/(2**k) where k is set to the security parameter of the
    1.44 +        runtime.
    1.45 +
    1.46 +        TODO: Make it work for any prime-modulo, the b's should be in
    1.47 +        {y,1} where y is a non-square modulo p.
    1.48 +
    1.49 +        TODO: Make the final "and"ing of the x's more efficient as
    1.50 +        described in the paper.
    1.51 +        """
    1.52 +
    1.53 +        Zp = share_x.field
    1.54 +
    1.55 +        a = share_x - share_y # We will check if a == 0
    1.56 +        k = self.options.security_parameter
    1.57 +
    1.58 +        # The b's are random numbers in {-1, 1}
    1.59 +        b = [self.prss_share_random(Zp, binary=True) * 2 - 1
    1.60 +             for _ in range(k)]
    1.61 +        r = [self.prss_share_random(Zp) for _ in range(k)]
    1.62 +        rp = [self.prss_share_random(Zp) for _ in range(k)]
    1.63 +
    1.64 +        # If b_i == 1 c_i will always be a square modulo p if a is
    1.65 +        # zero and with probability 1/2 otherwise (except if rp == 0).
    1.66 +        # If b_i == -1 it will be non-square.
    1.67 +        c = [self.open(a * r[j] + b[j] * rp[j] * rp[j]) for j in range(k)]
    1.68 +
    1.69 +        def finish(cj, bj):
    1.70 +            l = legendre_mod_p(cj)
    1.71 +            # This will only happen with negligible probability.
    1.72 +            assert l != 0
    1.73 +            if l == 1:
    1.74 +                xj = (1/Zp(2)) * (bj + 1)
    1.75 +            else: # l == -1
    1.76 +                assert(l == -1)
    1.77 +                xj = (-1) * (1/Zp(2)) * (bj - 1)
    1.78 +            return xj
    1.79 +
    1.80 +        x = [cj.addCallback(finish, bj) for cj, bj in zip(c, b)]
    1.81 +
    1.82 +        # Take the product (this is here the same as the "and") of all
    1.83 +        # the x'es
    1.84 +        while len(x) > 1:
    1.85 +            x.append(x.pop() * x.pop())
    1.86 +
    1.87 +        return x[0]
    1.88 +
    1.89 +def legendre_mod_p(a):
    1.90 +    """Return the legendre symbol ``legendre(a, p)`` where *p* is the
    1.91 +    order of the field of *a*.
    1.92 +
    1.93 +    The legendre symbol is -1 if *a* is not a square mod *p*, 0 if
    1.94 +    ``gcd(a, p)`` is not 1, and 1 if *a* is a square mod *p*:
    1.95 +
    1.96 +    >>> from viff.field import GF
    1.97 +    >>> legendre_mod_p(GF(5)(2))
    1.98 +    -1
    1.99 +    >>> legendre_mod_p(GF(5)(5))
   1.100 +    0
   1.101 +    >>> legendre_mod_p(GF(5)(4))
   1.102 +    1
   1.103 +    """
   1.104 +    assert a.modulus % 2 == 1
   1.105 +    b = (a ** ((a.modulus - 1)/2))
   1.106 +    if b == 1:
   1.107 +        return 1
   1.108 +    elif b == a.modulus-1:
   1.109 +        return -1
   1.110 +    return 0