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. 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. > 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? Claudio _______________________________________________ viff-devel mailing list (http://viff.dk/) viff-devel@viff.dk http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk
