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).
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.
Tord
Martin Geisler wrote:
[EMAIL PROTECTED] writes:
I talked with Rune Thorbek yesterday, and he asked why we have not
implemented your comparison protocol from your PhD thesis:
http://www.daimi.au.dk/~tomas/publications/dissertation.pdf
Is there any good reason why we haven't done that? Is the constants
much worse than the ones implemented?
Short answer: Yes.
Longer Answer: You need to do lots of tricks to go to
constant-rounds. The logarithmic solutions do not give (much) worse
round complexity, but require notably fewer multiplications.
Okay.
The best one published that I know of is Tord's and mine from
ICITS07. This is reasonable to implement (complexity-wise), but
trust me, you don't want to :-)
Hmm... Rune says that I should consider this a challange... :-)
I wont really have time before I return from Switzerland in September
(I leave in a week), but can I find the article online? I found the
conference webpage, but it does not link to your article, and neither
does your own publication list.
/*
* Testclass.java
*
* Created on 11. juni 2007, 01:30
*
* To change this template, choose Tools | Template Manager
* and open the template in the editor.
*/
package multiparty;
/**
*
* @author item
*/
import java.math.BigInteger;
import java.util.Stack;
import multiparty.Field;
//import org.lsmp.djep.groupJep.groups.Zn;
public class Testclass {
// private class Share extends multiparty.Field {
// public Share(long l) {super(l);}
// public Share(BigInteger v) {super(v);}
// }
/** Creates a new instance of Testclass */
public Testclass() {
}
static BigInteger BIG2 = BigInteger.valueOf(2);
static java.util.Random random = new java.util.Random();
public Share generateRandom() {
return new Share(Field.random());
}
public Share generateBit() {
// Not propper way to do it.
if (random == null)
random = new java.util.Random();
boolean r = random.nextBoolean();
if (true == r)
return new Share(BigInteger.ONE);
else
return new Share(BigInteger.ZERO);
}
public Field[] splitP() {
// Splits the fieldsize p into bits
// to reconstruct the value compute bits[i]*2^i
return splitNum(Field.getBaseField());
}
public Field[] splitNum(BigInteger a) {
Field [] bits = new Field[Field.getBaseField().bitLength()];
for (int i=0; i<bits.length; i++) {
if (a.testBit(i))
bits[i] = new Field(BigInteger.ONE);
else
bits[i] = new Field(BigInteger.ZERO);
}
return bits;
// To print with biggest to the left use
// for (int i=a.length-1; i>-1; i--)
}
public int initialBitsSetInP() {
BigInteger a = Field.getBaseField();
int numBits = 0;
for (int i=a.bitLength()-1; i>-1; i--) {
if (a.testBit(i)) {
numBits = numBits + 1;
} else
break;
}
return numBits;
}
public BigInteger convertFromBitsToValueB(Share[] a) {
BigInteger temp = BigInteger.ZERO;
BigInteger exp;
for (int i=0; i<a.length; i++) {
exp = BIG2.pow(i);
BigInteger temp2 = a[i].getvalue();
temp = temp.add(temp2.multiply(exp));
}
return temp;
}
public Share convertFromBitsToValueS(Share[] a) {
return new Share(convertFromBitsToValueB(a));
}
public Share[] Faunin(Share[] a, boolean reverse) {
if (true == reverse) {
Share [] b = new Share[a.length];
for (int i=0; i<a.length; i++)
b[a.length-1-i] = a[i];
Share [] c = Faunin(b);
for (int i=0; i<a.length; i++)
b[a.length-1-i] = c[i];
return b;
}
else
return Faunin(a);
}
public Share[] Faunin(Share[] a) {
// Computes a faun-in multiplication of the shares given in the array a
// Setting u_(-1) = 1 to save multiplications
// Revaling [u_(i-1)][a][r_i]/[u_i][r_i] = [u_(i-1)][a][u_i^(-1)]
// Final multiplication is with [u_i]
//Set reverse if the a
Share [] u = new Share[a.length];
Share [] r = new Share[a.length];
Share [] temp1 = new Share[a.length];
Field [] temp2 = new Share[a.length];
Field [] revealed = new Field[a.length];
for (int i=0; i<a.length; i++) {
u[i] = generateRandom();
r[i] = generateRandom();
}
temp1[0] = r[0];
for (int i=0; i<a.length; i++) {
if (i != 0)
temp1[i] = r[i].mpcmult(u[i-1]); // u_(i-1) r
temp2[i] = r[i].mpcmult(u[i]).reveal().inverse(); // (u_i r)^(-1)
}
for (int i=0; i<a.length; i++) {
revealed[i] = temp1[i].mpcmult(a[i]).reveal(); // u_(i-1) r a
revealed[i] = revealed[i].multf(temp2[i]); // u_(i-1) a u_i^(-1)
}
for (int i=1; i<a.length; i++) {
revealed[i] = revealed[i].multf(revealed[i-1]);
}
//The following step can be modified if not all the values are needed
for (int i=0; i<a.length; i++) {
r[i] = u[i].mpcmult(revealed[i].getvalue());
}
return r;
}
public Share[] generateRandomBitwiseSharedValue() {
Field[] Psplit = splitP();
Share[] Rand = new Share[Psplit.length];
boolean Finished = false;
while (!Finished) {
Finished = true;
for (int i=0; i<Psplit.length; i++) {
Rand[i] = generateBit();
}
// If the two highest order bits of P are 1 and 0, then the failure
// rate can be as high as 50%, this is reduced by 25% by checking
// that the two highest order bits multipled together do not produce
// a 1.
if (1 == initialBitsSetInP()) {
Share tempIni =
Rand[Rand.length-1].mpcmult(Rand[Rand.length-2]);
Field tempIni2 = tempIni.reveal();
//System.out.println("Rand[max-1]="+Rand[Rand.length-1]+ "
Rand[max-2]="+Rand[Rand.length-2]+" tempIni2="+tempIni2);
while (tempIni2.compareToONE()) {
Rand[Rand.length-1] = generateBit();
Rand[Rand.length-2] = generateBit();
tempIni = Rand[Rand.length-1].mpcmult(Rand[Rand.length-2]);
tempIni2 = tempIni.reveal();
//System.out.println("Rand[max-1]="+Rand[Rand.length-1]+ "
Rand[max-2]="+Rand[Rand.length-2]+ " tempIni2="+tempIni2);
}
}
//BigInteger tt = BigInteger.ZERO;
BigInteger tt = convertFromBitsToValueB(Rand);
//System.out.print("Random in bi ");
//for (int i=Psplit.length-1; i>-1; i--) {
// System.out.print(Rand[i]);
//}
//System.out.println("");
//for (int i=Psplit.length-1; i>-1; i--) {
// BigInteger tt2 = BIG2.pow(i);
// tt2 = tt2.multiply(Rand[i].getvalue());
// tt = tt.add(tt2);
//System.out.println("TT2 is " +tt2+" TT is "+tt);
//}
//System.out.println("TT is " + tt);
// Testing if Rand > P, there is no need to test for any bit where
// p_i = 1. p_i xor r_i is either r_i if p_i=0 or 1-r_i if p_i=1.
// There is a separate test for the last bit.
// Testing if (1-r_i+p_i) + \sum (r_j xor p_j)
// For last bit testing (p_0-r_0) + \sum (r_j xor p_j)
for (int i=Psplit.length-1; i>-1; i--) {
// Only check if p_i=0 or if last bit
if (Psplit[i].compareToZERO() || (0 == i)) {
Share temp = new Share(BigInteger.ONE);
temp = temp.mpcsub(Rand[i]);
//System.out.println("Start " + i + " with " + temp);
for (int j=Psplit.length-1; j>i; j--) {
// If p_i=0 add r_i to temp, if p_i=1 add 1-r_i to temp
if (Psplit[j].compareToZERO()) {
temp = temp.mpcadd(Rand[j]);
//System.out.println(j+" Add 0+"+Rand[j]+" gir
"+temp);
} else {
temp = temp.mpcadd(BigInteger.ONE);
temp = temp.mpcsub(Rand[j]);
//System.out.println(j+" Add 1-"+Rand[j]+" gir
"+temp);
}
}
//System.out.println("Test " + i + " gir " + temp);
//Multiply by a random value and reveal
Share random_mult = generateRandom();
while (random_mult.compareToZERO()) {
//Cheat to remove finding zeros for small values
//System.out.println("Zero as random number");
random_mult = generateRandom();
}
temp = temp.mpcmult(random_mult);
Field temp2 = temp.reveal();
if (temp2.compareToZERO()) {
Finished = false;
//if (! random_mult.compareToZERO())
//if (-1 == tt.compareTo(temp2.getBaseField())) {
// System.out.println("Error1 when tt is "+tt);
//}
//System.out.println("Restart at bit "+i);
Finished = true;
break; //Breaks the for loop
}
} // compareToZERO
} //for
} //while (!Finished)
BigInteger tt = convertFromBitsToValueB(Rand);
//if (-1 != tt.compareTo(Rand[0].getBaseField()))
// System.out.println("Error2 when tt is "+tt);
//else
//System.out.println("Ok when tt is "+tt);
return Rand;
}
public Share comparisonRestricted(Share a, Share b) {
//Comparing a > b, where a,b are shares and a,b < p/2
//Starting restating the comparison to p/2 > b-a > 0
//If this is true then 2(b-a)_0 is 0, otherwise 2(b-a)_0 is 1
//The least significant bit of 2(b-a), 2(b-a)_0 is equal to
//2(b-a)_0 = c_0 xor r_0 xor (r > c)
//Where c is revealed, r is bitwise secret shared value and
// c = 2(b-a) + r
Share temp = new Share(2L);
temp = temp.mpcmult(b.mpcsub(a));
Share[] Random = generateRandomBitwiseSharedValue();
Share tempRandom = convertFromBitsToValueS(Random);
temp = temp.mpcadd(tempRandom);
Field c = temp.reveal();
Field[] c_ar = splitNum(c.getvalue());
Share comp = CompareBitwiseRandomKnown(Random,c_ar);
int c0 = c.mod(BIG2).intValue();
Share r0comp = Random[0].mpcmult(comp);
// Return c0 xor Random[0] xor comp
if (0 == c0)
return comp.mpcxor(Random[0]);
else {
Share temp3 = new Share(BigInteger.ONE);
return temp3.mpcxor(comp.mpcxor(Random[0]));
} }
public Share CompareBitwiseRandomKnown(Share[] rand, Field[] c_ar) {
//First generate the value x from the shared values such that
// x = \sum r_i(1-c_i) \prod r_i xor c_i on two bits at a time
// x < 2^(l/2+1)
// Find the last bit of x by setting x' = x + r
// Then reveal x' and either use the last bit of x' or x' - 2^(l-1)
// As one of these values corresponds to a value of r with the first
bit not set.
Share x = CompareBitwiseRandomKnownReturnValueX (rand, c_ar);
Share[] Random = generateRandomBitwiseSharedValue();
Share temp = convertFromBitsToValueS(Random);
temp = x.mpcadd(temp);
Field c = temp.reveal();
Field [] cartemp = splitNum(c.getvalue());
Field c0Low = cartemp[0];
int highestbit = Field.getBaseField().bitLength();
BigInteger SetHighbit = BigInteger.ZERO;
SetHighbit.flipBit(highestbit);
Field highBitSet = new Field(SetHighbit);
c = c.subtractf(highBitSet);
cartemp = splitNum(c.getvalue());
Field c0High = cartemp[0];
temp = rand[highestbit-1].mpcmult(BigInteger.valueOf(-1)); // -r_h
temp = temp.mpcadd(BigInteger.ONE); // 1 - r_h
temp = temp.mpcmult(c0Low); // (1-r_h)c0Low
Share RetVal = rand[highestbit-1].mpcmult(c0High); // r_h c0High
RetVal = RetVal.mpcadd(temp); // r_h c0High + (1-r_h) c0Low
return RetVal;
}
public Share CompareBitwiseRandomKnownReturnValueX (Share[] rand, Field[]
c_ar) {
//Generating a new share where r > c is given by the last bit
//As the number x is even if c <= r otherwise x is odd.
//If rand and c_ar are l bit long then x < 2^(l/2 + log(l))
// x = \sum r_i(1-c_i) \prod r_i xor c_i on two bits at a time
if (rand.length != Field.getBaseField().bitLength())
System.out.println("Wrong size of the random");
if (c_ar.length != Field.getBaseField().bitLength())
System.out.println("Wrong size of c");
//Comparing 2 and 2 bits, special test for bit if it is alone
int halvedLen = rand.length/2; //rounded down
int oddNum = rand.length%2;
Share[] xor = new Share[halvedLen+oddNum];
Share[] rnotc = new Share[halvedLen+oddNum];
Field two = new Field(2L);
Field one = new Field(1L);
if (1 == oddNum) {
Field tempF = c_ar[0].multf(two); // 2c_0
Share tempS = rand[0].mpcmult(tempF); // 2r_0 c_0
xor[0] = rand[0].mpcadd(c_ar[0]).mpcadd(tempS); // r_0 + c_0 - 2
r_0 c_0
tempF = c_ar[0].inverse(); // -c_0
tempF = tempF.addf(one); // 1 - c_0
rnotc[0] = rand[0].mpcmult(tempF); // (1 - c_0)r_0
}
for (int i=0; i<halvedLen; i++) {
long c_double = c_ar[2*i+oddNum].getvalue().longValue() +
2* c_ar[2*i+oddNum+1].getvalue().longValue();
Share high = rand[2*i+oddNum+1];
Share low = rand[2*i+oddNum];
Share randN = high.mpcmult(low); //r_i r_(i+1)
Share notrandN = randN.mpcmult(BigInteger.valueOf(-1)); //-r_i
r_(i+1)
switch ((int)c_double) {
//This switch statment will look at two bits at a time:
//Returns a share xor which is 0 if r = c for the two bits
//otherwise returns xor with the value 1
//Returns a share rnotc which is 1 if r>c for the two bits
//otherwise returns rnotc with the value 0
case 0:
xor[i+oddNum] = notrandN.mpcadd(low).mpcadd(high); // low +
high - randN
rnotc[i+oddNum] = xor[i+oddNum];
break;
case 1:
xor[i+oddNum] = randN.mpcsub(low).mpcadd(one); // 1 - low +
randN
rnotc[i+oddNum] = high; // high
break;
case 2:
xor[i+oddNum] = randN.mpcsub(high).mpcadd(one); // 1 - high
+ randN
rnotc[i+oddNum] = randN; //randN
break;
case 3:
xor[i+oddNum] = notrandN.mpcadd(one); // 1 - randN
rnotc[i+oddNum] = new Share(0L);
break;
default: //Should never be reached
System.out.println("Case statement reaches wrong end");
break;
}
// Turning the xor values from the set {0,1} to the set {1,2}
xor[i+oddNum] = xor[i+oddNum].mpcadd(one);
} //xor and rnotc are now set
xor = Faunin (xor, true); //reversed Faun-in on xor
Share Returnval = new Share(0L);
for (int i=0; i<halvedLen+oddNum; i++) {
Share temp = xor[i].mpcmult(rnotc[i]);
Returnval = Returnval.mpcadd(temp);
}
return Returnval;
}
public void runtest() {
runtest3();
}
public void runtest2() {
// A test of generateing random bitwise shared numbers
int field_size = 31;
BigInteger field2 = BigInteger.valueOf((long)field_size);
//BigInteger field2 = BigInteger.valueOf(8191L);
Field.setBaseField(field2);
//System.out.println("Number of bits in P is " +
Field.getBaseField().bitLength());
//System.out.println("Number of bits set is " + initialBitsSetInP());
System.out.println("P is " + Field.getBaseField());
Field[] Psplit = splitP();
System.out.print("P is in bits ");
for (int i=Psplit.length-1; i>-1; i--) {
if (Psplit[i].compareToONE())
System.out.print("1");
else
System.out.print("0");
}
System.out.println("");
int[] eq_cont = new int[field_size+1];
for (int i=0; i<eq_cont.length; i++)
eq_cont[i] = 0;
Share[] Rand;
Field.writeWithPlussMinus = false;
for (int j=0; j<10000; j++) {
Rand = generateRandomBitwiseSharedValue();
BigInteger test = convertFromBitsToValueB(Rand);
int val = test.intValue();
eq_cont[val]++;
//System.out.println("i "+i);
}
for (int i=0; i<eq_cont.length; i++) {
System.out.println("Val "+i+ " happens "+eq_cont[i]+" times.");
}
}
public void runtest3() {
}
}
_______________________________________________
viff-devel mailing list (http://viff.dk/)
[email protected]
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
