[viff-devel] Active comparisons in less than a second! (was: viff: Switch to prss_share_bit_double in comparisons.)

[Martin Geisler]

Martin Geisler [EMAIL PROTECTED] writes:

 Running three players on my home computer gives these results:

   Before: 1309 ms per comparison with 100 parallel comparisons
   After:   324 ms per comparison with 100 parallel comparisons

 That is a factor of four! I measured similar improvements earlier
 today when using three different machines at DAIMI.

I have now benchmarked the comparison protocols using the
ActiveRuntime class. The actively secure runtime has a preprocessing
phase in which triples (a, b, c) where ab = c are generated. These are
the results per comparison for 100 parallel comparisons done between
three machines at DAIMI using a 65-bit prime modulus:

  ++-+--+
  || Passive | Active   |
  ++-+--+
  | Toft05 | 389 ms  | 590-632 ms (2-3 sek) |
  ++-+--+
  | Toft07 | 368 ms  | 690-774 ms (3-5 sek) |
  ++-+--+

The numbers matched on all three players in the passive case, but in
the active case one player was always slower at the proprocessing (in
parenthesis), but faster at the online processing. The other two
players behaved the other way around.

With these results we can now securely compare a 32-bit number in a
65-bit prime field in less than one second online, even in the
presence of an active adversary!

-- 
Martin Geisler
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] viff: Switch to prss_share_bit_double in comparisons.

[Tomas Toft]

Hi

Martin Geisler wrote:

viff-devel@viff.dk writes:

Hi everybody,

I don't know how many of you follow the commits to the VIFF repository?
Would anybody be interested in a mailing list for it?

Anyway -- the latest commit is this:


http://hg.viff.dk/viff/rev/5dd8c277268c
changeset: 751:5dd8c277268c
user:  Martin Geisler [EMAIL PROTECTED]
date:  Tue May 13 16:28:41 2008 +0200
summary:   Switch to prss_share_bit_double in comparisons.


This change makes the ComparisonToft05Mixin.greater_than_equal method
actively secure and much faster!

Running three players on my home computer gives these results:

  Before: 1309 ms per comparison with 100 parallel comparisons
  After:   324 ms per comparison with 100 parallel comparisons

That is a factor of four! I measured similar improvements earlier today
when using three different machines at DAIMI.


Nice speedup. It's also possible to do a similar thing for 
ComparisonToft07Mixin. In the two-fields variation we need the same bit 
in Zp and Zq, where qp, say p is 500-bit and q=3001.


Similarly to generating the same random bit in Zp and GF(256), we can

1) generate a random bit [b]_p in Zp
2) generate a pseudorandom number [r]_p (of limited size) in Zp and the 
same number mod q in Zq [r mod q]_q (similar to the present case, where 
q implicitly is two)

3) c  - open([b]_p + [r]_p)
4) [b]_q = ((c mod q) - [r mod q]_q)


Anyway. looking at this lead Mikkel and me to look at
prss_share_random in runtime.py, and there seems to be either a bug 
(information leak) /or/ a possibility of optimisation when sharing a bit 
in Zp.



The problem is the following:

result = self.open(Share(self, field, share*share), 
threshold=2*self.threshold)


Is the * in share*share a multiplication protocol or a 
multiplication of actual values? If it is actual values, then we 
*cannot* simply call it shares and open it, as the polynomial is not 
uniformly random (this can also be done with PRSS and no communication).


If on the other hand it is an invoation of the multiplication protocol, 
then it is secure but can be optimised with the PRSS version mentioned 
above.



Regards,
  Tomas













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