A simple and compact algorithm for SIDH with arbitrary degree isogenies

Craig Costello and Huseyin Hisil

Abstract

We derive a new formula for computing arbitrary odd-degree isogenies between elliptic curves in Montgomery form. The formula lends itself to a simple and compact algorithm that can efficiently compute any low odd-degree isogenies inside the supersingular isogeny Diffie-Hellman (SIDH) key exchange protocol. Our implementation of this algorithm shows that, beyond the commonly used 3-isogenies, there is a moderate degradation in relative performance of $(2d+1)$-isogenies as $d$ grows, but that larger values of $d$ can now be used in practical SIDH implementations. We further show that the proposed algorithm can be used to both compute isogenies of curves and evaluate isogenies at points, unifying the two main types of functions needed for isogeny-based public-key cryptography. Together, these results open the door for practical SIDH on a much wider class of curves, and allow for simplified SIDH implementations that only need to call one general-purpose function inside the fundamental computation of the large degree secret isogenies. As an additional contribution, we also give new explicit formulas for 3- and 4-isogenies, and show that these give immediate speedups when substituted into pre-existing SIDH libraries.

Available format(s)
Publication info
Keywords
Post-quantum cryptographyisogeny-based cryptographySIDHMontgomery curves.
Contact author(s)
craigco @ microsoft com
History
2017-09-11: revised
See all versions
Short URL
https://ia.cr/2017/504

CC BY

BibTeX

@misc{cryptoeprint:2017/504,
author = {Craig Costello and Huseyin Hisil},
title = {A simple and compact algorithm for SIDH with arbitrary degree isogenies},
howpublished = {Cryptology ePrint Archive, Paper 2017/504},
year = {2017},
note = {\url{https://eprint.iacr.org/2017/504}},
url = {https://eprint.iacr.org/2017/504}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.