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:
Ivan Bjerre Damgård wrote:
> Quoting Marcel Keller <mkel...@cs.au.dk>:
>> 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
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
Hope that helps a bit, if not then just keep asking questions.
viff-devel mailing list (http://viff.dk/)