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