Re: [viff-devel] Equality protocol : error

2010-04-08 Thread Jonathan Van den Schrieck
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, 

Re: [viff-devel] Equality protocol : error

2010-04-08 Thread Sigurd Torkel Meldgaard
I know this is talking around the problem but:

For very small moduli like yours, another protocol for equality is
actually simpler, better (no risk of failing) and faster (I guess):

raise (a-b) to n-1 (with square and multiply), and if this difference
was 0 you will get 0, otherwise you will get 1 (good old fermat), this
result can be subtracted from 1, to turn the bit correctly.

I actually coded this once, but for some reason I never got to put it into Viff

I have attached a patch you can try to apply (use hg qimport
fermatequality, hg qpush), and play with for now.

I will try to look into the real bug later.

The best
Sigurd

On Thu, Apr 8, 2010 at 11:34 PM, Marcel Keller mkel...@cs.au.dk wrote:
 Hi Jonathan,

 I can't reproduce the error here. Can you send me your config files? The
 error might be triggered by certain random numbers, which depend on the PRSS
 keys. By the way, the error message is about the same every time something
 goes wrong in a callback. This is because VIFF does not define errbacks. To
 get a little bit more meaningful output, you can use the --deferred-debug
 parameter.

 Best regards,
 Marcel



fermatequality
Description: Binary data
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk