Re: [viff-devel] Choice of comparison protocol
[EMAIL PROTECTED] writes: * ComparisonToft05Mixin which gives a result in GF256. It is described in your progress report: http://www.daimi.au.dk/~tomas/publications/progress.pdf * ComparisonToft07Mixin where the result is a Zp element. As far as I know it is not described in any published material. True. And on a sidenote: it bugs me that the comparisons return things differently, and therefore cannot be interchanged. It shouldn't be too costly to move the GF(256) back to Zp though. Yeah, it is definitely annoying that they don't agree on the return type. Alternatively, the '05 could be written entirely in Zp avoiding GF(256) all together. The XORs in the diamond operator can still be local by replacing them with addition and subtraction. bot = top_b * (bot_a - bot_b) + bot_b rather than bot = top_b * (bot_a ^ bot_b) ^ bot_b Hehe, that is cool! And since (^) == (+) == (-) for GF256, we can easily switch to always computing the diamond operator like this. This does the same and avoids the conversion to GF(256), but may be more expensive online (IIRC GF(256) computation is /really/ fast). Well, that is easy to check. The timeit module says: % python -m timeit -s 'from viff.field import GF' \ -s 'F = GF(256)' -s 'x = F(17)' -s 'y = F(152)' \ 'x + y' 10 loops, best of 3: 4.91 usec per loop % python -m timeit -s 'from viff.field import GF' \ -s 'F = GF(256)' -s 'x = F(17)' -s 'y = F(152)' \ 'x * y' 10 loops, best of 3: 6.05 usec per loop % python -m timeit -s 'from viff.field import GF' \ -s 'from viff.util import find_prime' \ -s 'F = GF(find_prime(2**32))' \ -s 'x = F(17)' -s 'y = F(152)' \ 'x + y' 10 loops, best of 3: 5.4 usec per loop % python -m timeit -s 'from viff.field import GF' \ -s 'from viff.util import find_prime' \ -s 'F = GF(find_prime(2**32))' \ -s 'x = F(17)' -s 'y = F(152)' \ 'x * y' 10 loops, best of 3: 5.44 usec per loop So for small field elements, both fields are about equally fast. Testing with larger elements gives about the same results: % python -m timeit [...] -s 'F = GF(find_prime(2**32))' \ -s 'x = F(-17)' -s 'y = F(-152)' 'x + y' 10 loops, best of 3: 5.95 usec per loop % python -m timeit [...] -s 'F = GF(find_prime(2**32))' \ -s 'x = F(-17)' -s 'y = F(-152)' 'x * y' 10 loops, best of 3: 6.59 usec per loop Like you, I had expected GF256 to be significantly faster. 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. -- Martin Geisler ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Choice of comparison protocol
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; ibits.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; ia.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; ia.length; i++)
b[a.length-1-i] = a[i];
Share [] c = Faunin(b);
for (int i=0; ia.length; i++)
b[a.length-1-i] = c[i];
return b;
}
else
return Faunin(a);
}
public
Re: [viff-devel] Choice of comparison protocol
Martin Geisler wrote: [EMAIL PROTECTED] writes: snip comparison return value disagreement snip '05 variation This does the same and avoids the conversion to GF(256), but may be more expensive online (IIRC GF(256) computation is /really/ fast). Well, that is easy to check. The timeit module says: snip timing data Like you, I had expected GF256 to be significantly faster. I don't like the fixed input data in the timings. The Zp elements chosen may be good or bad candidates, and computation on random elements may be worse... Regarding GF(256) this should not be a problem, as IIRC the multiplication is a table lookup. However, you may avoid cache-misses entirely, so those numbers should also be taken with a small grain of salt. snip old constant rounds solution 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. My publication list is my fault. But the paper will be available in the conference proceedings; to appear in LNCS I believe. I can dig out a copy and mail it to you if you like. Regards, Tomas ___ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Choice of comparison protocol
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/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Choice of comparison protocol
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/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
Re: [viff-devel] Fixed memory leak
Tomas Toft [EMAIL PROTECTED] writes:
Hi everybody!
Nope, memory usage has grown.
viff-0.4:
~630,000kB
viff-f993269c2660:
~690,000kB
And this is per party (three of them in all).
Okay, thanks for testing! But maybe something else changed since
viff-0.4, so could you try revisions 563bcc37fe47 and f993269c2660?
It is quite easy in a Mercurial clone: if you have all local
modifications committed, then just do a 'hg update 563bcc37fe47' to
change the working copy to that revision. Do a 'hg update tip' to get
back to the tip.
But I do see a difference: In 0.4 the memory usage was constantly
max'ed out. In f993269c2660, two parties can finish early and then
free essentially all their memory. Later they then reallocate ~0.5GB.
So something good is definitely happening, but it doesn't solve my
problem :-(
Hmm... I think we need to do some serious work on memory profiling (and
profiling in general). The new gc-test.py program shows a simple way to
do it under Linux -- it could be extended and built into VIFF.
I imagine some setting where memory usage will be sampled and dumped at
the end. The code would then do something like this:
enter_phase('starting x')
x = something big
x.addCallback(enter_phase, 'x ready')
x.addCallback(do_stuff_with_x)
enter_phase('starting y')
y = something else
y.addCallback(enter_phase, 'y ready')
which would result in 'phases' being defined and marked on the graph. If
several phases are active at the same time it could lead to several bars
like in this image:
http://www.bootchart.org/images/bootchart.initial.png
There they trace the boot sequence and each process is a separate bar.
It would be very cool if we could produce something similar!
And just to describe my gigantic computation, it's actually not so
big: I load 100,000 shares (of Z_7 :-) from disk, reconstruct the
associated values, and print them.
Yeah, that sounds simple :-)
Saying 4 bytes/field-element (say using 32-bit integers as could be
done easily in C), and 400,000 field-elements (100,000 shares from
each of the three parties and 100,000 reconstructed secrets) this
amounts to around an astonishing 400kB (per party).
Right, 100,000 32-bit values would be 400 KB. If you allocated them as
integers using the array module, then they would take up close to 400 KB
in Python. But each Share holds a FieldElement which holds two integers.
So some of the massive overhead is simply due to more objects being
tossed around. Then there is a per object malloc overhead, reference
counters, list overallocation, etc... :-/
By the way, there is now an open ticket at Twisted about the memory
consumption of Deferred:
http://twistedmatrix.com/trac/ticket/3245
I made a patch and I hope they will eventually include it. Another guy
reported that using __slots__ cut the memory usage in half.
One positive thing here is that I've gotten an idea of how to
potentially remove /some/ of that overhead (honest-but-curious only).
Have you tried the code I sent you? I posted it here as well:
http://article.gmane.org/gmane.comp.python.twisted/16519
and got two comments that said that similar functionality already
existed in Twisted :-) There is a DeferredQueue and DeferredSemaphore in
twisted.internet.defer which could be used to limit concurrency.
The observation is that we don't need to store all shares and
reconstruct at the end. We can just keep track of the sum of the
shares (times their lambda's) we've recieved. Whenever a new one
arrives we add it to that accumulator. This might not make a big
difference in a 3-party setting, but if many (e.g. 10) parties are
involved, then this seems like a good idea to reduce memory
requirements.
Do you mean that we can sort of recombine as we go? I can see how that
makes sense if we know which recombination vector to use -- and if
people are honest-but-curious (as you write) then that is no problem.
In the honest-but-curious setting we could even make it so that only t+1
players ever send their shares. If there are S such subsets, then we
could choose subset number hash(program_counter) % S for each
operation -- that would distribute the load evenly over all parties.
--
Martin Geisler
pgpLtAi6RH12Z.pgp
Description: PGP signature
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
