Re: [Cfrg] How to (pre-)compute a ladder [revised version]

[Francisco Rodriguez- Henriquez <[e-mail]>]

Hi Peter,

Please see my reply below.

Cheers,
Francisco
[on behalf of the authors]

On Fri, 16 Jun 2017, Peter Dettman wrote:

> Hi Francisco,
>
> I've updated my (java) implementations of X25519 and X448 in line with
> your revised paper. My rough benchmark results for a complete ECDH are
> -17.7% and -19.5% time required for X25519 and X448 respectively.

Great!
This is roughly in the same ballpark of what we are getting in our C 
implementation, which is available at,

https://github.com/armfazh/rfc7748_precomputed

[please check my previous email to this list]

> These are perhaps slightly more modest than the paper's estimates. Your
> paper already anticipates that (uncounted) field add/sub are significant
> in practice.

Right!

This effect appears to be more significant in the case of X25519 than in 
the case of X448.


> Part of the difference however is that my implementation of Algorithm 3
> handles the final 'q' bits using simple doublings, and removes redundant
> cswaps - just as Algorithm 5 does. Of course Alg. 3 is just as presented
> in RFC 7748, but it might be a fairer comparison to first apply to Alg.
> 3 those of your optimizations that are applicable.
>
> Also, my (32-bit) X448 implementation (Alg. 5) required a carry
> propagation for 'A' (line 10), due to tight bounds on limbs when
> squaring D, E. I did the same for (32-bit) X25519 although I haven't yet
> proved it necessary.

OK!
If you have time please compare against the C implementation mentioned 
above.

> An idea: for fixed-base X25519, why not precompute one doubling? i.e.
> just calculate (k/2) * 2P, needing only 2 final doublings (you even
> already have S of order 4). I am not sure whether this extends to
> precomputing (q-1) doublings.
>
> Another thought that occurred to me is that someone might get the idea
> to use your fixed-base ladder with some other point. Couldn't this go
> awry if that point were already "P + S" or similar? If so, a caution
> somewhere in the paper on preconditions for the fixed point might be
> advised.
>
> Regards,
> Pete Dettman

Thanks for both suggestions. We will carefully analyze both of them.


Cheers,
Francisco