Tomas Toft <[EMAIL PROTECTED]> writes: > Martin Geisler wrote: > >> Before: 1309 ms per comparison with 100 parallel comparisons >> After: 324 ms per comparison with 100 parallel comparisons > > 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 q<<p, 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)
Will you send a patch with this? There are also scary number of TODOs still left in the the code you wrote in ComparisonToft07Mixin class... > 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? The types are always such that the Share class wraps FieldElements, which in turn wraps normal integers. So this is a multiplication of two FieldElements with no multiplication protocol running behind the scenes :-( > 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). You're right... I made that change five weeks ago: http://hg.viff.dk/viff/rev/d1d4c633fca8 I'm glad that you guys took a look at the code! > 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. If you see how to make it both secure and efficient, then please send a patch (or let me know where I can pull one)! I once put up a guide for VIFF developement, that might come in handy: http://viff.dk/doc/development.html I just tried fixing it, but it seems that I have stepped into some strange bugs (which I do not understand) by doing so. I tried with element = prss(self.num_players, self.id, field, prfs, prss_key) share = Share(self, field, element) if field is GF256 or not binary: return share # Open the square and compute a square-root result = self.open(share * share) def finish(square, element, binary): if square == 0: # We were unlucky, try again... return self.prss_share_random(field, binary) else: # We can finish the calculation root = square.sqrt() # When the root is computed, we divide the share and # convert the resulting -1/1 share into a 0/1 share. return Share(self, field, (element/root + 1) / 2) self.schedule_callback(result, finish, element, binary) return result 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! :-) -- Martin Geisler _______________________________________________ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
