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
-
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},
url = {https://eprint.iacr.org/2020/378}
}
