Dear Ivan, Yes I know about that. But 367 is 3 mod 4 so it should be OK. And the existing protocol works with 367 only if the two numbers are not equal. If they are, I got the error mentioned in my first message. If I can solve the error in the existing protocol, I will be able to continue my work.
Thank you for your answer, Jonathan Le 8 avr. 2010 à 16:26, Ivan Damgård a écrit : > Dear Jonathan, > > You cannot expect the protocol to work for primes that are 1 mod 4, > it is based on the fact that for primes p that are 3 mod 4, you can > deterministically > compute a square root mod p by raising to power (p+1)/4. > This does not work if p is 1 mod 4. > > regards, Ivan > > On 08/04/2010, at 14.11, Jonathan Van den Schrieck wrote: > >> Hello, >> >> I am trying to modify the equality protocol to make it work for primes >> congruent to 5 mod 8 (exists for Blum primes). >> The problem is that I have an error with the original protocol. It works >> perfectly with p = 211 for example. But for p = 367, it doesn't. >> Here is the code I'm using to test it : >> >> from optparse import OptionParser >> import viff.reactor >> viff.reactor.install() >> from twisted.internet import reactor >> from viff.field import GF >> from viff.runtime import create_runtime, gather_shares >> from viff.passive import PassiveRuntime >> from viff.equality_ohta import ProbabilisticEqualityMixin2 >> from viff.equality import ProbabilisticEqualityMixin >> from viff.comparison import Toft05Runtime >> from viff.config import load_config >> from viff.util import rand, find_prime >> >> class EqualityRuntime(PassiveRuntime, ProbabilisticEqualityMixin): >> """Default mix of :class:`~viff.equality.ProbabilisticEqualityMixin` >> and :class:`~viff.passive.PassiveRuntime`. >> """ >> pass >> >> class Protocol: >> >> def __init__(self, runtime): >> # Save the Runtime for later use >> self.runtime = runtime >> k = runtime.options.security_parameter >> print "security parameter = ", k >> Zp = GF(367) >> >> # We must secret share our input with the other parties. They >> # will do the same and we end up with three variables >> # input is equal to the player id >> >> rand = runtime.prss_share_random(Zp) >> #rand1 = runtime.prss_share_random(Zp) >> rand1 = rand >> print "rand = ", rand, "rand1 = ", rand1 >> >> #open rand and rand1 to print their value >> open_rand = runtime.open(rand) >> open_rand1 = runtime.open(rand1) >> temp = gather_shares([open_rand, open_rand1]) >> temp.addCallback(self.results_ready) >> >> # we test if rand == rand1 by using equality protocol >> test = (rand == rand1) >> test_open = runtime.open(test) >> results = gather_shares([test_open]) >> results.addCallback(self.results_ready) >> >> runtime.schedule_callback(results, lambda _: runtime.synchronize()) >> runtime.schedule_callback(results, lambda _: runtime.shutdown()) >> >> def results_ready(self, results): >> print "ALGO_QUAD temp results =", results >> >> >> def mtemp(self, temp): >> print "local part of shares after callback =" >> print temp >> >> >> # Parse command line arguments. >> parser = OptionParser() >> EqualityRuntime.add_options(parser) >> options, args = parser.parse_args() >> >> if len(args) == 0: >> parser.error("you must specify a config file") >> else: >> id, players = load_config(args[0]) >> >> # Create a deferred Runtime and ask it to run our protocol when ready. >> pre_runtime = create_runtime(id, players, 1, options, EqualityRuntime) >> pre_runtime.addCallback(Protocol) >> >> # Start the Twisted event loop. >> reactor.run() >> >> as you can see, I simply generate 2 random numbers, then I test if they have >> the same value, and I print the result of the test. >> This will work if rand != rand1, but if I set rand1 = rand => ERROR. >> This error will only happen if p = 367 (and maybe with others primes, but I >> couldn't test them all) >> Here is the error : >> >> Unhandled error in Deferred: >> Traceback (most recent call last): >> File >> "/System/Library/Frameworks/Python.framework/Versions/2.5/Extras/lib/python/twisted/internet/defer.py", >> line 328, in _runCallbacks >> self.result = callback(self.result, *args, **kw) >> File "/Users/jonathanvds/opt/lib/python/viff/runtime.py", line 239, in >> _callback_fired >> self.callback(self.results) >> File >> "/System/Library/Frameworks/Python.framework/Versions/2.5/Extras/lib/python/twisted/internet/defer.py", >> line 243, in callback >> self._startRunCallbacks(result) >> File >> "/System/Library/Frameworks/Python.framework/Versions/2.5/Extras/lib/python/twisted/internet/defer.py", >> line 312, in _startRunCallbacks >> self._runCallbacks() >> --- <exception caught here> --- >> File >> "/System/Library/Frameworks/Python.framework/Versions/2.5/Extras/lib/python/twisted/internet/defer.py", >> line 328, in _runCallbacks >> self.result = callback(self.result, *args, **kw) >> File "/Users/jonathanvds/opt/lib/python/viff/passive.py", line 211, in >> <lambda> >> result.addCallback(lambda (a, b): a * b) >> exceptions.TypeError: unsupported operand type(s) for *: 'instance' and >> 'GFElement' >> >> I can't find where the problem comes from since I only have the error with p >> = 367 (and I have the same error with my new protocol for p = 5 mod 8, but >> I'm guessing that if I can solve the problem in the existing protocol, I'll >> be able to do the same with my implementation). >> >> Thank you for your help, >> >> Jonathan Van den Schrieck >> >> >> _______________________________________________ >> viff-devel mailing list (http://viff.dk/) >> viff-devel@viff.dk >> http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk >
_______________________________________________ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk