Yes, as you said the best published algorithm is from ICITS07, but that
has still to be implemented in some program.
A correction to my previous statements: The 5*l multiplication-solution
is for restricted inputs [a < b], where [a], [b] < p/2, so for arbitrary
elements in the field you have to triple that to 15*l multiplications.
The restriction of p = 2^l - 1 and psaudorandom secret sharing, reduces
the work of finding random bitwise shared values in the field to 1 l
multiplications, if this restriction is lifted we are looking at 4 l for
each (of the two) random bitwise shared values. So that means 11 l for
the restricted case and 33 l for the general case.
The number of rounds will also increase to 6 if you do not use
psaudorandom values. The number of rounds can grow to 8 for the
comparison with no restrictions, if you do not allow for preprocessing
of the final multiplications.
If I remember correctly the code deviates from the constant round
solution in that for primes where the two highest order bits are '10' it
tests separately for the first two bits. This increases the possible
number of rounds, but it decreases the failure rate.
Tord
Tomas Toft wrote:
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/)
[email protected]
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
