Here is an incomplete list of problems I care about in the intersection of {important to cryptography}\(\cap\){interesting to mathematicians}, in the order that I thought about them. I will attempt to keep this list up-to-date by removing any that are solved or updating the state-of-the-art. If you know of a change that should happen (e.g. an updated state-of-the-art), either because you wrote it or because you read about it, and would like that to be reflected here, or feel that a problem you care about is one I should care about too and have not yet included, please email me at chloe (dot) martindale (at) bristol (dot) ac (dot) uk.

The purpose of this list is to publicise these problems outside of the cryptographic community, primarily to mathematicians, with the goal of increasing the number of people who have thought about the mathematical problems underlying the security of our modern world. For this reason, the problem stated is intentionally **not** the most exact problem from which we have a security reduction but something more similar to a problem likely to be studied in a number theory/geometry/coding theory paper.

Isogeny-based cryptography

1. Given two uniformly random supersingular elliptic curves \(E,E'/\mathbb{F}_{p^2}\), find and efficiently compute an isogeny \(E \rightarrow E'\).
  • State-of-the-art: van Oorschot-Wiener. All isogeny-based schemes completely broken if algorithm is polynomial in \(\text{log}(p)\).
  • Sometimes called 'the isogeny problem'.
    1a. As above but \(p \equiv 11\pmod{12}\) and \(j(E) = 1728\).

    2. Given a uniformly random supersingular elliptic curve \(E/\mathbb{F}_{p^2}\), efficiently compute \(\text{End}(E)\).
  • Polynomially equivalent to (1). All isogeny-based schemes completely broken if algorithm is polynomial in \(\text{log}(p)\).
  • Sometimes called 'the Endomorphism Ring problem'.

    3. Given two uniformly random supersingular elliptic curves \(E,E'/\mathbb{F}_p\), find and efficient compute an isogeny \(E \rightarrow E'\).
  • State-of-the-art: Kuperberg, as applied by Childs-Jao-Soukharev. CSIDH completely broken if algorithm is polynomial in \(\text{log}(p)\).
    3a. As above but \(p \equiv 11\pmod{12}\) and \(j(E) = 1728\).

    4. Given a uniformly random supersingular elliptic curve \(E/\mathbb{F}_p\), efficiently compute \(\text{End}(E)\).
  • Contains \(\mathbb{Z}[\sqrt{-p}]\). If a solution polynomial in \(\text{log}(p)\) to (4) found, completely breaks (3).
  • CSIDH completely broken if algorithm is polynomial in \(\text{log}(p)\).

    5. Given a supersingular elliptic curve \(E/\mathbb{F}_{p^2}\) and an integer \(N \geq 2\sqrt{2p}/\pi\), find an algorithm that efficiently* outputs a random isogeny \(\varphi: E \rightarrow E'\) in efficient* representation such that:
    a. The distribution of \(E'\) is uniform among all supersingular elliptic curves.
    b. The conditional distribution of \(\varphi\) given \(E'\) is uniform among isogenies \(E \rightarrow E'\) of degree \(\leq N\).
  • *This problem is important because of a constructive application, so here 'efficient' is much stronger than above. Polynomial-time and polynomial-size is a must, but we also need concrete efficiency for cryptographic-size primes.
  • A solution to this would remove the need for the UTO oracle in SQISign2D-West, strengthening the security claims of the NIST candidate SQISign.

    6. Given a supersingular elliptic curve \(E/\mathbb{F}_{p^2}\) and an integer \(N\), find an algorithm that efficiently* outputs a uniformly random isogeny \(\varphi: E \rightarrow E'\) in efficient* representation with domain \(E\) and degree \(N\).
  • State-of-the-art on efficient computation for non-smooth isogeny degrees in general and over \(\mathbb{F}_p\).
  • *This problem is important because of a constructive application, so here 'efficient' is much stronger than above. Polynomial-time and polynomial-size is a must, but we also need concrete efficiency for cryptographic-size primes.
  • A solution to this would remove the need for the FIDIO oracle in SQISign2D-West, strengthening the security claims of the NIST candidate SQISign.

    7. Given a (large) prime \(p\), give an efficient* algorithm to compute a uniformly random supersingular elliptic curve \(E\) over \(\mathbb{F}_{p^2}\) (or \(\mathbb{F}_p\) ) such that \(\text{End}(E)\) remains infeasible* to compute (for anyone, including the person running the algorithm).
  • State-of-the-art on things that don't work.
  • This is sometimes called 'hashing into the isogeny graph'.
  • *The applications of this are constructive, but there are plenty of applications where it would only need to be done once (perhaps modulo some kind of regular renewal). So 'polynomial-time in \(\text{log}(p)\)' is generally sufficient here (within reason, of course polynomials can in principle be arbitrarily large!). 'Remains infeasible' is assuming no significant progress on (2) or (4).

    8. Given a supersingular elliptic curve \(E/\mathbb{F}_{p^2}\), an integer \(N \geq \sqrt{p}\), and a codomain \(E'/\mathbb{F}_{p^2}\) of a uniformly random \(N\)-isogeny \(\varphi: E \rightarrow E'\), find and efficiently compute an isogeny \(E \rightarrow E'\).
  • State-of-the-art. The main application of this problem is cryptanalysis, so any improvement of the state-of-the-art is interesting. A 'complete break' would be an algorithm that is polynomial in \(\text{log}(p)\).
  • Sometimes called 'the fixed degree isogeny problem'.
    8a. As above but \(p \equiv 11 \pmod{12}\) and \(j(E) = 1728\).

    Lattice-based cryptography

    1. Let \(n \in \mathbb{Z}\) and \(R = \mathbb{Z}[x]/(x^{2^n}+1)\). Given a basis of an ideal \(I\) of \(R\), efficiently* compute an element of \(I\) with (close to) the smallest norm.
  • If 'norm' is interpreted as 'Euclidean norm', this is an instantiation of Ideal-SVP. From a number-theoretic perspective it may be easier to consider the usual algebraic norm, which is the same up to a polynomial factor (see Equation 1).
  • *Efficient here means better than the state-of-the-art. The smallest \(n\) being standardized currently is \(n=8\).
  • Attacks on this problem would weaken the security claims of the NIST standards CRYSTALS-Kyber and CRYSTALS-Dilithium, but not actually give an attack.

    2. Let \(p\) be a prime and let \(R = \mathbb{Z}[x]/(x^p+1)\). Given a basis of an ideal \(I\) of \(R\), efficiently* compute an element of \(I\) with (close to) the smallest norm.
  • If 'norm' is interpreted as 'Euclidean norm', this is an instantiation of Ideal-SVP. From a number-theoretic perspective it may be easier to consider the usual algebraic norm, which is the same up to a polynomial factor (see Equation 1).
  • *Efficient here means better than the state-of-the-art. The smallest parameter set being considered for standardization has \(p = 509\).
  • Attacks on this problem would weaken the security claims of the ETSI standards finalist NTRU, but not actually give an attack.

    3. Let \(p\) be a prime and let \(R = \mathbb{Z}[x]/(x^p-x-1)\). Given a basis of an ideal \(I\) of \(R\), efficiently* compute an element of \(I\) with (close to) the smallest norm.
  • If 'norm' is interpreted as 'Euclidean norm', this is an instantiation of Ideal-SVP. From a number-theoretic perspective it may be easier to consider the usual algebraic norm, which is the same up to a polynomial factor (see Equation 1).
  • *Efficient here means better than the state-of-the-art. The smallest parameter set being considered for standardization has \(p = 653\).
  • Attacks on this problem would weaken the security claims of the ETSI standards alternate finalist NTRU Prime, but not actually give an attack.

    4. Let \(R\) be a number ring. Given a basis of an ideal \(I\) of \(R\), efficiently compute an element of \(I\) with (close to) the smallest norm.
  • Constructing examples in which this problem is easy (or easier) and \(R\) has a similar order of magnitude to the above examples would give more insight on the relative hardness of said above 3 problems.

    5. Let \(q\) be a prime power and let \(s \in (\mathbb{Z}/q\mathbb{Z})^n\) be a secret. Given \(A\) sampled uniformly at random from \(\text{Mat}_{m\times n}(\mathbb{Z}/q\mathbb{Z})\) and \(As+(e \pmod{q})\) such that \(e \in \mathbb{Z}^m\) is an error vector of \(m\) independent secret errors sampled according to a fixed probability distribution \(\chi\), (efficiently) compute \(s\).
  • This is the Search-LWE problem and is the hard problem underlying the NIST candidate FrodoKEM.
  • FrodoKEM uses \(q = 2^t\) and the probability distribution \(\chi\) is defined as follows. Let \(\gamma\) be the Gaussian distribution. The errors \(e_j \in \mathbb{Z}\) are all sampled from \([-s,s]\) and the probability \(\chi(i) = \chi(-i)\) of sampling \(i \in [-s,s]\) is given by \(\chi(0) = 2^{\text{len}_{\chi}-1} \cdot \gamma(0) - 1\) and for \(1 \leq z \leq s\), by \(\chi(z) = \chi(0) + 2^{\text{len}_\chi}\sum_{i=1}^z\gamma(i).\) For NIST Levels I, III, and V, the value len\(_\chi = 16\) [FrodoKEM, Table 4].
  • Although this looks wildly different to the above hard problems, something similar to this would solve each of the above shortest vector problems.

    Code-based cryptography

    Watch this space. TODO: add (at least) problems relating to HQC (random quasi-cyclic codes) and Classic McEcliece (Goppa codes).