Tomas Toft wrote:
Hi Tord et. al.
Tord Ingolf Reistad wrote:
Hello all,
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).
I think there is, specifically I believe that the output of
CompareBitwiseRandomKnownReturnValueX can be wrong.
Or rather: As far as I can see the output will *always* be even.
All the (prefix) xor's computed in the faun-in (ITYM fan-in :-) will be
1 until the first differing position, i, is hit and from then on even.
Computing
Share Returnval = new Share(0L);
for (int i=0; i<halvedLen+oddNum; i++) {
Share temp = xor[i].mpcmult(rnotc[i]);
Returnval = Returnval.mpcadd(temp);
}
Yes, it might be wrong, I have not have time to look at it in detail.
I got as far as checking that the random values created where ok, and
then the rest was done somewhat fast and never tested.
I will look closer at the code again when I have finished programming
another thing I am working on. (No, not my thesis, but a full
implementation of MPC in java, so I can get some real results for my
thesis).
then sums zeros (rnotc == 0) or even values (xor[i] will be even when
they start to differ, and 2*1 is even). If I'm right, the just use
xor[i-1] instead (or xor[i+1] -- I can't get these arrays right in my
head once they are reversed a few times).
Or did I miss the spot where you do this?
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.
Deal! At least regarding the help :-) I think that comparisonRestricted
is entirely correct, but I do not understand what goes on in
CompareBitwiseRandomKnown. This might be due to bugs, but can also just
be me not understanding your code.
Three very specific questions:
1) You write
temp = rand[highestbit-1].mpcmult(BigInteger.valueOf(-1)); // -r_h
From the comments it seems you want
Random[highestbit-1]
rather than
rand[highestbit-1]
Is this right? If not, what is the intuition?
The intuition is to avoid overflow. We have created a value x <
2^((l/2)+1), and we want to find the last bit. Now when adding with a
random value we might get an overflow in the field, but as we have the
highest bit of r as a separate value, we can test for that. So we create
two values c0Low or c0High which is the lowest bit of c given either
that c=x+r(-2^(l-1)). Now in one of these cases there will be no
overflow and in that case x0 = c0 xor r0.
2)
You write
int highestbit = Field.getBaseField().bitLength();
BigInteger SetHighbit = BigInteger.ZERO;
SetHighbit.flipBit(highestbit);
Field highBitSet = new Field(SetHighbit);
Do you mean
SetHighbit.flipBit(highestbit - 1);
^^^^
?
It seems that you want to find the value you would have gotten if Random
did not have it's top bit set in the case when it actually does.
See above comment for intuition, I cannot check the code today.
3)
Have you forgotten to xor the return value with Random[0]?
Probably.
/Tomas
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.
Tord
_______________________________________________
viff-devel mailing list (http://viff.dk/)
[email protected]
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
