viff

changeset 1436:a3cc11ca0ca0

equality: Start over with new randomness if c is zero.
author Marcel Keller <mkeller@cs.au.dk>
date Mon, 19 Apr 2010 11:46:46 +0200
parents 6d838b2d24a2
children 1772506977cc
files viff/equality.py
diffstat 1 files changed, 15 insertions(+), 14 deletions(-) [+]
line diff
     1.1 --- a/viff/equality.py	Tue Mar 30 11:34:39 2010 +0200
     1.2 +++ b/viff/equality.py	Mon Apr 19 11:46:46 2010 +0200
     1.3 @@ -49,29 +49,30 @@
     1.4          a = share_x - share_y # We will check if a == 0
     1.5          k = self.options.security_parameter
     1.6  
     1.7 -        # The b's are random numbers in {-1, 1}
     1.8 -        b = [self.prss_share_random(Zp, binary=True) * 2 - 1
     1.9 -             for _ in range(k)]
    1.10 -        r = [self.prss_share_random(Zp) for _ in range(k)]
    1.11 -        rp = [self.prss_share_random(Zp) for _ in range(k)]
    1.12 +        def gen_test_bit():
    1.13 +            # The b's are random numbers in {-1, 1}
    1.14 +            b = self.prss_share_random(Zp, binary=True) * 2 - 1
    1.15 +            r = self.prss_share_random(Zp)
    1.16 +            rp = self.prss_share_random(Zp)
    1.17  
    1.18 -        # If b_i == 1 c_i will always be a square modulo p if a is
    1.19 -        # zero and with probability 1/2 otherwise (except if rp == 0).
    1.20 -        # If b_i == -1 it will be non-square.
    1.21 -        c = [self.open(a * r[j] + b[j] * rp[j] * rp[j]) for j in range(k)]
    1.22 +            # If b_i == 1 c_i will always be a square modulo p if a is
    1.23 +            # zero and with probability 1/2 otherwise (except if rp == 0).
    1.24 +            # If b_i == -1 it will be non-square.
    1.25 +            c = self.open(a * r + b * rp * rp)
    1.26 +            return self.schedule_callback(c, finish, b)
    1.27  
    1.28          def finish(cj, bj):
    1.29              l = legendre_mod_p(cj)
    1.30 -            # This will only happen with negligible probability.
    1.31 -            assert l != 0
    1.32              if l == 1:
    1.33                  xj = (1/Zp(2)) * (bj + 1)
    1.34 -            else: # l == -1
    1.35 -                assert(l == -1)
    1.36 +            elif l == -1:
    1.37                  xj = (-1) * (1/Zp(2)) * (bj - 1)
    1.38 +            else:
    1.39 +                # Start over.
    1.40 +                xj = gen_test_bit()
    1.41              return xj
    1.42  
    1.43 -        x = [self.schedule_callback(cj, finish, bj) for cj, bj in zip(c, b)]
    1.44 +        x = [gen_test_bit() for _ in range(k)]
    1.45  
    1.46          # Take the product (this is here the same as the "and") of all
    1.47          # the x'es