A Simple and Compact Algorithm for SIDH with Arbitrary Degree Isogenies
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
- PDF / 608,440 Bytes
- 27 Pages / 439.37 x 666.142 pts Page_size
- 99 Downloads / 165 Views
Microsoft Research, Redmond, USA [email protected] 2 Yasar University, Izmir, Turkey [email protected]
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. Keywords: Post-quantum cryptography phy · SIDH · Montgomery curves
1
·
Isogeny-based cryptogra-
Introduction
Post-quantum Key Establishment. The existence of a quantum computer that is capable of implementing Shor’s algorithm [36] at a large enough scale would have devastating consequences on the current public-key cryptographic standards and thus on the current state of cybersecurity [32]. Subsequently, the field of post-quantum cryptography (PQC) [4] is rapidly growing as cryptographers look for public-key solutions that can resist large-scale quantum adversaries. Recently, the USA’s National Institute of Standards and Technology (NIST) began a process to develop new cryptographic standards and announced a call for PQC proposals with a deadline of November 30, 2017 [40]. c International Association for Cryptologic Research 2017 T. Takagi and T. Peyrin (Eds.): ASIACRYPT 2017, Part II, LNCS 10625, pp. 303–329, 2017. https://doi.org/10.1007/978-3-319-70697-9_11
304
C. Costello and H. Hisil
Although the PQC community is currently examining alternatives to replace both traditional key establishment and traditional digital signature algorithms, there is an argument for scrutinising proposals in the former category with more haste than those in the latter. While digital signatures only need to be quantumsecure at the moment a powerful enough quantum adversary is realised, the realistic threat of long-term archival of sensitive data and a retroactive quantum break means that, ideally, key establishment protocols will offer quantum resistance long before such a quantum adversary exists [38]. Post-quantum key establishment proposals typically fall under one of three umbrellas: (i) Code-based
Data Loading...
