What particular goals will there be toward which the leading cryptographical spirits of coming generations will strive?
Lofty minds are led to strive for the advance of science by nothing more than by laying before them difficult and at the same time useful problems: this page enumerates the foremost unsolved problems in the domain of isogeny-based cryptography. The resolution of any of these profound questions would mark a monumental advance in our discipline, and the broader cryptographical sciences. Thus, we hear within us the perpetual call: There is the problem. Seek its solution. You can find it by pure reason, for in isogeny-based cryptography, as in mathematics, there is no ignorabimus.
This page contains a short description per problem, together with a detailed exposition by an expert. The compilation of these seven expositions is available here.
Statement: Given two supersingular elliptic curves \( E \) and \( E' \) over a finite field
\( \mathbb{F}_{p^2} \),
compute an explicit isogeny \( \varphi : E \to E' \).
A solution contains: the description of a classical algorithm
with time complexity below \( \mathcal{O} ( p^{\frac{1}{2} - \varepsilon} ) \) for some \( \varepsilon > 0 \),
or, show that such an algorithm cannot exist.
Statement: Let \( \mathcal{O} \) be an imaginary quadratic order of discriminant \( d \).
Given two \( \mathcal{O} \)-oriented elliptic curves \( (E, \omega) \) and \( (E', \omega') \),
find an ideal \( \mathfrak{a} \) such that \( \mathfrak{a} \ast (E, \omega) = (E', \omega') \).
A solution contains: the description of a classical or quantum algorithm with time complexity below \( L_d( 1/2 ) \), or, show that such an algorithm cannot exist.
Statement: Give an algorithm \( \mathcal{A} \) that takes a prime \( p \) and a binary string \( \mathtt{m} \),
and returns a supersingular curve \( E \) over \(\mathbb{F}_{p^2} \).
A correct solution contains: the
description of a deterministic polynomial-time algorithm that satisfies the following properties
or, show that such a function cannot exist.
Statement: Given a prime number \( p \), a maximal order \( O \) in \(B_{p, \infty}\),
and a left integral \( O \)-ideal \( I \), find an equivalent ideal \( J \sim I \)
of norm \( N(J) = \ell^e \).
A solution contains: the description of a polynomial-time
algorithm that finds an ideal \( J \) with norm (close-to) optimal,
or, show that such an algorithm cannot exist.
Statement: Given a supersingular curve \( E \) over a finite field \( \mathbb{F}_q \) and a positive integer \( n \), generate an isogeny
\( \varphi : E \to E' \) of degree \( n \) where \( E' \) is some other curve.
A solution contains: the description of a polynomial-time algorithm to compute \( \varphi(P) \) for any point \( P \in E(\mathbb{F}_q) \),
without any a priori non-trivial knowledge of the endomorphism ring \( \operatorname{End}(E) \), or, show that such an algorithm cannot exist.
Statement: Given \( \operatorname{End}(E) \) and a representation of an isogeny \( \varphi : E \to E' \),
compute \( \operatorname{End}(E') \).
A solution contains: the description of a classical polynomial-time algorithm to compute \( \operatorname{End}(E') \)
for any representation of \( \varphi \), or, show that such an algorithm cannot exist.
Statement: Construct post-quantum encryption schemes, whose security reduces to (a small variant of)
the Endomorphism Ring Problem.
Several solutions can be accepted for:
the construction of an efficient post-quantum instantiation of a
or, show that such a scheme cannot exist.
Statement: We have an efficient quantum reduction from vectorization to parallelization for class group actions. Give an efficient classical algorithm that reduces vectorization to parallelization for class group actions, or show that a classical reduction cannot exist.
The reward system is pledge-based. If you want to pledge to a certain problem, mail us, and let us know if you wish to remain anonymous. For solutions, mail these in the form of a paper, preprint, or pdf. Only solutions that are peer-reviewed will be accepted. The editor reserves final discretion on whether any submission constitutes a valid solution.
A similar list of mathematical problems at the core of post-quantum cryptography, including lattice-based and code-based problems, is given by Chloe Martindale here.