Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography / Diffie-Hellman key agreement, Montgomery ladder, Curve25519, Curve448, ECDH, vectorization, SIMD.

Date: received 2 Apr 2020, last revised 29 May 2020

Contact author: kaushikn_r at isical ac in,palash@isical ac in

Available format(s): PDF | BibTeX Citation

Note: Minor correction in Figure 2.

Version: 20200529:133153 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]