Cryptology ePrint Archive: Report 2020/378

Efficient 4-way Vectorizations of the Montgomery Ladder

Kaushik Nath and Palash Sarkar

Abstract: In this work we propose three new algorithms for 4-way vectorization of the well known Montgomery ladder. The first algorithm requires three multiplication rounds which is optimal. The computation of the Montgomery ladder includes a multiplication by a constant which is small for curves that are used in practice. In this case, using the round optimal algorithm is not the best choice. Our second algorithm requires two multiplication rounds, a squaring round and a round for the multiplication by the constant. This provides an improvement over the first algorithm. The third algorithm improves upon the first two for fixed base scalar multiplication, where the base point is small. 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 shared secret computation phase of the Diffie-Hellman key agreement protocol. Timing results on the Haswell and Skylake processors show significant speed improvements in comparison to best known existing implementations corresponding to previously published works.

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

Date: received 2 Apr 2020

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

Available format(s): PDF | BibTeX Citation

Version: 20200402:123039 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]