Paper 2017/1015

A Faster Software Implementation of the Supersingular Isogeny Diffie-Hellman Key Exchange Protocol

Armando Faz-Hernández, Julio López, Eduardo Ochoa-Jiménez, and Francisco Rodríguez-Henríquez

Abstract

Since its introduction by Jao and De Feo in 2011, the supersingular isogeny Diffie-Hellman (SIDH) key exchange protocol has positioned itself as a promising candidate for post-quantum cryptography. One salient feature of the SIDH protocol is that it requires exceptionally short key sizes. However, the latency associated to SIDH is higher than the ones reported for other post-quantum cryptosystem proposals. Aiming to accelerate the SIDH runtime performance, we present in this work several algorithmic optimizations targeting both elliptic-curve and field arithmetic operations. We introduce in the context of the SIDH protocol a more efficient approach for calculating the elliptic curve operation P + [k]Q. Our strategy achieves a factor 1.4 speedup compared with the popular variable-three-point ladder algorithm regularly used in the SIDH shared secret phase. Moreover, profiting from pre-computation techniques our algorithm yields a factor 1.7 acceleration for the computation of this operation in the SIDH key generation phase. We also present an optimized evaluation of the point tripling formula, and discuss several algorithmic and implementation techniques that lead to faster field arithmetic computations. A software implementation of the above improvements on an Intel Skylake Core i7-6700 processor gives a factor 1.33 speedup against the state-of-the-art software implementation of the SIDH protocol reported by Costello-Longa-Naehrig in CRYPTO 2016.

Note: To cite this work use: @ARTICLE{flor_sidh_x64, author={A. Faz-Hernández and J. López and E. Ochoa-Jiménez and F. Rodríguez-Henríquez}, journal={IEEE Transactions on Computers}, title={A Faster Software Implementation of the Supersingular Isogeny Diffie-Hellman Key Exchange Protocol}, year={2017}, volume={PP}, number={99}, pages={1-1}, keywords={Acceleration;Cryptography;Elliptic curves;Kernel;Proposals;Protocols;Montgomery ladder;Montgomery reduction;SIDH protocol;post-quantum cryptography}, doi={10.1109/TC.2017.2771535}, ISSN={0018-9340}, month={}, }

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Minor revision. IEEE Transactions on Computers
DOI
10.1109/TC.2017.2771535
Keywords
SIDH protocolMontgomery ladderpost-quantum cryptographyMontgomery reduction
Contact author(s)
armfazh @ ic unicamp br
History
2017-12-31: last of 2 revisions
2017-10-18: received
See all versions
Short URL
https://ia.cr/2017/1015
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/1015,
      author = {Armando Faz-Hernández and Julio López and Eduardo Ochoa-Jiménez and Francisco Rodríguez-Henríquez},
      title = {A Faster Software Implementation of the Supersingular Isogeny Diffie-Hellman Key Exchange Protocol},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1015},
      year = {2017},
      doi = {10.1109/TC.2017.2771535},
      note = {\url{https://eprint.iacr.org/2017/1015}},
      url = {https://eprint.iacr.org/2017/1015}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.