A note on how to (pre-)compute a ladder

Thomaz Oliveira; Julio López; Hüseyin Hışıl; Armando Faz-Hernández; Francisco Rodrıíguez-Henrıíquez

eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2017/264

A note on how to (pre-)compute a ladder

Thomaz Oliveira, Julio López, Hüseyin Hışıl, Armando Faz-Hernández, and Francisco Rodrıíguez-Henrıíquez

Abstract

In the RFC 7748 memorandum, the Internet Research Task Force specified a Montgomery-ladder scalar multiplication function based on two recently adopted elliptic curves, ``curve25519" and ``curve448". The purpose of this function is to support the Diffie-Hellman key exchange algorithm that will be included in the forthcoming version of the Transport Layer Security cryptographic protocol. In this paper, we describe a ladder variant that permits to accelerate the fixed-point multiplication function inherent to the Diffie-Hellman key pair generation phase. Our proposal combines a right-to-left version of the Montgomery ladder along with the pre-computation of constant values directly derived from the base-point and its multiples. To our knowledge, this is the first proposal of a Montgomery ladder procedure for prime elliptic curves that admits the extensive use of pre-computation. In exchange of very modest memory resources and a small extra programming effort, the proposed ladder obtains significant speedups for software implementations. Moreover, our proposal fully complies with the RFC 7748 specification. Our estimates suggest that a full implementation of our pre-computable ladder 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.

Note: This version shows a significantly improved differential addition formula

Metadata

Available format(s): PDF
Publication info: Published elsewhere. Minor revision. Proceedings of SAC 2017
Keywords: Montgomery ladder Scalar multiplication diffie-Hellman protocol RFC 7748
Contact author(s): francisco @ cs cinvestav mx
History: 2017-10-01: last of 9 revisions; 2017-03-25: received; See all versions
Short URL: https://ia.cr/2017/264
License: CC BY

BibTeX

@misc{cryptoeprint:2017/264,
      author = {Thomaz Oliveira and Julio López and Hüseyin Hışıl and Armando Faz-Hernández and Francisco Rodrıíguez-Henrıíquez},
      title = {A note on how to (pre-)compute a ladder},
      howpublished = {Cryptology ePrint Archive, Paper 2017/264},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/264}},
      url = {https://eprint.iacr.org/2017/264}
}