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