[viff-devel] ComparisonToft07Mixin

[Tomas Toft]

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 <mkeller at 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