CAREER: Accelerating Algorithms for Computing Isogenies and Endomorphisms of Supersingular Elliptic Curves

Virginia Polytechnic Institute And State University, Blacksburg VA

Investigators

Abstract

This award focuses on finding paths in certain families of large graphs, called isogeny graphs. Isogeny-based cryptography bases its security on the hardness of path-finding in isogeny graphs, and the path-finding problem is believed to be hard even for quantum computers. Based on this, isogeny-based cryptosystems are believed to be secure even in a post-quantum world. This project will focus on studying the structure of isogeny graphs in order to uncover faster algorithms for computing paths and cycles, leading to a better understanding of the security of isogeny-based cryptosystems. These cryptosystems could one day help secure the modern internet, so a concrete understanding of their security, and hence a concrete understanding of the difficulty of path-finding in isogeny graphs, is imperative. The research component is complemented by educational activities focused on incorporating project-based learning involving programming in undergraduate mathematics courses on number theory and cryptography. Isogeny-based cryptosystems base their security on the difficulty of computing an isogeny between two given supersingular elliptic curves. Such cryptosystems are attractive for their small public keys and their supposed resistance to quantum attacks. SIKE, the lone isogeny-based KEM in the NIST process, was recently completely broken after over a decade of cryptanalysis, highlighting the necessity of relying on the general isogeny problem instead of a weaker one. The general supersingular isogeny problem is equivalent to the problem of computing the endomorphism ring of a given supersingular elliptic curve. The primary research goal for this project is to design and analyze algorithms for computing the endomorphism ring of a supersingular elliptic curve. The second theme of the project aims to determine the expansion properties of isogeny graphs whose mixing rates have yet to be determined. These generalizations of isogeny graphs could have cryptographic applications so it is important to study their expansion properties. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.