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

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

On May 12, 2017, at 2:15 PM, Mike Hamburg <[e-mail]> wrote:

> Hello Francisco et al,

> This is a clever and useful piece of work.  It's a good intermediate 
> between just using the standard Montgomery ladder for everything, and 
> going to a full Edwards implementation with combs or something.  It 
> especially seems useful where power analysis resistance is required, 
> because other precomputation methods usually aren't suitable.  The RTL 
> Montgomery ladder (or Joye double-add ladder) is already known to be 
> useful in this situation, at least with some modification to prevent 
> coordinates from staying the same between iterations.  Since you're 
> speeding up the RTL Montgomery ladder, your optimization can slot right 
> in to some implementations.

Hi Mike,

Thanks for your comments and sorry for this really slow reply :)

I agree with you about the fact that the RTL Montgomery ladder by Joye was 
already known for performing this feature.

> You should probably compare to existing Edwards precomputation methods 
> in your paper, since they are the likely alternative to your technique. 
> In particular, I noticed that you compared against the EBACS version of 
> Ed448-Goldilocks.  With a fixed base point, your method uses 41% less 
> time for the Montgomery ladder with a 25kiB table.  However, the EBACS 
> version of Ed448-Goldilocks doesn't use the Montgomery ladder for 
> fixed-base scalarmul.  Instead it uses a combs algorithm, which uses a 
> 15kiB table and takes about 70% less time than the Montgomery ladder; 
> see https://bench.cr.yp.to/results-dh.html.  Libdecaf likewise uses 
> precomputed combs for fixed-base scalarmul.  But your new technique is 
> certainly simpler.

I agree with you, there are faster methods to perform pre-computation, 
which offer [some] protection against side-channel attacks.

In our work, we were specifically targeting the RFC 7748 Memo, and hence 
we only meant to compare against ladder procedures for computing the 
scalar multiplication.

I believe that the tradeoffs between the simplicity/elegance/beauty of 
the ladders Vs. the efficiency of regular recoding + other methods of 
pre-computation, was already debated in this list :)

Cheers,
Francisco

> Cheers,
> -- Mike