Re: [viff-devel] ComparisonToft07Mixin
ARGH! I replied to this earlier, but only to Ivan. Martin: You should be surprised that this goes wrong for me again, and by the principle of least surprise, you should therefore set reply to be to the list :-) OK, here is what I wrote: Hi all Ivan Bjerre Damgård wrote: Quoting Marcel Keller mkel...@cs.au.dk: Hi Does anyone know of a documentation explaining the code in the ComparisonToft07Mixin class in comparison.py? I've read the relevant part of Tomas' dissertation but it seems that the algorithm there is different. Source code *is* documentation! There are even comments in there... :-) But seriously, I have some slides, but I'm pretty sure they won't make sense without me standing in front of them speaking. Indeed that's not the same algorithm as in Tomas' thesis. I think it is an algorithm from a paper he wrote with Tord Reistad, unfortunately I could not find the paper on-line anywhere, even though it was published in a conference called ICITS 2007 in Spain. Of course, Tomas may be slightly better at answering this :-) Correct, the algorithm is not in my dissertation. In a sense, the implementation is a non-constant-rounds variation of the ICITS07 paper (i.e. get rid of all the bothersome tricks needed to go to constant-rounds, but those tricks were the key point of that paper). The reason you can't find it online is that the proceedings haven't appeared yet, though last I heard they were on their way. Here is a short description of the implementation: 1) Translate to comparison of shared to comparison of one bitwise shared and one public value. The computation is basically (2^\ell + a - b) - ((2^\ell + a - b) mod 2^\ell) and the new comparison enters as part of the mod 2^\ell-reduction. 2) Perform the new comparison. The basic idea is the same as in the ICITS paper which builds on DGK from ACISP2007. For each bitposition i, compute a value [e_i], which states if this is the most differing bit position and if so, if the first number greater than the second. This is encoded as 0 or non-zero; the goal is now to determine whether there is a 0. DGK and the ICITS paper multiplicatively mask and permute, but here the values are just multiplied together in log-rounds and then masked. The final thing is to map the outcome to a 0/1 encoding. This is done w/o an equivality test by masking the meaning of the 0 -- essentially, we know we are comparing two values but we don't know if the comparison is GT or LT (s_sign in the code). This is secure as s_sign can be viewed as a one time pad for the outcome. One trick in the code is that the second comparison doesn't have to occur modulo the original prime, a smaller one can be specified for efficiency reasons. Hope that helps a bit, if not then just keep asking questions. Regards, Tomas ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Choice of comparison protocol
Martin Geisler wrote: [EMAIL PROTECTED] writes: snip comparison return value disagreement snip '05 variation This does the same and avoids the conversion to GF(256), but may be more expensive online (IIRC GF(256) computation is /really/ fast). Well, that is easy to check. The timeit module says: snip timing data Like you, I had expected GF256 to be significantly faster. I don't like the fixed input data in the timings. The Zp elements chosen may be good or bad candidates, and computation on random elements may be worse... Regarding GF(256) this should not be a problem, as IIRC the multiplication is a table lookup. However, you may avoid cache-misses entirely, so those numbers should also be taken with a small grain of salt. snip old constant rounds solution The best one published that I know of is Tord's and mine from ICITS07. This is reasonable to implement (complexity-wise), but trust me, you don't want to :-) Hmm... Rune says that I should consider this a challange... :-) I wont really have time before I return from Switzerland in September (I leave in a week), but can I find the article online? I found the conference webpage, but it does not link to your article, and neither does your own publication list. My publication list is my fault. But the paper will be available in the conference proceedings; to appear in LNCS I believe. I can dig out a copy and mail it to you if you like. Regards, Tomas ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Choice of comparison protocol
Hi all Tord Ingolf Reistad wrote: As you are discussing implementing the algorithm from ICITS07, I have improved on that to get a very effective algorithm. For p = 2^l - 1 and using psaudorandom secret sharing. The comparison can be done in 5 rounds and 5l multiplications. The algorithm has never been published, but attached is a java implementation of the algorithm. (There might be an error in the faun in algorithm as that is not tested). As I said, the best, *published* algorithm I know is from ICITS07. :-) Btw, does the 5*l multiplications-solution allow arbitrary input from the field or only (l-1)-bit? If it's full-field then I *really* need to see it. Unfortunately I do not have a phyton implementation of it, as I am bad at programming in phyton, on the other hand I am working on a java implementation of MPC, which should be ready in a month. If anyone else want to try to implement it in phyton I will be more than happy to help. To understand the code please start with the function public Share comparisonRestricted(Share a, Share b) and please observe that many small functions on the top are just returning values instead of shares, this is for test purposes. I'll take a look at it and perhaps try a python port if time permits. Regards, Tomas ___ 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.
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
