# Re: [viff-devel] OrlandiRuntime implementation

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

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
>

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.

> Regards,
> Marcel
>
>
_______________________________________________
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk