Factoring Isogenies in Higher Dimension and Applications

Abstract

In this manuscript, we tackle the problem of secure communication in the presence
of an adversary with quantum capabilities. Our focus is isogeny-based cryptography, a branch of post-quantum cryptography that relies on the computational
difficulty of finding isogenies between certain elliptic curves.
In cryptography, isogenies typically appear as chains of prime-degree maps. Much
like prime numbers, prime-degree isogenies can be considered “atomic entities”. This
raises a natural question: is it possible to “factor” composite-degree isogenies, and if so,
under what conditions?
We show that, in specific instances, this question is indeed meaningful, and finding a
partial answer to this problem provides interesting applications, both as a cryptanalytic
tool and a building block.
We then describe an attack on SIDH, which was one of the most promising postquantum key exchanges. This attack relies on the computation of isogenies between
products of elliptic curves. We study the problem of computing a specific class of isogenies
between such products and provide an algorithm that significantly improves on the state
of the art.
With an efficient method for computing these isogenies, we then explore constructive
applications stemming from the attack on SIDH. We first propose a public-key encryption
mechanism, followed by a verifiable delay function.
Finally, we consider other potential applications of this novel technique for factoring
isogenies between elliptic curves and discuss future research directions in isogeny-based
cryptography.

Date of Award	18 Mar 2025
Original language	English
Awarding Institution	University of Bristol
Supervisor	Chloe Martindale (Supervisor)