Paper 2020/378

Efficient 4-way Vectorizations of the Montgomery Ladder

Kaushik Nath and Palash Sarkar

Abstract

We propose two new algorithms for 4-way vectorization of the well known Montgomery ladder over elliptic curves of Montgomery form. The first algorithm is suitable for variable base scalar multiplication. In comparison to the previous work by Hisil et al. (2020), it eliminates a number of non-multiplication operations at the cost of a single multiplication by a curve constant. Implementation results show this trade-off to be advantageous. The second algorithm is suitable for fixed base scalar multiplication and provides clear speed improvement over a previous vectorization strategy due to Costigan and Schwabe (2009). The well known Montgomery curves Curve25519 and Curve448 are part of the TLS protocol, version~1.3. For these two curves, we provide constant time assembly implementations of the new algorithms. Additionally, for the algorithm of Hisil et al. (2020), we provide improved implementations for Curve25519 and new implementation for Curve448. Timings results on the Haswell and Skylake processors indicate that in practice the new algorithms are to be preferred over previous methods for scalar multiplication on these curves.

Note: Minor correction in Figure 2.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Diffie-Hellman key agreementMontgomery ladderCurve25519Curve448ECDHvectorizationSIMD.
Contact author(s)
kaushikn_r @ isical ac in
palash @ isical ac in
History
2020-05-29: last of 2 revisions
2020-04-02: received
See all versions
Short URL
https://ia.cr/2020/378
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/378,
      author = {Kaushik Nath and Palash Sarkar},
      title = {Efficient 4-way Vectorizations of the Montgomery Ladder},
      howpublished = {Cryptology ePrint Archive, Paper 2020/378},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/378}},
      url = {https://eprint.iacr.org/2020/378}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.