The problem of finding short vectors in Euclidean lattices is a central hard problem in complexity theory. The case of module lattices (i.e., lattices which are also modules over a number ring) is of particular interest for cryptography and computational number theory. The hardness of finding short vectors in the asymptotic regime where the rank (as a module) is fixed is supporting the security of quantum-resistant cryptographic standards such as ML-DSA and ML-KEM.

Abstract An oriented supersingular elliptic curve is a curve which is enhanced with the information of an endomorphism. Computing the full endomorphism ring of a supersingular elliptic curve is a known hard problem, so one might consider how hard it is to find one such orientation. We prove that access to an oracle which tells if an elliptic curve is $$\mathfrak {O}$$ O -orientable for a fixed imaginary quadratic order $$\mathfrak {O}$$ O provides non-trivial information towards computing an endomorphism corresponding to the $$\mathfrak {O}$$ O -orientation. We provide explicit algorithms and in-depth complexity analysis. We also consider the question in terms of quaternion algebras. We provide algorithms which compute an embedding of a fixed imaginary quadratic order into a maximal order of the quaternion algebra ramified at p and $$\infty $$ ∞ . We provide code implementations in Sagemath (in Stein et al. Sage Mathematics Software (Version 10.0), The Sage Development Team, http://www.sagemath.org , 2023) which is efficient for finding embeddings of imaginary quadratic orders of discriminants up to O(p), even for cryptographically sized p.

We prove that the path-finding problem in isogeny graphs and the endomorphism ring problem for supersingular elliptic curves are equivalent under reductions of polynomial expected time, assuming the generalised Riemann hypothesis. The presumed hardness of these problems is foundational for isogeny-based cryptography. As an essential tool, we develop a rigorous algorithm for the quaternion analog of the path-finding problem, building upon the heuristic method of Kohel, Lauter, Petit and Tignol. This problem, and its (previously heuristic) resolution, are both a powerful cryptanalytic tool and a building-block for cryptosystems. This is an extended abstract of the full article available at http://arxiv.org/abs/2111.01481. This full article will be referred to as “the full version” throughout the text.

In this article, we study the geometry of units and ideals of cyclotomic rings and derive an algorithm to find a mildly short vector in any given cyclotomic ideal lattice in quantum polynomial time, under some plausible number-theoretic assumptions. More precisely, given an ideal lattice of the cyclotomic ring of conductor m , the algorithm finds an approximation of the shortest vector by a factor exp (Õ(√ m )). This result exposes an unexpected hardness gap between these structured lattices and general lattices: The best known polynomial time generic lattice algorithms can only reach an approximation factor exp (Õ(m)). Following a recent series of attacks, these results call into question the hardness of various problems over structured lattices, such as Ideal-SVP and Ring-LWE, upon which relies the security of a number of cryptographic schemes. N OTE . This article is an extended version of a conference paper [11]. The results are generalized to arbitrary cyclotomic fields. In particular, we also extend some results of Reference [10] to arbitrary cyclotomic fields. In addition, we prove the numerical stability of the method of Reference [10]. These extended results appeared in the Ph.D. dissertation of the third author [46].