Isogeny-Based Zero-Knowledge Proofs and Their Applications

Abstract

Isogeny-based cryptography is one of the main avenues of research in post-quantum cryptography. The fundamental idea of this breach is that there is currently no known efficient algorithm to compute an isogeny between two supersingular elliptic curves, even when one has access to a quantum computer. However, this pure primitive keeps too much information about the secret isogeny hidden to be directly applied to most applications. As such, almost every protocol based on isogeny reveals some extra information about the secret isogeny. This is famously the case for Supersingular Isogeny Diffie--Hellman (SIDH), which transmits the mapping of the isogeny on a torsion subgroup, the degree of the isogeny, and the endomorphism ring of the domain curve.

The recent polynomial-time attacks on SIDH have shown that leaking the torsion subgroup mapping gives away too much information to an attacker. Because of this, the SIDH variants proposed to resist these attacks all mask the mapping in some way. However, less attention has been paid to the other types of information that SIDH and most of its new variants transmit. This is especially worrying when it comes to the endomorphism ring of the starting curve, as it was shown multiple times that it can lead to easier attacks. In fact, the first of the recent polynomial-time attacks on SIDH made direct use of the endomorphism ring. Also, before these attacks fully broke SIDH, Petit showed that knowledge of the endomorphism ring could lead to a polynomial-time attack on SIDH when the parameter sets were unbalanced. Castryck and Vercauteren recently showed that the same attacks on unbalanced parameters with known endomorphism rings can be extended to some of the new SIDH variants, such as M-SIDH.

An interesting fact about SIDH variants is that most of them do not explicitly need to transmit the endomorphism ring. Most implementations do so because it is simpler. The goal of this thesis is therefore to further study the case for masking the endomorphism ring of the domain curve for SIDH variants. We start by showing that, for well-chosen parameter sets, working with a random starting curve can never lead to a loss of security. This thesis also explores the use of multiparty computations to generate curves of unknown endomorphism rings. Finally, we present a new set of zero-knowledge proofs for SIDH variants that do not require knowledge of any endomorphism rings and can be made to mask the degree of the secret isogeny.