[viff-devel] OrlandiRuntime implementation

[Claudio Orlandi]

Ok let's use additive notation. Right now I believe that if you need to compute
C=x*P
where x is integer and P is a point on the curve you use some kind a
double-and-add ladder, right? (if not you should -- probably this is
hidden in the library).
This is the most stupid ladder (this is bad because of timing attacks,
anyway...)
Let x= \sum 2^i x_i
Then
1) Init: C=0
2) for i = log_2(x)-1 to 0
   C=2C
   if (x_i =1 ) C=C+P
3) output C
This uses an average of 2log(x) additions.
C is correct in fact C = 2(2(...)+x_1*P)+x_0*P = \sum 2^i x_i P = xP

Now the thing is, say you have to compute
C=x*P+y*Q.
You can do it like this
1) A=x*P
2) B=y*Q
3) C=A+B
And you use an average of 4log(x) additions.

Or you can do it smarter, precompute
G00 = 0
G01= Q
G10 = P
G11 = P+Q

And then do a ladder where you look at two bits at the time, that is
Let x= \sum 2^i x_i
y= \sum 2^i y_i
Then
1) Init: C=0
2) for i = log_2(x)-1 to 0
   C=2C
   if (x_i =0 and y_i = 0) C=C+G00
   if (x_i =0 and y_i = 1) C=C+G01
   if (x_i =1 and y_i = 0) C=C+G10
   if (x_i =1 and y_i = 1) C=C+G11
3) output C
C is correct in fact C = 2(2(...)+(x_1*P+y_1*Q) )+(x_0*P+y_0*Q) = xP+yQ
The number of additions is exactly 2log(x), i.e. this takes half the
time than the other method (the time spent in the if is small compared
to one addition).
(Our commitments have three elements g,h_1,h_2, so we save a factor 3)

If you want, you can also look at more than 1 bit at the time and do
something like

Precompute
G_i,j = i*P+j*Q
for i,j = 0,1,2,3

Now the ladder is:
1) Init: C=0
2) for i = log_2(x)-1 to 0 step -2
   C=4C
   C=C+ G_(2x_i + x_(i-1) ),( 2y_i + y_(i-1) ) // I hope that this
notation is clear...
3) output C

This ladder uses exactly 3 additions (2 to compute 4C --- or is there
a smarter method?) per iterations, with a total of log(x)/2
iterations. So the number of additions is 3/2 log(x), but requires to
use a bigger table of 16 base elements G_ij.
One can go on and look at k bits at the time, then the ladder requires
(k+1)/k log(x) additions, and needs to precompute a table of size 2^k.

In the extreme case one looks at log(x) bit at the time, and then
computing a multiplication is just looking up in a table. Clearly this
last solution requires too much memory, so my question is, what's the
optimal number of bits to consider at the same time? This should
depend on the machine/language characteristics... I would bet that
it's not worth to go over 5.

By the way this is not mine, is something that Shamir noticed a long time ago...

Claudio



On Thu, Nov 5, 2009 at 12:38 AM, Janus Dam Nielsen
<janus.nielsen at alexandra.dk> wrote:
> Hi Claudio,
>
> 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 computations are done on an elliptic curve, and thus the exponentiations
> are done using multiplications, and the multiplications are done using
> additions on points on the curve.
> I don't know how the improvements you suggests maps to this?
> ____________________________________________________
> Janus Dam Nielsen
> Research and Innovationspecialist, PhD.
> CENTRE FOR IT-SECURITY
> THE ALEXANDRA INSTITUTE LTD.
> T +45 42 22 93 56
> E janus.nielsen at alexandra.dk
> W alexandra.dk
> ____________________________________________________
>