# Re: [viff-devel] OrlandiRuntime implementation

On Wed, Nov 4, 2009 at 3:18 PM, Marcel Keller <mkel...@cs.au.dk> wrote:
> 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
>>>
>>>> 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?
>

Oh that's fine. It would also be fine to do the test set first and the
TripleTest after. Sorry for the confusion.

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