Re: [Cfrg] A note on how to (pre-)compute a ladder

Hi Francisco,

Seems like a nice performance win for key generation with very little
extra effort over the variable-point ladder in RFC 7748.

Would it be worth briefly addressing safe-error attacks?

At first glance Algorithm 4 appears to not involve R2 in the final
result, although it's made clear later in Algorithm 5 that both R1 and
R2 are used in every addition due to the choice of addition formula.

Remark 2 at the end of 5.1 presents this as a minor performance
optimization, but fails to point out that it is needed to protect
against safe-error attacks.

Regards,
Pete Dettman

On 30/03/2017 8:00 AM, Francisco Rodriguez- Henriquez wrote:
> Dear CFRG community,
> 
> We would like to draw your attention to our IACR pre-print entitled,
> 
> "A note on how to (pre-)compute a ladder
> Improving the performance of X25519 and X448"
> 
> https://eprint.iacr.org/2017/264.pdf.
> 
> For the point multiplication computation Q = kP, this note describes a
> right-to-left version of the Montgomery ladder, which is amenable for
> pre-computing multiples of the base point P. By requiring very modest
> memory resources and a small implementation effort, it obtains noticeable
> performance improvements with respect to the RFC 7748 classical ladder
> procedure.
> 
> We stress that our proposal fully complies with the RFC 7748
> specification, in the sense that given any arbitrary secret keys of
> Alice and Bob, our ladder generates exactly the same public keys that an
> implementation of the RFC 7748 would output.
> 
> As a way of illustration, in Appendix B of our note, we include a magma
> script, which given Alice and Bob private keys of RFC7748 Sec. 6.2, it
> computes the same public keys as specified in that document.
> 
> We would be delighted to receive feedback (including sightings of typos)
> from the CFRG community.
> 
> With best regards,
> 
> Thomaz Oliveira, Julio López and Francisco Rodríguez-Henríquez
> 
> 
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
> 