Mercurial > mkeller
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 wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/viff/equality.py Tue Sep 16 16:09:25 2008 +0200 @@ -0,0 +1,107 @@ +# Copyright 2008 VIFF Development Team. +# +# This file is part of VIFF, the Virtual Ideal Functionality Framework. +# +# VIFF is free software: you can redistribute it and/or modify it +# under the terms of the GNU Lesser General Public License (LGPL) as +# published by the Free Software Foundation, either version 3 of the +# License, or (at your option) any later version. +# +# VIFF is distributed in the hope that it will be useful, but WITHOUT +# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY +# or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General +# Public License for more details. +# +# You should have received a copy of the GNU Lesser General Public +# License along with VIFF. If not, see <http://www.gnu.org/licenses/>. + +"""Equality protocol. The mixin class defined here provide an +:meth:`equal` method to the :class:`Runtime <viff.runtime.Runtime>` it +is mixed with. +""" + +from viff.runtime import increment_pc + +class ProbabilisticEqualityMixin: + """This class implements probabilistic constant-round secure + equality-testing of secret shared numbers.""" + + @increment_pc + def equal(self, share_x, share_y): + """Equality testing with secret shared result. + + Assumes p = 3 mod 4, returns a secret sharing of 1 if share_x + == share_y and 0 otherwise. + + This is the probabilistic method based on quadratic + reciprocity described in: "Constant-Round Multiparty + Computation for Interval Test, Equality Test, and Comparison" + by Takashi Nishide and Kazuo Ohta, and fails with probability + 1/(2**k) where k is set to the security parameter of the + runtime. + + TODO: Make it work for any prime-modulo, the b's should be in + {y,1} where y is a non-square modulo p. + + TODO: Make the final "and"ing of the x's more efficient as + described in the paper. + """ + + Zp = share_x.field + + a = share_x - share_y # We will check if a == 0 + k = self.options.security_parameter + + # The b's are random numbers in {-1, 1} + b = [self.prss_share_random(Zp, binary=True) * 2 - 1 + for _ in range(k)] + r = [self.prss_share_random(Zp) for _ in range(k)] + rp = [self.prss_share_random(Zp) for _ in range(k)] + + # If b_i == 1 c_i will always be a square modulo p if a is + # zero and with probability 1/2 otherwise (except if rp == 0). + # If b_i == -1 it will be non-square. + c = [self.open(a * r[j] + b[j] * rp[j] * rp[j]) for j in range(k)] + + def finish(cj, bj): + l = legendre_mod_p(cj) + # This will only happen with negligible probability. + assert l != 0 + if l == 1: + xj = (1/Zp(2)) * (bj + 1) + else: # l == -1 + assert(l == -1) + xj = (-1) * (1/Zp(2)) * (bj - 1) + return xj + + x = [cj.addCallback(finish, bj) for cj, bj in zip(c, b)] + + # Take the product (this is here the same as the "and") of all + # the x'es + while len(x) > 1: + x.append(x.pop() * x.pop()) + + return x[0] + +def legendre_mod_p(a): + """Return the legendre symbol ``legendre(a, p)`` where *p* is the + order of the field of *a*. + + The legendre symbol is -1 if *a* is not a square mod *p*, 0 if + ``gcd(a, p)`` is not 1, and 1 if *a* is a square mod *p*: + + >>> from viff.field import GF + >>> legendre_mod_p(GF(5)(2)) + -1 + >>> legendre_mod_p(GF(5)(5)) + 0 + >>> legendre_mod_p(GF(5)(4)) + 1 + """ + assert a.modulus % 2 == 1 + b = (a ** ((a.modulus - 1)/2)) + if b == 1: + return 1 + elif b == a.modulus-1: + return -1 + return 0