[viff-devel] OrlandiRuntime implementation

[Marcel Keller]

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.

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.

Best regards,
Marcel