# [viff-devel] OrlandiRuntime implementation

Janus Dam Nielsen janus.nielsen at alexandra.dk
Thu Nov 5 04:11:17 PST 2009

Hi Claudio,

On 05/11/2009, at 10.28, Claudio Orlandi wrote:

> 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.
The addition is indeed a part of the library. I haven't looked at the
implementation but I would expect better than this from a commercial
crypto library.

> 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...
This is an interesting idea, I will add it to the list of things to do.

____________________________________________________

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
____________________________________________________

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.viff.dk/pipermail/viff-devel-viff.dk/attachments/20091105/a14f9f24/attachment-0002.htm>