### 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.

Available format(s)
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Contact author(s)
kaushikn_r @ isical ac in
palash @ isical ac in
History
2020-05-29: last of 2 revisions
See all versions
Short URL
https://ia.cr/2020/378

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.