[viff-devel] OrlandiRuntime implementation

[Marcel Keller]

Claudio Orlandi wrote:
> On Wed, Nov 4, 2009 at 5:46 AM, Marcel Keller <mkeller at 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.

>> 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.

Regards,
Marcel