Cryptanalysis of Isogeny-based Protocols in Genus 1 and 2

Download Statistics

Downloads

Downloads per month over past year

Weitkämper, Charlotte (2023). Cryptanalysis of Isogeny-based Protocols in Genus 1 and 2. University of Birmingham. Ph.D.

Preview

Weitkaemper2023PhD.pdf
Text - Accepted Version
Available under License All rights reserved.
Download (2MB) | Preview

Abstract

Isogeny-based cryptography is one of the contenders for providing cryptosystems based on mathematical problems which are assumed to be hard for both classical and quantum computers. The most general of these isogeny-related problems, the pure isogeny problem, is the task of finding an isogeny between any two given supersingular elliptic curves. Many variants of this problem exist - not all of which are actually hard both classically and quantumly. Some variants use special primes, require the found isogeny to be of a certain degree, provide additional torsion point information, use specific elliptic curves instead of arbitrary ones, or translate the problem to a higher-dimensional setting using genus-2 curves.

This thesis focuses on the cryptanalysis of encryption schemes using variants of the pure isogeny problem for their underlying hardness assumption. We provide several attacks on the Supersingular Isogeny Diffie–Hellman (SIDH) protocol and some variants thereof. Note that these results predate the recent remarkable full break of the SIDH protocol by Castryck and Decru, as well as others.

We first introduce a general attack framework using a malleability oracle to reduce inverting a one-way function with specific characteristics to quantumly solving a hidden shift problem. This framework can be instantiated to provide a quantum subexponential attack on SIDH with overstretched parameters by defining a group acting on subsets of the SIDH keyspace. Furthermore, we present adaptive attacks on two variants of the SIDH
protocol which recover static secret keys by repeatedly sending malformed public information. The first protocol produces related key exchange instances from making use of non-trivial automorphisms existing on special elliptic curves. The second protocol is a variant using Jacobians of hyperelliptic genus-2 curves as well as elliptic curve products and isogenies between them. We conclude this thesis with the presentation of several new algorithms for computing isogenies between arbitrary supersingular elliptic curves of prescribed degree which, in most cases, require knowledge of the endomorphism rings. Making use of speedups obtained from quantum search and factoring algorithms, these methods result in an acceleration of the computation of certain isogenies.

Type of Work:

Thesis (Doctorates > Ph.D.)

Award Type:

Doctorates > Ph.D.

Supervisor(s):