A simple and compact algorithm for sidh with arbitrary degree isogenies

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. © 2017 Elsevier B.V. All rights reserved.