# [viff-devel] OrlandiRuntime implementation

Claudio Orlandi orlandi at cs.au.dk
Wed Nov 4 08:36:43 PST 2009

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