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

[Martin Geisler]

Ivan Bjerre Damgaard [EMAIL PROTECTED] writes:

 Quoting Martin Geisler [EMAIL PROTECTED]:
..
 but this makes

   viff.test.test_runtime_comp.ActiveToft05GreaterThanEqualTest

 go into what looks like a never-ending loop?! You you have a better
 solution, then I'm all ears! :-)

 What is wrong with just doing a single normal secure multiplication,
 and then open the result?

That was what I tried to do... I don't know why it didn't work. I have
now created Issue 42 to track this:

  http://tracker.viff.dk/issue42

Who wants to have the honor of fixing bug 42?! :-)

-- 
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.

[Ivan Bjerre Damgaard]

Quoting Martin Geisler [EMAIL PROTECTED]:
..
 but this makes

   viff.test.test_runtime_comp.ActiveToft05GreaterThanEqualTest

 go into what looks like a never-ending loop?! You you have a better
 solution, then I'm all ears! :-)

What is wrong with just doing a single normal secure multiplication, and then
open the result?

If we want to optimize, we have to have a way to PRSS-create a random degree 2t
polynomial that is 0 in 0. This is close to what we discussed at the meeting
today. Given that, we first make a random shared a, and a random degree 2t
polynomial g, with g(0)=0. Then locally square your share in a, add to your
share in g and broadcast. This will securely compute a^2, with passive security
if t n/2.

If you want active security, it's more complicated, and it may be easier as a
first step to just call a normal multiplication to get a^2. Then you get
whatever security that multiplication offers.

regards, Ivan

regards, Ivan
___
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