Claudio Orlandi schrieb:
On Wed, Nov 4, 2009 at 10:15 AM, Marcel Keller <mkel...@cs.au.dk> wrote:
Claudio Orlandi wrote:
On Wed, Nov 4, 2009 at 5:46 AM, Marcel Keller <mkel...@cs.au.dk> wrote:
Hi Claudio and Jesper,
In the code review of the OrlandiRuntime we found two points, we want to
discuss with you.
Step 3 of the triple generation protocol says: Coin-flip a subset
\fancy_T
\subset \fancy_M of size \lambda(2d + 1)M. The current implementation
loops
over the elements in \fancy_M and decides fifty-fifty for every element
whether it should by in \fancy_T until there are enough elements in
\fancy_T. I however think that this choice should be biased according to
the
size of \fancy_M and \fancy_T, i.e. every element of \fancy_M should be
put
in \fancy_T with probability \lambda(2d + 1)M / (1 + \lambda)(2d + 1)M =
\lambda / (1 + \lambda). Furthermore, I think the probability should be
updated whenever \fancy_M is processed completely and \fancy_T still is
not
big enough. Maybe it would be easier to choose \lambda(2d + 1)M times a
random element of the remaining ones in \fancy_M instead.
So you could loop the elements of M and include them in T with
probability \lambda/(1+\lambda), but then you're not guaranteed that
you have enough triplets left in M.
Exactly, that's why I suggested the solution which in that case would
restart with an adapted probability.
Choosing the right number of
random elements from M and include them in T is the right choice (or
any solution that guarantees the size of M \ T to be 2(2d+1)M --- I
don't know if the typo is in your email or in Step 3, but the size of
the set M should be (1+\lambda)2(2d+1)M --- you miss a 2.
I think the 2 is missing in your report and the code.
Wow. Then it really shouldn't work!
The factors are:
1+lambda : because in the test we check a fraction lambda/1+lambda of
the triplets
2 : because there is a test to check the correctness of the triplets
that burns one triplet to ensure the other one is good
2d+1: because we do the shamir secret sharing multiplication
Isn't the burning already done in TripleTest, so you really have just
(lambda+1)(2d+1)M triples when doing coin-flipping for the test set?
I guess at some point I should also give a look at the code...
In step 6, the implementation generates a distributed random number in
Z_p
to determine a partition where one element should be put if there is
still
space there. I suggest to use the randomness more efficiently to save
communication. E.g., if a random number in Z_p is smaller than M^l with l
\le log_M(p), one can extract l random numbers in Z_M. The same method
probably could be used in step 3 as well.
Right. Actually if you want to save communication here you can also
use a PRG using the distributed random number as the seed.
Best regards,
Marcel
If you have time, there are a lot of things that need to be done here.
I already told Janus knows some of them, but said he can't work on
them. Here is something nice we should do to reduce the online time of
a factor (at least) 3:
In the protocol there are Pedersen commitemnts with three base element
g,h_1,h_2. To commit to x using randomness r_1,r_2 one computes
g^xh_1^r_1h_2^r_2. The protocol now does it in the following way:
1) compute a=g^x
2) compute b=h_1^r_1
3) compute c=h_2^r_2
4) compute d=a*b*c
The complexity is dominated by the three exponentiation, that one
implements using some ladder (square and multiply)
There is no need to do three exponentiation if one does something a bit
smarter:
- precompute
g001=g^0h_1^0h_2^1
g010=g^0h_1^1h_2^0
...
g010=g^1h_1^1h_2^1
Now, to compute g^xh_1^r_1h_2^r_2 one does the ladder by looking
comtemporarily at the i-th bit of x, r_1, r_2. The complexity of this
is just one ladder, so virtually the same as just one of the above
exponentiation.
One can go further and precompute more elements, for instance
g000
...
g333
And now you look at 2 bits of x,r_1,r_2 for every square in the
square-and-multiply. This saves another factor 2 in time but you need
to store a bigger table of size 8^2.
What is the best strategy given our architecture? How many powers
should we precompute?
The commitments are computed by an external elliptic curve library, so I
can't answer anything here. Janus should know more about it.
Actually i think that the elliptic curve library offers method for
square, multiply, and a multiplication, not for the commitments as an
object... I seem to remember that Janus implemented them.
In any case, the commitments are completely implemented in C and I
didn't have a look at that code.
_______________________________________________
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
