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 : > >> 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
Hi Tord et. al. Tord Ingolf Reistad wrote: Hello all, 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). I think there is, specifically I believe that the output of CompareBitwiseRandomKnownReturnValueX can be wrong. Or rather: As far as I can see the output will *always* be even. All the (prefix) xor's computed in the faun-in (ITYM fan-in :-) will be 1 until the first differing position, i, is hit and from then on even. Computing Share Returnval = new Share(0L); for (int i=0; ithen sums zeros (rnotc == 0) or even values (xor[i] will be even when they start to differ, and 2*1 is even). If I'm right, the just use xor[i-1] instead (or xor[i+1] -- I can't get these arrays right in my head once they are reversed a few times). Or did I miss the spot where you do this? 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. Deal! At least regarding the help :-) I think that comparisonRestricted is entirely correct, but I do not understand what goes on in CompareBitwiseRandomKnown. This might be due to bugs, but can also just be me not understanding your code. Three very specific questions: 1) You write temp = rand[highestbit-1].mpcmult(BigInteger.valueOf(-1)); // -r_h From the comments it seems you want Random[highestbit-1] rather than rand[highestbit-1] Is this right? If not, what is the intuition? 2) You write int highestbit = Field.getBaseField().bitLength(); BigInteger SetHighbit = BigInteger.ZERO; SetHighbit.flipBit(highestbit); Field highBitSet = new Field(SetHighbit); Do you mean SetHighbit.flipBit(highestbit - 1); ? It seems that you want to find the value you would have gotten if Random did not have it's top bit set in the case when it actually does. 3) Have you forgotten to xor the return value with Random[0]? /Tomas 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. Tord ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Fixed memory leak
Hi folks Martin Geisler wrote: viff-devel@viff.dk writes: Hi Tomas and others, http://hg.viff.dk/viff/rev/c8810dc507f3 changeset: 766:c8810dc507f3 user: Martin Geisler <[EMAIL PROTECTED]> date: Tue May 20 14:18:27 2008 +0200 summary: Fixed memory leak. It turned out that we kept references to empty deques in incoming_data without ever releasing them. This caused the memory usage to grow as more and more communication was done. Could you please try your gigantic computations again and see if this helps in your case? Nope, memory usage has grown. viff-0.4: ~630,000kB viff-f993269c2660: ~690,000kB And this is per party (three of them in all). But I do see a difference: In 0.4 the memory usage was constantly max'ed out. In f993269c2660, two parties can finish early and then free essentially all their memory. Later they then reallocate ~0.5GB. So something good is definitely happening, but it doesn't solve my problem :-( And just to describe my "gigantic" computation, it's actually not so big: I load 100,000 shares (of Z_7 :-) from disk, reconstruct the associated values, and print them. Saying 4 bytes/field-element (say using 32-bit integers as could be done easily in C), and 400,000 field-elements (100,000 shares from each of the three parties and 100,000 reconstructed secrets) this amounts to around an astonishing 400kB (per party). Or alternatively: Using ~(6/4)kB = ~12,000 bits per 32-bit field-element. One positive thing here is that I've gotten an idea of how to potentially remove /some/ of that overhead (honest-but-curious only). The observation is that we don't need to store all shares and reconstruct at the end. We can just keep track of the sum of the shares (times their lambda's) we've recieved. Whenever a new one arrives we add it to that accumulator. This might not make a big difference in a 3-party setting, but if many (e.g. 10) parties are involved, then this seems like a good idea to reduce memory requirements. 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] Choice of comparison protocol
Martin Geisler wrote: [EMAIL PROTECTED] writes: 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: 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. 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] 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 q< 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
Re: [viff-devel] [issue24] Do log right
Hi Martin Geisler wrote: > New submission from Martin Geisler <[EMAIL PROTECTED]>: > > In ComparisonToft07Mixin.convert_bit_share a local function is defined. > It starts with a comment that says "TODO: Don't do log like this...". > > Tomas, would you please figure out if there is any reason why the > standard math.log is not used instead? There is no reason not to use the standard math.log. I had a steep learning curve when I coded this, so rather than go hunting for log in python (and loosing my context), I did the quick and dirty (and /horribly/ ugly) thing. > It accepts a base argument, so I > think math.log(x, 2) does the same as your function. It should except for powers of two, where my function has a bug. No problem in the code though, as I only use it on odd primes. /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] Small BuildBot fix
Hi all Martin Geisler wrote: > Martin Geisler <[EMAIL PROTECTED]> writes: > >> I'll try and make a third builder now which runs Epydoc whenever the >> source changes and maybe even uploads the API docs to viff.dk. > > This now works -- the documentation is now automatically built and > uploaded to viff.dk on every change. Try it out: improve one of the > docstrings, commit it and let me know! > > We should probably indicate somewhere that the API docs reflects the > code in Mercurial and not the latest release. Or maybe it would be > better if we put both online? What do you guys think? I would go for both (or rather: /all/ releases + current) and clearly mark what is what. For project developers, the current is best as it lets everyone know what the state of everything is at the present. But most "standard" developers will pick a release version and stick to it rather than use the current, and leaving actual users without an online api sounds really bad. :-) 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] GMPY with Python 2.5
Hi Martin Geisler wrote: > Hi there, > > Tomas tells me that one can download binary Windows GMPY packages for > Python 2.5 on the projects new home: > > http://code.google.com/p/gmpy/ Got that from Thomas, so he's the one to credit for finding it. > I'll update the URL in the INSTALL file to point to there instead of > its old home on SourceForge. Is the google page the official home of gmpy? Also, the google page has gmpy 1.02, but I'm not sure if that's only a pre-release version -- prerelease and real-world crypto sound like a bad combination, though for toying around things should be fine. The sourceforge site has gmpy 1.01, though only compiled for python 2.3 and 2.4. It does appear that viff works with either -- at least on windows. (I've run python 2.4 with gmpy 1.01, and Thomas has run 2.5 with 1.02.) 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] Mini Twisted tutorial
Hi all > Using a thread to receive listed for input, and another thread to work > on reducing the tree, then this should work nicely. Perhaps a third > thread to send out messages produced by the tree reducer... > > Tomas, I guess this design is similar to the one you though of when we > discussed alternatives for the SIMAP runtime? Yes, that was very much my idea. Drop rounds and split communication out in one or two threads, so that communication and computation could be parallelized. I'm not sure if the above is the best idea, but implementing rounds explicitly means "wasting" potential communication time on processing (and vice versa), which is bad. Of course this means a new proof of security (how is that coming along?). /Tomas ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
