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

[Mike Hamburg <[e-mail]>]

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.

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 <https://bench.cr.yp.to/results-dh.html>.  Libdecaf likewise uses precomputed combs for fixed-base scalarmul.  But your new technique is certainly simpler.

Cheers,
— Mike

> On May 11, 2017, at 5:14 PM, Francisco Rodriguez- Henriquez <[e-mail]> wrote:
> 
> Dear CFRG community,
> 
> We would like to draw your attention to an improved version of our IACR pre-print 2017/264 now entitled:
> 
> 	"How to (pre-)compute a ladder"
> 
> In this revised version, we present an improved differential addition formula that uses pre-computation to match the computational cost of the classical Montgomery differential addition.
> 
> Accordingly, our estimates suggest that a full implementation of our pre-computable ladder proposal should outperform state-of-the-art software implementations of the X25519 and X448 functions by a 40% speedup when working in the fixed-point scenario.
> 
> We would be delighted to receive feedback (including sightings of typos) from the CFRG community.
> 
> With best regards,
> 
> Thomaz Oliveira, Julio López, Hüseyin Hisil and Francisco Rodríguez-Henríquez_______________________________________________
> Cfrg mailing list
> [e-mail]
> https://www.irtf.org/mailman/listinfo/cfrg