École Normale Supérieure de Lyon
Habilitation à diriger des recherches
Discipline : Section CNU 25, Mathématiques

RANDOM WALKS IN
NUMBER-THEORETIC CRYPTOLOGY
Benjamin Wesolowski

Rapporteurs :Steven D. Galbraith

Professeur, The University of Auckland, Nouvelle-Zélande

Pierrick Gaudry

Directeur de recherche, CNRS, LORIA, Nancy, France

Hendrik W. Lenstra

Professeur émérite, Universiteit Leiden, Pays-Bas

Soutenance publique le 29 août 2024, devant le jury composé de :Jean-Marc Couveignes

Professeur, Institut de Mathématiques de Bordeaux, France

Pierrick Gaudry

Directeur de recherche, CNRS, LORIA, Nancy, France

Hendrik W. Lenstra

Professeur émérite, Universiteit Leiden, Pays-Bas

Sophie Morel

Directrice de recherche, CNRS, ENS de Lyon, France

Adeline Roux-Langlois

Directrice de recherche, CNRS, GREYC, Caen, France

René Schoof

Professeur, Università di Roma “Tor Vergata”, Italie

ACKNOWLEDGEMENTS
I am deeply grateful to Steven D. Galbraith, Pierrick Gaudry and Hendrik W. Lenstra
who accepted to review this manuscript, and to Jean-Marc Couveignes, Sophie Morel,
Adeline Roux-Langlois and René Schoof who, with Pierrick and Hendrik, have accepted
to form the jury of my habilitation defense.
This manuscript is the product of a decade-long journey in the world of cryptology andnumber theory. That journey certainly owes the most to Arjen K. Lenstra, who hooked
me to this field of research with his course on Algorithms for Public Key Cryptography,
then welcomed me to his Laboratory for Cryptologic Algorithms to pursue a PhD under his
guidance in Lausanne. My gratitude extends to my second PhD advisor, Robert Granger,
who introduced me to one of the most challenging and stimulating problems I ever worked
on, and to Thorsten Kleinjung, who chewed over that problem with me for four years.
The present manuscript is about the après-PhD, which first led me to Amsterdam. I
am deeply grateful to Ronald Cramer for his warm welcome in his team at the Centrum
Wiskunde & Informatica. Having already met a few of its members, I knew what to expect,and I was not disappointed. I wish to thank the entire team for the wonderful year I spent
there. I was lucky to work closely with Léo Ducas, who had a significant impact on myscientific journey, became a friend, and trusted me to co-advise the PhD thesis of Koen
de Boer. I owe no less to Koen, who made this first advising experience a pleasure, andwith whom I have kept collaborating since his resoundingly successful graduation.
I spent the following three years in Bordeaux. I wish to thank Andreas Enge forwelcoming me to the LFANT team and all its members for making it such a stimulating
and friendly place. I am particularly grateful to my collaborators Aurel Page, Alice Pellet–
Mary and Damien Robert, from whom I learned so much. I had already collaborated with
Alice, and her arrival in Bordeaux led to the development of a precious friendship.
My last move brought me back to my birth-town, Lyon. I warmly thank the number
theory team of the École Normale Supérieure de Lyon for welcoming me. The team, theentire laboratory and the support staff offer a wonderful, rich and friendly work environment. I am also grateful to the cryptography people in Lyon, in particular Guillaume
Hanrot and Damien Stehlé for their sustained support and advice.
I wish to thank all the interns and students I have had the chance to advise, inparticular my two current PhD students, Pierrick Dartois and Arthur Herlédan Le Merdy.
This journey was filled with too many invaluable encounters for these meagre paragraphs to do them all justice: all my coauthors, colleagues, advisors, advisees, support
staff, host institutions, the CNRS, the IACR... Thank you all! To wrap it up, a special
mention goes to Cécile Pierrot, one of the first friends I made in the community.
Et finalement, un grand merci à mes amis, à ma famille, et à Benjamin (pas moi).

ABSTRACTThis habilitation thesis presents a selection of the author’s contributions at the intersectionof computational number theory and cryptography. Its main focus is on the mathematicalfoundations of isogeny-based and lattice-based cryptography.

CONTENTS
Acknowledgements

3

Abstract

5

Introduction
9
Notation and terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
Chapter 1. Supersingular isogenies and endomorphisms
19
1.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.2. Random walks in isogeny graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.3. The `-Isogeny Path and Endomorphism Ring problems . . . . . . . . . . . . . . . . . . . . . 28
1.4. Finding one endomorphism is as hard as finding them all . . . . . . . . . . . . . . . . . . . 32
1.5. The fall of SIDH. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
1.6. The development of SQIsign . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
Chapter 2. Oriented elliptic curves
2.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2. Oriented elliptic curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3. Orientations and the supersingular endomorphism ring problem . . . . . . . . . . . . .
2.4. The supersingular endomorphism ring problem given one endomorphism . . . .
2.5. Knowing the structure of the acting group . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

45
45
48
52
55
59

Chapter 3. Ideal lattices
3.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2. Ideal lattices and the Arakelov class group . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3. Random walks in Arakelov class groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4. Average hardness of ideal lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.5. A rigorous tool for algorithmic number theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

63
63
66
69
72
76

Bibliography83

INTRODUCTION
Cryptography met number theory in 1976, when Diffie and Hellman [DH76] achieved what
had long been considered impossible: a protocol for two people to exchange secret information on a public channel, even if they had never met before to establish some kind ofpassword, a pre-shared key. Diffie and Hellman designed the protocol such that a spy attempting to find the secret would need to solve a presumably hard computational problem:the discrete logarithm problem in the multiplicative group of a finite field.
This protocol is the first public key cryptosystem. In public key cryptography, eachparty has a pair of keys: a public key and a private key. The security of a cryptosystem
is formalised by computational problems such as: given a public key, can one recover apaired private key? Proving the security consists in proving that these problems are hard,
or at least as hard as some other well-studied problems. Cryptography requires hard andversatile computational problems. Number theory provides such problems, together witha powerful toolset for their analysis. The vast majority of deployed cryptosystems relyon the presumed hardness of the discrete logarithm problem, and the integer factorisation
problem. Decades of cryptanalysis forged our confidence in these classical foundations.
In 1994, Shor [Sho97] discovered a quantum algorithm of polynomial complexity solving both of these problems, threatening all deployed public-key cryptography. Research on
quantum technology is accelerating, and the threat is seriously considered by the cryptographic community, which has strived to develop schemes that resist quantum algorithms:
post-quantum cryptography. Emerging post-quantum candidates build their foundations
on a handful of computational problems rooted in arithmetic and geometry, and this manuscript explores two of them: isogeny-based cryptography, and lattice-based cryptography.
What to expect from this manuscript. This habilitation thesis is written as part of myapplication for the Habilitation à Diriger des Recherches. As such, its primary purposeis the exposition of a representative selection of the research I have conducted since theobtention of my PhD diploma in 2018. It is not an exhaustive account of my work, but
an organized selection of interconnected topics: random walks and elliptic curves, elliptic
curves and ideals, ideals and random walks.
Selected results are not presented in exhaustive mathematical detail. Instead, themanuscript focuses on context and motivation, explains the main theorems and ideas, andonly hints at the proofs and techniques deployed. When relevant, results beyond my own
contributions are discussed to leave the reader with a good overview of the current stateof the field — this document is thereby a biased survey on selected topics. For clarity,references of which I am a coauthor are indicated with double brackets, as [[KW22]], whileother references have simple brackets, as [Piz90].

10

INTRODUCTION

The three chapters of this thesis concern three different objects arising in post-quantum
cryptography: supersingular isogeny graphs, oriented elliptic curves, and ideal lattices.
Chapter 1: Supersingular isogenies and endomorphisms. Elliptic curves have longplayed a role in cryptography, as a platform for the discrete logarithm problem. They
have kept a central place in post-quantum cryptography thanks to the emergence of newcomputational problems resisting quantum algorithms: isogeny problems. An isogeny isa map connecting two elliptic curves. An isogeny problem is a computational problemof this form: given two elliptic curves, find an isogeny between them. Most of isogenybased cryptography is based on the presumed hardness of the “supersingular” isogeny
problem and on a network of variants. In Chapter 1, we study these problems and theirapplications, and the central role of random walks in so-called supersingular isogeny graphs.
It is organised around the following contributions.
• In the article [[Wes21]], we solidify the foundations of the field by proving that twoof its most emblematic problems are in fact equivalent (assuming the Generalized
Riemann Hypothesis): the supersingular isogeny path problem, and the endomorphism ring problem. The first is the path-finding problem in the so-calledsupersingular isogeny graph. The second is the problem of finding all endomorphisms (i.e., isogenies to itself) of a supersingular elliptic curve.
• In the article [[PW24]], we prove that the endomorphism ring problem is equivalent
to the problem of finding one single (non-trivial) endomorphism. This so-called
one endomorphism problem supports the security of several cryptosystems. This
new connection immediately extends the web of equivalent problems supporting
isogeny-based cryptography, leads to better algorithms for their resolution, andunlocks new security proofs. Our main tool is a new equidistribution theorem for
random walks in a versatile generalization of isogeny graphs.
• One important problem resisted unification with the others: the computational
problem supporting the security of the SIDH cryptosystem [JD11]. In a spectacular turn of events, this variant proved easy and SIDH was broken in 2022
in the series of articles [CD23], [[MMP+ 23]] and [Rob23]. We recount this downfall,carefully delineating our own contribution through [[Wes22b, MMP+ 23]].
• In [[DKL+ 20]], we introduce SQIsign, a digital signature scheme whose development
is intertwined with all previously mentioned results. The latest version, called
SQIsignHD [[DLRW24]], makes constructive use of the new tools which broke SIDH,
and its security lies firmly on the hardest problems of the field. The developmentof SQIsign and its “HD” aspects is the topic of the thesis of my PhD student
Pierrick Dartois, coauthor of SQIsignHD [[DLRW24]], SQIsign2D [[BDD+ 24]], andalgorithms for evaluating isogenies in higher dimension [DMPR23].
The following is a complete list of my articles related to supersingular isogeny graphs
and their applications in cryptography.
[[BDD+ 24]]

Andrea Basso, Luca De Feo, Pierrick Dartois, Antonin Leroux, Luciano Maino, Giacomo Pope, Damien Robert, and Benjamin Wesolowski.
SQIsign2D-West: The Fast, the Small, and the Safer. Cryptology ePrint
Archive, Paper 2024/760, 2024. https://eprint.iacr.org/2024/760.

[[PW24]]

Aurel Page and Benjamin Wesolowski. The supersingular endomorphismring and one endomorphism problems are equivalent. To appear in Advancesin Cryptology – EUROCRYPT 2024, 2024.

INTRODUCTION

11[[DLRW24]]

Pierrick Dartois, Antonin Leroux, Damien Robert, and Benjamin
Wesolowski. SQISignHD: new dimensions in cryptography. To appear in
Advances in Cryptology – EUROCRYPT 2024, 2024.

[[MMP+ 23]]

Luciano Maino, Chloe Martindale, Lorenz Panny, Giacomo Pope, andBenjamin Wesolowski. A direct key recovery attack on SIDH. In Carmit
Hazay and Martijn Stam, editors, Advances in Cryptology – EUROCRYPT
2023, volume 14008 of Lecture Notes in Computer Science, pages 448–471.
Springer, 2023.

[[BCC+ 23]]

Andrea Basso, Giulio Codogni, Deirdre Connolly, Luca De Feo, Tako Boris
Fouotsa, Guido Maria Lido, Travis Morrison, Lorenz Panny, Sikhar Patranabis, and Benjamin Wesolowski. Supersingular curves you can trust. In
Carmit Hazay and Martijn Stam, editors, Advances in Cryptology – EUROCRYPT 2023, volume 14005 of Lecture Notes in Computer Science, pages
405–437. Springer, 2023.

[[DLLW23]]

Luca De Feo, Antonin Leroux, Patrick Longa, and Benjamin Wesolowski.
New algorithms for the Deuring correspondence - towards practical andsecure SQISign signatures. In Carmit Hazay and Martijn Stam, editors,
Advances in Cryptology – EUROCRYPT 2023, volume 14008 of Lecture
Notes in Computer Science, pages 659–690. Springer, 2023.

[[Wes22b]]

Benjamin Wesolowski. Understanding and improving the Castryck–Decru
attack on SIDH. Archive ouverte HAL, Report hal-04557845, 2022. https://hal.science/hal-04557845.

[[Wes21]]

Benjamin Wesolowski. The supersingular isogeny path and endomorphismring problems are equivalent. In 62nd IEEE Annual Symposium on Foundations of Computer Science – FOCS 2021, pages 1100–1111. IEEE, 2021.

[[DKL+ 20]]

Luca De Feo, David Kohel, Antonin Leroux, Christophe Petit, andBenjamin Wesolowski. SQISign: Compact post-quantum signatures fromquaternions and isogenies. In Shiho Moriai and Huaxiong Wang, editors,
Advances in Cryptology – ASIACRYPT 2020, volume 12491 of Lecture
Notes in Computer Science, pages 64–93. Springer, 2020.

[[DDF+ 21]]

Luca De Feo, Cyprien Delpech de Saint Guilhem, Tako Boris Fouotsa,
Péter Kutas, Antonin Leroux, Christophe Petit, Javier Silva, and Benjamin Wesolowski. Séta: Supersingular encryption from torsion attacks. In
Mehdi Tibouchi and Huaxiong Wang, editors, Advances in Cryptology –ASIACRYPT 2021, volume 13093 of Lecture Notes in Computer Science,
pages 249–278. Springer, 2021.

[[GW17]]Alexandre Gélin and Benjamin Wesolowski. Loop-abort faults on supersingular isogeny cryptosystems. In Tanja Lange and Tsuyoshi Takagi, editors,
International Workshop on Post-Quantum Cryptography – PQCrypto 2017,
pages 93–106. Springer, 2017.

Chapter 2: Oriented elliptic curves. The discrete logarithm problem is a special
case of the group action inversion problem. While Shor’s algorithm solves the former,
the general case still resists quantum algorithms. The Diffie–Hellman protocol (and muchof the vast array of “discrete logarithm”-based cryptosystems which followed) can be

12

INTRODUCTION

brought to the post-quantum world by replacing discrete logarithms with an appropriate“hard to invert” group action. The classical theory of complex multiplication induces anaction of an ideal class group on a collection of elliptic curves. Exploiting this action
in cryptosystems presented significant challenges, until supersingular elliptic curves wereconsidered [CLM+ 18]. Complex multiplication is typically associated to ordinary (i.e., nonsupersingular) elliptic curves. The notion of oriented elliptic curve generalizes the methodsof complex multiplication to the supersingular case. In Chapter 2, we study oriented
elliptic curves and their applications in cryptography. It is organised around the following
contributions.
• While this “group action” branch of isogeny-based cryptography looks substantially different from the “isogeny path and endomorphism ring” problems discussed in Chapter 1, we prove in the article [[Wes22a]] that the group action
inversion problem is still equivalent to the problem of computing endomorphism
rings (but now, for oriented elliptic curves). This result further reinforces thefoundational status of the endomorphism ring problem: its presumed hardness
also governs the security of the “group action” branch of the field.
• In the article [[HW23]], with my PhD student Arthur Herlédan Le Merdy, we study
the concrete hardness of the “oriented” endomorphism ring problem, describing
and analysing the fastest classical and quantum algorithms. In the process, we
prove that the complexities claimed by the previous best heuristic algorithms
for the group action inversion problem can actually be achieved assuming theGeneralised Riemann Hypothesis. In addition, we obtain the first polynomial
time algorithm for the problem of turning an arbitrary orientation into a primitiveorientation (a kind of “best possible” orientation).
• In the article [[DFK+ 23]], we introduce SCALLOP. The group acting on supersingular curves is an ideal class group. Class groups are generally hard to compute,and that has been a source of difficulty in the design of cryptosystems. SCALLOP offers a framework to define a hard-to-invert action by an easy-to-computeclass group. This brings this group action one step closer to the capabilitiesof the discrete logarithm paradigm, while preserving its claim for post-quantum
security.

The following is a complete list of my articles related to the notion of oriented elliptic
curves and their applications in cryptography.
[[HW23]]

Arthur Herlédan Le Merdy and Benjamin Wesolowski. The supersingularendomorphism ring problem given one endomorphism. Cryptology ePrint
Archive, Paper 2023/1448, 2023. https://eprint.iacr.org/2023/1448.

[[ACD+ 23]]

Sarah Arpin, James Clements, Pierrick Dartois, Jonathan Komada Eriksen,
Péter Kutas, and Benjamin Wesolowski. Finding orientations of supersingular elliptic curves and quaternion orders. Cryptology ePrint Archive, Paper
2023/1268, 2023. https://eprint.iacr.org/2023/1268.

[[DFK+ 23]]

Luca De Feo, Tako Boris Fouotsa, Péter Kutas, Antonin Leroux, SimonPhilipp Merz, Lorenz Panny, and Benjamin Wesolowski. SCALLOP: scaling
the CSI-FiSh. In Alexandra Boldyreva and Vladimir Kolesnikov, editors,
Public-Key Cryptography – PKC 2023, volume 13940 of Lecture Notes in
Computer Science, pages 345–375. Springer, 2023.

INTRODUCTION

13[[CHVW22]]

Wouter Castryck, Marc Houben, Frederik Vercauteren, and Benjamin
Wesolowski. On the decisional Diffie-Hellman problem for class group actions on oriented elliptic curves. Research in Number Theory, 8(4):99, 2022.
Proceedings of the Fifteenth Algorithmic Number Theory Symposium –ANTS-XV.

[[Wes22a]]

Benjamin Wesolowski. Orientations and the supersingular endomorphismring problem. In Orr Dunkelman and Stefan Dziembowski, editors, Advances in Cryptology – EUROCRYPT 2022, volume 13277 of Lecture Notes
in Computer Science, pages 345–371. Springer, 2022.

Chapter 3: Ideal lattices. A lattice is a discrete subgroup in a Euclidean vector space.
The problem of finding a shortest non-zero vector in a lattice (the shortest vector problem,
or SVP) is a central hard problem in complexity theory, and the heart of lattice-based
cryptography. Lattices appear naturally in algebraic number theory: the ring of integers
of a number field is a lattice, and so is any (fractional) ideal. These ideal lattices havea special place in computational number theory, and provide a powerful playground for
cryptography, via the corresponding Id-SVP problem. In Chapter 3, we study ideal lattices through the development and application of a new tool: random walks in the spaceof ideal lattices. It is organized around the following contributions.
• In the article [[BDPW20]], we describe random walks in the Arakelov class group, andprove their rapid-equidistribution properties (assuming the Generalized RiemannHypothesis). The Arakelov class group is essentially the space of ideal lattices up
to isometry. As a first application of this new randomization tool, we prove that
Id-SVP is hard on average for uniformly random ideal lattices (with respect tothe Haar measure): if there exist hard instances of Id-SVP, then it is hard for
random ideal lattices. Average hardness is of primary interest for cryptographic
applications. These random walks are the main topic of the PhD thesis of Koen deBoer, coauthor of [[BDPW20]] and [[BPW24]]. His thesis, of which I was co-promotor,
was successfully defended in 2022.
• Average hardness is defined with respect to a distribution on instances (here,
ideal lattices), and while uniformity for the Haar measure is mathematically themost natural candidate, it is not the best suited for applications. In the article [[FPSW23]], we prove that Id-SVP is hard on average for uniformly random
prime ideals of bounded norm. This distribution is well-suited, for instance, forapplication to the NTRU cryptosystem.
• In the article [[BPW24]], we solve a recurring problem in computational number
theory: sampling ideals in a given class, with a prescribed property (smooth,near-prime...). While it is easy to design a heuristic algorithm for this task
(i.e., relying on unproven ad hoc assumptions), we provide the first rigorous
method, under the Generalized Riemann Hypothesis. To illustrate the power ofthis technique, we describe the first rigorous subexponential time algorithm forsome of the most emblematic problems of the domain: computing class groups
and unit groups of arbitrary number fields. Previous rigorous algorithms wererestricted to quadratic fields.
The following is a complete list of my articles related to the notion of ideal lattices
and their applications in cryptography and computational number theory.

14

INTRODUCTION[[BPW24]]

Koen de Boer, Alice Pellet-Mary, and Benjamin Wesolowski. Rigorous
methods for computational number theory. Preprint available on demand,
2024.

[[FPSW23]]Joël Felderhoff, Alice Pellet-Mary, Damien Stehlé, and Benjamin
Wesolowski. Ideal-SVP is hard for small-norm uniform prime ideals. In
Guy N. Rothblum and Hoeteck Wee, editors, Theory of Cryptography –21st International Conference, TCC 2023, volume 14372 of Lecture Notes
in Computer Science, pages 63–92. Springer, 2023.

[[CDW21]]

Ronald Cramer, Léo Ducas, and Benjamin Wesolowski. Mildly short vectors
in cyclotomic ideal lattices in quantum polynomial time. Journal of theACM, 68(2):8:1–8:26, 2021.

[[BDPW20]]

Koen de Boer, Léo Ducas, Alice Pellet-Mary, and Benjamin Wesolowski.
Random self-reducibility of Ideal-SVP via Arakelov random walks. In
Daniele Micciancio and Thomas Ristenpart, editors, Advances in Cryptology – CRYPTO 2020, volume 12171 of Lecture Notes in Computer Science,
pages 243–273. Springer, 2020.

[[DPW19]]

Léo Ducas, Maxime Plançon, and Benjamin Wesolowski. On the shortnessof vectors to be found by the Ideal-SVP quantum algorithm. In Alexandra Boldyreva and Daniele Micciancio, editors, Advances in Cryptology –CRYPTO 2019, volume 11692 of Lecture Notes in Computer Science, pages
322–351. Springer, 2019.

[[CDW17]]

Ronald Cramer, Léo Ducas, and Benjamin Wesolowski. Short Stickelberger
class relations and application to Ideal-SVP. In Jean-Sébastien Coron andJesper Buus Nielsen, editors, Advances in Cryptology – EUROCRYPT
2017, volume 10210 of Lecture Notes in Computer Science, pages 324–348.
Springer, 2017.

Other articles. The following is a complete list of my articles on themes not covered inthis manuscript.

Discrete logarithms in finite fields. The following articles concern the problem of computing discrete logarithms in finite fields. We prove in [[KW22]] that they can be computed inquasi-polynomial time in finite fields of small characteristic. This result improves upon thesubexponential complexity proved by Pomerance in 1987 [Pom87]. The quasi-polynomial
complexity had been conjectured to be reachable since [BGJT14], where a first heuristic
algorithm was proposed. We illustrate the power of the method with the record computation of a 30750-bit discrete logarithm in [[GKL+ 21]].
[[KW22]]Thorsten Kleinjung and Benjamin Wesolowski. Discrete logarithms inquasi-polynomial time in finite fields of fixed characteristic. Journal of theAmerican Mathematical Society, 35(2):581–624, 2022.

[[GKL+ 21]]

Robert Granger, Thorsten Kleinjung, Arjen K. Lenstra, Benjamin
Wesolowski, and Jens Zumbrägel. Computation of a 30750-bit binary field
discrete logarithm. Mathematics of Computation, 90(332):2997–3022, 2021.

INTRODUCTION[[KW19]]15

Thorsten Kleinjung and Benjamin Wesolowski. A new perspective on the
powers of two descent for discrete logarithms in finite fields. In Proceedingsof the Thirteenth Algorithmic Number Theory Symposium – ANTS-XIII,
volume 2, pages 343–352. The Open Book Series, Mathematical Sciences
Publishers, 2019.

Isogenies between Drinfeld modules. The following article proves that one can computeisogenies in polynomial time between Drinfeld modules over finite fields. This breaks
Drinfeld analogs of isogeny-based cryptosystems [LS22]. Former attempts had exponential complexity [JN19, CGS20].
[[Wes24]]

Benjamin Wesolowski. Computing isogenies between finite Drinfeld modules. To appear in IACR Communications in Cryptology, 2024.

Isogeny graphs of ordinary abelian varieties. The following articles concern the graphs
formed by isogenies between ordinary abelian varieties in higher dimension.
[[JW19]]Dimitar Jetchev and Benjamin Wesolowski. Horizontal isogeny graphs ofordinary abelian varieties and the discrete logarithm problem. Acta Arithmetica, 187:381–404, 2019.

[[Wes19b]]

Benjamin Wesolowski. Generating subgroups of ray class groups with small
prime ideals. In Proceedings of the Thirteenth Algorithmic Number Theory
Symposium – ANTS-XIII, volume 2, pages 461–478. The Open Book Series,
Mathematical Sciences Publishers, 2019.

[[BJW17]]

Ernest Hunter Brooks, Dimitar Jetchev, and Benjamin Wesolowski. Isogeny
graphs of ordinary abelian varieties. Research in Number Theory, 3(1):28,
2017.

Verifiable delay functions and randomness. The following articles concern verifiable delay
functions and the generation of random numbers. In [[LW17]], we describe the first scalable
protocol for the public and trustworthy generation of random numbers, using a new slowtimed hash function. This notion of slow hash function was formalised and generalised asa verifiable delay function (VDF) in [BBBF18]. In [[Wes19a]], we construct the first practical
VDF.
[[BFH+ 24]]

Alex Biryukov, Ben Fisch, Gottfried Herold, Dmitry Khovratovich, Gaëtan
Leurent, María Naya-Plasencia, and Benjamin Wesolowski. Cryptanalysisof algebraic verifiable delay functions. To appear in Advances in Cryptology– CRYPTO 2024, 2024.

[[BKSW23]]

Karim Belabas, Thorsten Kleinjung, Antonio Sanso, and Benjamin
Wesolowski. A note on the low order assumption in class group of an imaginary quadratic number fields. Mathematical Cryptology, 3:44–51, Jul. 2023.

[[WW20]]Ryan Williams and Benjamin Wesolowski. Lower bounds for the depth ofmodular squaring. IACR Cryptology ePrint Archive, Report 2020/1461,
2020. https://eprint.iacr.org/2020/1461.

[[Wes20]]

Benjamin Wesolowski. Efficient verifiable delay functions. Journal of Cryptology, 33(4):2113–2147, 2020.

16

INTRODUCTION[[Wes19a]]

Benjamin Wesolowski. Efficient verifiable delay functions. In Yuval Ishai
and Vincent Rijmen, editors, Advances in Cryptology – EUROCRYPT
2019, volume 11478 of Lecture Notes in Computer Science, pages 379–407.
Springer, 2019.

[[PW18]]

Cécile Pierrot and Benjamin Wesolowski. Malleability of the blockchain’s
entropy. Cryptography and Communications, 10(1):211–233, 2018.

[[LW17]]

Arjen K. Lenstra and Benjamin Wesolowski. Trustworthy public randomness with sloth, unicorn, and trx. International Journal of Applied Cryptography, 3(4):330–343, 2017.

Broadcast encryption. In the following article, we design a new attribute-based broadcast
encryption scheme with small keys.
[[WJ15]]

Benjamin Wesolowski and Pascal Junod. Ciphertext-policy attribute-based
broadcast encryption with small keys. In Soonhak Kwon and Aaram Yun,editors, Information Security and Cryptology – ICISC 2015, volume 9558
of Lecture Notes in Computer Science, pages 53–68. Springer, 2015.
Notation and terminology

Rings and fields. We write Z, Q, R, C and Fq for the ring of integers, the fields of rational,
real and complex numbers, and a finite field with q elements. For any field K, we write
K for an algebraic closure. For any ring R, we write R× for the multiplicative group of
invertible elements.
Complexities. We write f = O(g) for the classic big O notation. We use the soft-O
notation Õ(g) = log(g)O(1) · O(g), and the polynomial growth notation poly(f1 , . . . , fn ) =(f1 + · · · + fn )O(1) . We use the classical L-notation for subexponential growthLx (α) = exp O(log x)α (log log x)1−α .
The logarithm function log is in base 2.
Sets and probabilities. For any set S, we write #S for its cardinality. If D is a probability distribution, we write x ← D to signify that x is a random variable sampled with
distribution D. If S is a finite set, we also write x ← S for x uniformly distributed in S.
The Generalized Riemann Hypothesis. Several of the results presented in this manuscript are conditional under the Riemann Hypothesis for Hecke L-functions, which we willrefer to as the Generalized Riemann Hypothesis (abbreviated GRH). When needed, thisassumption is explicitly mentioned in the statement. Note that the proof of such results
do not use GRH in its original form, but rely on some of its established consequences,such as the effective Chebotarev density theorem of Lagarias and Odlyzko [LMO79].
The “heuristic” terminology. The meaning of “heuristic” in computational number
theory differs from other areas of computer science. Let us clarify this terminology. In
computational number theory (and in the present manuscript) an algorithm is said to beheuristic if it is believed to work, but its analysis relies on unproven ad hoc assumptions.
For instance, an algorithm may craft an integer, and one expects this integer to “behave”
like a uniformly random integer of a certain size; we can then deduce the probabilityof certain events, like it being prime. It is often hard to prove such a behavior, but

NOTATION AND TERMINOLOGY17

its assumption unlocks the analysis of the algorithm. The underlying assumption, theheuristic assumption, may be supported by experiments and intuition.
We make an informal distinction between heuristic assumptions and standard numbertheoretic conjectures (like the Generalized Riemann Hypothesis). Heuristic assumptions
are generally ad hoc, highly dependent on the situation, and are often in the spirit of:“at this point in the algorithm, all goes well”. Sometimes, a heuristic assumption is notexpected to be literally true: in the above example, the integer may not be uniformly
distributed, and one only expects it to “behave uniformly”.
A few contributions presented in this manuscript consist in turning a heuristic result
into a rigorous result. This means that a heuristic algorithm already existed, and we
provide a fully rigorous algorithm (either unconditional or subject to GRH).

1
Supersingular isogenies and endomorphisms
In this chapter, we present contributions related to the computational problem of finding
isogenies between supersingular elliptic curves and its applications in cryptography. We
explore connections between this problem, random walks in isogeny graphs, the problem
of computing endomorphisms of elliptic curves, and the power of higher dimensional isogenies. We conclude this chapter by presenting the SQIsign digital signature scheme, which
has benefited from all these advances from its original design to its latest improvements.
This chapter is built around the presentation of the articles (in order of appearance):[[PW24]]

Aurel Page and Benjamin Wesolowski. The supersingular endomorphismring and one endomorphism problems are equivalent. To appear in Advancesin Cryptology – EUROCRYPT 2024, 2024.

[[Wes21]]

Benjamin Wesolowski. The supersingular isogeny path and endomorphismring problems are equivalent. In 62nd IEEE Annual Symposium on Foundations of Computer Science – FOCS 2021, pages 1100–1111. IEEE, 2021.

[[MMP+ 23]]

Luciano Maino, Chloe Martindale, Lorenz Panny, Giacomo Pope, andBenjamin Wesolowski. A direct key recovery attack on SIDH. In Carmit
Hazay and Martijn Stam, editors, Advances in Cryptology – EUROCRYPT
2023, volume 14008 of Lecture Notes in Computer Science, pages 448–471.
Springer, 2023.

[[DKL+ 20]]

Luca De Feo, David Kohel, Antonin Leroux, Christophe Petit, andBenjamin Wesolowski. SQISign: Compact post-quantum signatures fromquaternions and isogenies. In Shiho Moriai and Huaxiong Wang, editors,
Advances in Cryptology – ASIACRYPT 2020, volume 12491 of Lecture
Notes in Computer Science, pages 64–93. Springer, 2020.

[[DLRW24]]

Pierrick Dartois, Antonin Leroux, Damien Robert, and Benjamin
Wesolowski. SQISignHD: new dimensions in cryptography. To appear in
Advances in Cryptology – EUROCRYPT 2024, 2024.

20

1. SUPERSINGULAR ISOGENIES AND ENDOMORPHISMS

1.1. Introduction
Given a field k of characteristic p > 3, and two parameters A, B ∈ k with 4A3 + 27B 2 6= 0,
the equationy 2 = x3 + Ax + B
defines a so-called elliptic curve over k. Elliptic curves can be more abstractly defined
as abelian varieties of dimension 1, and the equation y 2 = x3 + Ax + B is merely ashort Weierstrass model of the elliptic curve. Given an elliptic curve E, its set E(k) of
k-rational points consists of the pairs (x, y) ∈ k 2 satisfying the curve equation, together
with an extra point 0E “at infinity” (a projective solution of the equation). They naturally
form an abelian group, written additively, where 0E is the neutral element.
Elliptic curves have long had a central place in cryptography, since Miller [Mil86]
and Koblitz [Kob87] proposed in 1986 to run the Diffie–Hellman key exchange protocol [DH76] over elliptic curves. In a world where large-scale quantum computers would
become available, Shor’s algorithm [Sho97] would render the Diffie–Hellman protocol obsolete, with or without elliptic curves. Yet, in the quest for post-quantum cryptography,
elliptic curves have kept a central place thanks to the emergence of new computational
problems that seem to resist quantum algorithms: isogeny problems. The first isogenybased cryptosystems were proposed by Couveignes in 1997 [Cou06]. This work was only
made public in 2006, when the idea reemerged in [RS06]. Supersingular elliptic curves
appeared to be particularly well suited for the design of post-quantum cryptosystems,
starting with the CGL hash function [CLG09], followed by the SIDH key exchange [JD11].
A wealth of other public-key protocols [CLM+ 18, DKPS19, Cos20, BMP23], [[DFK+ 23]], signature schemes [YAJ+ 17, DG19, BKV19, GPS20], [[DKL+ 20, DLRW24]] and other cryptosystems [DMPS19, BKW20] have since been proposed, built on the presumed hardness of isogeny
problems.
Let E1 and E2 be two elliptic curves defined over k. An isogeny ϕ : E1 → E2 is
a non-constant rational map (i.e., coordinates of the output are given by fractions ofpolynomials in the input coordinates) that sends 0E1 to 0E2 . This rather simple definition
automatically implies strong properties: an isogeny is a group homomorphism from E1 (k)to E2 (k), and its kernel over the algebraic closure, written ker(ϕ), is finite. This notion
naturally leads to a computational problem.
Problem 1.1 (The isogeny problem, informally). Given two elliptic curves E1 and E2
over a finite field, find, if it exists, an isogeny ϕ : E1 → E2 .
Versions of this problem are believed to be hard, and isogeny-based cryptography
leverages this hardness. This problem is most often considered for so-called supersingularelliptic curves. Then, a solution is guaranteed to exist (two supersingular elliptic curves
over the same field are always connected by an isogeny), and the isogeny problem appears
to be at its hardest for such curves. Almost all isogeny-based cryptography considers
supersingular elliptic curves.
To formally define an isogeny problem, one must specify what it means to “find an
isogeny”. Encoding an isogeny is not a straightforward task. It has rapidly appeared
convenient to consider isogenies formed as compositions of simple building-blocks. An`-isogeny, for ` a small prime, is such a family of simple, easy-to-work-with isogenies. An`-isogeny path is a composition of `-isogenies. Here is another motivation to work withsupersingular elliptic curves: any pair is connected by an `-isogeny path (whatever `,including the typical choice ` = 2). This leads to the first fully-specified version of theisogeny problem: the supersingular `-isogeny path problem.

1.1. INTRODUCTION

21

Problem 1.2 (`-IsogenyPath). Given a prime p, and two supersingular elliptic curves
E1 and E2 over Fp2 , find an `-isogeny path from E1 to E2 .
This problem was first considered in [CLG09], and has since assumed a foundationalrole in isogeny-based cryptography, raising questions such as:• How hard is the `-IsogenyPath problem? How efficient are the best algorithms?
Is it the hardest of its kind?
• What kind of cryptosystems can be built from it? Can it, or variants, be used toprove the security, or to attack schemes?
A large part of the work towards answering these questions consists in defining and analyzing related problems: some that may be easier to study, or easier to connect to cryptosystems. Here are a few such problems of central interest:• EndRing: given a supersingular elliptic curve E, compute its endomorphismring End(E). An endomorphism is an isogeny from the curve to itself (or thezero-morphism). This problem has been studied as early as [Koh96], originallymotivated by the importance of these structures in arithmetic geometry.
• OneEnd: given a supersingular elliptic curve, find one non-scalar endomorphism.
This is a straightforward simplification of EndRing: instead of finding all endomorphisms, can one find even a single one? This problem naturally emerges incryptosystems: it supports the collision-resistance of [CLG09] or the soundness of
SQIsign [[DKL+ 20]].
• Isogeny: given two supersingular elliptic curves, find an isogeny between them,in any form that allows to efficiently evaluate it on points. This is perhaps themost natural form of the isogeny problem, as, contrary to `-IsogenyPath, thesolution is not restricted to special kinds of isogenies.
• Interpolation: given two supersingular elliptic curves, and the images of a few
points through an unknown isogeny, find the isogeny. This version of the isogeny
problem supports the SIDH key exchange protocol [JD11].
In this chapter, we study these problems. We connect them to one another, study thebest algorithms for their resolution, and how to build cryptosystems from their presumed
hardness.
1.1.1. Contributions and organisation of the chapter. The chapter is organized asfollows.
Random walks in isogeny graphs. In Section 1.2, we define `-isogeny graphs, whose vertices
are elliptic curves, and edges represent `-isogenies between them. The `-IsogenyPath
problem is the pathfinding problem in these graphs. Pizer proved in [Piz90] that they
are Ramanujan graphs: an optimal form of expander graphs, where random walks rapidly
converge to the uniform distribution. This is a key property for cryptographic applications
and for the analysis of `-IsogenyPath and its friends. We illustrate this fact with a few
simple examples.
We then present isogeny graphs of “higher level” as defined and analysed in ourwork [[PW24]]. It is often useful to consider some additional structure attached to theelliptic curves. The vertices of the graph, instead of being curves, could be pairs (E, P )where P ∈ E is a point, or (E, α) where α ∈ End(E)/N End(E) (for some integer N ).
Edges would be isogenies that preserve this additional structure. In the article [[PW24]], we
introduce a general framework for such graphs, and prove that, like in the classical case,random walks equidistribute optimally.

22

1. SUPERSINGULAR ISOGENIES AND ENDOMORPHISMS

The `-Isogeny Path and Endomorphism Ring problems. It was soon identified that the
problems `-IsogenyPath and EndRing are closely related, and heuristic computational
reductions between them were described in [EHL+ 18]. In [[Wes21]], we prove that these two
problems are indeed equivalent, assuming the Generalised Riemann Hypothesis (GRH).
As in [EHL+ 18], this is done by passing through a third equivalent problem: MaxOrder.
We present these results in Section 1.3.
Finding one endomorphism is as hard as finding them all. In Section 1.4, we present themain result of [[PW24]]: the EndRing and OneEnd problems are equivalent. In otherwords, finding one endomorphism of a supersingular elliptic curve is as hard as finding
them all. We sketch the reduction, which makes critical use of the equidistribution for
random walks in higher isogeny graphs discussed in Section 1.2.
We then present a number of consequences. First, assuming the hardness of EndRing,
the Charles–Goren–Lauter hash function [CLG09] is collision-resistant. Second, EndRing
is equivalent to Isogeny. Third, there exists an unconditional probabilistic algorithm tosolve EndRing in time Õ(p1/2 ), a result which previously required to assume GRH.
The fall of SIDH. Supersingular Isogeny Diffie-Hellman (or SIDH [JD11]) is a key exchange
protocol proposed in 2011 by Jao and De Feo. It has been among the most popular isogenybased schemes, and the first key exchange using supersingular elliptic curves. However,its security relies not on the `-IsogenyPath problem, but on its cousin Interpolation:
given two elliptic curves and images of a few points through some unknown isogeny, findthe isogeny. Of course, there is a spectrum of hardness for this problem, depending on
the order of the group generated by the revealed points. Revealing too many points was
known to be dangerous, but SIDH has long been believed to be in a secure regime.
In Section 1.5, we recount the earthquake that struck isogeny-based cryptography in2022, when the series of work [CD23], [[MMP+ 23]] and [Rob23] solved the Interpolation
problem in an unforeseen level of generality. In particular, SIDH is now completely broken.
While carefully delineating our own contribution through [[Wes22b, MMP+ 23]], we present
the result in a greater level of generality to include the final nail hammered by Robert[Rob23].
SQIsign: signing with isogenies. In Section 1.6, we present the digital signature scheme
SQIsign. We introduced this scheme in [[DKL+ 20]], improved it in [[DLLW23]], and redesigned
it in SQIsignHD [[DLRW24]]. SQIsign is currently submitted to the NIST call for standardisation of post-quantum digital signature schemes. It boasts the smallest public keys andsignatures combined of today’s post-quantum portfolio.
We describe the general structure of SQIsign, with a focus on the variant SQIsignHD,
which makes constructive use of the recent advances on the Interpolation problem
discussed in Section 1.5.
1.1.2. Preliminaries on isogenies. In this section, we briefly review some of the mostimportant properties of isogenies required in the rest of the text. We refer the reader
to [Sil86] for a detailed account of the theory of elliptic curves and isogenies. In this text,
all elliptic curves are defined over a finite field. We denote by Fpn a finite field with pnelements and characteristic p, and by Fp an algebraic closure of Fpn .
Isomorphisms. An isogeny ϕ : E → E 0 is an isomorphism if there exists an isogenyϕ̂ : E 0 → E such that ϕ̂ ◦ ϕ (and thereby ϕ ◦ ϕ̂) is the identity. Isomorphisms from E toitself form the group of automorphisms Aut(E). For E defined over Fpn , the j-invariantj(E) ∈ Fpn is a complete invariant of the isomorphism class of E over the algebraic closure
Fp : there exists an isomorphism E → E 0 over Fp if and only if j(E) = j(E 0 ).

1.1. INTRODUCTION

23

Degree and separability. Intuitively, the degree of an isogeny ϕ measures how “complicated”
it is. A simple measure of this complexity would be # ker(ϕ), and this is close to the correct
definition. The degree is actually an integer of the form pk · # ker(ϕ), where p > 0 is thecharacteristic of the field. When k = 0, i.e., when deg(ϕ) = # ker(ϕ), the isogeny is called
separable. The case k > 0 can only arise from a special isogeny: the pk -Frobenius isogeny
defined as
k
k
(pk )
φE
: (x, y) 7−→ (xp , y p ).
pk : E −→ E
For any isogeny ϕ, there is a maximal integer n such that ϕ factors in the form ψ ◦ φE.
pkk
We then define deg(ϕ) = p · # ker(ϕ).
The kernel encodes most of the information about a separable isogeny. Indeed, for any
separable isogenies ϕ1 : E → E1 and ϕ2 : E → E2 , if ker(ϕ1 ) = ker(ϕ2 ), then there exists
an isomorphism ψ : E1 → E2 such that ϕ2 = ψ ◦ ϕ1 . Moreover, for any finite subgroup
G ⊂ E, there exists a separable isogeny ϕG with kernel G. In virtue of its unicity (up toisomorphism), we write E/G for the codomain of ϕG .
Prime decomposition. If deg(ϕ) = ` is a prime number, we say that ϕ
Qis an `-isogeny.
Any isogeny can be written as a composition of `-isogenies: if deg(ϕ) = i `i with each `iprime, there exist isogenies ϕi of appropriate domains and codomains such that each ϕiis an `i -isogeny and ϕ = ϕn ◦ · · · ◦ ϕ1 .
Endomorphisms. An endomorphism of E is an isogeny from E to itself (or the zero morphism). The collection of all endomorphisms of E (over Fp ) forms the endomorphism ringEnd(E). As its name suggests, it is a ring for pointwise addition, and composition ofmaps. For any integer m ∈ Z, the multiplication-by-m map [m]E : E → E : P 7→ m · P
is an endomorphism. Abusing notation, we will often consider Z as a subring of End(E),since this construction m 7→ [m]E is injective. Elements of this subring Z ⊂ End(E) arecalled scalar endomorphisms.
Dual. For any isogeny ϕ : E1 → E2 , there exists a unique isogeny ϕ̂ : E2 → E1 , the dualof ϕ, such that ϕ̂ ◦ ϕ = [deg(ϕ)].
Torsion and supersingularity. The m-torsion of E is the subgroup E[m] = ker([m]E ).
Multiplication by m is separable if and only if gcd(m, p) = 1, in which case E[m] ∼=(Z/mZ)2 . The situation at the prime p leads to a dichotomy:• either E[pn ] ∼= Z/pn Z for all n ≥ 0, and we say E is ordinary, orn• E[p ] = {0E } for all n ≥ 0, and we say E is supersingular.
1.1.3. Computing with isogenies. Isogenies are rather abstract objects, yet we wish
to work with them computationally: store them, evaluate them. One could represent
an isogeny by explicit formulas, as a rational map, but that rapidly becomes impracticalwith increasing degrees. Alternatively, an isogeny can be described by generators of its
kernel. Let G ⊂ E be a subgroup generated by (P1 , . . . , Pn ). The data of (P1 , . . . , Pn ) thenencodes the isogeny ϕG : E → E/G. We call this the kernel representation of an isogeny,
and Vélu proposed formulas which given the generators of G, returns the codomain E/Gand evaluates ϕG at any point in√O(#G) arithmetic operations [Vél71]. This complexity
has recently been improved to O( #G) [BDFLS20]. This method is well-suited for isogenies
of reasonably small degree. Yet, in cryptographic applications, one will routinely encounter
isogenies of degree of the order of 2256 . Another solution is needed.
One can exploit the multiplicativity of the degree: composing small degree isogenies
rapidly produces large degree ones. Consider a sequence ϕi : Ei−1 → Ei . The composition ϕn ◦ · · · ◦ ϕ1 can be represented by a tuple (ϕ1 , . . . , ϕn ) where each ϕi is in kernel
representation. The length grows linearly in n, but the degree grows exponentially. One

24

1. SUPERSINGULAR ISOGENIES AND ENDOMORPHISMS

can thus efficiently manipulate isogenies of degree 2n as sequences of n isogenies of degree
2. We call such a sequence an isogeny path.
The isogeny path representation is an example of an efficient representation: a representation of an isogeny ϕ that allows to store and evaluate it in polynomial time inlog(deg(ϕ)).
Definition 1.3 (Efficient representation). Let A be a polynomial time algorithm. It isan efficient isogeny evaluator if for any D ∈ {0, 1}∗ such that A (validity, D) outputs >,there exists an isogeny ϕ : E → E 0 (defined over some finite field Fq ) such that:(1) on input (curves, D), A returns (E, E 0 ),(2) on input (degree, D), A returns deg(ϕ),(3) on input (eval, D, P ) with P ∈ E(Fqk ), A returns ϕ(P ).
If furthermore D is of polynomial size in log(deg ϕ) and log q, then D is an efficient
representation of ϕ (with respect to A ).
When we say that an isogeny is in efficient representation, the algorithm A is often
left implicit. There are only a handful of known algorithms to evaluate isogenies, so one
can think of A as an algorithm that implements each of these, and D would start withan indicator of which algorithm to use. In the following sections, we will see more recent
and powerful examples of efficient representations — including a universal method: theinterpolation representation discussed in Section 1.5.2.
1.2. Random walks in isogeny graphs
1.2.1. The standard supersingular isogeny graph. An isogeny graph is a multigraph where vertices are elliptic curves up to isomorphism, and edges represent certain
isogenies between them. Fix two distinct prime numbers p and `. The (full) `-isogeny
graph over Fp is defined as follows:• Its vertices are the (isomorphism classes of) elliptic curves over Fp .
• Its edges are all the isogenies of degree ` (also called `-isogenies). More precisely,
there is an edge of multiplicity m from E1 to E2 if there are m distinct subgroups
G ⊂ E of order ` such that E2 ∼= E1 /G.
This graph has infinitely many vertices, and exactly one of its connected components isfinite: the supersingular component SS` (p), whose vertices are the supersingular elliptic
curves. We call this component the supersingular `-isogeny graph over Fp . Almost all
isogeny-based cryptography takes place in this component. Here are a few first observations about this graph.
• The supersingular `-isogeny graph counts p/12 + O(1) vertices (isomorphismclasses of supersingular elliptic curves). They each admit a model defined over Fp2 .
• The graph is (` + 1)-out-regular. One can efficiently enumerate the neighbors of
any given vertex (in time polynomial in ` and log p), and thereby navigate in thegraph.
• The `-IsogenyPath problem is simply the pathfinding problem in the supersingular `-isogeny graph.
1.2.2. Rapid mixing of random walks. Given a vertex E0 of the `-isogeny graph, arandom walk (of length n) from E0 is a sequence (Ei )ni=0 where each Ei+1 is a randomneighbor of Ei . Unless otherwise specified, we will consider the uniform distribution onneighbors.
These random walks are useful in isogeny-based cryptography for one particular reason: they have rapid mixing properties. In fact, the supersingular `-isogeny graph is a
Ramanujan graph, a family of graphs in which random walks equidistribute optimally: the1.2. RANDOM WALKS IN ISOGENY GRAPHS

25

target of a random walk of length at least O(log p) is indistinguishable from a uniformly
random vertex.
For a more formal statement, let us recall the notion of total variation distance. Given arandom variable X with values in a discrete set X , we say it hasPdistribution f : X → [0, 1]
if f (x) = Pr[X = x] for every x ∈ X . We also write f (A) = x∈A f (x) for any A ⊆ X .
For two distributions f1 and f2 over the same set X , their total variation distance is11 X
kf1 − f2 k1 =|f1 (x) − f2 (x)| = sup |f1 (A) − f2 (A)|.
2
2
A⊆X
x∈X

The rapid-mixing of supersingular `-isogeny graphs is the following well-known proposition. In Section 1.2.4, we present the much more general version of [[PW24, Theorem 3.10]].
Proposition 1.4. Let E be a supersingular elliptic curve over Fp2 , and ` 6= p a prime
number. Let ε > 0. There is a bound n = O(log` (p) − log` (ε)) such that the endpoint of a
uniform random walk of length at least n from E in the `-isogeny graph is at total variation
distance at most ε from the stationary distribution f , which is f (E) = (p−1)#24Aut(E) .
Proof. This is a standard consequence of Pizer’s proof that the supersingular `-isogeny
graph is Ramanujan [Piz90]. Details can be found, for instance, in [[BCC+ 23, Theorem 11]]
for the length of the walk, and in [[BCC+ 23, Theorem 7, Item 2]] for the description of thestationary distribution.

The stationary distribution is at statistical distance O(1/p) of the uniform distribution (because # Aut(E) = 2 for almost all curves, and # Aut(E) = O(1) for the rare
exceptions). For all cryptographic purposes, the stationary and uniform distributions areindistinguishable, and we often conflate them in the rest of the text.
1.2.3. Cryptographers care about random walks. Random walks play a key role inisogeny-based cryptography. A critical point is that cryptography requires computational
problems that are hard on average: problems which cannot be solved efficiently for random inputs, with non-negligible probability. Thus designing and analysing cryptosystems
requires good randomisation tools. We now illustrate this with a few classical applicationsof random `-isogeny walks.
Average-case problems. Here is an average-case version of `-IsogenyPath.
Problem 1.5 (Average-case `-IsogenyPath). Given a prime p, and two uniformly random supersingular elliptic curves E1 and E2 over Fp2 , find an `-isogeny path from E1 toE2 .
One can prove that the CGL hash function [CLG09] is preimage-resistant if averagecase `-IsogenyPath is hard (i.e., if no efficient algorithm solves it with good probability).
The CGL hash function was the first isogeny-based construction using random walks inthe supersingular `-isogeny graph. The idea is the following. Fixing a reference curve E0 ,a binary string x ∈ {0, 1}n encodes a (non-backtracking) walk ϕx : E0 → Ex of lengthn in the 2-isogeny graph (the graph has degree 3, so there are two possibilities for each“next step”, arbitrarily labelled 0 and 1; for the first step, we arbitrarily discard one of
the three possibilities). The CGL hash function is the function
CGLE0 : {0, 1}∗ −→ Fp2 : x 7−→ j(Ex )which sends any binary string to the j-invariant of the target curve Ex of the encoded
walk ϕx . Finding a preimage for that function CGLE0 thus amounts to finding a path
E0 → Ex in the `-isogeny graph. The cryptographic notion of preimage-resistance is an“average case” property: CGLE0 is preimage-resistant if it is hard to find preimages withgood probability for uniformly random inputs of a certain length. This is where random

26

1. SUPERSINGULAR ISOGENIES AND ENDOMORPHISMS

walks come in: a random input x ∈ {0, 1}n ⊂ {0, 1}∗ for f encodes a random walk oflength n. When n is large enough, the output of this random walk is close to uniform.
From there, it is easy to deduce that if average-case `-IsogenyPath is hard, then the
CGL hash function is preimage-resistant (with small technicalities to deal with, like thefact that {0, 1}∗ only encodes non-backtracking walks).
Worst-case to average-case reductions. The CGL construction is already an interesting first
application of the rapid-mixing property, but the result is not yet satisfactory. The core assumption of isogeny-based cryptography is the worst-case hardness of the `-IsogenyPath
problem: no algorithm can solve it efficiently on every input. Clearly, if it is hard on average, then it is hard in the worst case. But we wish to prove the converse: if it is hard in theworst case (our core assumption), then it is hard on average. Random walks unlock sucha proof. Suppose there is an efficient algorithm A for average-case `-IsogenyPath, andlet E1 and E2 be any instance of `-IsogenyPath (the worst case). Proceed as follows:(1) First, generate two random `-isogeny walks ϕi : Ei → Ei0 such that each Ei0 is
indistinguishable from uniform.
(2) Call A on input E10 and E20 (an average-case instance); it returns an `-isogeny
path ψ : E10 → E20 with good probability.
(3) Return ϕ̂2 ◦ ψ ◦ ϕ1 .
This is a simple example of a worst-case to average-case reduction.
Design and analysis of algorithms. As a last illustration of the power of random walks in`-isogeny graphs, we sketch the fastest known algorithm to solve `-IsogenyPath.
Proposition 1.6. The `-IsogenyPath problem can be solved in expected time (` +log p)O(1) · p1/2 .
Sketch of the proof. This can be done by a straigtforward meet-in-the-middle algorithm.
Let n as in Proposition 1.4 such that the output of a random walk of length n is indistinguishable from uniform. Then, generate many random walks ϕi : E1 → Ei0 until one has
found p1/2 distinct targets Ei0 , and store them. Now, generate random walks ψ : E2 → E
until the random target E is isomorphic to one of the curves Ei0 (this happens with probability Ω(p−1/2 ), so requires an expected number of trials O(p1/2 )). For this i, returnψ̂ ◦ ϕi .

1.2.4. Higher level isogeny graphs. It is often useful to attach some additional data
to elliptic curves. For instance, fix an integer N > 0, and consider pairs (E, C) whereC ⊂ E[N ] is a cyclic subgroup of order N . We can then consider isogenies that preserve
this structure: an isogeny (E1 , C1 ) → (E2 , C2 ) is an isogeny ϕ : E1 → E2 such thatϕ(C1 ) = C2 . This naturally leads to a generalization of isogeny graphs, where vertices arepairs (E, C) and edges are such “structure preserving” isogenies.
This particular example is the isogeny graph with level N Borel structure. They are thefirst example of higher level isogeny graphs that appeared in isogeny-based cryptography,
in [[BCC+ 23]]. In that article, we prove that random walks in these graphs equidistribute
optimally, leading to the first general purpose statistically zero-knowledge proof of isogeny
knowledge (a cryptographic protocol to prove that one knows a solution to `-IsogenyPath
without revealing it). A key observation is that a vertex (E, C) of this graph can beinterpreted as an N -isogeny E → E/C, hence random walks in this graph can be used toequidistribute not just curves, but isogenies.
Other types of additional data can be attached to elliptic curves, and the corresponding
graphs and random walks have proved to be powerful tools. The most general framework
to date is introduced in our article [[PW24]]. In the rest of this section, we present this1.2. RANDOM WALKS IN ISOGENY GRAPHS

27

framework and the corresponding equidistribution result. For the highest level of generality, we resort to the language of categories. The first category of interest is SSΣ (p),underlying the standard isogeny graph.
Definition 1.7. Let Σ be a set of prime numbers. The category SSΣ (p) has• objects: supersingular elliptic curves over Fp ;• morphisms HomΣ (E, E 0 ): isogenies of degree a product of the primes in Σ.
The next step consists in attaching extra structure to objects of this category. This isdone through the construction of a “category of elements”.
Definition 1.8. Let C be a category and F : C → Sets be a functor. The category ofelements El(F) is the category with• objects: pairs (c, x) where c ∈ C and x ∈ F (c);• morphisms (c, x) → (c0 , x0 ): morphisms f ∈ HomC (c, c0 ) s.t. F(f )(x) = x0 .
Example 1.9. Assume p - N . Let Σ be the set of primes not dividing N . Define thefunctor CycN : SSΣ (p) → Sets by:• CycN (E) is the set of cyclic subgroups of order N of E;• for every isogeny ϕ ∈ HomΣ (E, E 0 ), the map CycN (ϕ) is C 7→ ϕ(C).
Then El(CycN ) is the category of pairs (E, C) where E is a supersingular elliptic curves
and C is a cyclic subgroup of order N — the so-called level N Borel structure usedin [[BCC+ 23]].
Example 1.10. Let Σ be the set of primes not dividing N . Let End /N denote the functor SSΣ (p) → Sets defined by• (End /N )(E) = End(E)/N End(E);• for ϕ : E → E 0 , the map (End /N )(ϕ) is α 7→ ϕαϕ̂.
Then El(End /N ) is is the category of supersingular elliptic curves equipped with an endomorphism modulo N . This example plays an important role in the equivalence between
the problems EndRing and OneEnd presented in Section 1.4.
We now introduce the graphs of interest.
Definition 1.11. Let F : SSΣ (p) → Sets be a functor with F(E) finite for all E. Let` ∈ Σ be a prime different from p. We define the graph GF` with:• vertices: isomorphism classes of objects in El(F);• edges: let (E, x) ∈ El(F); edges from (E, x) are isogenies ϕ ∈ HomΣ (E, E 0 ) ofdegree `, modulo automorphisms of (E 0 , F(ϕ)(x)).
`
Returning to Example 1.9, if ` is a prime not dividing N p, the graph GCycis theN`-isogeny graph of supersingular elliptic curves with Borel structure studied in [Arp23]
and [[BCC+ 23]]. When N = 1 this is the standard supersingular `-isogeny graph.

This general construction of graph GF` is perhaps too general. For random walks
to behave well, one needs the functor F to preserve some of the underlying arithmetic
structure. We require it to satisfy the (mod N )-congruence property.
Definition 1.12. Let F : SSΣ (p) → Sets be a functor and N ≥ 1 an integer. We saythat F satisfies the (mod N )-congruence property if for every E ∈ SS(p) and every ϕ, ψ ∈EndΣ (E) such that ϕ − ψ ∈ N End(E), we have F(ϕ) = F(ψ).
The functors CycN and End /N from Examples 1.9 and 1.10 above do satisfy the(mod N )-congruence property.
Stated informally, the equidistribution theorem we prove in [[PW24]] is the following.

28

1. SUPERSINGULAR ISOGENIES AND ENDOMORPHISMS

Theorem 1.13 (Informal formulation of [[PW24, Theorem 3.10]]). If F satisfies the (mod N )congruence property, then random walks in GF` equidistribute optimally.
The optimality refers to the fact that the graphs can be disconnected or multipartite(clear obstructions to equidistribution) but the equidistribution is “as good as possible”
under these constraints.
Independently, a similar result was proved by Codogni and Lido [CL23], in the casewhere the extra data is of a particular kind: a level structure, expressed in terms of N torsion points. Example 1.9 fits in that framework, but Example 1.10 does not. Bothproofs use Deligne’s bounds on coefficients of modular forms, but the proof in [CL23]
is purely algebro-geometric, whereas ours proceeds via the Deuring correspondence and
the Jacquet–Langlands correspondence; as a result, the two proofs could have different
interesting generalisations.
1.3. The `-Isogeny Path and Endomorphism Ring problems
Recall that given an elliptic curve E, an endomorphism is an isogeny from E to itself (orthe zero morphism), and the set of all endomorphisms of E, written End(E), is a ring.
Loops in `-isogeny graphs provide endomorphisms, hinting at a connection between pathfinding problems and computing endomorphism rings. This connection is a fundamental
aspect of isogeny-based cryptography.
The endomorphism ring is always a lattice; and in the supersingular case, it is a latticeof rank 4. The endomorphism ring problem consists in finding a basis of this lattice.
Problem 1.14 (EndRing). Given a prime p, and a supersingular elliptic curve E overFp2 , find four endomorphisms of E (in an efficient representation) that generate End(E)as a lattice.
The EndRing problem, and its connection to `-IsogenyPath, has been studied as
early as [Koh96], before any cryptographic motivation. With the increasing practicalrelevance of these problems, it has become critical to understand their relation. It was soon
suspected that they were equivalent, and heuristic reductions were described in [EHL+ 18].
The following theorem is the main result from our article [[Wes21]].
Theorem 1.15 ([[Wes21]]). The problems `-IsogenyPath and EndRing are equivalent under probabilistic polynomial time reductions, assuming the Generalized RiemannHypothesis.
This section gives an overview of its proof. One of the main ingredients is an importantpiece of the underlying theory which will play a role in the rest of this chapter: the Deuringcorrespondence.
1.3.1. The Deuring correspondence. The Deuring correspondence states that themap E 7→ End(E) is essentially a bijection (even an equivalence of categories) between
supersingular elliptic curves and a certain family of rings: maximal orders in a quaternion
algebra Bp,∞ .
First, let us define more precisely this family of rings. The quaternion algebra Bp,∞ isdefined as the algebra of dimension 4 over Q with basis 1, i, j, k satisfying the multiplication
rules i2 = −q, j 2 = −p, and k = ij = −ji, with
1 if p ≡ 3 mod 4, or
q = 2 if p ≡ 5 mod 8, and otherwise the smallest prime such that q ≡ 3 mod 4 and p = −1.
q
An order in Bp,∞ is a discrete subring containing a basis of the algebra (i.e., a subringthat is also a lattice of rank 4). It is maximal if not contained in any other order.

1.3. THE `-ISOGENY PATH AND ENDOMORPHISM RING PROBLEMS

29

Given a supersingular elliptic curve E over Fp , the endomorphism algebra End(E)⊗Z Q
is isomorphic to Bp,∞ . Through this isomorphism, the endomorphism ring End(E) is a
maximal order in the algebra. This so-called Deuring correspondence provides a bijection
between the isomorphism classesnonoIsomorphism classes of
Isomorphism classes of
/
Gal(F
/F
)
←→
2
p
p
supersingular elliptic curves E over Fp2
maximal orders O in Bp,∞ .
The MaxOrder problem. The MaxOrder problem is the computational incarnation ofthis bijection.
Problem 1.16 (MaxOrder). Given a prime p, and a supersingular elliptic curve E overFp2 , find four quaternions in Bp,∞ that generate a maximal order O such that O ∼= End(E).
This problem is similar to EndRing: it asks to compute the endomorphism ring ofa curve. But while EndRing asks for actual endomorphisms that generate End(E), theMaxOrder problem only asks for the ring structure of End(E), up to isomorphism.
The MaxOrder problem was already identified in [EHL+ 18] as lying at the heart ofthe equivalence between EndRing and `-IsogenyPath. Indeed, following in the footstepsof [EHL+ 18], we prove in [[Wes21]] that EndRing and `-IsogenyPath are equivalent by
proving that each is equivalent to MaxOrder.
The correspondence between morphisms. As already mentioned, this correspondence extends to an equivalence of categories. Morphisms on the side of elliptic curves are isogenies
and the zero morphism. Morphisms on the side of orders are ideals: any left ideal I ina maximal order O1 is a right ideal in another order O2 . The zero ideal is in correspondence with the zero morphism of curves. When I is non-zero, we call it a connecting
ideal between O1 and O2 , and we think of it as a morphism from O1 to O2 . For such an
ideal I, we call OL (I) = O1 its left order, and OR (I) = O2 its right order. A (non-zero)
morphism from O1 to O2 is a (non-zero) left ideal I in O1 such that OR (I) ∼= O2 . The
correspondence between morphisms is defined as follows:• An isogeny ϕ : E1 → E2 , corresponds to the ideal Iϕ = Hom(E2 , E1 ) ◦ ϕ ⊆End(E1 ). It is a left ideal in End(E1 ), and a right ideal in OR (I) ∼= End(E2 ).
• A left ideal
I⊆
End(E)
corresponds
totheisogenyϕ=E→
E/E[I] whereIT
E[I] = α∈I ker α (at least in the separable case, when the norm of I is coprimeto p).
For any ϕ and I, we have IϕI = I and ϕIϕ = ϕ (up to an isomorphism of the target).
p Furthermore, the degree of a non-zero isogeny matches the reduced norm Nrd(I) =[OL (I) : I] of the corresponding ideal I.
Remark 1.17. Aspects of this correspondence are better captured when replacing thecategory of maximal orders with the category of invertible right O-modules for somereference maximal order O. See for instance [Voi21, Theorem 42.3.2]. That point of view
avoids issues raised by working up to isomorphism as above.
As MaxOrder asks to compute the map between objects E 7→ End(E), one can ask
the analogous question for morphisms: can the maps ϕ 7→ Iϕ and I 7→ ϕI be computed
efficiently? The first positive answer to this question is the following lemma: we cantranslate between isogenies and ideals if we already know the endomorphism ring of thesource curve.
Lemma 1.18. Assuming the Generalized Riemann Hypothesis, there is an algorithm suchthat the following holds. Let E0 be a supersingular elliptic curve, O0 an order in Bp,∞ ,and ι : O0 −→ End(E0 ) a bijection (computationally represented by a basis of O0 and an
efficient representations of its image). Then,

30

1. SUPERSINGULAR ISOGENIES AND ENDOMORPHISMS• on input ι and an isogeny ϕ : E0 → E1 (in isogeny path representation), thealgorithm returns the left O0 -ideal Iϕ ,• on input ι and a left O0 -ideal I, returns the isogeny ϕI (in isogeny path representation).
The algorithm runs in polynomial time in the length of the input, and in the largest prime
factor of the degree of ϕ and norm of I.
Sketch of the proof. The technique finds its roots in the heuristic result [GPS20, Lemma 6].
It was revisited in [EHL+ 18], and the first rigorous algorithm is given in [[Wes21]].
The idea is to first deal with the case where the degree (or norm) is powersmooth:all its prime-power factors are small. One can then deal with each prime-power factor
independently, and reconstitute the output via the following fact: if I and J are left O0 ideals of coprime norm, we have ker ϕI∩J = ker ϕI + ker ϕJ . Translating between ideals
and isogenies for a small prime-power factor `e is rather straightforward, as there are O(`e )possible kernels or ideals, and a correct guess can be validated efficiently.
Dealing with large prime powers is much trickier, and requires reducing the problem tothe powersmooth case. The idea consists in chopping the long isogeny path (or ideal) into
smaller chunks, and iteratively find powersmooth alternative paths to each intermediate
step. There lies the technical heart of [[Wes21]]: an algorithm which, on input a left
O0 -ideal, finds an equivalent ideal whose norm is powersmooth (two left O0 -ideals areequivalent if their right orders are isomorphic). A heuristic algorithm for this task was firstpresented in [KLPT14], known as the KLPT algorithm. We prove in [[Wes21, Theorem 6.4]]
that the same task can be performed assuming only GRH.

1.3.2. The quaternion analog of the `-IsogenyPath problem. Through the Deuring correspondence, a computational problem involving supersingular elliptic curves canbe translated into a computational problem involving quaternions. For instance, as the`-IsogenyPath problem asks one to find an isogeny of degree a power of ` between two
curves, its quaternionic analog is: given two (isomorphism classes of) maximal orders O1
and O2 , find an ideal of norm a power of ` connecting them.
While `-IsogenyPath is believed to be hard, this quaternion version turns out tobe easy. The first heuristic resolution of this problem is the KLPT algorithm [KLPT14],
already mentioned in the proof of Lemma 1.18. In the article [[Wes21]], we prove that it
can be solved in polynomial time assuming GRH.
Theorem 1.19 (Special case of [[Wes21, Theorem 6.3]]). There is an algorithm which given
two maximal orders O1 and O2 in Bp,∞ and a prime `, finds a left O1 -ideal I of norm apower of ` such that OR (I) ∼= O2 , and runs in expected polynomial time in ` and in thesize of the input, assuming the Generalized Riemann Hypothesis.
The reader may already see how this could help reducing `-IsogenyPath to MaxOrder:
an oracle for MaxOrder can turn an instance of `-IsogenyPath into an instance of its
quaternionic analog, which is easy. We would then need to translate the quaternionicsolution back to an isogeny, perhaps with Lemma 1.18, but that requires an additional
ingredient.
1.3.3. Finding a reference supersingular elliptic curve. The translation between
ideals and isogenies with Lemma 1.18 plays a key role in proving that the three problems`-IsogenyPath, MaxOrder and EndRing are equivalent. Yet, applying the lemma
requires prior knowledge of the endomorphism ring of one of the curves involved. We
are thus interested in generating a “reference” curve, a special supersingular elliptic curve
E0 for which we know, by construction, a solution to both MaxOrder and EndRing.
Then, Lemma 1.18 can be used to connect instances of `-IsogenyPath, MaxOrder orEndRing to that reference curve E0 .

1.3. THE `-ISOGENY PATH AND ENDOMORPHISM RING PROBLEMS

31

Such “special” elliptic curves can be found by turning to the usual suspects, such as
the elliptic curves of j-invariant 0 or 1728. Which curve to pick depends on the congruenceclass of p mod 8, but the general idea is always the same: find an elliptic curve over Q
which has supersingular reduction modulo p, and has complex multiplication by an orderof small discriminant. Then, the Frobenius endomorphism πp together with the reductionof the complex multiplication already reveals a large part of the endomorphism ring.
Lemma 1.20 ([EHL+ 18, Proposition 3]). There is an algorithm that for any prime p > 2
computes an elliptic curve E0 over Fp , a basis (1, α1 , α2 , α3 ) of a maximal order O0 of
Bp,∞ , and three endomorphisms β1 , β2 , β3 of E0 (in efficient representation), such that
O0 −→ End(E0 ) : 1, α1 , α2 , α3 7−→ [1], β1 , β2 , β3
is an isomorphism, and runs in time polynomial in log p (if p ≡ 1 mod 8, we assume
GRH).
Sketch of the proof. If p ≡ 3 mod 4, then the curve E0 defined by y 2 = x3 − x is supersingular. It is defined over Fp , so has the Frobenius endomorphism π : (x, y) 7→ (xp , y p ).
Furthermore, if α ∈ Fp2 satisfies α2 = −1, it is easy to check that ι : (x, y) 7→ (−x, αy) is
also an endomorphism. These endomorphisms generate almost all End(E0 ): we actuallyhaveι + ιπ1+πEnd(E0 ) = Z ⊕ Zι ⊕ Z
⊕Z
.
2
2
1+π
2
2
Therefore we can consider (β1 , β2 , β3 ) = (ι, ι+ιπ
2 , 2 ). Since ι = [−1] and π = [−p], we
i+ij 1+j
can set the corresponding quaternions (α1 , α2 , α3 ) = (i, 2 , 2 ). The case p ≡ 5 mod 8
enjoys similar explicit formulae, and the case p ≡ 1 mod 8 requires to first find a small
quadratic non-residue q modulo p (hence the√need for GRH), then generate an elliptic
curve over Q with complex multiplication by −q (hence the need for q to be small). 

1.3.4. `-IsogenyPath is equivalent to MaxOrder. We now have all the ingredientsto sketch the proof that `-IsogenyPath is equivalent to MaxOrder.
MaxOrder reduces to `-IsogenyPath. Suppose we wish to solve MaxOrder for some
elliptic curve E, and we have access to an oracle for `-IsogenyPath.
From Lemma 1.20, we can find a supersingular curve E0 together with a maximal
order O0 and an isomorphism O0 −→ End(E0 ). Using the oracle for `-IsogenyPath, one
can find an isogeny path ϕ : E0 → E. It remains to “transport” the information from E0
along the path to E. This is where Lemma 1.18 comes in: one can compute the ideal Iϕ ,then return the right-order of Iϕ , which is isomorphic to End(E).
`-IsogenyPath reduces to MaxOrder. Suppose we wish to solve `-IsogenyPath for
two elliptic curve E1 and E2 , and we have access to an oracle for MaxOrder.
It is enough to show how to find an `-isogeny path E0 → E1 for the special curve E0
from Lemma 1.20. Indeed, the same can be applied to E0 → E2 , and the composition
gives a path E1 → E2 . Now, the oracle for MaxOrder reveals an order O1 isomorphic
to End(E1 ). There is an efficient algorithm to find a connecting ideal between O0 andO1 [KV10, Algorithm 3.5]. One can then find an equivalent ideal of norm a power of `(thanks to Lemma 1.19), and use Lemma 1.18 to translate this ideal to the corresponding
isogeny: a `-isogeny path E0 → E1 .
1.3.5. MaxOrder is equivalent to EndRing. Finally, we sketch the proof that the
problems MaxOrder and EndRing are equivalent.

32

1. SUPERSINGULAR ISOGENIES AND ENDOMORPHISMS

MaxOrder reduces to EndRing. The reduction from MaxOrder to EndRing is perhaps the least surprising direction. On one hand, the endomorphism ring End(E) is a Euclidean lattice with the positive definite integral quadratic form deg : End(E) → Z. On theother hand, the algebra Bp,∞ is a Euclidean space with the reduced norm Nrd : Bp,∞ → Z.
A ring embedding End(E) → Bp,∞ preserves the Euclidean structure. The idea is thus tofind a subring in Bp,∞ that has the same “geometry” as End(E), and deduce that they
are isomorphic as rings.
Concretely, from a basis (βi )4i=1 of the lattice End(E), one can compute the Grammatrix (hβi , βj i)4i,j=1 , then find a basis of Bp,∞ with the same Gram matrix. This amounts
to solving a few homogeneous quadratic equations over Q, which can be done with [Sim05,
Sim06].
EndRing reduces to MaxOrder. The reduction from EndRing to MaxOrder may
appear more difficult, as solving EndRing requires finding actual endomorphisms of E,
while solving MaxOrder only seems to provide abstract “quaternionic” information on
the endomorphism ring. The idea is to relate E to the reference curve E0 for which
we know both actual endomorphisms and an embedding in the quaternion world. The
reduction works as follows.
(1) Generate E0 together with an isomorphism ι : O0 → End(E0 ) (Lemma 1.20).
(2) Solve MaxOrder to find an order O in Bp,∞ isomorphic to End(E).
(3) Find a connecting ideal I between O0 and O ([KV10, Algorithm 3.5]).
(4) Find the corresponding isogeny ϕI : E0 → E (Lemma 1.18).
(5) We obtain an isomorphism of algebras(1.1)

 : End(E0 ) ⊗ Q −→ End(E) ⊗ Q : β 7−→ (ϕI ◦ β ◦ ϕ̂I ) ⊗1.
deg(ϕI )(6) The composition  ◦ (ι ⊗ Q) : Bp,∞ → End(E) ⊗ Q is also an isomorphism.
(7) Output the basis of  ◦ (ι ⊗ Q)(O) = End(E).
Of course, one should ensure that the output basis consists of endomorphisms in efficient
representation. There a several ways to do this. The main obstacle is the division bydeg(ϕI ) in the map (1.1). The originally proposed solution is to ensure that deg(ϕI ) is
powersmooth, so there is an efficient algorithm to divide points. Alternatively, a more
recent algorithm allows to divide any endomorphism in efficient representation by any
integer [[HW23, Theorem 4.1]] (see Section 2.4.1).
1.4. Finding one endomorphism is as hard as finding them all
While the endomorphism ring problem asks to find, in a sense, all the endomorphisms ofa supersingular curve, it has appeared hard to find even a single one. Scalar multiplications [m] for m ∈ Z are trivial to find, so we exclude them. This is the (supersingular)
one endomorphism problem.
Problem 1.21 (OneEnd). Given a prime p and a supersingular elliptic curve E overFp2 , find an endomorphism in End(E) \ Z in efficient representation.
The connection between EndRing and OneEnd bears important consequences on thehardness of EndRing and on its connection with variants of the isogeny problem. On thecryptographic side, the OneEnd problem naturally emerges when analyzing the securityof certain schemes. Most notably, it is easy to prove that some version of the CGL hashfunction is collision-resistant if OneEnd is hard. This result alone is unsatisfactory, as
OneEnd seems, at first glance, simpler that the pinnacle problem of the field, EndRing.
Unfortunately, former heuristic arguments suggesting that OneEnd should be as hard as1.4. FINDING ONE ENDOMORPHISM IS AS HARD AS FINDING THEM ALL

33

EndRing do not withstand close scrutiny, and actually fail in simple cases.
In the article [[PW24]], we prove the following theorem.
Theorem 1.22 ([[PW24, Theorem 1.1]]). The EndRing and OneEnd problems are equivalent, under probabilistic polynomial time reductions.
In Section 1.4.1 below, we present the proof strategy. This theorem was our motivation to prove the general rapid-mixing in higher level isogeny graphs, Theorem 1.13.
In Section 1.4.2, we present a few important consequences of this theorem: the collisionresistance of the CGL hash function, the equivalence between EndRing and the “pure”
Isogeny problem, and the fastest known unconditional algorithm to solve EndRing.
1.4.1. Proving that EndRing reduces to OneEnd. The ideas behind our reduction
are as follows. Assume we have an oracle O for OneEnd and we want to compute End(E)for a given E.
The ring End(E) is a lattice of dimension 4 and volume p/4 (with respect to the quadratic form deg : End(E) → Z). A solution of EndRing consists in four endomorphismsthat generate all the others. Given a collection of endomorphisms, one can decide whether
they generate the whole ring End(E) by computing the volume of the lattice they generate, and comparing it to p/4. Once a generating set has been found, it is easy to deducea basis.
A first flawed attempt. We thus need a way to generate several endomorphisms of E.
Naively, one could repeatedly call O(E), hoping to eventually obtain a generating set.
This can fail, for instance if the oracle is deterministic and O(E) always returns the sameendomorphism.
To circumvent this issue, it was proposed in [EHL+ 18] to randomise the curve. Moreprecisely, one constructs a richer, randomised oracle RichO from O as follows. On input
E, walk randomly on the 2-isogeny graph, resulting in an isogeny ϕ : E → E 0 . This graphhas rapid mixing properties, so E 0 is close to uniformly distributed among supersingularcurves. Now, call the oracle O on E 0 , to get an endomorphism β ∈ End(E 0 ). The
composition α = ϕ̂ ◦ β ◦ ϕ is an endomorphism of E, the output of RichO .
With this randomisation, there is hope that calling RichO repeatedly on E could yieldseveral independent endomorphisms that would eventually generate End(E). This method
is essentially what is proposed in [EHL+ 18, Algorithm 8]. In that article, it is heuristicallyassumed that endomorphisms produced by RichO are very nicely distributed, and they
deduce that a generating set for End(E) is rapidly obtained. This heuristic has a critical
flaw: one can construct oracles that contradict it. Consider an integer M > 1, andsuppose that for any input E, the oracle O returns an endomorphism from the strict
subring Z + M End(E). Then, the above algorithm would fail, because the randomisation
RichO would still be stuck within the subring Z+M End(E). Worse, juggling with several
related integers M , we will see that there are oracles for which this algorithm only stabilises
after an exponential time.
Invariance by conjugation. The core of our method rests on the idea that this issue is,in essence, the only possible obstruction. The key is invariance by conjugation. If ϕ, ϕ0 :E → E 0 are two random walks of the same length, and β is an endomorphism of End(E 0 ),the elements α = ϕ̂ ◦ β ◦ ϕ and α0 = ϕ̂0 ◦ β ◦ ϕ0 are equally likely outputs of RichO . These
two elements are conjugates of each other in End(E)/N End(E) for any odd integer N , asα=ϕ̂ ◦ ϕ0
ϕ̂0 ◦ ϕ0◦α◦
mod N.
[deg(ϕ0 )][deg(ϕ0 )]34

1. SUPERSINGULAR ISOGENIES AND ENDOMORPHISMS

From there, one can prove that the output of RichO follows a distribution that is invariant
by conjugation: each output is as likely as any of its conjugates, modulo odd integers N(up to some bound). It is a consequence of Theorem 1.13, our general equidistribution
result.
Intuitively, for the outputs of RichO to be “stuck” in a subring (such as Z+M End(E)above), that subring must itself be stable by conjugation (modulo odd integers N ). Therecomes the next key: every subring of End(E) (of finite index not divisible by p) stable byconjugation modulo all integers is of the form Z+M End(E). So samples from RichO must
eventually generate a ring of the form Z + M End(E). From a basis of Z + M End(E), it iseasy to recover a basis of End(E) essentially by dividing by M (using a method developedin [Rob22] and [[HW23, Theorem 4.1]]).
Local obstructions. This intuition does not immediately translate into an algorithm, as
an oracle could be “bad” without really being stuck in a subring. Imagine an oracle that
outputs an element of Z + 2e End(E) (and not in Z + 2e+1 End(E)) with probability 2e−n
for each e ∈ [0, . . . , n − 1]. A sequence of samples (αi )i would eventually generate End(E),but only after an amount of time exponential in n. This particular case could be resolved
as follows: for each sample α, identify the largest e such that β = (2α − Tr(α))/2e isan endomorphism. A sequence of samples (βi )i would rapidly generate Z + 2 End(E),from which one easily recovers End(E). This resolution first identifies the prime 2 as thesource of the obstruction, then “reduces” each sample “at 2”. In general, such obstructive
primes would appear as factors of disc(α). Identifying these primes, and ensuring thateach sample is “reduced” at each of them, one gets, in principle, a complete algorithm.
However, factoring disc(α) could be hard. Instead, we implement an optimistic approach:
we identify obstructive pseudo-primes using a polynomial time partial-factoring algorithm.
The factors may still be composite, but it is fine: the algorithm will either behave as if
they were prime, or reveal a new factor.
1.4.2. Consequences. We now discuss some consequences of Theorem 1.22.
1.4.2.1. Collision resistance of the Charles–Goren–Lauter hash function. The first cryptographic construction based on the supersingular isogeny problem is the CGL hash function [CLG09]
CGLE0 : {0, . . . , ` − 1}∗ −→ Fp2 ,introduced in Section 1.2.3. Recall that any binary string x ∈ {0, . . . , ` − 1}∗ encodes a
non-backtracking random walk ϕx : E0 → Ex from a source E0 in the 2-isogeny graph,and CGLE0 (x) = j(Ex ) is the j-invariant of the target of this walk. As discussed in
Section 1.2.3, using the rapid equidistribution of random walks, it is rather straightforward
to prove that if `-IsogenyPath is hard, then CGLE0 is preimage-resistant.
Its resistance to collisions is considerably more delicate. A collision for CGLE0 is apair of distinct inputs x, x0 ∈ {0, . . . , ` − 1}∗ such that CGLE0 (x) = CGLE0 (x0 ). In otherwords, a collision consists in two distinct paths ϕx , ϕx0 : E0 → E 0 to the same target E 0(up to isomorphism). The composition ϕ̂x0 ◦ ϕx is a non-scalar endomorphism of E0 . At
first glance, this is good news: if OneEnd is hard for E0 , then finding collisions is hard.
This reasoning also hints at a weakness: one who already knows End(E0 ) could perhaps
find collisions in polynomial time. This is indeed the case [EHL+ 18]. To prove collisionresistance from the hardness of EndRing, one must consider a family of hash functions
CGLE where E is random. Let SampleSS(p) be an algorithm sampling a uniformly
random supersingular elliptic curve over Fp2 . We define the advantage of a collision-finding
algorithm A for the CGL family of hash functions as
m 6= m0 andE ← SampleSS(p)A
AdvCGL (p) = Pr.
CGLE (m) = CGLE (m0 )(m, m0 ) ← A (E)1.4. FINDING ONE ENDOMORPHISM IS AS HARD AS FINDING THEM ALL

35

The hash function is collision-resistant if all efficient algorithms A have negligibly small
advantage. It was heuristically argued in [EHL+ 18] that the collision-resistance of thisconstruction is equivalent to EndRing. Theorem 1.22 unlocks the proof: in [[PW24]], weprove that a collision-finding algorithm with good running time and advantage can solve
EndRing efficiently.
Theorem 1.23 (Collision-resistance of the CGL hash function, [[PW24, Theorem 8.1]]).
For any algorithm A , there is an algorithm to solve EndRing in expected polynomial−1 and in the expected running time of A .
time in log(p), in AdvACGL (p)Sketch of the proof. Since EndRing is equivalent to OneEnd (Theorem 1.22), it is sufficient to prove that A can be used to solve OneEnd. First, we observe that a successful
collision for CGLE gives a non-scalar endomorphism of E: if ϕ, ψ : E → E 0 are two distinct
non-backtracking walks, then ϕ̂ ◦ ψ ∈ End(E) \ Z.
Therefore, the algorithm A finding a collision for CGLE 0 (with good probability for
uniformly random E 0 ) in fact solves OneEnd (with good probability for uniformly random
E 0 ). To solve OneEnd on an arbitrary (non-random) input E, one first computes a random
walk ϕ : E → E 0 with uniformly random target E 0 , calls the oracle to find α ∈ End(E 0 )\Z,
and returns ϕ̂ ◦ α ◦ ϕ ∈ End(E) \ Z.
1.4.2.2. The endomorphism ring problem is equivalent to the isogeny problem. We havealready established that the problem EndRing is equivalent to `-IsogenyPath (assuming
the Generalised Riemann Hypothesis, Theorem 1.15). The latter problem asks to findisogenies of a very specific form: `-isogeny paths. Lifting this restriction yields the moregeneral Isogeny problem.
Problem 1.24 (Isogeny). Given a prime p and two supersingular elliptic curves E andE 0 over Fp2 , find an isogeny from E to E 0 in efficient representation.
From Theorem 1.15, it is easy to see that Isogeny reduces to EndRing.
Proposition 1.25. Assuming the Generalised Riemann Hypothesis, the problem Isogeny
reduces to EndRing in probabilistic polynomial time.
Proof. The Isogeny problem immediately reduces to `-IsogenyPath, which is equivalent
to EndRing (Theorem 1.15).
The converse reduction is trickier. As a solution to Isogeny is not guaranteed to havesmooth degree, previous techniques have failed to prove that it is equivalent to EndRing.
Theorem 1.22 unlocks this equivalence. Better yet, Theorem 1.26 below is unconditional.
In particular, it implies that EndRing reduces to the `-IsogenyPath independently of
the Generalised Riemann Hypothesis.
Theorem 1.26 ([[PW24, Theorem 8.6]]). The EndRing problem reduces to Isogeny inprobabilistic polynomial time.
Sketch of the proof. Since EndRing is equivalent to OneEnd (Theorem 1.22), it suffices
to prove that OneEnd reduced to Isogeny. Let E be a supersingular curve for which wewant to solve OneEnd, and let A be an algorithm for Isogeny. The idea is quite simple:
generate a random walk ϕ : E → E 0 , then call A to find an isogeny ψ : E 0 → E, andreturn ψ ◦ ϕ ∈ End(E). The unpredictibility of ϕ makes it possible to prove that whatever
A does, the endomorphism ψ ◦ ϕ is non-scalar with overwhelming probability.

1.4.2.3. An unconditional algorithm for EndRing in time Õ(p1/2 ). We have established
EndRing as a (or the) foundational problem of isogeny-based cryptography: all rests on its
presumed hardness. But how hard is it? The fastest known algorithms have complexity

36

1. SUPERSINGULAR ISOGENIES AND ENDOMORPHISMS

in Õ(p1/2 ). However, all previous algorithms reaching that complexity have relied on
unproven assumptions such as the Generalised Riemann Hypothesis.
With Theorem 1.22, we can prove that EndRing can be solved in time Õ(p1/2 ) unconditionally. In contrast, the previous fastest unconditional algorithm had complexity Õ(p)and only returned a full-rank subring of the endomorphism ring [Koh96, Theorem 75].
The first method to reach complexity Õ(p1/2 ) under the Generalised Riemann Hypothesis consists in reducing EndRing to `-IsogenyPath (with Theorem 1.15), and solving`-IsogenyPath by a generic graph path-finding algorithm (with Proposition 1.6). Unconditionally, we can follow the same strategy, but using the unconditionally reduction
from EndRing to `-IsogenyPath (Theorem 1.26).
Theorem 1.27 ([[PW24, Theorem
 8.8]]). There is an algorithm solving the EndRing
1/2
problem in expected time Õ p.
Proof. This follows from the fact that there is an algorithm of complexity Õ p1/2 for the
2-isogeny path problem (a folklore meet-in-the-middle strategy, see Proposition 1.6), andEndRing reduces to polynomially many instances of `-IsogenyPath (Theorem 1.26). 
1.5. The fall of SIDH
Supersingular Isogeny Diffie-Hellman (SIDH) is a key exchange protocol proposed in 2011
by Jao and De Feo [JD11]. For the following eleven years, it was the crown jewel ofisogeny-based cryptography. The influence of SIDH is notably illustrated by its incarnation
Supersingular Isogeny Key Encapsulation (SIKE) [JAC+ 17], a primitive submitted to thecall for standardization of new quantum-safe cryptographic primitives by the American
National Institute of Standards and Technology (NIST). SIKE reached the final round of
the process in 2022.
Yet, the security of SIDH (hence, SIKE) is not guaranteed by the hardness of the“pure” isogeny problem. It instead relies on a variant, where the image of some torsion
points under a hidden isogeny are also revealed. This has come to be known as thesupersingular isogeny with torsion (SSI-T) problem. It can be seen as an interpolation
problem, which we formalise as follows.
Problem 1.28 (Interpolation). Let ϕ : E → E 0 be an isogeny. Given E, E 0 , somepoints Pi ∈ E and their images ϕ(Pi ), and a point Q ∈ E, compute ϕ(Q).
This problem comes with a spectrum of difficulty, according to how many points are
revealed — or more precisely, according to the order of the group generated by the revealed
points. This problem has been shown to be weaker than the pure isogeny problem in aline of work pioneered by Petit [Pet17] in 2017 and expanded by multiple papers in thefollowing years [KMP+ 21, BdQL+ 19, FKMT22]. SIDH remained immune to these attacks:
they only tackled versions of Interpolation where the revealed points have large order— much larger than the points revealed by SIDH.
That was until 2022, when Castryck and Decru published a preprint [CD23] solving
this problem in polynomial time for SIDH parameters, and effectively breaking even thehighest security levels of SIKE. An earthquake in the isogeny world. A rapid series ofworks followed, culminating in a complete break of the Interpolation problem in any
regime where the input fully determines the hidden isogeny, and the provided points havesmooth order.
Our contribution to the attack first came in the form of the preprint [[Wes22b]], later
published in the merged article [[MMP+ 23]]. In the preprint:• We improve the efficiency of the attack, describing a much more direct approachthan [CD23]. Essentially, Castryck and Decru reconstitute the isogeny bit-by-bit,1.5. THE FALL OF SIDH

37

with iterative trial and error. In contrast, the algorithm in [[Wes22b, MMP+ 23]]
recovers the secret in one go, dividing the complexity by the bit-length of theisogeny. As a result, the attack has become fast enough for constructive applications: it runs in a matter of milliseconds for interesting sets of parameters [[BDD+ 24]].
• We prove that the algorithm runs in polynomial time, assuming the Generalised
Riemann Hypothesis, when the endomorphism ring of the domain curve is known(as in SIKE). In contrast, the original attack relied on heuristic assumptions.
When the endomorphism ring is not known, we point out that the complexity isheuristically subexponential.
Robert then broke another barrier in [Rob23], proving that the polynomial running
time can be reached even when the endomorphism ring of the source is not known.
1.5.1. Isogeny interpolation. In this section we choose to present the algorithm in arather elementary form as in [[Wes22b]], yet including the powerful trick of Robert [Rob23].
The resulting Theorem 1.29 is close to the most general version known today, and benefits
from a simple proof. Simple enough, perhaps, that the reader may come to wonder how
it was missed for eleven years of scrutinizing SIDH.
Theorem 1.29. Let ϕ : E → E 0 be an isogeny. Given:• E, E 0 , deg(ϕ),• an integer N > deg(ϕ) coprime to deg(ϕ),• a basis (P1 , P2 ) of E[N ],• the images ϕ(P1 ) and ϕ(P2 ),• and a point Q ∈ E,
one can compute ϕ(Q) (or assert that the input is ill-formed) in polynomial time in thelength of the input and in the largest prime factor of N .
Remark 1.30. Note that the statement can be improved by a number of other tricks: one
can remove the coprimality condition, loosen the bound to N 2  deg(ϕ), or replace E[N ]with more general subgroups.
The critical insight of Castryck and Decru came from looking at isogenies in higher
dimension. For a complete picture of the situation, one should delve into the theoryof abelian varieties, but for the simplified exposition below, it is sufficient to consider
products of elliptic curves. A product E1 × · · · × En is an abelian variety of dimension n.
Definition 1.31. Consider elliptic curves E1 , . . . , En , E10 , . . . , En0 , and isogenies ϕi,j : Ei →Ej0 . The matrix M = (ϕi,j )i,j defines a map!
X00Φ : E1 × · · · × En −→ E1 × · · · × En : (Pi )i 7−→
ϕi,j (Pi ) .
ij

We call M̃ = (ϕ̂j,i )i,j the dual matrix, which induces the map!
Φ̃ : E10 × · · · × En0 −→ E1 × · · · × En : (Pi )i 7−→Xi

ϕ̂j,i (Pi ).
j

We say that Φ is an N -isogeny, for N ∈ Z>0 , if M̃ M = N ·In (with In the identity matrix).
These N -isogenies are higher-dimensional analogs of “isogenies of degree N ”. In particular, when N is coprime to the characteristic p, an N -isogeny is determined by its kernel(which has order N n ), up to automorphisms of the target. A generalisation of Vélu’s formulae allows to compute an N -isogeny from its kernel, in time polynomial in the largest
prime factor of N . We are going to use the following simplified version of that fact.

38

1. SUPERSINGULAR ISOGENIES AND ENDOMORPHISMS

Lemma 1.32. There is an algorithm such that for any N -isogeny Φ : X → Y over Fq thefollowing holds: given X, Y , a generating set of ker(Φ), and points (Pi )ki=1 ∈ X(Fq )k , thealgorithm returns (ν ◦ Φ(Pi ))ki=1 for some ν ∈ Aut(Y ) in polynomial time in q and in thelargest prime factor of N .
The reader familiar with theta models of abelian varieties can deduce this lemma
from [LR12].
The strategy of the attack is the following. There is a secret isogeny ϕ : E → E 0 ,which we only know how to evaluate on the N -torsion, for some N (indeed, we know theimage of a basis of E[N ], and N being smooth, we can efficiently rewrite any N -torsion
point as a combination of the basis points, by a discrete logarithm computation). We cancraft a matrix of isogenies containing ϕ as one of the entries, and the other entries arecarefully chosen for the resulting matrix to define an N -isogeny. Each entry of the matrix
can be evaluated on the N -torsion, which allows us the reconstruct the kernel (a subgroupof the N -torsion). From the kernel, we can evaluate the N -isogeny on any other input(Lemma 1.32), which in turn allows us to evaluate any entry of the matrix, including ϕ,on any input.
This strategy is most easily implemented when N − deg(ϕ) is a perfect square.
Proposition 1.33. Theorem 1.29 holds if A = N − deg(ϕ) is a perfect square.
√
Sketch of the proof. Let a = A ∈ Z. Consider the isogeny[a] −ϕ̂Ψ=: E × E 0 −→ E × E 0 .
ϕ [a]Let ι : E → E × E 0 be the inclusion and π : E × E 0 → E 0 be the projection. We haveπ ◦ Ψ ◦ ι(Q) = π ◦ Ψ(Q, 0) = π([a]Q, ϕ(Q)) = ϕ(Q).
Therefore, if we can evaluate Ψ, we can evaluate ϕ = π ◦ Ψ ◦ ι. We show that we canevaluate Ψ by proving that it is an N -isogeny, and we know its kernel. Indeed, we have[a] ϕ̂
[a] −ϕ̂Ψ̂ ◦ Ψ =−ϕ [a]ϕ [a] 2
[a + deg(ϕ)]
0== N · I2 ,0
[a2 + deg(ϕ)]
so Ψ is an N -isogeny. Furthermore, we haveker(Ψ) = {(P, Q) ∈ (E × E 0 )[N ] | [a]P = ϕ̂(Q) and ϕ(P ) = −[a]Q}= {([−a]P, ϕ(P )) | P ∈ E[N ]}= h([−a]P1 , ϕ(P1 )), ([−a]P2 , ϕ(P2 ))i ,so we have a generating set for ker(Ψ). By Lemma 1.32, we can evaluate Ψ at any point.
Therefore, we can compute ϕ(Q) by evaluating π ◦ Ψ ◦ ι(Q). Note that Lemma 1.32 only
evaluates ν ◦ ϕ for some unknown ν ∈ Aut(E). This defect can be corrected by applying
the evaluation algorithm to (P1 , P2 , Q), which returns (ν ◦ϕ(P1 ), ν ◦ϕ(P2 ), ν ◦ϕ(Q)). Then,
one can recover ν as the unique automorphism sending each ϕ(Pi ) to ν ◦ ϕ(Pi ).

The general case with known endomorphism ring. Of course, one cannot generally expect
A to be a perfect square. This assumption is used to build an isogeny from E of degree
A: the isogeny [a] : E → E. For arbitrary A, the very same method can be adapted
if one knows an isogeny γ : E → C of degree A: simply use γ in place of [a]. Given
the endomorphism ring of E, one can always find such an isogeny γ in polynomial time

1.6. THE DEVELOPMENT OF SQISIGN

39(assuming GRH [[Wes22b]]), which proves that SIDH is broken in the special case where
the endomorphism ring of the source curve E is known.
The general case. The final nail in SIDH’s coffin was hammered by Robert [Rob23], byusing endomorphisms in higher dimension. The case where A = N − deg(ϕ) is a perfectsquare leverages the√ fact that End(E) contains a very simple endomorphism of norm A:
multiplication by A. Robert observed that if A is a sum of two squares, then End(E ×E)
contains a similarly simple endomorphism of norm A. Writing N − deg(ϕ) = a2 + b2 , wecan do the same as above with
a b −ϕ̂ 0
−b a 0 −ϕ̂Ψ=
 ϕ 0 a −b  .
0 ϕ baNot every integer is a sum of two squares, but all are sums of four squares. In all generality,
one can write N − deg(ϕ) = a2 + b2 + c2 + d2 , and use the matrix
a −b −c −d −ϕ̂ 000b ad −c 0 −ϕ̂ 00  c −d ab00 −ϕ̂ 0 
 d c −b a000 −ϕ̂

.
Ψ=

ϕ
0
0
0
a
b
c
d


0 ϕ
0
0 −b a −d c 


0 0
ϕ
0 −c da −b 
0 0
0
ϕ −d −cbaThis proves Theorem 1.29.
1.5.2. The post-SIDH era. While the resolution of the Interpolation problem inpolynomial time put an end to SIDH, it has not affected the core problems of isogenybased cryptography: EndRing and its friends.
Since its devastating entrance, the interpolation algorithm has become a powerful constructive tool for isogeny-based cryptography. Indeed, it provides a new way to represent
isogenies: given the degree d, a basis (P1 , P2 ) of the N -torsion of the source (for somelarge enough, smooth N ), and the images (ϕ(P1 ), ϕ(P2 )), one can evaluate the isogeny
ϕ on any other input. In other words, the tuple (d, P1 , P2 , ϕ(P1 ), ϕ(P2 )) is an efficient
representation of ϕ — called the interpolation representation, or the HD representation
due to the role of higher dimensions. Contrary to previous methods like the isogeny-path
representation, it works for arbitrary isogenies, even with large prime degree. In fact, it
is in a sense a universal efficient representation: any efficient representation of an isogeny
can be converted to an interpolation representation in polynomial time.
The first constructive application of this method was the digital signature scheme
SQIsignHD, discussed in the next section. The subsequent “HD rush” [CLP23, BMP23,
Ler23] came along practical improvements of the “HD machinery”: fast algorithms toevaluate isogenies in higher dimension [Kun22, DMPR23].
1.6. The development of SQIsign
So far, we have focused on the theoretical foundations and cryptanalysis of isogeny-based
cryptography. We conclude this chapter with a constructive contribution: the SQIsigndigital signature scheme [[DKL+ 20, DLRW24]], whose development is intertwined with all
previously presented results.
There had been several attempts at building an isogeny-based digital signature scheme
before SQIsign. However, they were impractically slow, requiring several seconds [YAJ+ 17],

40

1. SUPERSINGULAR ISOGENIES AND ENDOMORPHISMS

minutes [DG19], or more [GPS20] to sign and verify. The most efficient candidate was CSIFish [BKV19] which still takes approximately half a second to sign or verify, and requires acostly sub-exponential precomputation (currently out of reach beyond the lowest security
level).
The design philosophy of SQIsign is rooted in the equivalence between EndRing and`-IsogenyPath presented in Section 1.3. The idea is the following. In a digital signaturescheme, a signer holds a secret key sk and a public key pk. A signature scheme consists in(1) a signing procedure: on input the secret key sk, and a message m, the signer
produces a signature σ. We expect this task to absolutely require knowledge ofthe secret key, so only the legitimate key holder can produce a valid signature.
(2) a verification procedure: on input the public key pk, a message m, and a signature
σ, the verification certifies whether or not σ was indeed produced by the signing
procedure on input m, with the secret key associated to pk.
In SQIsign, the public key is a supersingular elliptic curve pk = E, and the secret key is its
endomorphism ring sk = End(E). Recovering the secret key End(E) from the public key
E is precisely EndRing, a supposedly hard problem. This is a good start. To design asigning procedure, we need a task that can only be performed with knowledge of End(E).
This is where the equivalence between EndRing and `-IsogenyPath comes in. At least
on an intuitive level, if signing requires solving an instance of `-IsogenyPath involving
E, the signer must know End(E), the secret key. This suggests a signing procedure of thisform: let the message m encode some supersingular elliptic curve Em . Using knowledgeof End(E), the signer solves `-IsogenyPath between E and Em . The signature is an`-isogeny path σ : E → Em . A verifier would recompute Em , and check that σ is indeed
a path between the “message curve” Em and the public key E.
1.6.1. The SQIsign identification protocol. To turn this intuition into a securescheme, it is useful to first design an identification protocol. An identification protocol provides more flexibility, and can be transformed into a signature scheme by standard
techniques (e.g., via the Fiat-Shamir transform [FS86]). A prover (instead of a signer)knows the pair (sk, pk), and tries to convince a verifier (who knows only pk) that theyknow the secret sk. The main difference with a signature scheme is that the prover andverifier can directly interact, exchanging messages back and forth.
The SQIsign identification protocol, introduced in [[DKL+ 20]], has the following structure (which the reader may recognize to be a sigma protocol):(1) Commitment phase: the prover generates a random pair (Ecom , End(Ecom )).
They keep End(Ecom ) secret, and send Ecom to the verifier.
(2) Challenge phase: the verifier generates a non-backtracking random walk ϕchl :E → Echl of length n in the 2-isogeny graph (for some fixed n). In other words,
ϕchl is a random isogeny of degree 2n with cyclic kernel. The verifier sends ϕchl
to the prover.
(3) Response phase: knowing the secret key sk = End(E) and ϕchl : E → Echl , theprover can compute End(Echl ). Now, knowing both End(Echl ) and End(Ecom ),the prover can compute an isogeny ϕrsp : Ecom → Echl . The prover sends ϕrsp to
the verifier.
(4) Verification phase: the verifier checks that ϕrsp is indeed an isogeny connecting
the commitment curve Ecom to the challenge curve Echl .
Intuitively, at the end of a successful interaction, the verifier should be convinced because
they saw the prover solve an instance of `-IsogenyPath involving E — a task that should
require knowledge of End(E). More precisely, the instance involves Echl rather than E,
but given the isogeny ϕchl : E → Echl , knowledge of End(E) is equivalent to knowledge of1.6. THE DEVELOPMENT OF SQISIGN

41

End(Echl ). Of course, we will give a formal argument, but first, a fatal flaw needs to be
fixed. As it is presented, a cheating prover (who does not know the secret End(E)) can
fool the verifier. Indeed, the cheating prover could generate a commitment curve Ecomby choosing a random isogeny ϕcheatcom : E → Ecom . They may not be able to compute
End(Ecom ), but it does not matter. In response to a challenge ϕchl : E → Echl , they would
simply respond with ϕcheat= ϕchl ◦ ϕ̂cheat
rsp
com .
There is a simple fix to this issue, by ensuring that no part of the response ϕrsp factors
through the challenge ϕchl . More precisely: the prover ensures (and the verifier checks)
that ϕ̂chl ◦ ϕrsp has cyclic kernel.
1.6.2. Special soundness. With this fix, one can actually prove that this protocol“proves knowledge” of at least some non-trivial part of End(E). Proving knowledge canbe formalized via a property called special soundness. A transcript of the protocol is thesequence of messages exchanged, i.e., the tuple (Ecom , ϕchl , ϕrsp ); it is accepting if the corresponding verification succeeds. We say that the above protocol has special soundness
if, given two accepting transcripts (Ecom , ϕchl , ϕrsp ) and (Ecom , ϕ0chl , ϕ0rsp ) with the samecommitment Ecom but distinct challenges ϕchl 6= ϕ0chl , one can find a non-scalar endomorphism of E. The motivation for this definition is the following. If a prover can successfully
respond to the challenge with good probability, then they can respond to at least two distinct challenges (for a fixed commitment). If they can respond to two distinct challenges
for one fixed commitment, then the prover is capable of producing two accepting transcripts (Ecom , ϕchl , ϕrsp ) and (Ecom , ϕ0chl , ϕ0rsp ) with ϕchl 6= ϕ0chl . With special soundness,this implies that the prover is capable of finding a non-scalar endomorphism of E.
In other words, if the protocol has special soundness, then a good prover (one who can
successfully respond with good probability) necessarily knows a non-scalar endomorphismof E. Only one non-scalar endomorphism, and not the full ring sk = End(E)? Yes, but
one is sufficient: as proved in Section 1.4, finding one non-scalar endomorphism is as hard
as finding them all.
Proposition 1.34. The SQIsign identification protocol has special soundness.
Sketch of the proof. Suppose we have two accepting protocol transcripts (Ecom , ϕchl , ϕrsp )and (Ecom , ϕ0chl , ϕ0rsp ) with distinct challenges ϕchl 6= ϕ0chl . Then, by construction, α =ϕ̂0chl ◦ ϕ0rsp ◦ ϕ̂rsp ◦ ϕchl is in End(E). It remains to prove that it is not a scalar. By
contradiction, suppose α = [λ] for some λ ∈ Z. We deduceϕ̂0rsp ◦ ϕ0chl ◦ [λ] = [deg(ϕ0chl ) deg(ϕ0rsp )] ◦ ϕ̂rsp ◦ ϕchl .
Since both ϕ̂0rsp ◦ ϕ0chl and ϕ̂rsp ◦ ϕchl have cyclic kernel (thanks to the “fix” against thecheating prover!), we deduce that λ = deg(ϕ0chl ) deg(ϕ0rsp ) (the largest integer dividing
the left- and right-hand side respectively), hence ϕ̂0rsp ◦ ϕ0chl = ϕ̂rsp ◦ ϕchl . As deg(ϕchl ) =deg(ϕ0chl ) = 2n , we getker(ϕchl ) = ker(ϕ̂rsp ◦ ϕchl )[2n ] = ker(ϕ̂0rsp ◦ ϕ0chl )[2n ] = ker(ϕ0chl ).
This contradicts the fact that ϕchl and ϕ0chl are distinct non-backtracking paths.



1.6.3. The response. The response phase can be summarized as follows: knowing bothEnd(Echl ) and End(Ecom ), the prover can compute in polynomial time an isogeny ϕrsp :Ecom → Echl . The prover sends this “response isogeny” ϕrsp to the verifier.
Implementing this idea in a secure way is not as straightforward as this summary suggests. The tricky part is that the response ϕrsp (and the way it is encoded) should notleak any non-trivial information about the secret. A naive application of the reduction
from `-IsogenyPath to EndRing (via MaxOrder) following Section 1.3.4 will resultin a solution ϕrsp : Ecom → Echl which “passes through” the special curve E0 : it factors

42

1. SUPERSINGULAR ISOGENIES AND ENDOMORPHISMS

as ϕrsp = ϕ2 ◦ ϕ1 with ϕ1 : Ecom → E0 and ϕ2 : E0 → Echl . From such a response ϕrsp , acurious verifier can extract the factor ϕ2 : E0 → Echl , and since the endomorphism ring of
E0 is publicly known, they can recover End(Echl ). From End(Echl ) and ϕchl : E → Echl ,they can recover the secret key End(E).
One needs a better way to generate a response, one which would not leak the secret.
In formal terms, we want the protocol to have the zero-knowledge property. SQIsign[[DKL+ 20]] and SQIsignHD [[DLRW24]] propose two distinct ways to select and represent the
response. The set of possible responses is the space
Hom(Ecom , Echl )of isogenies from Ecom to Echl (and the zero map). It is a lattice of rank 4, with a Euclidean
structure induced by the positive definite integral quadratic form deg : Hom(Ecom , Echl ) →Z. The methods discussed in Section 1.3 show that given End(Echl ) and End(Ecom ), one
can find an isogeny Ecom → Echl ; from there, one can deduce not just one isogeny, but acomplete basis of Hom(Ecom , Echl ).
The original SQIsign. SQIsign [[DKL+ 20]] selects the response as follows:(1) Fix a large enough power of two 2n , and solve the norm equation deg(ϕ) = 2nfor ϕ ∈ Hom(Ecom , Echl ) (in other words, find a lattice point of prescribed norm).
We show in SQIsign [[DKL+ 20]] that this can be done in polynomial time by avariant of [KLPT14], without “passing through” the special curve E0 .
(2) The solution ϕ is initially represented as a formal linear combination of the basisof Hom(Ecom , Echl ). This representation cannot be revealed: it would leak thebasis, which would leak the secret. Instead, it is converted to a 2-isogeny path oflength n. This path is the response.
There are two issues with this approach. The first is efficiency. For Step 1, one needs 2nof the order of p3.5 , and converting such a large isogeny into a 2-isogeny path is costly.
After algorithmic improvements and low-level optimizations, we showed in [[DLLW23]] thatsignatures can be computed in the order of 400ms (for the NIST-I security level, which isroughly 128 bits of classical security). While not absurdly slow, it is orders of magnitudes
slower than other post-quantum signature schemes (for instance, from the family of latticebased cryptography).
The second issue concerns the security proof. It is difficult to argue that this response
is zero-knowledge, that it does not leak any information about the secret. The reason isthat the distribution of the solution ϕ of the norm equation is rather mysterious. While wecan check that ϕ does not “pass through” a special curve E0 , there is no formal guaranteethat this carefully crafted ϕ is totally innocuous. To prove the zero-knowledge property
in [[DKL+ 20]], we resort to a heuristic assumption about the norm equation solver. Thissituation is unsatisfactory.
On the bright side, public keys and signatures are very compact. For the NIST-I
security level, public keys are 64 bytes, and signatures are 205 bytes. In particular, thesignature and public key sizes combined are an order of magnitude smaller than all otherpost-quantum signature schemes (they are 5.8 times smaller than the lattice-based scheme
Falcon [PFH+ 17]).
SQIsignHD. SQIsignHD [[DLRW24]] resolves both drawbacks, bringing down the signing
time to the order of 30ms, and enabling a much cleaner security proof. The signatures
are even more compact, at a record-breaking 109 bytes for the NIST-I security level. Thisleap forward was enabled by the algorithmic breakthrough underlying the attack on SIDH.
As discussed in Section 1.5.2, the attack provides a new way to represent an isogeny ϕ:1.6. THE DEVELOPMENT OF SQISIGN

43

the interpolation representation (deg(ϕ), P1 , P2 , ϕ(P1 ), ϕ(P2 )), where (P1 , P2 ) is a basis ofa sufficiently large torsion subgroup. This representation applies to arbitrary isogenies,
unlike the very constrained `-isogeny path representation.
SQIsignHD selects the response as follows:(1) Fix a bound r > 0, and sample a uniformly random ϕ ∈ Hom(Ecom , Echl ) ∩ B(r),where B(r) = {ϕ | deg(ϕ) < r2 } is the ball of radius r (with respect to thequadratic form deg).
(2) The solution ϕ is initially represented as a formal linear combination of the basisof Hom(Ecom , Echl ). Consider a basis (P1 , P2 ) of E[2n ] for n sufficiently large,
and represent the response isogeny ϕ as (deg(ϕ), P1 , P2 , ϕ(P1 ), ϕ(P2 )).
In contrast with the mysterious distribution of ϕ in the original SQIsign, the uniform
distribution ϕ ∈ Hom(Ecom , Echl ) ∩ B(r) is well-understood, making it much easier toprove that this response does not leak any information about the secret.
SQIsignHD comes at a cost: the verifier has to check that the tuple(deg(ϕ), P1 , P2 , ϕ(P1 ), ϕ(P2 ))indeed represents an isogeny Ecom → Echl . To do so, they need to evaluate it with
the interpolation algorithm, Theorem 1.29. This requires the computation of an isogeny
between abelian varieties of dimension 2, 4 or 8. When 2n − d is a perfect square, a2-dimensional isogeny is sufficient. When 2n − d is a sum of two squares, one can use a4-dimensional isogeny. In all other cases, one needs an 8-dimensional isogeny.
In [[DLRW24]], we propose two constructions:• SQIsign8D: this version benefits from a fully rigorous security analysis, but requires the computation of an isogeny in dimension 8. This has not been implemented, and is likely to be impractical.
• SQIsign4D: this version benefits from essentially the same security proof, but
requires heuristic assumptions. These heuristics account for the fact that 2n − dis restricted to sums of two squares. The computation of a 4-dimensional isogeny
is more practical, but no optimized implementation is available yet.
In the recent preprint [[BDD+ 24]], we successfully devise a variant in dimension 2, which
cumulates the advantages of all other variants. It benefits from a heuristic-free security
proof, and boasts a verification time of the order of 4.5ms, and a signing time of the orderof 80ms (even 50ms for a heuristic variant) on a 2GHz processor Intel Xeon Gold 6338
(Ice Lake). There is today significant activity around SQIsign, and improvements arearriving fast [SEMR23, RK24, JMKR23]. What could have been considered a prohibitively
slow construction a few years ago is becoming increasingly competitive. It is currently
submitted to the call for standardization of post-quantum digital signature schemes by
the American National Institute of Standards and Technology (NIST).

2
Oriented elliptic curves
In this chapter, we present contributions that relate to oriented elliptic curves and theirapplications in cryptography. Orientations bring the methods of complex multiplication
to supersingular elliptic curves. In particular, they induce an action of class groups onsupersingular curves. The presumed hardness of inverting this action is the foundation of
the “group action” branch of isogeny-based cryptography. We explore the connection ofthis branch with the rest of isogeny-based cryptography, showing that it is also supportedby the hardness of computing endomorphisms. We study the fastest algorithms for theunderlying problems, and build collections of orientations with useful properties.
This chapter is built around the presentation of the articles (in order of appearance):[[Wes22a]]

Benjamin Wesolowski. Orientations and the supersingular endomorphismring problem. In Orr Dunkelman and Stefan Dziembowski, editors, Advances in Cryptology – EUROCRYPT 2022, volume 13277 of Lecture Notes
in Computer Science, pages 345–371. Springer, 2022.

[[HW23]]

Arthur Herlédan Le Merdy and Benjamin Wesolowski. The supersingularendomorphism ring problem given one endomorphism. Cryptology ePrint
Archive, Paper 2023/1448, 2023. https://eprint.iacr.org/2023/1448.

[[DFK+ 23]]

Luca De Feo, Tako Boris Fouotsa, Péter Kutas, Antonin Leroux, SimonPhilipp Merz, Lorenz Panny, and Benjamin Wesolowski. SCALLOP: scaling
the CSI-FiSh. In Alexandra Boldyreva and Vladimir Kolesnikov, editors,
Public-Key Cryptography – PKC 2023, volume 13940 of Lecture Notes in
Computer Science, pages 345–375. Springer, 2023.

2.1. Introduction
The Diffie–Hellman key exchange is among the most emblematic protocols of modern
cryptography. Introduced in 1974 [DH76], this paradigm-defining protocol allows two parties, Alice and Bob, to establish a shared secret (a key) over an insecure communication
channel. It is remarkably simple. Alice and Bob first agree on a cyclic group G (written
multiplicatively) and a generator g of this group. Alice secretly chooses a random integera, and sends the group element g a to Bob via the public communication channel. On hisside, Bob also chooses a random integer b, and sends g b to Alice. Both of them are now

46

2. ORIENTED ELLIPTIC CURVES

able to compute the value(g a )b = (g b )a ,a shared secret, to be used as a key to encrypt subsequent communications. An outsider
eavesdropping on the communication channel knows g, g a and g b . Recovering the sharedvalue g ab from this information should be infeasible, and is known as the computational
Diffie-Hellman problem. This problem, and the security of the protocol, is closely tied tothe presumed hardness of the discrete logarithm problem in the group G: given g a , recovera. Diffie and Hellman suggested to choose for group G the multiplicative group F×
q of afinite field. A more modern choice for G is the group of rational points E(Fq ) of an elliptic
curve over a finite field, in which the discrete logarithm problem seems to be as hard as it
gets. Not only the Diffie–Hellman key exchange has remained to this day one of the mostcommonly used cryptographic protocols securing the Internet, it has sparked a long seriesof cryptosystems whose security relies on the hardness of computing discrete logarithms.
Shor’s quantum algorithm [Sho97] is capable of solving the discrete logarithm problem
in polynomial time in any group, rendering the Diffie–Hellman protocol and its lineage
obsolete in a post-quantum world. Yet, it can be rescued, by replacing the group exponentiation (a, g) 7→ g a with some other group action. A group action of a group G (withneutral element e) on a set X is a map? : G × X −→ X : (g, x) 7−→ g ? xsuch that for any x ∈ X and g, h ∈ G, we have
• Compatibility: g ? (h ? x) = (gh) ? x, and• Identity: e ? x = x.
We say that the action is effective if the group operations and group action can be computed efficiently (as well as other natural tasks, like sampling random group elements).
Such group actions are a powerful tool to build cryptographic schemes. For instance, when
G is abelian, we can immediately generalize the Diffie–Hellman key exchange:(1) Alice and Bob agree on an effective group action, and on a “reference point”
x0 ∈ X.
(2) Alice samples a random secret element gA ∈ G, and sends xA = gA ? x0 ∈ X to
Bob.
(3) Similarly, Bob samples a secret gB ∈ G, and sends xB = gB ? x0 ∈ X to Alice.
(4) Alice can compute xAB = gA ? xB , and Bob can compute xBA = gB ? xA .
The compatibility property and the commutativity of the group imply that xAB = xBA ;it is Alice’s and Bob’s shared secret. An eavesdropper can intercept x0 , xA = gA ? x0 and
xB = gB ? x0 . A cryptographic group action is one for which recovering the shared secretfrom the intercepted data is hard. In particular, it must be hard to “invert” the group
action: given x, y ∈ X, compute g such that y = g ? x, when it exists. This problem isknown as the group action inversion problem, or the vectorisation problem.
The Diffie-Hellman protocol is a particular case of the above protocol, where the action
is given by exponentiation in a finite cyclic group. Given a finite abelian group G of order
N , we have an effective action(Z/N Z)× × G 7−→ G : (n, g) 7−→ g n .
The corresponding vectorisation problem is the discrete logarithm problem: given g and
g n , compute n. But while Shor’s algorithm can solve the discrete logarithm problem, no
polynomial time (quantum) algorithm is known for the vectorisation problem is general.
An effective group action which is “hard to invert” even for quantum algorithms would
lead to a post-quantum Diffie–Hellman, and may bring to the post-quantum world many
“discrete logarithm”-based cryptosystems.

2.1. INTRODUCTION

47

Complex multiplication. Couveignes proposed in 1997 [Cou06] to use a group action arisingfrom the theory of complex multiplication. The endomorphism ring of an elliptic curve E
over C is either Z or an order O in a quadratic number field. In the latter case, we saythat E has complex multiplication by O. A central result of the theory states that theclass group Cl(O) acts (freely and transitively!) on the collection E``C (O) of isomorphismclasses of elliptic curves with complex multiplication by O.
This result reduces to finite fields. An elliptic curve over Fp is ordinary when its
endomorphism ring is an order O in a quadratic number field. Complex multiplicationinduces an action? : Cl(O) × E``p (O) −→ E``p (O),where E``p (O) is the collection of isomorphism classes of pairs (E, ι) where E is an elliptic curve over Fp and ι : O → End(E) is a ring isomorphism. Couveignes conjectured
in [Cou06] that the vectorization problem for this action is hard to invert, and it can beused in the generalized Diffie–Hellman key exchange.
This idea did not get much attention for a while. First, there was no “post-quantum”
motivation yet. That changed in 2006 when Rostovtsev and Stolbunov independently
rediscovered the idea [RS06], this time with the observation that the corresponding vectorization problem seemed hard even for quantum computers. Second, and perhaps more
importantly, computing the action appeared to be very inefficient, making it unsuitable
for any real-world application. Indeed, the best algorithms to compute this action arevery sensitive to the degree of the field over which certain torsion subgroups are defined.
It is very difficult to find ordinary elliptic curves in which the torsion behaves well enough.
That, in turn, changed with the development of CSIDH in 2018 [CLM+ 18], combining two
observations:(1) the torsion is much easier to control for supersingular elliptic curves, and(2) there is a similar group action for supersingular elliptic curves.
The idea is to use supersingular elliptic curves E defined over a prime-order field Fp (rather
than the general case Fp2 ). Then, the subring Z[π] ⊂ End(E) generated by the Frobenius
endomorphism π is a quadratic order, and we have an action of Cl(Z[π]) like in the ordinarycase.
Orientations. The notion of orientation introduced by Colò and Kohel [CK20] provides a
generalized framework for these group actions, and have since proved to play a ubiquitousrole in isogeny-based cryptography. Given a quadratic order O, and an elliptic curve E,
an O-orientation of E is an embeddingι : O −→ End(E).
The pair (E, ι) is an O-oriented curve. More precise definitions are provided in Section 2.2.
Orientations generalize complex multiplication by providing an action? : Cl(O) × E``p (O) −→ E``p (O),where E``p (O) is the collection of isomorphism classes of (primitively) O-oriented elliptic
curves over Fp .
Remark 2.1. The curves in E``p (O) are either all ordinary (and coincide with the definitionof E``p (O) for ordinary curves given in the previous paragraph), or all supersingular.
The vectorization problem for this group action is the O-Vect problem. Its presumed hardness for interesting families of orders O is the foundation of many cryptosystems [CLM+ 18, DG19, CLP23], [[DFK+ 23]].
2.1.1. Contributions and organisation of the chapter. The chapter is organized asfollows.

48

2. ORIENTED ELLIPTIC CURVES

Oriented elliptic curves. We start in Section 2.2 by presenting some background aboutoriented elliptic curves. We provide the basic definitions, discuss how to represent andmanipulate them computationally, and how to compute the action of the class group. We
sketch a parallel with the classical theory of ordinary elliptic curves and isogeny volcanoes.
Orientations and the supersingular endomorphism ring problem. The O-Vect problem
can be seen as an isogeny problem (the action of an ideal on an oriented curve corresponds to some kind of isogeny — see Section 2.2). Yet, this vectorization problem looks
substantially different from the computational problems studied in Chapter 1. Does theendomorphism ring problem still play a foundational role in the “group action” subfamilyof isogeny-based cryptography?
In Section 2.3, we present the positive answer obtained in the article [[Wes22a]]. The
main result, Theorem 2.18, states that the vectorization problem for the action of Cl(O)is equivalent to the endomorphism ring problem for O-oriented curves. In particular, thesecurity of the CSIDH cryptosystem [CLM+ 18] is equivalent to the problem of computing
the endomorphism ring of supersingular curves defined over Fp .
In the same article, we study the closely related problem O-Uber (introduced in thearticle [[DDF+ 21]]), and prove that it is equivalent to a harder variant of the endomorphismring problem.
The supersingular endomorphism ring problem given one endomorphism. In Section 2.4,
we discuss the concrete hardness of the problem O-Vect, through the results of the article [[HW23]]. More precisely, the article [[HW23]] considers the following problem: given asupersingular curve and one of its endomorphisms (non-scalar), find all the other endomorphisms. Knowing one endomorphism is essentially the same as knowing an orientation,
so thanks to the equivalences of [[Wes22a]], this “endomorphism ring problem given one
endomorphism” is essentially equivalent to O-Vect. Only “essentially”, because of animportant nuance about the so-called primitivity of orientations. As a first step, we close
this gap by proving in [[HW23]] that any orientation can efficiently be made primitive (Theorem 2.22).
We then solve O-Vect (hence the endomorphism ring problem given one endomorphism). The fastest algorithms formerly required heuristic assumptions, and we provethat the same running times can be achieved under the Generalized Riemann Hypothesis(Theorem 2.20).
Knowing the structure of the acting group. Orientations provide a powerful framework
to build cryptographic group actions. The acting group is the class group Cl(O) of aquadratic order. Computing the structure of a class group (even its order) is a notoriously
difficult task (which we investigate further in Section 3.5.2). Interestingly, one does notneed to know the structure of Cl(O) to compute its action on oriented curves, and run a
Diffie–Hellman-like protocol. Still, the mystery around Cl(O) has proved to be a sourceof difficulty [BKV19], and a better understanding of the acting group may unlock moreadvanced cryptographic applications.
In Section 2.5, we present the result of the article [[DFK+ 23]]: how to construct a familyof oriented curves for easy-to-compute class groups Cl(O). We discuss its security, andhow the careful choice of the order O impacts the hardness of the associated vectorization
problem.
2.2. Oriented elliptic curves
Let K be a quadratic number field, and let O be an arbitrary order in K.

2.2. ORIENTED ELLIPTIC CURVES

49

Definition 2.2 (Orientation). A K-orientation on an elliptic curve E is an embeddingι : K ,→ End(E) ⊗ Q. It is an O-orientation if ι(O) ⊆ End(E). It is a primitive Oorientation if ι(O) = ι(K)∩End(E). Such a pair (E, ι) is called a (primitively) O-oriented
elliptic curve, and we say that E is (primitively) O-orientable.
Remark 2.3. If (E, ι) is an O-oriented elliptic curve, we will often consider ι as an embedding of O into End(E) (which naturally extends to an embedding of K into End(E) ⊗ Q).
If E is ordinary, the endomorphism algebra End(E) ⊗ Q is itself a quadratic number field, so the curve can only be K-oriented if K ∼= End(E) ⊗ Q, and there are# Gal(K/Q) = 2 distinct K-orientations. The situation is much richer for supersingular elliptic curves, since infinitely many quadratic fields embed in infinitely many ways
in the quaternion algebra Bp,∞ ∼= End(E) ⊗ Q. The choice of an orientation (i.e., of aquadratic subfield of End(E) ⊗ Q) allows one to transpose ideas and theorems from theclassical theory of complex multiplication to the context of supersingular elliptic curves.
Given a K-oriented elliptic curve (E, ι), any isogeny ϕ : E → E 0 induces a Korientation ϕ∗ (ι) on E 0 defined asϕ∗ (ι)(α) = (ϕ ◦ ι(α) ◦ ϕ̂) ⊗1.
deg(ϕ)

Definition 2.4 (Oriented isogeny). Given two K-oriented elliptic curves (E, ι) and (E 0 , ι0 ),an isogeny ϕ : (E, ι) → (E 0 , ι0 ) is K-oriented if ι0 = ϕ∗ (ι).
We write E``p (O) for the set of primitively O-oriented elliptic curves over Fp up to
K-oriented isomorphism.
Proposition 2.5 ([Onu21, Proposition 3.2]). The curves in E``p (O) are supersingular if
and only if p does not split completely in K and does not divide the conductor of O.
In this chapter, we only consider the supersingular case: we assume throughout thatp does not split completely in K and does not divide the conductor of O.
Class groups acting on sets of elliptic curves. Fix an oriented curve (E, ι) ∈ E``p (O). An
O-ideal a induces a subgroup\
E[a] =
ker(ι(α)),α∈aand a separable isogeny ϕa : E → E a of kernel E[a] called the a-multiplication. The target
E a is the a-transform of (E, ι). This construction induces an action of O-ideals on the set
E``p (O), defined bya ? (E, ι) = (E a , (ϕa )∗ (ι)),
which factors through Cl(O). This action, well understood for ordinary elliptic curves withcomplex multiplication, was first studied in the context of oriented supersingular curves
in [CK20] and [Onu21].
Theorem 2.6 ([Onu21]). The action
Cl(O) × E``p (O) −→ E``p (O) : ([a], (E, ι)) 7−→ a ? (E, ι)is free and has one or two orbits. For any orbit A, and any (E, ι) ∈ E``p (O), either(E, ι) ∈ A, or both (E, ι) and (E (p) , ι(p) ) are in A. Here, ι is the orientation ι composedwith the canonical involution, and ι(p) is the orientation induced by the Frobenius isogeny.
Proof. This theorem combines [Onu21, Proposition 3.3] and [Onu21, Theorem 3.4]. The
statement about (E, ι) is from the proof of [Onu21, Proposition 3.3].


50

2. ORIENTED ELLIPTIC CURVES

Figure 2.1. A (truncated) 3-isogeny volcano. The cycle at the top is
the crater (level 0). The points just below the surface are at level 1, andpoints below them are at level 2. The full volcano continues to lower levels,
forming an infinite (3 + 1)-regular graph.
2.2.1. Isogeny volcanoes. If (E, ι) is a primitively O-oriented curve, and ϕ : (E, ι) →(E 0 , ι0 ) is a K-oriented isogeny, the target (E 0 , ι0 ) is not necessarily primitively O-oriented.
It could be primitively oriented by another order in K, inducing the following classificationof isogenies.
Definition 2.7. Let ϕ : (E, ι) → (E 0 , ι0 ) be a K-oriented isogeny, and suppose that ι is aprimitive O-orientation, and ι0 a primitive O0 -orientation. If deg(ϕ) is prime then one of
the following three possibilities holds:• the isogeny is horizontal when O = O0 ,• the isogeny is ascending when O ( O0 (then, [O0 : O] = deg(ϕ)), and• the isogeny is descending when O ) O0 (then, [O : O0 ] = deg(ϕ)).
We say that an isogeny of composite degree is horizontal, ascending or descending if it
factors as prime degree isogenies all of that same type.
This classification of isogenies gives the graph of oriented `-isogenies the structure of
an isogeny volcano, as in the classical case of ordinary curves [FM02]. Let K be a quadratic
number field, and[E``p (K) =E``p (O)O⊂K

be the collection of isomorphism classes of K-oriented curves. Let ` 6= p be a prime
number, and consider the graph with vertex set E``p (K), and with edges representing
oriented `-isogenies between them.
Recall that any order O in K is of the form O = Z + f OK , where OK is the maximal
order, and f = [OK : O] is the conductor of O. This classification organises the graph inlevels: the level of a vertex (E, ι) ∈ E``p (O) is the valuation at ` of the conductor of O.
Ascending isogenies go from level i to level i − 1, horizontal isogenies preserve the level,and descending isogenies go from level i to level i + 1. Each connected component of thegraph is called an `-isogeny volcano, due to its particular shape (see Figure 2.1):• Horizontal isogenies only exist at level 0 (known as the crater). The subgraphformed by the crater is regular of degree d ≤ 2.
• From any vertex in the crater, there are d horizontal `-isogenies, and ` + 1 − ddescending `-isogenies.
• From any vertex below the crater, there is 1 ascending `-isogeny, and ` descending`-isogenies.
Remark 2.8. A similar structure arises on the side of quaternions, through the Deuringcorrespondence (see Section 1.3.1). Instead of oriented curves, one can consider “oriented
orders” in the quaternion algebra Bp,∞ . Let O ⊂ Bp,∞ be a maximal order, and ι :K → Bp,∞ an embedding. Let O ⊂ K be an order. The pair (O, ι) is a primitively Ooriented order if ι(O) = O∩ι(K). A left O-ideal I is ascending (respectively horizontal, or2.2. ORIENTED ELLIPTIC CURVES

51

descending), if OR (I) ∩ ι(K) ) ι(O) (respectively OR (I) ∩ ι(K) = ι(O), or OR (I) ∩ ι(K) (ι(O)). Ascending, horizontal, or descending ideals correspond to ascending, horizontal,
or descending isogenies through the Deuring correspondence, and we similarly obtain
volcanoes of oriented orders.
2.2.2. Computing the action of the class group. We conclude this section with afew words on the first computational question raised by the class group action: given a and(E, ι), compute a ? (E, ι). Any cryptographic application exploiting this action requires
an efficient algorithm for this task — if not for any a, at least for some interesting familyof ideals.
Computationally, an O-orientation ι is encoded as a generator ω of O together with anefficient representation (Definition 1.3) of the endomorphism ι(ω). An ideal a is encoded
as a pair (α, N ) where N = N (a) is the norm and α ∈ a is an element such that a = hα, N i.
2.2.2.1. The classical method. There is a simple algorithm to compute a ? (E, ι) in timepolynomial in the length of the encoding of (E, ι), in log(N (a)) and in the largest primepower factor of N (a). It consists in factoring a into a product of prime ideals, and applying
the action of each factor iteratively. For l a prime ideal of norm `, we proceed as follows:(1) Write l = hα, `i for some α ∈ O.
(2) Generate a basis (P1 , P2 ) of E[`]; compute Qi = ι(α)(Pi ).
(3) Find coefficients a1 , a2 ∈ Z not both divisible by ` such that a1 Q1 + a2 Q2 = 0.
(4) Compute the separable isogeny ϕa : E → E a with kernel E[l] = ha1 P1 + a2 P2 i.
(5) Return a ? (E, ι) = (E a , (ϕa )∗ (ι)).
Each step can be performed within the claimed running time. A first bottleneck is therequirement to work with a basis of E[`]: in the worst case, it requires looking for points
in a field extension of degree O(`) — while polynomial time in `, this can be very costly
in practice. One may want to restrict the action to primes ` such that the points in E[`]are defined over the base field Fp2 or a small extension.
The orientation (ϕa )∗ (ι) deserves more attention: it needs to be represented in an efficient way, a way that allows one to evaluate the corresponding endomorphisms (ϕa )∗ (ι)(α)
efficiently. For a while, the only polynomial-time method available was to represent it as
a composition, as it is defined:1(ϕa )∗ (ι)(α) = (ϕa ◦ ι(α) ◦ ϕ̂a ) ⊗.
deg(ϕa )Each factor of the composition can be evaluated efficiently, and the division by deg(ϕa ) = `can be computed in polynomial time in `.
However, this method “degrades” the quality of the representation after iterative applications. Indeed, after applying k actions of l, the resulting orientation requires a divisionby `k — a task that requires exponential time in k in the worst case. Therefore thisclassical method only allows one to evaluate the action of ideals a of powersmooth norm
(meaning that all its prime-power factors are bounded). The result has a “degraded”
representation, making each further action costlier to evaluate.
2.2.2.2. The case of CSIDH. The most emblematic orientation in isogeny-based cryptography is the orientation by the Frobenius used in CSIDH [CLM+ 18]. Let SS(Fp ) be the set ofsupersingular elliptic curves defined over the prime-order field Fp , up to Fp -isomorphism.
E
E
For any E ∈ SS(Fp ), its Frobenius endomorphism φEp satisfies φp ◦ φp = [−p]. Therefore,√
writing π = −p, any E ∈ SS(Fp ) has a Z[π]-orientation given byι : Z[π] −→ End(E) : π 7−→ φEp.
Either this orientation is primitive, or its extension to Z[(1 + π)/2] (when Z[π] is not
maximal) is primitive. Reciprocally, one can show that if E is Z[π]-orientable, then it is52

2. ORIENTED ELLIPTIC CURVES

isomorphic to a curve defined over Fp . Hence the set SS(Fp ) is essentially the union ofE``p (Z[π]) and possibly E``p (Z[(1 + π)/2]) (when Z[π] is not maximal).
One can apply the algorithm from Section 2.2.2.1 to compute the action of ideals, with
one advantage: there is no need to compute the induced orientation (ϕa )∗ (ι), because it isautomatically given by the Frobenius. In particular, there is no “degradation” issue, andone can apply the action of any smooth ideal (instead of powersmooth).
There is another major advantage: choosing a prime of the form p = 4`1 . . . `n − 1
where the `i are distinct odd primes, for any supersingular elliptic curve E over Fp , wehave E[`i ] ⊆ E(Fp2 ). Furthermore, each `i splits in Z[π]. This means that for any i,there are two ideals of norm `i , and their action can be computed using arithmetic in Fp2(even Fp , with finer observations!), as opposed to extensions of degree O(`i ) in general.
This good control of the rationality of torsion subgroups is the reason why CSIDH, using
supersingular curves, is considerably more practical than its ordinary predecessors [Cou06,
RS06].
2.2.2.3. Post-SIDH progress. The fall of SIDH (see Section 1.5) came with a powerful new
tool: the isogeny interpolation algorithm (Theorem 1.29). In the article [[HW23]], we exploit
this tool to break the “powersmooth” barrier of the classical action-evaluation algorithm:
we describe an algorithm to compute the action of any smooth ideal in polynomial time.
This is explained in more detail in Section 2.4.1. The last barrier was lifted by Page andRobert in [PR23], where they describe a polynomial time algorithm to evaluate the actionof any ideal. The practicality of [PR23] is not yet clear, and former methods may remain
the preferred choice in certain contexts.
2.3. Orientations and the supersingular endomorphism ring problem
The action of class groups on oriented supersingular curves can be used to build cryptosystems. Since this action is defined by isogenies, it naturally qualifies as “isogenybased cryptography”. Yet, it feels like a substantially different paradigm from the kind of
isogeny-based cryptography explored in Chapter 1.
In the article [[Wes22a]], we prove a strong connection between the endomorphism ringproblem and the problem of inverting the group action. These computational equivalences
further reinforce the foundational status of the endomorphism ring problem: its presumed
hardness also governs the security of the “group action” family of isogeny-based cryptography. In particular, the reductions imply that the security of the CSIDH cryptosystem
is equivalent to a version of the endomorphism ring problem. In this section, we present
this bridge between class group problems and endomorphism ring problems, culminatingin Theorem 2.18, the main result of [[Wes22a]].
2.3.1. Class group action problems. Recall the motivation for O-orientations: they
induce a group action, and if this group action is “hard to invert”, then we can build secure
cryptographic protocols. Inverting the group action is formalized as the vectorization
problem. Let us specialize this notion to the context of oriented curves.
Definition 2.9 (O-Vect). Given primitively O-oriented curves (E, ι), (E 0 , ι0 ) ∈ E``p (O),find an O-ideal a such that (E 0 , ι0 ) ∼= a ? (E, ι).
Instead of this “pure” vectorization problem, we work in [[Wes22a]] with two variants:
one seemingly weaker, and the other seemingly stronger. One of the conclusions of thearticle is that they all are equivalent. The weaker variant, ineffective O-Vect, does not
require the solution to preserve the orientation. The main motivation for this omission isthat per Theorem 2.6, such a solution always exists (even when the action has two orbits).
Problem 2.10 (Ineffective O-Vect). Given (E, ι) and (E 0 , ι0 ) in E``p (O), find an O-ideala such that E 0 ∼= Ea.

2.3. ORIENTATIONS AND THE ENDOMORPHISM RING PROBLEM

53

The stronger variant, effective O-Vect, additionally asks to evaluate the action of aon some arbitrary curve (F, ).
Problem 2.11 (Effective O-Vect). Given (E, ι), (E 0 , ι0 ), (F, ) ∈ E``p (O), find an Oideal a (or decide that it does not exist) such that (E 0 , ι0 ) ∼= a ? (E, ι), and an efficient
representation of ϕa : (F, ) → a ? (F, ).
For an adversary to break the key exchange in Section 2.1, they would need to solve
the effective O-Vect problem. This point used to be critical, since for a long time, nogeneral polynomial-time algorithm was known to evaluate the action of arbitrary ideals.
In [[Wes22a]], we circumvented the obstacle by proving that both variants are equivalent
to a third problem: computing the endomorphism ring.
Now, one may observe that since the ineffective O-Vect problem does not require thesolution to preserve the orientation ι0 , the problem remains well-defined if we drop ι0 fromthe input. This modification seems to make the problem much harder, and this presumed
hardness (for large discriminant) has been introduced in [[DDF+ 21]] as the Uber isogeny
assumption.
Problem 2.12 (Ineffective O-Uber). Given (E, ι) ∈ E``p (O) and a primitively Oorientable curve E 0 , find an O-ideal a such that E 0 ∼= Ea.
We similarly have an effective variant.
Problem 2.13 (Effective O-Uber). Given (E, ι), (F, ) ∈ E``p (O) and a primitively Oorientable curve E 0 , find an O-ideal a (or decide that it does not exist) such that E 0 ∼= Ea,
and an efficient representation of ϕa : (F, ) → a ? (F, ).
Ineffective O-Vect immediately reduces to ineffective O-Uber. The results from[[Wes22a]] clarify the hardness gap between these problems.
2.3.2. Oriented endomorphism ring problems. In the article [[Wes22a]], we introduced three oriented variants of the endomorphism ring problem. The first is simply theendomorphism ring problem when the input is an oriented curve.
Problem 2.14 (O-EndRing). Given (E, ι) ∈ E``p (O), compute End(E).
Remark 2.15. In light of the results of [[Wes21]] presented in Section 1.3, when we say“compute End(E)”, we mean both finding a basis of End(E) and an explicit isomorphismwith a quaternionic order (i.e., solving both EndRing and MaxOrder simultaneously).
The O-EndRing problem is a priori easier than EndRing, as the orientation readily
provides some information about the endomorphism ring. The second variant is the sameproblem but without being provided the orientation.
Problem 2.16 (EndRing|O ). Given a primitively O-orientable curve E, compute End(E).
Finally, we consider the seemingly harder problem of computing the endomorphismring and an orientation.
Problem 2.17 (O-EndRing∗ ). Given a primitively O-orientable curve E, compute End(E)and a primitive orientation ι : O → End(E).
Clearly O-EndRing reduces to EndRing|O , which in turn reduces to O-EndRing∗ .
There seems to be a significant gap between O-EndRing and EndRing|O — except
in the special case where the orientation is provided by the Frobenius, like in CSIDH.
However, the distinction between EndRing|O and O-EndRing∗ is not clear. We provein [[Wes22a, Corollary 1]] that they are equivalent when disc(O) = O(p1/2 ). We later
improved that bound to O(p) in [[CHVW22]], and Eriksen and Leroux improved it further toO(p4/3 ) in [EL24].

54

2. ORIENTED ELLIPTIC CURVES

2.3.3. Two classes of problems. The main contribution of [[Wes22a]] is the identificationof two classes of equivalent problems.
Theorem 2.18 ([[Wes22a]]). Assume the Generalized Riemann Hypothesis. If the factorization of disc(O) is known, then
(1) O-EndRing and (effective or ineffective) O-Vect are equivalent, and(2) O-EndRing∗ and (effective or ineffective) O-Uber are equivalent,
under probabilistic polynomial time reductions in the size of the instances and in # Cl(O)[2].
The dependency in # Cl(O)[2] only appears in the “vectorization to endomorphismring” direction. Note that in all cases that are currently of interest, the discriminant of
O is essentially one large prime (or prime power). Then, # Cl(O)[2] = O(1) causes notrouble, and the factorization of disc(O) comes for free.
Previous work. The first article to investigate the relation between EndRing and thevectorisation
problem was [CPV20], in the particular case of curves defined over Fp (with√−p ∈ O, the orientation used in the CSIDH cryptosystem). They prove that knowledgeof the endomorphism ring of a CSIDH public key allows one to recover the ideal class of thesecret key. This surprising result, however, only implied a subexponential reduction frombreaking CSIDH to computing endomorphism rings. In essence, they prove a reduction
from the ineffective vectorisation problem, but not from its effective variant — at a time
where the distinction was critical. In [[Wes22a]], we circumvent this issue, proving thefirst polynomial time reduction from the effective vectorisation problem (hence breaking
CSIDH) to the endomorphism ring problem.
Subsequent work. The above theorems have been improved since [[Wes22a]]. In the article [[CHVW22]], we develop new techniques for the “decisional O-DiffieHellman problem”,
and as an application, we reduce the dependency in # Cl(O)[2] to a subexponential quantity. For the reduction from O-Vect to O-EndRing, the article [EL24] has since entirely
removed the dependency in # Cl(O)[2], as well as the need for the factorization of thediscriminant and the Generalized Riemann Hypothesis.
2.3.4. Finding a reference oriented elliptic curve. Recall that in Section 1.3, toprove the equivalence between EndRing and `-IsogenyPath, the first ingredient was
to build a “reference” curve E0 , a special curve with known endomorphism ring. Such areference curve is equally important in proving the equivalence between O-EndRing and
O-Vect. But now, the reference curve must be primitively O-oriented.
In [[Wes22a]], we present a general algorithm to generate such a curve in E``p (O) in
polynomial time. This already requires knowledge of the factorization of disc(O).
Theorem 2.19 ([[Wes22a, Lemma 4]]). Assume the Generalized Riemann Hypothesis.
There is an algorithm which, given a prime p, a quadratic order O, and the factorizationof disc(O), returns (or asserts that it does not exist) a primitively oriented curve (E0 , ι0 ) ∈E``p (O) together with a basis of its endomorphism ring End(E0 ), and runs in polynomial
time in log p and log(| disc(O)|).
Sketch of the proof. The algorithm consists in first solving the quaternion analog of the
problem (find a maximal order O ⊂ Bp,∞ in which O primitively embeds), then solve the“reverse Deuring correspondence” (find an elliptic curve with endomorphism ring isomorphic to O). The second step uses techniques discussed in Section 1.3.
Let us say a bit more about the first step. Embedding O into Bp,∞ , then extending thequadratic order to a maximal quaternionic order O, can be done in a rather straightforwardmanner, by solving quadratic equations. However, the resulting embedding O → O is notnecessarily primitive. Instead, we consider OK the maximal order in K = O ⊗ Q, and find

2.4. THE ENDOMORPHISM RING PROBLEM GIVEN ONE ENDOMORPHISM

55

an embedding OK → Õ to some maximal order Õ in Bp,∞ . This embedding is necessarily
primitive, since OK is maximal. To find a primitive embedding O → O, we carefully work
our way down the “volcano of oriented orders” (see Remark 2.8).

2.3.5. O-EndRing reduces to O-Vect. Let us sketch the reduction from O-EndRing
to O-Vect. Suppose we are given an instance (E, ι) ∈ E``p (O) of the O-EndRing
problem, and we have an oracle solving the O-Vect problem. Find (E0 , ι0 ) ∈ E``p (O)together with a basis of its endomorphism ring End(E0 ), as in Theorem 2.19. The oracle
finds an O-ideal a such that E ∼= E0a . The isogeny ϕa : E0 → E corresponds to theideal Iϕa = End(E0 ) · ι0 (a), and we have OR (Iϕa ) ∼= End(E). Knowing the ideal a, theorientation ι0 and a basis of End(E0 ), we can compute a basis of Iϕa . The right-order
OR (Iϕa ) can be computed with [Rón92, Theorem 3.2], thereby solving O-EndRing for(E, ι).
The equivalence between MaxOrder and EndRing (discussed in Section 1.3.5) plays
a role under the hood, to translate the order OR (Iϕa ) (only isomorphic to End(E)) into
the actual endomorphism ring End(E).
2.3.6. O-Vect reduces to O-EndRing. Reducing O-Vect to O-EndRing is moredelicate. Suppose we are given an instance (E, ι), (E 0 , ι0 ) ∈ E``p (O) of O-Vect, andwe know the endomorphism rings End(E) and End(E 0 ). Knowing the endomorphism
rings (or equivalently, isomorphic orders in Bp,∞ ), it is easy to find a “connecting ideal”
between them, corresponding to an isogeny E → E 0 . However, in general, such an ideal
is not related to an O-ideal a (equivalently, the isogeny E → E 0 does not preserve theorientations). Careful steps which we do not detail here allow one to craft a special
connecting ideal of the form End(E) · ι(a), from which one can recover an O-ideal a.
2.4. The supersingular endomorphism ring problem given one endomorphism
Given a supersingular elliptic curve E and a non-scalar endomorphism α ∈ End(E) \ Z,how hard is it to find all the other endomorphisms of E? This question naturally emerges
in the context of oriented curves, as the data of an orientation is essentially the same as
one endomorphism (a generator of the orientation). In the article [[HW23]], we prove thefollowing theorem.
Theorem 2.20 ([[HW23, Theorem I and II]]). There is an algorithm which, given a supersingular curve E and an endomorphism α ∈ End(E) \ Z, computes the endomorphism ringof E in• classical expected time lO(1) | disc(Z[α])|1/4 , or
• quantum subexponential time lO(1) L| disc(Z[α])| (1/2),
where l is the length of the input, assuming the Generalized Riemann Hypothesis.
This question closely relates to the hardness of the O-EndRing problem (and therewith O-Vect, thanks to the equivalence in Theorem 2.18). Indeed, in the O-EndRing
problem, one is given a primitive orientation, hence an endomorphism. Reciprocally, any
endomorphism α induces an orientation of E by the order Z[α]. However, this orientation
is not necessarily primitive, a requirement in O-EndRing. Thanks to this observation, we
prove Theorem 2.20 in three steps. Suppose we are given a curve E and an endomorphism
α ∈ End(E) \ Z.
(1) Primitivization. First, we extend the orientation Z[α] → End(E) to a primitive orientation ι : O → End(E), for some superorder O ⊇ Z[α]. This is
the Primitivization step. The Primitivization problem was first introduced
in [ACL+ 23], where it was believed to be hard. We show that it can actually besolved in polynomial time.

56

2. ORIENTED ELLIPTIC CURVES(2) Reduction. Now that we have a primitively O-oriented curve (E, ι), we can apply
the equivalence of Theorem 2.18: to compute End(E), it is sufficient to solve the
O-Vect problem.
(3) Vectorization. Finally, we solve O-Vect. Heuristic algorithms for this step had
already been described, and the contribution of [[HW23]] lies in the design andanalysis of rigorous algorithms, assuming the Generalized Riemann Hypothesis
The reduction step was the object of Section 2.3. We now discuss the algorithms for
Primitivization and O-Vect.
2.4.1. Primitivization. The primitivization problem is the following computational problem.
Problem 2.21 (Primitivization). Given an O0 -oriented elliptic curve (E, ι0 ), find asuperorder O ⊇ O0 and a primitive orientation ι : O → End(E) such that ι|O0 = ι0 .
For supersingular elliptic curves, this problem is first considered in [ACL+ 23], wherea quantum subexponential-time algorithm is given. In the article [[HW23]], we prove thatgiven the factorization of disc(O0 ), the problem can be solved in classical polynomial
expected time. The idea comes from observing that Primitivization is very similar
to the endomorphism ring problem for ordinary elliptic curves, which can be solved inpolynomial time with Robert’s algorithm [Rob22] (up to some factorization).
Indeed, given an ordinary elliptic curve E over the finite field Fq , the q-Frobenius
endomorphism πq generates a quadratic subring Z[πq ] ⊆ End(E). The full endomorphismring is given by the primitivization of the inclusion Z[πq ] → End(E) (recall that in theordinary case, the endomorphism ring is a quadratic ring). Adapting Robert’s algorithm,
we get the following theorem.
Theorem 2.22 ([[HW23, Corollary 5.2]]). There is a probabilistic polynomial time algorithm
solving Primitivization, given the factorization of disc(O0 ).
Sketch of the proof. The input orientation ι0 : O0 → End(E) is given by a generator ω0
of O0 , and an efficient representation of its image α0 = ι0 (ω0 ). Without loss of generality,
we can write ω0 = f ω where f is the conductor of O0 , and ω is a generator of the maximal
order of O0 ⊗ Q.
Let ` be a prime factor of f . If α0 /` is not an endomorphism, we say that the orientation is locally primitive at `. Otherwise, α0 /` is an endomorphism, and the orientation
ι0 : Z[f ω] → End(E) : f ω 7→ α0 can be extended to the superorderZ[(f /`)ω] → End(E) : (f /`)ω 7→ α0 /`.
One can perform this step recursively for all prime factors of the conductor, until theorientation is locally primitive at each of them. When the orientation is locally primitiveat every prime factor of f , it is a primitive orientation.
A question remains: how to test whether α0 /` is an endomorphism (i.e., whether `divides α0 in End(E)), and if is it, how to find an efficient representation for it? Notethat ` divides α0 if and only if ker([`]) ⊆ ker(α0 ), so this task is easy when ` is a small
prime number. But dealing with large primes (or even large prime powers) requires morecare. An idea of [Rob22] which we generalize in [[HW23]] consists in using the interpolation
representation (see Section 1.5.2): for any isogeny ϕ : E → E 0 , powersmooth integer N >deg(ϕ), and basis (P1 , P2 ) of E[N ], the tuple (deg(ϕ), P1 , P2 , ϕ(P1 ), ϕ(P2 )) is an efficient
representation of ϕ. Furthermore, for any tuple of the same form (d, P1 , P2 , Q1 , Q2 ), one
can efficiently verify whether it actually represents an isogeny. Therefore, we can choose an
integer N coprime to `, and consider a tuple (deg(α0 ), P1 , P2 , α0 (P1 ), α0 (P2 )) representing
α0 . Then, α0 /` is an endomorphism if and only if it is represented by(deg(α0 )/`2 , P1 , P2 , [`−1 mod N ]α0 (P1 ), [`−1 mod N ]α0 (P2 )).

2.4. THE ENDOMORPHISM RING PROBLEM GIVEN ONE ENDOMORPHISM

57

One can efficiently verify whether that tuple actually represents an isogeny, and when it
does, it readily provides an efficient representation of α0 /`.

2.4.1.1. A first consequence: computing the action of smooth ideals. Recall that the classical algorithm to evaluate the action a ? (E, ι) runs in polynomial time in the largest
prime-power factor of N (a). Therefore, to be efficient, it requires a to be powersmooth.
The reason is that the induced isogenyϕ∗ (ι)(α) = (ϕ ◦ ι(α) ◦ ϕ̂) ⊗1.
deg(ϕ)

is represented in the most straightforward way, as a composition of ϕ, ι(α), ϕ̂, and adivision by deg(ϕ). The dependence in the prime-power factors comes from the division.
One may be tempted to decompose a as a product of powersmooth ideals, and applying
the action of each factor iteratively. However, iterative applications of the classical algorithm increases the denominator, hence “degrades” the quality of the representation of theorientation. A solution would be, at each step, to clear the denominator: finding anotherrepresentation of the orientation. This can be done by representing the orientation with
the interpolation method, like in the Primitivization algorithm. Concretely, to avoid
the division, consider the division-free orientation by the order Z + deg(ϕ)O. Now, insteadof dividing by deg(ϕ), solve Primitivization, which returns a good representation of theprimitive O-orientation ϕ∗ (ι). This method allows one to compute the action of a in timepolynomial in the largest prime factor of a, instead of its largest prime-power factor.
2.4.1.2. A second consequence: ascending the volcano. Recall that fixing a quadratic fieldK, and a prime `, the graph of K-oriented `-isogenies forms a so-called volcano. A vertex
in the volcano is a primitively O-oriented curve (E, ι) for some order O = Z + `i f OK ,where gcd(f, `) = 1, and i is the level of the vertex in the volcano.
An ascending isogeny from (E, ι) reaches a curve (E 0 , ι0 ) primitively oriented by O0 =Z + `i−1 f OK . The conductor decreases by a factor `. In particular, the discriminantdecreases, so the size of the class group decreases, and the corresponding vectorization
problem gets simpler. This motivates the problem of ascending the volcano: given an
instance of, say, O-EndRing, one could first try to ascend to the level of O0 -oriented
curves for an order O0 of smallest possible discriminant, where the problem is easier (then“transport the endomorphism information” back down through the vertical isogenies).
Previously, ascending walks in the volcano were limited to small powers of small primes,
because of the degradation induced by division of endomorphisms. We proved in [[Wes22a,
Theorem 5]] that (Z + cO)-EndRing reduces to O-EndRing in polynomial time in thelargest prime-power factor of c. Thanks to the new division method, we obtain the following theorem, unlocking large powers of small primes.
Theorem 2.23 ([[HW23, Theorem 7.11]]). Let c be a positive integer, and O a quadraticorder. The (Z + cO)-EndRing problem reduces to O-EndRing in probabilistic polynomial
time in the length of the input, and in the largest prime factor of c.
2.4.2. Vectorization. The resolution of O-Vect is the heart of Theorem 2.20, dominating the running times.
Classical algorithm. The case of ordinary elliptic curves (and its natural generalization to
CSIDH) has been studied as early as [GHS02], and the development of theoretical tools
such as [JMV09] unlocked a rigorous analysis of these algorithms. We now present thesolution for general orientations, which combines these “ordinary” methods with the newtechnique for the evaluation of the action of smooth ideals (Section 2.4.1.1).

58

2. ORIENTED ELLIPTIC CURVES

The fastest known classical algorithm for the O-Vect problem is a meet-in-the-middle
algorithm. We are given two O-oriented elliptic curves (E, ι) and (E 0 , ι0 ) (we suppose they
are in the same orbit). Note that the orbit has size # Cl(O) ≈ | disc(Z[α])|1/2 .
(1) First, generate random ideals ai until the list T = (ai ? (E, ι))i contains about| disc(Z[α])|1/4 distinct isomorphism classes.
(2) Second, generate random ideals b until b ? (E 0 , ι0 ) is an entry in the list T , sayb ? (E 0 , ι0 ) = ai ? (E, ι). Return the ideal class [b]−1 [ai ].
If one can sample ideals a uniformly distributed in the class group, the corresponding
curves a ? (E, ι) are uniformly distributed in the orbit. Using such a procedure, each of theabove steps requires approximately | disc(Z[α])|1/4 samples, leading to the claimed runningtime.
The main difficulty thus resides in sampling uniformly random classes [a] in a way thatthe action a ? (E, ι) can be computed efficiently. This is where random walks come in.
We define random walks in E``p (O) as follows. Consider a collection S of ideals in O.
An S-step from a starting point (E, ι) ∈ E``p (O) consists in sampling a ∈ S uniformly
at random, and going to a ? (E, ι). An S-walk of length k is a sequence of k consecutive
S-steps. A classical choice for S is the set S = PB of all prime ideals of norm at mostsome bound B. It is well-known that PB -walks have rapid-mixing properties.
Theorem 2.24 ([JMV09], adapted to the context of oriented curves). Let ε > 0. Assuming
the Generalized Riemann Hypothesis, there are bounds
B = O((log | disc(O)|)3 ), andκ = log(| disc(O)|) · poly(log log(| disc(O)|), log(1/ε))such that for any k ≥ κ, the endpoint of a PB -walk in E``p (O) of length k is at total
variation distance at most ε from the uniform distribution in the orbit of the starting point.
A PB -walk corresponds to the action of a B-smooth ideal. Smooth, but not powersmooth. This was not an issue in the classical case of ordinary elliptic curves. For thegeneral case, it motivated the development of the algorithm described in Section 2.4.1.1
for the action of smooth ideals. The equidistribution property of random walks, together
with the efficient algorithm to compute them, results in a rigorous meet-in-the-middle
algorithm for the O-Vect problem, assuming the Generalized Riemann Hypothesis.
Quantum algorithm. The subexponential quantum resolution of the O-Vect proven in[[HW23]] is based on the work of Childs, Jao and Soukharev [CJS14] to construct an isogeny
between two given isogenous ordinary elliptic curves. In particular, we use the fact thatgiven two oriented elliptic curves (E0 , ι0 ), (E1 , ι1 ) ∈ E``p (O) in the same orbit, finding an
O-ideal a such that a ? (E0 , ι0 ) = (E1 , ι1 ) can be viewed as an instance of the hidden shiftproblem.
Problem 2.25 (HiddenShift). Given a finite abelian group (A, +), a finite set S ⊂{0, 1}m , and two black-box functions f0 , f1 : A → S where f0 is injective and such that
there exists an element s ∈ S verifying f1 (x) = f0 (s + x) for any x ∈ S, find the elements called the shift hidden by f0 and f1 .
Defining f0 , f1 : Cl(O) → E``p (O) as
f0 ([a]) = a ? (E, ι), andf1 ([a]) = a ? (E 0 , ι0 ),one can use Kuperberg’s quantum algorithm to solve the HiddenShift problem (hence
O-Vect) in a subexponential number of queries to f0 and f1 .

2.5. KNOWING THE STRUCTURE OF THE ACTING GROUP

59

Theorem 2.26 (Theorem 7.1. [Kup05]). There is a quantum
algorithm for HiddenShift
p
O(
log
n)
over abelian groups with time and query complexity 2, where n is the size of theabelian group.
The complexity of evaluating the functions fi (a “query”) presents a challenge: it requires evaluating the action of arbitrary ideals. We can generalize the strategy of [CJS14]:
find a smooth representative of the class [a], then apply the action of that representative with the method of Section 2.4.1.1. A subexponential smoothness bound leads to a
subexponential complexity. Today, the algorithm of [PR23] enables a more straightforward
approach, since it can evaluate the action of any ideal in polynomial time.
2.5. Knowing the structure of the acting group
Orientations provide a powerful framework to obtain a cryptographic group action. The
orientation provided by the Frobenius on supersingular curves over Fp is the most prominent incarnation of this framework, and the heart of the CSIDH key exchange (see Section 2.2.2.2).
One downside of this framework is that the structure of the acting group Cl(O) is,in general, hard to compute. “Computing the structure” means computing a complete
set of generators and relations, but even computing the order of the group is a difficult
task in general. The best known algorithm is the index-calculus algorithm [HM89], runningin subexponential expected time L| disc(O)| (1/2). For security, the discriminant must be
chosen large enough for the cost of solving O-Vect to be prohibitively high; the fastest
known quantum algorithm itself has complexity about L| disc(O)| (1/2) (Theorem 2.20).
Therefore, at first glance, it looks like (quantumly) breaking the security has about thesame cost as computing the structure Cl(O). In other words, it seems hard to have thetwo following properties simultaneously:• the O-Vect problem is hard (even for a quantum computer), and• the structure of Cl(O) is known.
This account of the situation is, of course, not fully accurate. The hidden constants inboth L| disc(O)| (1/2) complexities are not the same, and it appears that computing the classgroup is substantially faster than the quantum algorithm for vectorization (and, of course,
has the advantage of not requiring a quantum computer). The CSI-FiSh scheme [BKV19]
demonstrated that fact: they computed the structure of the class group for the first
security level of CSIDH (namely CSIDH-512, where | disc(O)| is a 512-bit integer). The
computation took an estimated effort of 52 core years. Applying this approach to higher
security levels is believed to be infeasible.
2.5.1. SCALLOP. In [[DFK+ 23]] we explore another route and introduce SCALLOP, ascalable framework for the action of class groups with known structure. We observe√ thatthe case of CSIDH is quite unfavorable: the corresponding order O = Z[π] = Z[ −p] isa maximal order (or of index 2 in a maximal order). For such orders, the index-calculus
algorithm is the best we can do, and we are stuck with the complexity L| disc(O)| (1/2). The
class group of non-maximal orders can be easier to compute; and in interesting cases, thecorresponding vectorization problem remains hard. In SCALLOP, we consider the classgroup of a quadratic order of large prime conductor inside an imaginary quadratic field ofsmall discriminant. This family of quadratic orders lets us easily determine the size of theclass group, and, by carefully choosing the conductor, even exercise significant control on
it. We analyse the security of this construction, and show how to efficiently represent thecorresponding orientations.
One of the motivations was to be able to evaluate the action of arbitrary ideals — at atime where no polynomial-time algorithm was known. SCALLOP was the first to achieve

60

2. ORIENTED ELLIPTIC CURVES

that goal for a security level equivalent to CSIDH-1024, a parameter firmly out of reachof the index-calculus approach of CSI-FiSh. Asymptotically, the evaluation algorithm
described in SCALLOP is still subexponential. Today, that motivation is challenged by
the polynomial time algorithm of Clapotis [PR23] to evaluate the action of arbitrary ideals(Clapotis is asymptotically more efficient, but its practicality is still under investigation).
Still, the approach of SCALLOP remains the only framework in which the structure of theacting group can be computed in polynomial time. It even unlocks an action for which thediscrete logarithm problem on the acting group is easy (it would be easy for a quantum
adversary anyway, but this power can now be given to the good guys, for constructive
applications).
2.5.2. Class groups of non-maximal orders. As mentioned in the previous section,
non-maximal orders can have easy-to-compute class groups. For the moment, assume thatthe size of the class group Cl(O) is an accurate metric for the hardness of O-Vect. We
simply wish to find large class groups whose structure can be computed efficiently.
Consider an imaginary quadratic number field K, with maximal order OK . Recall
that any order in K is of the form O = Z + f OK , where f ∈ Z>0 is the conductor. We
start from two observations:(1) The class group Cl(O) is a well-understood combination of Cl(OK ) and othersimpler groups.
(2) The size of the class group Cl(O) grows linearly with the conductor f .
Therefore, it is possible to construct large class groups Cl(O) as follows: consider a field ofsmall discriminant (so the class group Cl(OK ) is easy to compute), and let O = Z + f OK
be an order with large conductor f . The structure of Cl(O) can be deduced from Cl(OK )thanks to the classical exact sequence×
1 → OK/O× → (OK /f OK )× /(O/f OK )× → Cl(O) → Cl(OK ) → 1.
×
Let us look at each group in that sequence. The group OK/O× is the simplest. Indeed,××
for all but two imaginary quadratic number fields, we have OK= {±1}, hence OK/O×is trivial. The two exceptions are the Gaussian integers and the Eisenstein integers, for×which OK
/O× has order at most 3.
To compute the group Cl(OK ), we choose a field K of small discriminant. In SCALLOP,√ we push this choice to the extreme, choosing a field for which Cl(OK ) is trivial, likeQ( −1).
To obtain the structure of Cl(O), it remains to compute (OK /f OK )× /(O/f OK )× .
It can be computed efficiently from the factorization of f . For SCALLOP, we only careabout the case where f is a large (hence unramified) prime number — for security reasons,see Section 2.5.3. When f is an unramified prime, there is an explicit isomorphism(××× ∼ Ff if f splits in K, or(OK /f OK ) /(O/f OK ) =F×/F×f if f is inert in K.
f2√√
×
Example 2.27. Let K = Q( −1) and OK = Z[ −1]. Then, OK/O× has order 2, andCl(OK ) is trivial. Let f be a prime number such that f ≡ 1 mod 4, and let O = Z + f OK .
Then, ` is inert in K, hence (OK /f OK )× /(O/f OK )× ∼= F×
f . Through this isomorphism,
××
the group OK /O maps to {±1} (the only subgroup or order 2). We deduce that


f −1
×
∼
∼
Cl(O) = Ff /{±1} = Z/Z.
2This is it: we have an order O with arbitrarily large class group Cl(O), and an explicit
description of the “structure” of Cl(O). It is cyclic of order (f − 1)/2. Now, one could
ask for more, like being able to compute discrete logarithms in Cl(O). In general, solving

2.5. KNOWING THE STRUCTURE OF THE ACTING GROUP

61

discrete logarithms in F×f cannot be done in polynomial time. But if it has smooth order, it
is easy. One could craft the prime conductor f such that f − 1 is smooth (say, f = 2n + 1).
Once a suitable order O has been found, it remains to find an initial O-oriented curve(E, ι) ∈ E``p (O). This can be done in polynomial time via Theorem 2.19. A large partof the article [[DFK+ 23]] is concerned with making these theoretical algorithms as practical as possible. These considerations have since largely been surpassed, for instance by
SCALLOP-HD [CLP23]. Leveraging the isogeny interpolation algorithm (Theorem 1.29),
this “HD” version is both simpler and faster than the original construction.
2.5.3. Security analysis. Does replacing maximal orders (as in CSIDH) with nonmaximal orders (in SCALLOP) jeopardize the security? Theorem 2.23 makes one thing
clear: the conductor of the order should not be smooth, otherwise an attacker could“ascend the volcano”, reducing the security to a case where the discriminant is small.
Precursors of that theorem motivated the choice in SCALLOP for the conductor to be one
large prime f . With this precaution, the fastest known attacks are essentially the meetin-the-middle (classical) and Kuperberg (quantum) algorithms, analyzed in Section 2.4.
In [[DFK+ 23]], we discuss another conceivable attack strategy. Let us focus on the
O-EndRing problem (which is essentially equivalent to O-Vect, thanks to Theorem 2.18).
We are give some (E1 , ι1 ) ∈ E``p (O), and wish to compute End(E1 ). In SCALLOP, theorder O is of the form Z + f OK where the maximal order OK has trivial class group. One
can compute the (essentially) unique (E0 , ι0 ) ∈ E``p (OK ) together with its endomorphismring End(E0 ). There exists a unique descending isogeny
ϕ : (E0 , ι0 ) −→ (E1 , ι1 ),which has degree f . To compute End(E1 ), one could try the following:(1) Design an algorithm to find an efficient representation of ϕ.
(2) Using this representation, convert ϕ to its corresponding left End(E0 )-ideal Iϕ .
(3) Deduce End(E1 ) as the right-order of Iϕ .
Step 3 can be done with the methods presented in Section 1.3. Step 2 is already morechallenging, but this “isogeny to ideal” problem for large prime degree has recently beensolved in quantum polynomial time [CII+ 23]. Now, the security of SCALLOP entirely
hangs on Step 1. The isogeny ϕ is uniquely determined by all the information available
to an attacker, but there is no known method to find it, other than solving O-EndRingin the first place with generic methods.

3
Ideal lattices
In this chapter, we present contributions related to ideal lattices, and their applications
in cryptography and computational number theory. We study random walks in the spaceof ideal lattices up to isometry: the Arakelov class group. These random walks are a
powerful tool to study the hardness of computational problems in ideal lattices, and todesign rigorous algorithms for algebraic number theory.
This chapter is built around the presentation of the articles (in order of appearance):[[BDPW20]]

Koen de Boer, Léo Ducas, Alice Pellet-Mary, and Benjamin Wesolowski.
Random self-reducibility of Ideal-SVP via Arakelov random walks. In
Daniele Micciancio and Thomas Ristenpart, editors, Advances in Cryptology – CRYPTO 2020, volume 12171 of Lecture Notes in Computer Science,
pages 243–273. Springer, 2020.

[[FPSW23]]Joël Felderhoff, Alice Pellet-Mary, Damien Stehlé, and Benjamin
Wesolowski. Ideal-SVP is hard for small-norm uniform prime ideals. In
Guy N. Rothblum and Hoeteck Wee, editors, Theory of Cryptography –21st International Conference, TCC 2023, volume 14372 of Lecture Notes
in Computer Science, pages 63–92. Springer, 2023.

[[BPW24]]

Koen de Boer, Alice Pellet-Mary, and Benjamin Wesolowski. Rigorous
methods for computational number theory. Preprint available on demand,
2024.

Part of the results of [[BPW24]] also appeared in the PhD dissertation of de Boer [Boe22].
3.1. Introduction
A lattice is a discrete subgroup in a Euclidean vector space. A lattice Λ is generally
represented by a basis: a collection (b1 , . . . , bm ) of linearly independent vectors with Λ =b1 Z + · · · + bm Z. The integer m is the rank of the lattice. As a group, the lattice isisomorphic to Zm . The Euclidean norm on the ambient space makes for a much richer
playground, inducing a notion of length on the vectors of the lattice. One can thenask geometric questions (what is the shortest possible length of a non-zero vector in thelattice?), or their computational counterparts (can one find a non-zero lattice vector withshortest possible length?).
Lattices have been a standard object in number theory since Minkowski’s seminal work
Geometrie der Zahlen published in 1896. This number-theoretic perspective on lattices

64

3. IDEAL LATTICES

came to be known as the field of geometry of numbers in reference to this work. Most
famously, Minkowski proved that any lattice contains a vector of relatively short norm
(Minkowski’s bound on the shortest vector). Lattices appear naturally in algebraic number theory: the ring of integers of a number field is a lattice, and so is any (fractional)
ideal. We call them ideal lattices. Considering ideals as lattices and applying Minkowski’s
bound is a classical approach to prove one of the most fundamental theorems in algebraic
number theory: the finiteness of the class group.
The shortest vector problem (SVP) is the following computational problem: given alattice Λ (described by a basis), find a non-zero vector in Λ with shortest norm. The shortest vector problem (or its approximated version, Approx-SVP) is a central hard problem
in complexity theory. It is presumed to be hard even for quantum algorithms, and thanks
to the worst-case to average-case reductions of Ajtai [Ajt99] and Regev [Reg09], it has
become the theoretical foundation for many post-quantum cryptographic constructions.
The idea is the following: the private key would be a “good” basis of a lattice Λ,consisting of n short vectors, and the public key would be a “bad” basis of the samelattice, from which it is hard to recover short vectors. The public basis, while “bad”, still
enables some simple operations: sampling random lattice points (far from the origin), or
encoding a message as a lattice point P ∈ Λ. Adding a small “error” ε to this point (i.e.,
shifting it to obtain a close point outside the lattice), only the secret “good” basis allows torecover the original point P from the noisy point P + ε. Hence the security of lattice-based
cryptography relies on the presumed hardness of finding short vectors (to recover a shortbasis from a bad one), and on closely related problems such as learning with errors (LWE)
and short integer solution (SIS).
The main disadvantage of such plain lattice-based cryptosystems is their heavy memory
and bandwidth footprint: the public and secret keys both are a lattice basis, an n × nmatrix, where the dimension n is in the order of hundreds. This issue can be addressedby using lattices with more structure. Ideal lattices (or the more general notion of module
lattices) thereby took a central place in lattice-based cryptography. The shortest vector
problem in ideal lattices is the Id-SVP problem. The Ring-SIS [Mic07, LM06, PR06]
and Ring-LWE [SSTX09, LPR13, PRS17] problems were introduced and shown to be atleast as hard as worst-case instances of Id-SVP. Both Ring-SIS and Ring-LWE have
proved very versatile problems for building efficient cryptographic schemes.
The additional algebraic structure, while practically useful to build efficient cryptosystems, also opens more cryptanalytic avenues. How hard is Id-SVP? While still far frombeing “solved”, we do know much better algorithms for some versions of Id-SVP thanfor the unstructured case [CGS14, CDPR16],[[CDW17, CDW21]]. Id-SVP has proved a fertile
cryptanalytic playground to test the impact of adding “structure” to lattice problems.
This chapter revolves around the development of a new tool and its consequences incryptography and in computational number theory: random walks in the space of ideal
lattices. The rapid-equidistribution properties of these random walks bring new insights
on the (average) hardness of computational problems in ideal lattices, and unlock newalgorithms for fundamental problems in computational number theory.
3.1.1. Contributions and organisation of the chapter. The chapter is organized asfollows.
Ideal lattices and the Arakelov class group. We open this chapter with a few preliminaries
on ideal lattices and the Arakelov class group in Section 3.2. After fixing some notation andrecalling the main definitions, we explore the classical connection between the two notions:
the Arakelov class group can be viewed as the group of all ideal lattices up to isometry.

3.1. INTRODUCTION

65

This connection, long known by number theorists [Bay99, Sch08], had been absent fromthe cryptographic literature until the article [[BDPW20]]. Remarkably, the Arakelov classgroup is a combination of two groups that had already led to significant cryptanalytic
advances: the unit torus [CGS14, CDPR16] and the class group [[CDW17, CDW21]].
Random walks in the Arakelov class group. In Section 3.3, we present the main resultof our article [[BDPW20]]: random walks in the Arakelov class group equidistribute rapidly,
assuming the Generalized Riemann Hypothesis. Contrary to the random walks in previous
chapters, we are now walking in an infinite, continuous space. We thus consider random
walks which combine two kinds of steps: “continuous” steps, akin to a Brownian motion,and “discrete” steps, capable of jumping between connected components.
Average hardness of ideal lattices. The motivation for the equidistribution theorem is thefollowing. Elements of the Arakelov class group are, essentially, ideal lattices. From astarting ideal lattice, a random walk rapidly reaches a uniformly random ideal lattice.
Through a (short) random walk, one can transfer a solution of Id-SVP (i.e., a shortvector) from the target to the source, with a small loss on the approximation factor. In
other words: if one can solve Id-SVP for uniformly random ideal lattices, then one cansolve Id-SVP for any ideal lattice. It is a worst-case to average-case reduction.
We explore this idea in Section 3.4. In the article [[BDPW20]], we follow this strategy
to obtain a worst-case to average-case reduction where “average” means uniform in the
Arakelov class group (in the sense of the Haar measure). There is a critical difficulty:
the Arakelov class group being continuous, this computational result requires rounding,resulting in ideals of rather large norm.
We refine this result in the article [[FPSW23]]. Combining the Arakelov random walks
with reductions of Gentry [Gen09, Gen10], we obtain a worst-case to average-case reduction where “average” means uniformly random prime ideal of small norm. Using the
reduction from Pellet-Mary and Stehlé [PS21], this notably leads to the first distribution
for instances of the NTRU cryptosystem with a polynomial modulus whose hardness is
supported by a worst-case lattice problem.
A rigorous tool for algorithmic number theory. Long before finding a place in cryptography,
ideal lattices have been a central object of interest in number theory. They naturally arise
in many computational number theoretic questions, like the computation of the classgroup and unit group of a number field, or perhaps more surprisingly, the factorisation of
integers.
Many algorithms for these fundamental problems (like the computation of class groups
in subexponential time) are not fully understood: their analysis resorts to heuristic assumptions. This persistent need for heuristic assumptions often stems from a step of thisform: given an ideal class [a] of a number field, find a representative b ∈ [a] belonging
to a particular family S of ideals (for instance, the family of prime ideals, or smoothideals). It is relatively simple to design an algorithm for this task: sample a randomb ∈ [a], and hope that it belongs to the desired family S. One then heuristically argues that the probability that b ∈ S should be proportional to the density of S. For
instance, the subexponential density of smooth ideals heuristically implies that one canfind smooth representatives in subexponential time. This is the heart of state-of-the-art
algorithms to compute class groups, unit groups, or generators of principal ideals in number fields [BF14, Buc88, LL93], and has long constituted a theoretical obstacle overcome
only by heuristic arguments (with the exception of quadratic fields [HM89]).
In Section 3.5, we present the result of the article [[BPW24]]: a general strategy to solvethese ideal sampling tasks rigorously and efficiently. We remove the need for heuristic
assumptions by leveraging the rigorous randomization properties of walks in the Arakelov

66

3. IDEAL LATTICES

class group. We illustrate the power of this technique by presenting the first algorithm forcomputing class groups and unit groups of arbitrary number fields that provably runs inprobabilistic subexponential time.
3.2. Ideal lattices and the Arakelov class group
In this section, we define the notions of ideal lattice and Arakelov class groups, and explain
their connection. A more detailed account can be found in the main inspiration for thissection: the article [Sch08].
3.2.1. Ideal lattices. Fix a number field K of degree n = [K : Q] and discriminant ∆K .
The field K is a vector space of dimension n over Q, and it has a canonical R-valued innerproduct. In algebraic terms, the inner product is defined as hα, βi = Tr(αβ ∗ ) where −∗ isthe canonical involution of the étale R-algebra K ⊗R. The Minkowski embedding provides
a more explicit description as follows. The number field K has n field embeddings into C,
which are divided into nR real embeddings and nC conjugate pairs of complex embeddings,
with n = nR + 2nC . Let()
M
KR = (xσ )σ ∈C xσ = xσ ∼= K ⊗ R,
σ:K→C

where the sum is over all field embeddings σ : K → C. We consider the Euclidean normP
2 1/2 on K . The Minkowski embedding is the map Ψ : K → K :k(xσ )σ k =RR
σ |xσ |
α 7→ (σ(α))σ . The field K inherits the Euclidean
structureofK
through
thisembedding.
R
P
More explicitly, for α ∈ K, we have kαk2 = σ |σ(α)|2 . Abusing notation, we treat Ψsimply as an inclusion K ⊂ KR .
Let OK be the ring of integers of K. It is a discrete additive subgroup of rank n, hence
a lattice in the vector space K. A fractional ideal in K is any subset of K of the form αawhere α ∈ K × and a a non-zero ideal in OK We denote by IK the group of fractional
ideals of K. Any fractional ideal is also a lattice in K. This is essentially what we define
as an ideal lattice in K, with one last generalization: we extend the scalars to R, leading
to the following definition.
Definition 3.1. An ideal lattice over K is a lattice in KR of the form xa, where x ∈ KR×
and a is an ideal in OK ⊂ K ⊂ KR . Equivalently, an ideal lattice over K is a lattice in
KR of rank n which is also an OK -submodule.
We denote by IdLatK the set of all ideal lattice over K. Note that it forms an abeliangroup, with xa · yb = xyab, and neutral element OK . The (co)volume of an ideal lattice isY
Vol(xa) = |∆K |1/2 N (a)|xσ |.
σOur problems of interest are invariant under rescaling. We thus define the subgroup
IdLat0K = {L ∈ IdLatK | Vol(L) = Vol(OK )}.
Definition 3.2. An isometry between two ideal lattices L1 , L2 ⊂ KR is an isomorphism
ϕ : L1 → L2 of OK -modules such that kϕ(z)k = kzk for all z ∈ L1 . Equivalently, it is a
map of the form ϕξ : z 7→ ξz for some ξ = (ξσ )σ ∈ KR with |ξσ | = 1 for all σ. If two ideal
lattices L1 and L2 are isometric, we write L1 ∼= L2 .
The set IsoK = {L ∈ IdLatK | L ∼= OK } is a subgroup of IdLat0K , and the quotient
IdLat0 /IsoK = IdLat0 / ∼=KKforms the group of (normalised) ideal lattices up to isometry. This is almost the Arakelov
class group: the latter is defined through a different formalism, but the result is isomorphic.

3.2. IDEAL LATTICES AND THE ARAKELOV CLASS GROUP

67

3.2.2. The Arakelov class group. In this section, we define the Arakelov class group
Pic0K , and outline the proof that it is isomorphic to IdLat0K / ∼=, the group of ideal lattices
up to isometry.
A finite place of K is a (non-zero) prime ideal in OK . An infinite place of K is afield embedding K → C up to complex conjugation; in other words, it is either a realembedding ν : K → R, or a pair ν = {σ, σ} of complex embeddings. Given an embedding
σ, we write νσ for the corresponding place; reciprocally, for any place ν, we let σν be oneof the corresponding embeddings. There are exactly nR + nC ≤ n infinite places. The
group of Arakelov divisors is
M
M
DivK =Z×R.
νp

We denote the canonical basis elements with the symbols LpM and LνM (the divisor withvalue 1 at p or ν respectively, and 0 everywhere else). Then, an arbitrary divisor can be
written asXXa=np · LpM +xν · LνM.
νp

The degree of an Arakelov divisor is given by the group homomorphism
deg : DivK −→ RX
pnp · LpM +Xνxν · LνM 7−→X

np log(N (p)) +Xν real

p

X

xν +

2xν .

ν complex

The kernel of this map is the group Div0K of degree-zero divisors.
Given any element α ∈ K × , one can construct an Arakelov divisor via the map
XX
div : K × 7−→ DivK : α 7−→
ordp (α) · LpM −log |σν (α)| · LνM.
νpDivisors of the form div(α) are called principal divisors, and the product formula statesthat principal divisors have degree zero, i.e., div(K × ) ⊂ Div0K .
Definition 3.3. The Arakelov class group of K is the group Pic0K = Div0K /div(K × ). For
any Arakelov divisor a, we denote by [a] its class in Pic0K .
3.2.3. Arakelov divisors and ideal lattices. In this section, we explain the connection
between Arakelov divisors and ideal lattices, culminating in the following theorem.
Theorem 3.4. The “exponential map” induces an isomorphism Pic0 → IdLat0 / ∼=.
KKIn other words, the Arakelov class group encodes the collection of ideal lattices up toisomorphism and rescaling. As the “exponential” terminology suggests, the Arakelov classgroup can informally be thought of as a “logarithmic space” for ideal lattices.
The connection between Arakelov divisors and ideal lattices L = xa (where x ∈ KR×
and a is a (fractional) ideal) can be understoodby separating the “finite” part and theL“infinite” part. First, the “finite” partZ
accounts
for the a-component: the uniquepLfactorisation of fractional ideals into prime ideals is a bijection between
p Z and thecollection of fractional ideals. We thus have a bijection between divisors and fractional
ideals:M
X
Y
Expfin :Z −→ IK :np · LpM 7−→
pnp .
p

p

Its inverse is the factorisation map
Logfin : IK −→Mp

Z : a 7−→p

X
p

ordp (a) · LpM.

68

3. IDEAL LATTICES

L
Second, the “infinite” part ν R somehow accounts for the continuouspart of an ideal
L
lattice: the x-component. That may not be as clear: how does ν R compare with KR× ?
We at least have an injective group homomorphism
M
X
Exp∞ :
R −→ KR× :xν · LνM 7−→ (exνσ )σ .
ννIt is not surjective, so does not have an inverse, but it does have a retraction:
M
X
Log∞ : KR× −→R : (yσ )σ 7−→
log |yσν | · LνM.
νν

Remark
3.5. The composition of the inclusion K → KR with Log∞ is the map Log : K × →Lν R often referred to as the Logarithmic embedding of K, which plays an important rolein the cryptanalysis of ideal lattices [CGS14, CDPR16], [[CDW21]].
Regrouping the “finite” and “infinite” parts, we obtain a map
Exp = Expfin · Exp∞ : DivK −→ IdLatK .
It is not surjective, because Exp∞ is not. However, the induced map to the quotient
IdLatK / ∼= is surjective. Indeed, for any ideal lattice xa, we have an isomorphism
xa → (ξx)a : z 7→ ξx where ξ = (|xσ |/xσ )σ , and the element ξx = (|xσ |)σ ∈ KR× isin the image of Exp∞ . In particular, IdLatK / ∼= is isomorphic to a quotient of DivK . It
can be verified that the kernel of Exp is the group div(K × ) of principal divisors, hence
DivK /div(K × ) ∼= IdLatK / ∼=. The last step to obtain Theorem 3.4 is to prove that the
subgroup of normalized ideal lattices IdLat0K corresponds to the subgroup of degree-zerodivisors Div0K . This follows from the formula
Vol(Exp(−)) = Vol(OK )edeg(−) .
In particular, the exponential map restricts and co-restricts to
Exp0 : Div0K −→ IdLat0K ,and we obtain Theorem 3.4.
Remark 3.6. Note that if one wishes to work with ideal lattices up to rescaling, but not
up to isomorphism, one could consider the oriented Arakelov class group [Sch08].
3.2.4. Structure of the Arakelov class group. The Arakelov class group Pic0K provides a convenient formalism to study the space of ideal lattices (up to isomorphism andscaling): it is naturally a compact topological group. In this section, we discuss the
structure of this group, summarized in the short exact sequence(3.1)

0 −→ TK −→ Pic0K −→ Cl(K) −→ 0,

where Cl(K) is the class group of K, and TK is a torus (the quotient of a real vector spaceby a lattice), the so-called Log-unit torus of K. Geometrically, the Arakelov class group isthus a finite union of copies of the torus TK : one copy for each ideal class. We illustrate
this structure in Figure 3.1.
Let us discuss this short exact sequence in greater detail. The map Pic0K −→ Cl(K)is the most straightforward. Consider the natural morphismXpnp · LpM +X
νDiv0K −→ IKYxν · LνM 7−→pnp .
p3.3. RANDOM WALKS IN ARAKELOV CLASS GROUPS

Log-unit torus T

69

Arakelov class group Pic0K

Class group Cl(K)

Figure 3.1. Schematic representation of the Arakelov class group, a combination of the class group and the Log-unit torus.
Evidently, principal divisors are sent to principal ideals, thereby inducing the morphism
Pic0K → Cl(K) in the second half of the sequence (3.1).
It remains to understand the first half of (3.1). The Log-unit torus TK is defined asfollows. Consider the real vector space



 M
M
X
X
H = (xν )ν ∈Rxν +2xν = 0 ⊂R.
ν realνν complexν×This vector space H is generated by the image of OK
through the logarithmic embedding
L××
Log : K →R
(see
Remark
3.5),
and
Log(O
ν
K ) is a full-rank lattice in H. The×
Log-unit torus is the quotient TK = H/ Log(OK ). The map TK → Pic0K in the exact
sequence (3.1) is induced by the obvious map
X
H −→ Div0K : (xν )ν 7−→xν · LνM.
ν

In summary, we have the following commutative diagram, where each line is exact,and each vertical arrow is the natural quotient map:
0

H

Div0K

IK

0

0

TK

Pic0K

ClK

0.

3.3. Random walks in Arakelov class groups
This section presents the new versatile tool developed in [[BDPW20]]: random walks in the
Arakelov class group, and their rapid equidistribution property. The goal is to design a
process which, starting with an arbitrary ideal lattice, applies a sequence of small random
modifications. Each modification, a step in the walk, affects the shape of the lattice in awell-controlled manner. The result is a random ideal lattice, closely related to the original
one, but well distributed in the space of ideal lattices.
3.3.1. The random walk. Before stating the equidistribution theorem, we must define
the random walks under consideration. The design of the walk is motivated by the structure of the Arakelov class group discussed in Section 3.2.4. The group is a combinationof a continuous part, the unit torus TK , and a discrete part, the class group Cl(K). The
walk is thus a combination of a discrete walk and a continuous walk.

70

3. IDEAL LATTICESThe random walk on the Arakelov class group Pic0K is best described as a walk on
Div0K , projected to Pic0K . For any probability distribution D on Div0K , we write [D] forthe corresponding quotient distribution on Pic0K .
The discrete walk. A discrete step is essentially a step of this form: from an arbitrary
Arakelov divisor a, sample a random prime ideal p, and go to a + LpM. The new divisor
a + LpM does not have degree 0, so we normalize it to
X log(N (p))
a + LpM −· LνM.
nν
We also write it as a + d0 (p), using the map
X
X log(N (a))
d0 : IK −→ Div0K : a 7−→
ordp (a) · LpM −· LνM.
npν
One needs to fix a distribution for p. Fix a bound B, and let PK (B) be the set of allprime ideals in OK of norm at most B. We consider p uniformly distributed in PK (B).
Definition 3.7 (Discrete step, discrete walk). Let D be any probability distribution on
Div0K . We denote by WB (D) the distribution of a + d0 (p), where a is sampled with
distribution D, and p ∈ PK (B) is uniform. In other words, WB (D) is the distribution
obtained by sampling from D, then taking a discrete step. A discrete walk of length k withinitial distribution D consists in sampling from D then taking k discrete steps sequentially.
The endpoint of a discrete walk of length k has distribution WBk (D).
On the side of ideal lattices, a discrete step consists in replacing the ideal lattice xa
with the random sublattice xap ⊂ xa, and rescaling it to normalise the volume.
A motivation for this choice of step comes from previous work on random walks in classgroups: the equidistribution result of Jao, Miller and Venkatesan [JMV09], presented in
Section 2.4.2. They define a similar random step in the class group: from a starting idealclass [a], go to the class [ap] for some uniformly random prime p ∈ PK (B). Assuming
GRH, the main theorem of [JMV09] states that for some B = Oε ((n log ∆K )2+ε ), applying
this step k times (i.e., a length k random walk) converges to the uniform distribution on
Cl(K) at an exponential rate in k.
In particular, we readily obtain that our discrete walk in the Arakelov class grouprapidly equidistributes among the # Cl(K) connected components. The discrete walk“jumps” between connected components, and very effectively so.
The continuous walk. Taking discrete steps from any starting point, no matter how long
the walk, the distribution of the endpoint will remain discrete. To hope for a convergenceto the uniform distribution in the sense of the total variation distance (i.e., convergencein L1 (Pic0K )), we need to “smooth it out”. This is where the continuous walk comes in, asa kind of “blurring” step.
Geometrically, a starting point [a] in the Arakelov class group is a point on a torus,
a copy of the unit torus TK . A continuous walk consists in replacing [a] with a random
nearby point on the torus: we consider a Gaussian distribution centered at [a] and withsomewhat small standard deviation.
Definition 3.8 (Continuous walk). Let D be any probability distribution on Div0K . Wes (D) the distribution of a + x, where a is sampled with distribution D, anddenote by LW∞
x ∈ H ⊂ ν R ⊂ Div0K is sampled from the Gaussian distribution on H with standard
deviation s centered at the origin.
On the side of ideal lattices, this continuous walk consists in replacing an ideal latticexa with a slight deformation of it, i.e., a lattice δxa with δ ∈ KR× close to the identity.

3.3. RANDOM WALKS IN ARAKELOV CLASS GROUPS

71

The Arakelov random walk. Any probability distribution on the Arakelov class group Pic0K
is of the form [D] for some distribution D on Div0K . We thus define the Arakelov random
walk as follows.
Definition 3.9 (Arakelov random walk). Let B, k, s > 0 be parameters. Let [D] be aprobability distribution on the Arakelov class group Pic0K . The Arakelov random walkwith initial distribution [D], prime bound B, length k, and standard deviation s is thefollowing process: sample a starting point [a] from [D], then apply the continuous walkwith standard deviation s, and k discrete steps with prime bound B. The distribution ofs (D))].
the endpoint is [WBk (W∞
3.3.2. Rapid equidistribution. The main tool developed in [[BDPW20]] is the following theorem, which states that Arakelov random walks rapidly converge to the uniform
distribution (for the Haar measure).
Theorem 3.10 (Simplified form of [[BDPW20, Theorem 3.3]]). Let ε > 0 and s > 0.
Assuming the Generalized Riemann Hypothesis, there are bounds
B = poly(n, log(∆K ), log log(1/ε), log(1/s)), andκ = log(∆K ) · poly(log n, log log(∆K ), log(1/ε), log(1/s))
such that for any initial distribution [D] on Pic0K , and any k ≥ κ, the endpoint of the
Arakelov random walk with prime bound B, length k, and standard deviation s is at total
variation distance at most ε from the uniform distribution (for the Haar measure on Pic0K ).
Remark 3.11. Instead of the discrete walk being a succession of small steps, one could takeone large leap: multiplication by a single prime ideal of larger norm. One obtains a result
similar to Theorem 3.10, with κ = 1 and B = poly(nn , ∆K ). More generally, a conditionof the form B κ = poly(nn , ∆K ) suffices for rapid equidistribution.
s (D))].
Sketch of the proof. The distribution of the endpoint of the random walk is [WBk (W∞It is obtained by sampling [a] from [D], then applying the continuous walk and k discrete
steps with starting point [a]. Observe that it is also the distribution of [a] + [b] where [a]s (1 )) (the endpoint ofis sampled from [D], and [b] is sampled for the distribution WBk (W∞0ksa random walk with starting point [0]). To prove that [WB (W∞ (D))] is close to uniform,s (1 ))] is close to uniform.
it is thus sufficient to prove that [WBk (W∞0s
The distribution Gs = W∞ (10 ) is the Gaussian distribution on H with standard deviation s centered at the origin.
The discrete step can be seen as an operator WB : L2 (Pic0K ) → L2 (Pic0K ), sending any
function f : Pic0K → C toX
1
WB (f ) : a 7−→
f (a − d0 (p)),#PK (B)p∈PK (B)averaging over all “incoming neighbors” of a. The proof proceeds with a spectral analysis
of WB , and decomposing [Gs ] as a sum of eigenfunctions. Showing that all the eigenvalues
are small except for the constant eigenfunction, all terms in the decomposition of [WBk (Gs )]vanish at an exponential rate in k — except the constant term, which corresponds to theuniform distribution.
The discrete walk operator WB is in fact a Hecke operator, whose spectral properties[
0
are well studied. It can easily be verified that the characters χ ∈ Pic
are eigenfunctions
K

with eigenvalueλχ =1#PK (B)

X
p∈PK (B)χ(d0 (p)),

72

3. IDEAL LATTICES[
0
where χ is the complex conjugate of χ. In other words, for any χ ∈ Pic
K , we have
WB (χ) = λχ χ. In particular, the constant function 1 has eigenvalue λ1 = 1, and all othereigenvalues satisfy |λχ | ≤ 1. Decomposing [Gs ] as a sum of eigenfunctions, we getX1[Gs ] =+cχ χ,
Vol(Pic0K )
\
0
χ∈Pic
K

where cχ ∈ C are the Fourier coefficients of [Gs ]. Applying the discrete walk operator, we
getX
1[WBk (Gs )] =+λkχ cχ χ.
Vol(Pic0K )
\
0
χ∈Pic
K

As soon as |λχ | < 1, the terms λkχ cχ vanish as k grows. But they do not vanish uniformly,
as eigenvalues λχ could be arbitrarily close to 1. To proceed, we distinguish two kinds ofterms according to the analytic conductor q∞ (χ):• Low-frequency characters. When the analytic conductor q∞ (χ) is small, we canthink of χ as a low frequency character. In that case, the eigenvalue λχ is reasonably small. Indeed, applying classical bounds from analytic number theory [IK04,
Theorem 5.15], we have1
(3.2)
|λχ | ≤ 1/2 · poly(n, log(∆K ), log(B), q∞ (χ)),
B
which can be made arbitrarily small by choosing B large enough. We can enforce
a clear, uniform gap |λχ | < 1/2 < 1, and the corresponding terms λkχ cχ χ vanish
rapidly and uniformly.
• High-frequency characters. When the analytic conductor q∞ (χ) is large, we canthink of χ as a high frequency character. In such a case, the above bound (3.2) isvacuous: the right-hand side could be larger than 1, while we know that λχ ≤ 1.
This is where our choice of the Gaussian distribution Gs comes in handy: its
Fourier coefficients cχ vanish rapidly for large “frequencies” q∞ (χ). In otherwords, while the decaying rate of λkχ cχ χ may not be so rapid in k, the coefficientcχ is vanishingly small to begin with, when q∞ (χ) is large.
In summary, we have
X
X
1
[WBk (Gs )] =λkχ cχ χ +λkχ cχ χ ,0 +Vol(PicK )χ of lowχ of high| {z }
frequency
frequency
The uniform
|
{z
}
|
{z
}
distribution
Decays rapidly with k

Small from the start,
and cannot increase

which means that [WBk (Gs )] rapidly approaches the uniform distribution.



3.4. Average hardness of ideal lattices
Our original motivation for the study of random walks in the Arakelov class group was tostudy the average hardness of computational problems in ideal lattices. We consider thefollowing version of the shortest vector problem for ideal lattices.
Problem 3.12 (Id-HSVPγ ). The ideal Hermite shortest vector problem with approximation factor γ is the following computational problem. Given a number field K of degree n
and a fractional ideal lattice Λ, find x ∈ Λ such that 0 < kxk ≤ γ · Vol(Λ)1/n .
Remark 3.13. We restrict the problem to fractional ideal lattices (i.e., fractional ideals seen
as ideal lattices through the Minkowski embedding) to avoid dealing with real numbers in
the input of the problem. Any ideal lattice can be approximated to arbitrary precision by3.4. AVERAGE HARDNESS OF IDEAL LATTICES

73

a fractional ideal (fractional ideals are dense in IdLatK ), and fractional ideals are mucheasier to manipulate. We consider them to be represented by a basis in Hermite Normal
Form (with respect to a well-chosen basis of K).
An average-case version of this problem requires a probability distribution on instancesof Id-HSVPγ . At this point of the chapter, the reader may suspect a natural candidate:the uniform distribution for the Haar measure. For computational purposes, we would
rather have a discrete distribution supported on fractional ideal lattices (or even integral— we can always rescale a fractional ideal to an integral one). For complexity-theoreticor cryptographic applications, one looks for distributions with certain valuable properties,
like being efficiently sampleable, easy to analyse, or supported on integral ideals of “small”
norm. Three distributions for Id-HSVPγ instances have been considered.
(1) Inverse-of-prime distribution. In [Gen09, Gen10], Gentry considers ideal lattices
sampled as the inverse of a uniformly random prime ideal with norm in a prescribed interval [A, B]. We refer to the corresponding average-case problem as
P−1 -Id-HSVPγ .
(2) Discrete Haar distribution. In the article [[BDPW20]], we consider a discretizationof the uniform distribution for the Haar measure. We refer to the corresponding
average-case problem as Haar-Id-HSVPγ .
(3) Prime distribution. In the article [[FPSW23]], we consider ideal lattices sampled asa uniformly random prime ideal with norm in a prescribed interval [A, B] (similar
to [Gen09, Gen10], but without the inversion). We refer to the corresponding
average-case problem as P-Id-HSVPγ .
These articles prove worst-case to average-case reductions for Id-HSVPγ for each of these
distributions (with a bounded loss in the approximation factor).
The “inverse of prime” distribution of [Gen09] may be surprising. This choice is explained by the fact that [Gen09] focuses on the bounded distance decoding problem (BDD),a problem dual to SVP. It is a convenient choice for studying BDD, but ill-suited for SVP.
Indeed, recall that we value distributions supported on integral ideals of “small” norm.
O(1)Gentry’s reduction allows for interval boundaries A and B as small as ∆K · nO(n) . Sampling p of norm at most B, inverting it, then rescaling it to an integral ideal yields an2O(n)instance of the form N (p)/p, with norm of the order of ∆K · nO(n ) . This is too large
for certain applications. Also note that the worst-case to average-case reduction of Gentry(and the algorithm to sample from this distribution) requires access to a factoring oracle(and otherwise runs in classical polynomial time).
The “discrete Haar distribution” is perhaps the most natural. It is mathematicallyvery convenient, thanks to the properties of the Haar distribution, such as the rapid
equidistribution of random walks, Theorem 3.10. The worst-case to average-case reduction (and the algorithm to sample from this distribution) from [[BDPW20]] runs in classicalpolynomial time, with no need for a factoring oracle. However, to obtain a “good enough”
approximation of the (continuous) Haar distribution, we define a discretization supported
2
O(1)on ideals of rather large norm, up to ∆K · 2O(n ) . We discuss this case in greater detailin Section 3.4.1.
Finally, the “prime distribution” is supported on integral ideals of much smaller norm:O(1)the bounds A and B can be as small as ∆K · nO(n) . It is the first distribution supported
on integral ideals of norm sufficiently small for certain applications. The worst-case to
average-case reduction proved in [[FPSW23]] unlocks the first distribution on instances for the
NTRU cryptosystem with a polynomial modulus whose hardness is supported by a worstcase lattice problem. The analysis of this distribution combines the results of [Gen09] withthe techniques of [[BDPW20]] (random walks on Arakelov class groups). Like the reduction

74

3. IDEAL LATTICES

of [Gen09], it requires a factoring oracle (and otherwise runs in classical polynomial time).
We discuss this case in greater detail in Section 3.4.2.
3.4.1. Hardness for the discrete Haar distribution. The random walks studied in
Section 3.3 hint at a natural strategy for a worst-case to average-case reduction, in thesame vein as Section 1.2.3. Suppose we have an oracle for Haar-Id-HSVPγ , i.e., solving
with good probability for “uniformly random” ideals. Let Λ be an arbitrary ideal lattice(a worst-case instance). We apply the following steps:(1) Randomization: from the starting point Λ, one can generate a random walkfollowing SectionQ3.3.1. It first consists in a discrete walk, replacing Λ with thesublattice Λ0 = ( i pi )Λ, for a random sequence of prime ideals (pi )i . Then, thecontinuous walk replaces Λ0 with Λ00 = δΛ0 where δ ∈ KR× is a random “distorsion”
close to the identity.
(2) Solving the average case: call the Haar-Id-HSVPγ oracle for the random ideal
Λ00 . Since Λ00 is close to uniform, the average-case oracle succeeds with good
probability. It returns an element x00 ∈ Λ00 such that 0 < kx00 k ≤ γ · Vol(Λ00 )1/n .
(3) Pulling back the solution: Return x = δ −1 x00 ∈ δ −1 Λ00 = Λ0 ⊆ Λ.
As required, we get x ∈ Λ. Let us estimate the approximation factorQachieved by thisstrategy. Since δ is close to the identity, we have kxk ≈ kx00 k. Let w = i pi be the ideal
corresponding to the discrete walk. We obtainkxk ≈ kx00 k ≤ γ · Vol(Λ00 ) n ≈ γ · Vol(Λ0 ) n = (γN (w) n ) · Vol(Λ) n .
1

1

1

1

Using the bounds B and κ from Theorem 3.10, we have N (w)1/n ≤ B κ/n . We obtain areduction from worst-case Id-HSVPγ 0 to average-case Haar-Id-HSVPγ with a loss ofγ 0 /γ ≈ B κ/n in the approximation factor. This loss is polynomial in the degree n and the
1/nroot-discriminant ∆K . More precisely, we prove in [[BDPW20, Theorem 4.5]] that we canachieve a loss of(ne n1/2Ofor prime-power
cyclotomic fields, assuming h+K ≤ (log n)
0
κ/n


γ /γ = O(B ) ≤ e 1−nC /n
1/(2n)O n· ∆K
for arbitrary number fields.
with h+K the class number of the maximal totally real subfield.
Discretization. The above discussion totally abstracts away the (significant) trouble ofdiscretization. In [[BDPW20]] we introduce a rounding procedure, which takes as input
an arbitrary ideal lattice, and returns a good approximation by a fractional ideal. The
actual average-case distribution for Haar-Id-HSVPγ is the result of sampling uniformly
at random for the Haar measure, then applying the rounding procedure. The rounding
procedure is itself randomized, and has the following properties:• The output is a good approximation of the input — its geometry is almost thesame.
• Given an input ideal lattice, the distribution on the output depends only on its
isomorphism class — not on a representative of the class.
• As a fractional ideal, the numerator and denominator of the output have bounded
norms.
When the input is a fractional lattice, there is an efficient algorithm to apply this rounding
procedure. In particular, one can efficiently sample from the discretized Haar distribution.
3.4.2. Hardness for random small-norm prime ideals. In the article [[FPSW23]], we
consider the average hardness of P-Id-HSVPγ , for ideal lattices sampled as a uniformly
random prime ideal with norm in a prescribed interval [A, B].

3.4. AVERAGE HARDNESS OF IDEAL LATTICES

75

Despite the similarity with P−1 -Id-HSVPγ , mimicking the technique of [Gen09] does
not work. The reduction in [Gen09] utilises the fact that O ⊂ p−1 , readily providing somereasonably small vectors like 1 ∈ p−1 . There is no exploitable analog for p.
However, we can still exploit the main result of [Gen09]: the worst-case to average-case
reduction from Id-HSVPγ 00 to P−1 -Id-HSVPγ 0 (for some approximation factors γ 0 andγ 00 ). We prove in [[FPSW23]] that P−1 -Id-HSVPγ 0 reduces to P-Id-HSVPγ , and deduce
the average-case hardness of P-Id-HSVPγ by composition of reductions:
Id-HSVPγ 00≤[Gen09]P−1 -Id-HSVPγ 0≤[[FPSW23]]

P-Id-HSVPγ .

The last reduction works as follows. Suppose we have an oracle for P-Id-HSVPγ , and weare given an instance p−1 of P−1 -Id-HSVPγ 0 . We proceed as follows:(1) Call the oracle on p, which finds (with good probability) a “small” element xp ∈ psuch that 0 < kxp k ≤ γ · Vol(p)1/n .
(2) Sample a pair (b, y) such that b is a uniformly random integral ideal of bounded
norm, and y ∈ (bp)−1 is small. This is some kind of trapdoor generation: first
generating an ideal b, then finding a small element y would be infeasible, but
generating both “simultaneously” can be done. It is not obvious how to perform
such a sampling task. For the moment, consider that this is feasible thanks to
the knowledge of a small element xp ∈ p, and using a factoring oracle.
(3) If b is not prime, try again from the start.
(4) Now that we have ensured that b is a random prime ideal, we can call the oracle(for the second time) on b, which finds a “small” element xb ∈ b such that0 < kxb k ≤ γ · Vol(b)1/n .
(5) Return x = xb · y ∈ b · (bp)−1 = p−1 .
We indeed obtain x ∈ p−1 as required, and x is a product of “small” elements, so it is itself“small”. It is a solution of P−1 -Id-HSVPγ 0 for some approximation factor γ 0 . We provein [[FPSW23, Corollary 5.3]] that this method achieves a loss in the approximation factor of1/n
γ 0 /γ = O(n∆K ).
The trapdoor generation of Step 2. Step 2 is the most subtle. It requires a combination ofingredients from [Gen09, Gen10] and from the upcoming Section 3.5.1 on ideal sampling.
Here, we only explain the ingredient from [Gen09, Gen10], which solves a simpler problemof the same type: sampling a random ideal a together with a small element α ∈ a.
From a random ideal, it may be hard to extract a small element, but one could proceed
the other way around: first sample a small element α ∈ OK , then let a = αOK . By
construction, α is small, and α ∈ a. The resulting ideal a may be random, but it is far
from any natural notion of uniformity: it is always a principal ideal.
To correct this obvious bias, one could replace the ideal αOK with a random idealcontaining α — in other words, a random ideal dividing αOK .QThis is where the needfor a factoring oracle arises: compute the factorization αOK = i qei i into distinct prime
ideals qi . One can then sample one of the ideals qi uniformly at random, and return (α, qi ).
Three obvious biases remain:(1) First, the distribution is now supported on prime ideals; this is not an issue.
(2) Second, small prime ideals are significantly overrepresented. This bias can becorrected by ignoring ideals below some bound A, and some rejection-sampling.
(3) Third, large principal prime ideals are overrepresented. Indeed, if αOK happens
to be prime, it is returned unchanged. More generally, there is a bias towards
large primes whose inverse class contains a small ideal. This bias can be correctedby ignoring ideals above some bound B.

76

3. IDEAL LATTICES

One can in fact show that for some appropriate bounds A and B, the above procedure
returns a pair (α, q) where α ∈ q is small and q is close to uniformly distributed among
prime ideals with norm in the interval [A, B].

3.5. A rigorous tool for algorithmic number theory
In this final section, we shift our attention away from cryptography, and towards someof the most fundamental problems in computational number theory: the computation ofclass groups, unit groups, or a variety of other problems related to the manipulation ofideals in number fields.
Many number theoretic algorithms resort to heuristic assumptions for their analysis.
This issue concerns even these field-defining problems. This persistent need for heuristic
assumptions often stems from a step of this form: given an ideal class [a] of a number fieldK, find a representative b ∈ [a] belonging to a particular family S of ideals (for instance, thefamily of smooth ideals). It is relatively simple to design an algorithm for this task: sample
a random representative b ∈ [a], and hope that it belongs to the desired family S. One thenheuristically argues that the probability that b ∈ S should be proportional to the densityof S. For instance, the subexponential density of smooth ideals heuristically implies that
one can find smooth representatives in subexponential time. This is the heart of state-ofthe-art algorithms to compute class groups, unit groups, or generators of principal ideals
in number fields [Buc88, LL93, BF14], and has long constituted a theoretical obstacle
overcome only by heuristic arguments (with the exception of quadratic fields [HM89]).
In the paper [[BPW24, Part 1]], we propose a general strategy to solve these ideal sampling tasks rigorously and efficiently, assuming only the Generalized Riemann Hypothesis.
Illustrating the power of this technique, we present in [[BPW24, Part 2]] the first algorithm
for computing class groups and unit groups of arbitrary number fields that provably runs
in probabilistic subexponential time, assuming GRH.
3.5.1. Sampling ideals in a class. Let S be an arbitrary family of ideals, and SB thefamily of B-smooth ideals (i.e., products of prime ideals of norm at most B). In [[BPW24,
Part 1]], we describe an efficient algorithm that samples b ∈ [a] such that b ∈ S · SBwith probability proportional to the density of S. The set SB is used to randomize theinput (it corresponds to the discrete walk of Section 3.3), and B can be chosen as small as(log ∆K )O(1) . In greater generality, we prove this result for arbitrary ray class groups, andwhen the set SB is restricted to ideals whose prime factors fall in a prescribed subgroup.
For concreteness, Theorem 3.14 below is a specialization of the main theorem of [[BPW24,
Part 1]] to the simplest case, without ray nor subgroups. Here, the quantity δS [rn ] is the
local density of S, i.e., the proportion of ideals of norm at most rn that belong to S. It is(b)<rn }essentially δS [rn ] ≈ #{b∈S|N#{b|N (b)<rn } , and tends to the natural density as r → ∞.
Theorem 3.14. Assuming the Generalized Riemann Hypothesis, there is a randomized
algorithm A such that the following holds. Let K be a number field, with degree n,discriminant ∆K , and ring of integers OK . Let a ⊆ OK be an integral ideal. Let ε ∈ R>0 ,let b ≥ 2 be an integer, and let r ≥ 16 · b2n/b · n7/2 · |∆K |3/(2n) .
Given the above data, the algorithm A outputs β ∈ a such that βa−1 ∈ S ·SB with probability at least δS [rn ]/3 − ε, for some smoothness bound B = (log |∆K | + log log(1/ε))O(1)and for any set S of integral ideals. Furthermore, the algorithm runs in expected polynomial
time in log |∆K |, log(N (a)), log(1/ε), bb , and in the length of the input.
Remark 3.15. Note that the algorithm is described in a slightly different way than theabove discussion: given a, we find β ∈ a such that βa−1 ∈ S · SB . The ideal βa−1 is in the3.5. A RIGOROUS TOOL FOR ALGORITHMIC NUMBER THEORY

77

inverse class of a, so up to an inversion, this problem is equivalent to the ideal sampling
problem discussed above.
Overview of the technique. The folklore strategy to solve ideal sampling tasks is the following. The input ideal a is seen as a lattice, via the Minkowski embedding. One mayfind a reasonably short basis of a (for instance, by means of LLL [LLL82]), which thenallows one to sample a reasonably short random element β ∈ a, and hope that the idealb = βa−1 belongs to the desired family S. One then typically argues (heuristically!) thatthe probability of success is proportional to the density of S.
To obtain a rigorous sampling algorithm, we proceed in two steps. First, we prove thata fairly straightforward strategy as above indeed has the desired probability of success when
the input a is treated as a random ideal lattice with uniformly random Arakelov class. Moreprecisely, we prove that there is a reasonably small “ball” rB (in the embedding space KR )such that the expected density of elements β ∈ a ∩ rB such that βa−1 ∈ S is proportional
to the density of S.
Second, we deal with arbitrary input a by randomizing its Arakelov class via a random walk, following Section 3.3. Concretely, the input a is multiplied by random idealsof small prime norm (the discrete part of the random walk), and is randomly distorted
according to some Gaussian distribution (the continuous part of the random walk). Theorem 3.10 ensures that the result is uniformly distributed in the Arakelov class group.
The discrete part of the random walk introduces small prime factors, hence our method
samples ideals in S ·SB instead of S. In all applications we are aware of, we have S = S ·SB .
The randomization step is a straightforward application of Section 3.3, so in the rest of
this section, we explain the main novelty of [[BPW24, Part 1]]: proving that the folklore sampling method works for random ideals whose Arakelov classes are uniformly distributed.
Sampling in a fixed ideal lattice. Let Λ = xa ∈ IdLat0K be a normalized ideal lattice. We
consider the following sampling procedure. It takes as input the ideal lattice Λ, and aparameter r > 0 controlling how large we want the sampled element to be.
(1) Consider a “ball” B in the embedding space KR . This is the shape we are goingto sample from. The reader may think of B as a unit ball in KR centered at theorigin. The conventional `2 -ball is not the most convenient choice. In [[BPW24]], we
consider the unit ball for the `∞ -norm. In [[FPSW23]] we achieve finer properties
by crafting a stranger shape.
(2) Sample β ← Λ ∩ rB uniformly at random. This finite set is the intersection ofa lattice with a “ball” of radius r. There is an efficient algorithm sampling fromthis distribution, at least when r is not too small.
(3) Return the integral ideal βΛ−1 .
Let us analyse the distribution of βΛ−1 . For the moment, we consider Λ to be fixed, andthe source of randomness is the uniform sampling β ← Λ ∩ rB. Consider the probability
for the output to be a particular ideal b:(3.3)#(gen(bΛ) ∩ rB)
Pr [βΛ−1 = b] = Pr [β generates the OK -module bΛ] =,β←Λ∩rBβ←Λ∩rB#(Λ ∩ rB)
where for any ideal lattice Λ, we denote by gen(Λ) = {x ∈ Λ | Λ = xOK } the set of OK generators (which may well be empty). The denominator #(Λ ∩ rB) is easy to estimate:assuming that rB is large enough (compared to the covolume of Λ — or more accurately,
to its covering radius), then #(Λ ∩ rB) is well-approximated by the volume-to-covolume

78

3. IDEAL LATTICES

ratio
(3.4)

#(Λ ∩ rB) ≈Vol(rB)
Vol(B)= rn.
Vol(Λ)|∆K |1/2

The numerator #(gen(bΛ) ∩ rB) presents a more delicate challenge. Clearly, it is zero×
if bΛ has no generator. If there exists a generator g ∈ gen(bΛ), then gen(bΛ) = gOK.
Recall the logarithm map
M
X
Log∞ : KR× −→R : (yσ )σ 7−→
log |yσν | · LνM.
ν

ν×
Writing α = Log∞ (g), we have Log∞ (gen(bΛ)) = α + Log(OK). Since the kernel of
Log |O× consists of the roots of unity µK , we obtain thatK×#(gen(bΛ) ∩ rB) = #µK · #((α + Log(OK
)) ∩
|
{z
}
A translated lattice

Log∞ (rB)| {z }).

A “logarithmic ball”

Now, we have reduced the problem of estimating Pr[βΛ−1 = b] to the problem of counting
×
the number of points in the intersection of a translated lattice (α + Log(OK)) with a kindof “logarithmic ball” Log∞ (rB). While not quite a ball, it is helpful to think of Log∞ (rB)
as a ball of radius log r.
One may be tempted to apply the same method as for the numerator: the intersection
×should be approximately the volume-to-covolume ratio Vol(Log∞ (rB))/ Vol(Log(OK)).
×
There are two issues with that. The first is that the lattice Log(OK) does not have fullrank in the ambient space: it spans the hyperplane H. Therefore, instead of the “ball”
Log∞ (rB), one should consider the volume of a “slice”
S (r, N (b)) = (α + H) ∩ Log∞ (rB).
As the notation suggests, it does not depend on a choice of α: the shifted hyperplane
α + H = Log∞ (N (b)1/n ) + H depends only on N (b). We should then expect
(3.5)

?

#(gen(bΛ) ∩ rB) ≈ #µK ·Vol(S (r, N (b)).
×
Vol(Log(OK))

The second issue is more fundamental: the volume-to-covolume approximation for lattice
points requires the volume of the ball to be significantly larger than the covolume of the×lattice. The volume of Log(OK) is, up to proper normalization, the regulator of the field,
and can grow exponentially in n and log |∆K |. Applying the volume-to-covolume approximation would require r to be unreasonably large.
Average sampling for uniform Arakelov classes. This is where randomization comes in.
While the estimation (3.5) is very inaccurate for any particular Λ, it does hold on average.
Suppose Λ ∈ IdLat0K is a random (normalized) ideal lattice, following a distribution D
such that the Arakelov class of Λ is uniformly distributed.
We make two observations. First, the quantity #(gen(bΛ) ∩ rB) depends only on the
Arakelov class (i.e., isometry class) of the ideal lattice Λ. Indeed, if Λ0 is isometric to Λ,
then so are bΛ and bΛ0 , and the isometry gives a bijection between gen(bΛ) ∩ rB andgen(bΛ0 ) ∩ rB. This is not exactly true for any choice of rB: we need that rB is somewhat
preserved by isometries (like an actual `2 -ball).
Second, the quantity #(gen(bΛ) ∩ rB) is non-zero only if the ideal class of bΛ istrivial, which means that its Arakelov class is in the image of TK → Pic0K . Recall that×
TK = H/ Log(OK) is the Log-unit torus. Let F ⊂ H be a fundamental domain for×
Log(OK ) (i.e., the projection F → TK is a bijection). The isometry class of bΛ is uniform

3.5. A RIGOROUS TOOL FOR ALGORITHMIC NUMBER THEORY

79

among lattices of volume Vol(b) = N (b)|∆K |1/2 . In particular, when non-empty, thetranslated lattice Log∞ (gen(bΛ)) is uniformly random among the translated lattices
×β + Log∞ (N (b)1/n ) + Log(OK) ⊂ Log∞ (N (b)1/n ) + H,

with β ∈ F . It is well-known that for any (full-rank) lattice L ⊂ V and measurable
set B ⊂ V , the average of #((α + L) ∩ B) over all possible translates α + L is equal toVol(B)/ Vol(L). We deduce that the estimation (3.5) holds on average in the following
sense:
EΛ←D [#(gen(bΛ) ∩ rB)]
h
i
#µK
×
=
· Eβ←F #((β + Log∞ (N (b)1/n ) + Log(OK)) ∩ Log∞ (rB))# Cl(K)#µK
Vol((Log∞ (N (b)1/n ) + H) ∩ Log∞ (rB))·×# Cl(K)
Vol(Log(OK))#µK=· Vol(S (r, N (b))).
×# Cl(K) Vol(Log(OK
))
=
(3.6)

We are ready to go back to estimating Pr[βΛ−1 = b], this time with a random ideal
lattice Λ. We have#(gen(bΛ) ∩ rB)(3.3)
Pr [βΛ−1 = b] = EΛ←DΛ←D#(Λ ∩ rB)β←Λ∩rB(3.4) |∆K |1/2 · EΛ←D [#(gen(bΛ) ∩ rB)]

≈

(3.6)

=

rn Vol(B)|∆K |1/2 · #µK
Vol(S (r, N (b)))·.
×
rn Vol(B)# Cl(K) Vol(Log(OK ))In summary, there is a constant CK , depending only on the field K, such that
Vol(S (r, N (b)))
Pr [βΛ−1 = b] ≈ CK ·.
Λ←D
rn Vol(B)β←Λ∩rBIn particular, the probability for the sampler to hit b depends only on N (b). With an appropriate choice of B, one can ensure that the volume of the slice S (r, N (b)) is essentiallyconstant for N (b) < rn , and suddenly drops to zero when N (b) > rn . On other words,
as a function of b, the probability Pr[βΛ−1 = b] is proportional to the indicator function
1N (b)<rn .
Needless to say, all the approximations we have made in this discussion require much
more careful consideration. Still, we hope that we have given enough elements to convince
the reader of the following informal lemma.
Lemma 3.16 (informal). When the input Λ has uniformly random Arakelov class, thesampler outputs an ideal βΛ−1 which is almost uniformly distributed among ideals of norm
at most rn .
Sketch of the proof of Theorem 3.14. The above informal lemma unlocks the proof of Theorem 3.14. On input an ideal a, first generate a random walk to Λ = δwa (where δ ∈ KR×is the continuous walk and the B-smooth ideal w ∈ SB is the discrete walk). Applying
Theorem 3.10, the ideal lattice Λ is uniformly random in the Arakelov class group. Sampling β0 ← Λ ∩ rB, Lemma 3.16 ensures that β0 Λ−1 is essentially uniform among integral
ideals of norm at most rn . We getX#{b ∈ S | N (b) < rn }Pr [β0 Λ−1 ∈ S] =Pr [β0 Λ−1 = b] ≈≈ δS [rn ],Λ←DΛ←D#{b | N (b) < rn }β0 ←Λ∩rBb∈S β←Λ∩rB

80

3. IDEAL LATTICES

where δS [rn ] is the “local density” of S, i.e., essentially the proportion of integral ideals ofnorm at most rn that belong to the family S.
Finally, output β = δ −1 β0 ∈ wa ⊂ a. We haveβa−1 = β0 Λ−1 w ∈ (β0 Λ−1 ) · SB ,which falls in S ·SB with probability at least (approximately) δS [rn ], proving Theorem 3.14.

3.5.2. Rigorous computation of class groups and unit groups. In [[BPW24, Part 2]],
we illustrate the power of the ideal-sampling technique of [[BPW24, Part 1]] by applying itto the computation of class groups and unit groups.
Let K be a number field of degree n and discriminant ∆K . The determination of thestructure of its class group Cl(K), together with a system of fundamental units, is oneof the main problems of computational number theory [Coh93, p. 217]. It has long been
believed that this task can be solved in probabilistic subexponential time. Such algorithms
have been described and analyzed under a variety of heuristic assumptions [Buc88, BF14].
Despite decades of investigation, only imaginary quadratic fields have been amenable toa rigorous analysis [HM89], assuming GRH. In [[BPW24, Part 2]], we present the first general algorithm for this problem that provably runs in probabilistic subexponential time,
assuming GRH. Recall the classical L-notationLx (α) = exp O(log x)α (log log x)1−α .
We prove the following theorem.
Theorem 3.17. Assuming the Generalized Riemann Hypothesis, there is a probabilistic
algorithm which, on input a number field K of degree n and discriminant ∆K , computes its
ideal class group and a compact representation of a fundamental system of units, and runs
in expected time polynomial in the length of the input, in L|∆K | (1/2), in Lnn (2/3), and inmin(ρK , L|∆K | (2/3 + o(1))), where ρK is the residue at 1 of the Dedekind zeta function ζK .
It has been conjectured since Buchmann’s 1988 heuristic algorithm [Buc88] that thisproblem can be solved in subexponential time L|∆K | (1/2) for any family of fields of fixed
degree. Theorem 3.17 implies this conjecture, assuming GRH.
Then, it was conjectured by Biasse and Fieker’s 2014 algorithm [BF14] that this problem can be solved in subexponential time even for varying degree. Again, Theorem 3.17
implies this conjecture, assuming GRH. However, Biasse and Fieker conjectured a complexity as in Theorem 3.17 where the quantity ρK is replaced with Lnn (2/3). In our
analysis, the quantity ρK arises from the best known estimates on the density of boundedsmooth ideals. It seems ρK should appear in the same way in the heuristic complexityof [BF14], unless one expects a better bound on the density of smooth ideals.
Blueprint of the algorithm. The algorithm in Theorem 3.17 follows the classical strategy
for the computation of the class group. Consider a bound B > 0, and let PK (B) be theset of prime ideals of norm at most B. For B large enough, this set PK (B) generates theclass group [Bac90]. “Computing the class group” consists in finding a basis of the kernelof the map
"
#
M
Y
np
Φ:
Z −→ Cl(K) : (np )p 7−→
p.
p∈PK (B)pThis kernel is a lattice. An element (np )p ∈ ker Φ is called a relation. All we need to dois generate many random relations, until they generate ker Φ. We thus need a relation
generator. The standard approach consists in generating a somewhat random B-smooth3.5. A RIGOROUS TOOL FOR ALGORITHMIC NUMBER THEORY

81

Q
Q
ideal s = p pap ∈ SB , then sample random elements β ∈ s until βs−1 = p pbp is also BQ
smooth. We obtain a “random” relation (ap + bp )p ∈ ker Φ, since [ p pap +bp ] = [βOK ] = 1.
This approach typically necessitates two heuristic assumptions:Q(1) Efficiency of the relation generator: the probability for βs−1 = p pbp to be
B-smooth is expected to be proportional to the density of B-smooth ideals.
(2) Random relations are well-distributed: the resulting relation (ap + bp )p ∈ ker Φshould be “random enough”: a few samples should rapidly generate ker Φ.
These are two serious challenges for a heuristic-free algorithm. While it is clear that the
new ideal-sampling technique, Theorem 3.14, solves the first challenge, the second requires
moreQ
work. The main idea is that, for some appropriate distribution on the input ideals = p pap , the sampler returns a relation (ap + bp )p ∈ ker Φ which follows a discrete
Gaussian distribution on ker Φ. Samples from a discrete Gaussian distribution rapidly
generate the lattice on which it is supported.
Computing S-units. While the main result Theorem 3.17 is stated as an algorithm forcomputing units and class groups, our algorithm actually does slightly more than that: it
computes the so-called Log-S-unit lattice for any set S of prime ideals. It is well known
that such an algorithm for S-units can be used to compute the class group and the unitgroup. The same method can also be used to solve other algorithmic problems, such as
the principal ideal problem (decide whether an ideal is principal, and when it is, find agenerator), or the class group discrete logarithm problem.
3.5.3. Further applications. Sampling smooth ideals is a task that regularly arises incomputational number theory. In [[BPW24, Part 2]], we focus on the problem of class group
computation, but it is more generally a common component of index-calculus algorithms,
like the general number field sieve for integer factorization [LL93] or the computation of
discrete logarithms in finite fields. This direction has not been investigated yet.
Applying the ideal-sampling method of [[BPW24, Part 1]] to the case where S is the setof prime ideals allows one to sample in the family S · SB of near-prime ideals, of particularinterest in that it constitutes a dense family of efficiently factorable ideals. Therefore, oursampling method provides a rigorous way to transform any ideal a into an equivalent ideal
b of known factorization. Obtaining such factorable ideals (or elements) is a key step inalgorithms to compute power residue symbols. Specifically, it allows one to perform the“principalization step” in [BP17, §5.2] efficiently. De Boer has developed this idea in his
PhD dissertation [Boe22], applying the main result of [[BPW24, Part 1]] to construct thefirst polynomial time algorithm to compute power residue symbols, assuming GRH.

BIBLIOGRAPHY[ACD+ 23]

Sarah Arpin, James Clements, Pierrick Dartois, Jonathan Komada Eriksen, Péter Kutas, and Benjamin Wesolowski. Finding orientations of supersingular elliptic curves
and quaternion orders. Cryptology ePrint Archive, Paper 2023/1268, 2023. https://eprint.iacr.org/2023/1268.
[ACL+ 23] Sarah Arpin, Mingjie Chen, Kristin E Lauter, Renate Scheidler, Katherine E Stange,and Ha TN Tran. Orienteering with one endomorphism. La Matematica, 2(3):523–582,
2023.
[Ajt99]Miklós Ajtai. Generating hard instances of the short basis problem. In Jiří Wiedermann, Peter van Emde Boas, and Mogens Nielsen, editors, Automata, Languages andProgramming – ICALP 1999, volume 1644 of Lecture Notes in Computer Science, pages
1–9, 1999.
[Arp23]
Sarah Arpin. Adding level structure to supersingular elliptic curve isogeny graphs.
Preprint arXiv:2203.03531, 2023. https://arxiv.org/abs/2203.03531.
[Bac90]Eric Bach. Explicit bounds for primality testing and related problems. Mathematics ofComputation, 55(191):355–380, 1990.
[Bay99]Eva Bayer. Lattices and number fields. Contemp. Math., 241, 1999.
[BBBF18] Dan Boneh, Joseph Bonneau, Benedikt Bünz, and Ben Fisch. Verifiable delay functions.
to appear in Advances in Cryptology – CRYPTO 2018, 2018.
[BCC+ 23] Andrea Basso, Giulio Codogni, Deirdre Connolly, Luca De Feo, Tako Boris Fouotsa,
Guido Maria Lido, Travis Morrison, Lorenz Panny, Sikhar Patranabis, and Benjamin
Wesolowski. Supersingular curves you can trust. In Carmit Hazay and Martijn Stam,
editors, Advances in Cryptology – EUROCRYPT 2023, volume 14005 of Lecture Notes
in Computer Science, pages 405–437. Springer, 2023.
[BDD+ 24] Andrea Basso, Luca De Feo, Pierrick Dartois, Antonin Leroux, Luciano Maino, Giacomo Pope, Damien Robert, and Benjamin Wesolowski. SQIsign2D-West: The Fast,
the Small, and the Safer. Cryptology ePrint Archive, Paper 2024/760, 2024. https://eprint.iacr.org/2024/760.
[BDFLS20] Daniel J Bernstein, Luca De Feo, Antonin Leroux, and Benjamin Smith. Faster computation of isogenies of large prime degree. Open Book Series, 4(1):39–55, 2020.
[BDPW20] Koen de Boer, Léo Ducas, Alice Pellet-Mary, and Benjamin Wesolowski. Random selfreducibility of Ideal-SVP via Arakelov random walks. In Daniele Micciancio and Thomas
Ristenpart, editors, Advances in Cryptology – CRYPTO 2020, volume 12171 of Lecture
Notes in Computer Science, pages 243–273. Springer, 2020.
[BdQL+ 19] Paul Bottinelli, Victoria de Quehen, Chris Leonardi, Anton Mosunov, Filip Pawlega,
and Milap Sheth. The dark sidh of isogenies. Cryptology ePrint Archive, Paper
2019/1333, 2019. https://eprint.iacr.org/2019/1333.
[BF14]
J.-F. Biasse and C. Fieker. Subexponential class group and unit group computation inlarge degree number fields. LMS Journal of Computation and Mathematics, 17:385–403,
1 2014.

84[BFH+ 24]
[BGJT14][BJW17][BKSW23][BKV19][BKW20][BMP23][Boe22][BP17][BPW24][Buc88][CD23][CDPR16][CDW17][CDW21][CGS14]

BIBLIOGRAPHYAlex Biryukov, Ben Fisch, Gottfried Herold, Dmitry Khovratovich, Gaëtan Leurent,
María Naya-Plasencia, and Benjamin Wesolowski. Cryptanalysis of algebraic verifiabledelay functions. To appear in Advances in Cryptology – CRYPTO 2024, 2024.
Razvan Barbulescu, Pierrick Gaudry, Antoine Joux, and Emmanuel Thomé. A heuristic
quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic.
In Phong Q. Nguyen and Elisabeth Oswald, editors, Advances in Cryptology – EUROCRYPT 2014, volume 8441 of Lecture Notes in Computer Science, pages 1–16. Springer,
2014.
Ernest Hunter Brooks, Dimitar Jetchev, and Benjamin Wesolowski. Isogeny graphs ofordinary abelian varieties. Research in Number Theory, 3(1):28, 2017.
Karim Belabas, Thorsten Kleinjung, Antonio Sanso, and Benjamin Wesolowski. A noteon the low order assumption in class group of an imaginary quadratic number fields.
Mathematical Cryptology, 3:44–51, Jul. 2023.
Ward Beullens, Thorsten Kleinjung, and Frederik Vercauteren. CSI-FiSh: Efficientisogeny based signatures through class group computations. In Steven D. Galbraith
and Shiho Moriai, editors, Advances in Cryptology - ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information
Security, volume 11921 of Lecture Notes in Computer Science, pages 227–247. Springer,
2019.
Dan Boneh, Dmitry Kogan, and Katharine Woo. Oblivious pseudorandom functions
from isogenies. In Shiho Moriai and Huaxiong Wang, editors, Advances in Cryptology- ASIACRYPT 2020 - 26th International Conference on the Theory and Applicationof Cryptology and Information Security, volume 12492 of Lecture Notes in Computer
Science, pages 520–550. Springer, 2020.
Andrea Basso, Luciano Maino, and Giacomo Pope. FESTA: fast encryption from supersingular torsion attacks. In Jian Guo and Ron Steinfeld, editors, Advances in Cryptology – ASIACRYPT 2023, volume 14444 of Lecture Notes in Computer Science, pages
98–126. Springer, 2023.
Koen de Boer. Random Walks on Arakelov Class Groups. PhD thesis, Leiden University,
2022.
Koen de Boer and Carlo Pagano. Calculating the power residue symbol and ibeta. In
ISSAC, volume 68, pages 923–934, 2017.
Koen de Boer, Alice Pellet-Mary, and Benjamin Wesolowski. Rigorous methods forcomputational number theory. Preprint available on demand, 2024.
Johannes Buchmann. A subexponential algorithm for the determination of class groups
and regulators of algebraic number fields. Séminaire de théorie des nombres, Paris,
1989:28–41, 1988.
Wouter Castryck and Thomas Decru. An efficient key recovery attack on SIDH. In
Advances in cryptology – EUROCRYPT 2023. Part V, volume 14008 of Lecture Notes
in Computer Science, pages 423–447. Springer, 2023.
Ronald Cramer, Léo Ducas, Chris Peikert, and Oded Regev. Recovering short generatorsof principal ideals in cyclotomic rings. In Marc Fischlin and Jean-Sébastien Coron,
editors, Advances in Cryptology – EUROCRYPT 2016, volume 9666 of Lecture Notes
in Computer Science, pages 559–585. Springer, 2016.
Ronald Cramer, Léo Ducas, and Benjamin Wesolowski. Short Stickelberger class relations and application to Ideal-SVP. In Jean-Sébastien Coron and Jesper Buus Nielsen,
editors, Advances in Cryptology – EUROCRYPT 2017, volume 10210 of Lecture Notes
in Computer Science, pages 324–348. Springer, 2017.
Ronald Cramer, Léo Ducas, and Benjamin Wesolowski. Mildly short vectors in cyclotomic ideal lattices in quantum polynomial time. Journal of the ACM, 68(2):8:1–8:26,
2021.
Peter Campbell, Michael Groves, and Dan Shepherd. Soliloquy:
A cautionary tale. ETSI 2nd Quantum-Safe Crypto Workshop, 2014. Available at
http://docbox.etsi.org/Workshop/2014/201410_CRYPTO/S07_Systems_and_Attacks/S07_Groves_Annex.pdf.

BIBLIOGRAPHY[CGS20][CHVW22][CII+ 23]

[CJS14][CK20][CL23][CLG09][CLM+ 18]

[CLP23][Coh93][Cos20][Cou06][CPV20][DDF+ 21]85

Perlas Caranay, Matthew Greenberg, and Renate Scheidler. Computing modular polynomials and isogenies of rank two drinfeld modules over finite fields. In 75 Years ofMathematics of Computation: Symposium on Celebrating 75 Years of Mathematics ofComputation, November 1-3, 2018, the Institute for Computational and Experimental
Research in Mathematics (ICERM), volume 754, page 283. American Mathematical
Soc., 2020.
Wouter Castryck, Marc Houben, Frederik Vercauteren, and Benjamin Wesolowski. On
the decisional Diffie-Hellman problem for class group actions on oriented elliptic curves.
Research in Number Theory, 8(4):99, 2022. Proceedings of the Fifteenth Algorithmic
Number Theory Symposium – ANTS-XV.
Mingjie Chen, Muhammad Imran, Gábor Ivanyos, Péter Kutas, Antonin Leroux, andChristophe Petit. Hidden stabilizers, the isogeny to endomorphism ring problem and thecryptanalysis of psidh. In Jian Guo and Ron Steinfeld, editors, Advances in Cryptology– ASIACRYPT 2023, Part III, volume 14440 of Lecture Notes in Computer Science,
pages 99–130. Springer, 2023.
Andrew Childs, David Jao, and Vladimir Soukharev. Constructing elliptic curve isogenies in quantum subexponential time. Journal of Mathematical Cryptology, 8(1):1–29,
2014.
Leonardo Colò and David Kohel. Orienting supersingular isogeny graphs. Journal of
Mathematical Cryptology, 14(1):414–437, 2020.
Giulio Codogni and Guido Lido. Spectral theory of isogeny graphs. Preprint
arXiv:2308.13913, 2023. https://arxiv.org/abs/2308.13913.
Denis X. Charles, Kristin E. Lauter, and Eyal Z. Goren. Cryptographic hash functions
from expander graphs. Journal of Cryptology, 22(1):93–113, Jan 2009.
Wouter Castryck, Tanja Lange, Chloe Martindale, Lorenz Panny, and Joost Renes.
CSIDH: an efficient post-quantum commutative group action. In Thomas Peyrin andSteven D. Galbraith, editors, Advances in Cryptology - ASIACRYPT 2018 - 24th International Conference on the Theory and Application of Cryptology and Information
Security, volume 11274 of Lecture Notes in Computer Science, pages 395–427. Springer,
2018.
Mingjie Chen, Antonin Leroux, and Lorenz Panny. Scallop-hd: group action from 2dimensional isogenies. Cryptology ePrint Archive, Paper 2023/1488, 2023. https://eprint.iacr.org/2023/1488.
Henri Cohen. A course in computational algebraic number theory, volume 8. SpringerVerlag Berlin, 1993.
Craig Costello. B-SIDH: supersingular isogeny diffie-hellman using twisted torsion. In
Shiho Moriai and Huaxiong Wang, editors, Advances in Cryptology - ASIACRYPT
2020 - 26th International Conference on the Theory and Application of Cryptology
and Information Security, volume 12492 of Lecture Notes in Computer Science, pages
440–463. Springer, 2020.
Jean Marc Couveignes. Hard homogeneous spaces. IACR Cryptology ePrint Archive,
Paper 2006/291, 2006. https://eprint.iacr.org/2006/291.
Wouter Castryck, Lorenz Panny, and Frederik Vercauteren. Rational isogenies fromirrational endomorphisms. In Anne Canteaut and Yuval Ishai, editors, Advances in
Cryptology - EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, volume 12106 of Lecture Notes in
Computer Science, pages 523–548. Springer, 2020.
Luca De Feo, Cyprien Delpech de Saint Guilhem, Tako Boris Fouotsa, Péter Kutas,
Antonin Leroux, Christophe Petit, Javier Silva, and Benjamin Wesolowski. Séta: Supersingular encryption from torsion attacks. In Mehdi Tibouchi and Huaxiong Wang,
editors, Advances in Cryptology – ASIACRYPT 2021, volume 13093 of Lecture Notes
in Computer Science, pages 249–278. Springer, 2021.

86[DFK+ 23]

[DG19][DH76][DKL+ 20]

[DKPS19][DLLW23][DLRW24][DMPR23][DMPS19][DPW19][EHL+ 18]

[EL24][FKMT22][FM02]

BIBLIOGRAPHY

Luca De Feo, Tako Boris Fouotsa, Péter Kutas, Antonin Leroux, Simon-Philipp Merz,
Lorenz Panny, and Benjamin Wesolowski. SCALLOP: scaling the CSI-FiSh. In Alexandra Boldyreva and Vladimir Kolesnikov, editors, Public-Key Cryptography – PKC 2023,
volume 13940 of Lecture Notes in Computer Science, pages 345–375. Springer, 2023.
Luca De Feo and Steven D. Galbraith. Seasign: Compact isogeny signatures from classgroup actions. In Yuval Ishai and Vincent Rijmen, editors, Advances in Cryptology EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, volume 11478 of Lecture Notes in Computer
Science, pages 759–789. Springer, 2019.
Whitfield Diffie and Martin Hellman. New directions in cryptography. IEEE transactions on Information Theory, 22(6):644–654, 1976.
Luca De Feo, David Kohel, Antonin Leroux, Christophe Petit, and Benjamin
Wesolowski. SQISign: Compact post-quantum signatures from quaternions and isogenies. In Shiho Moriai and Huaxiong Wang, editors, Advances in Cryptology – ASIACRYPT 2020, volume 12491 of Lecture Notes in Computer Science, pages 64–93.
Springer, 2020.
Cyprien Delpech de Saint Guilhem, Péter Kutas, Christophe Petit, and Javier Silva.
Séta: Supersingular encryption from torsion attacks. IACR Cryptology ePrint Archive,
Paper 2019/1291, 2019. https://eprint.iacr.org/2019/1291.
Luca De Feo, Antonin Leroux, Patrick Longa, and Benjamin Wesolowski. New algorithms for the Deuring correspondence - towards practical and secure SQISign signatures. In Carmit Hazay and Martijn Stam, editors, Advances in Cryptology – EUROCRYPT 2023, volume 14008 of Lecture Notes in Computer Science, pages 659–690.
Springer, 2023.
Pierrick Dartois, Antonin Leroux, Damien Robert, and Benjamin Wesolowski.
SQISignHD: new dimensions in cryptography. To appear in Advances in Cryptology– EUROCRYPT 2024, 2024.
Pierrick Dartois, Luciano Maino, Giacomo Pope, and Damien Robert. An algorithmic
approach to (2, 2)-isogenies in the theta model and applications to isogeny-based cryptography. Cryptology ePrint Archive, Paper 2023/1747, 2023. https://eprint.iacr.
org/2023/1747.
Luca De Feo, Simon Masson, Christophe Petit, and Antonio Sanso. Verifiable delay
functions from supersingular isogenies and pairings. In Steven D. Galbraith and Shiho
Moriai, editors, Advances in Cryptology - ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, volume
11921 of Lecture Notes in Computer Science, pages 248–277. Springer, 2019.
Léo Ducas, Maxime Plançon, and Benjamin Wesolowski. On the shortness of vectors to
be found by the Ideal-SVP quantum algorithm. In Alexandra Boldyreva and Daniele
Micciancio, editors, Advances in Cryptology – CRYPTO 2019, volume 11692 of Lecture
Notes in Computer Science, pages 322–351. Springer, 2019.
Kirsten Eisenträger, Sean Hallgren, Kristin Lauter, Travis Morrison, and Christophe
Petit. Supersingular isogeny graphs and endomorphism rings: Reductions and solutions. In Jesper Buus Nielsen and Vincent Rijmen, editors, Advances in Cryptology –EUROCRYPT 2018, pages 329–368, Cham, 2018. Springer International Publishing.
Jonathan Komada Eriksen and Antonin Leroux. Computing orientations from the endomorphism ring of supersingular curves and applications. Cryptology ePrint Archive,
Paper 2024/146, 2024. https://eprint.iacr.org/2024/146.
Tako Boris Fouotsa, Péter Kutas, Simon-Philipp Merz, and Yan Bo Ti. On the isogeny
problem with torsion point information. In Goichiro Hanaoka, Junji Shikata, and Yohei
Watanabe, editors, Public-Key Cryptography – PKC 2022, Part I, volume 13177 of
Lecture Notes in Computer Science, pages 142–161. Springer, 2022.
M. Fouquet and F. Morain. Isogeny volcanoes and the SEA algorithm. In Claus Fieker
and David R. Kohel, editors, Algorithmic number theory, 5th International Symposium –ANTS-V, volume 2369 of Lecture Notes in Computer Science, pages 276–291. Springer,
Berlin, 2002.

BIBLIOGRAPHY[FPSW23][FS86][Gen09][Gen10][GHS02][GKL+ 21]
[GPS20][GW17][HM89][HW23][IK04][JAC+ 17]
[JD11][JMKR23][JMV09][JN19][JW19][KLPT14]87Joël Felderhoff, Alice Pellet-Mary, Damien Stehlé, and Benjamin Wesolowski. Ideal-SVP
is hard for small-norm uniform prime ideals. In Guy N. Rothblum and Hoeteck Wee,
editors, Theory of Cryptography – 21st International Conference, TCC 2023, volume14372 of Lecture Notes in Computer Science, pages 63–92. Springer, 2023.
Amos Fiat and Adi Shamir. How to prove yourself: Practical solutions to identification and signature problems. In Andrew M. Odlyzko, editor, Advances in Cryptology– CRYPTO ’86, volume 263 of Lecture Notes in Computer Science, pages 186–194.
Springer, 1986.
C. Gentry. A Fully Homomorphic Encryption Scheme. PhD thesis, Stanford University,
2009.
Craig Gentry. Toward basing fully homomorphic encryption on worst-case hardness. In
Tal Rabin, editor, Advances in Cryptology – CRYPTO 2010, volume 6223 of Lecture
Notes in Computer Science, pages 116–137. Springer, 2010.
Steven D. Galbraith, Florian Hess, and Nigel P. Smart. Extending the GHS Weil descentattack. In Lars R. Knudsen, editor, Advances in Cryptology – EUROCRYPT 2002,
volume 2332 of Lecture Notes in Computer Science, pages 29–44. Springer, 2002.
Robert Granger, Thorsten Kleinjung, Arjen K. Lenstra, Benjamin Wesolowski, and Jens
Zumbrägel. Computation of a 30750-bit binary field discrete logarithm. Mathematics ofComputation, 90(332):2997–3022, 2021.
Steven D. Galbraith, Christophe Petit, and Javier Silva. Identification protocols andsignature schemes based on supersingular isogeny problems. Journal of Cryptology,
33(1):130–175, 2020.
Alexandre Gélin and Benjamin Wesolowski. Loop-abort faults on supersingular isogeny
cryptosystems. In Tanja Lange and Tsuyoshi Takagi, editors, International Workshop
on Post-Quantum Cryptography – PQCrypto 2017, pages 93–106. Springer, 2017.
James L Hafner and Kevin S McCurley. A rigorous subexponential algorithm for computation of class groups. Journal of the American mathematical society, 2(4):837–850,
1989.
Arthur Herlédan Le Merdy and Benjamin Wesolowski. The supersingular endomorphismring problem given one endomorphism. Cryptology ePrint Archive, Paper 2023/1448,
2023. https://eprint.iacr.org/2023/1448.
H. Iwaniec and E. Kowalski. Analytic Number Theory. Number v. 53 in American
Mathematical Society Colloquium Publications. American Mathematical Society, 2004.
David Jao, Reza Azarderakhsh, Matt Campagna, Craig Costello, Luca De Feo, BasilHess, Amir Jalili, Brian Koziel, Brian Lamacchia, Patrick Longa, et al. Sike: Supersingular isogeny key encapsulation. 2017.
David Jao and Luca De Feo. Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. In Bo-Yin Yang, editor, International Workshop on
Post-Quantum Cryptography – PQCrypto 2011, pages 19–34, 2011.
David Jacquemin, Anisha Mukherjee, Péter Kutas, and Sujoy SINHA ROY. Ready tosqi? safety first! towards a constant-time implementation of isogeny-based signature,sqisign. Cryptology ePrint Archive, Paper 2023/807, 2023. https://eprint.iacr.org/
2023/807.
D. Jao, S. D. Miller, and R. Venkatesan. Expander graphs based on GRH with anapplication to elliptic curve cryptography. Journal of Number Theory, 129(6):1491–1504,
2009.
Antoine Joux and Anand Kumar Narayanan. Drinfeld modules may not be for isogeny
based cryptography. Cryptology ePrint Archive, Report 2019/1329, 2019. https://ia.
cr/2019/1329.
Dimitar Jetchev and Benjamin Wesolowski. Horizontal isogeny graphs of ordinary
abelian varieties and the discrete logarithm problem. Acta Arithmetica, 187:381–404,
2019.
David Kohel, Kristin Lauter, Christophe Petit, and Jean-Pierre Tignol. On thequaternion `-isogeny path problem. LMS Journal of Computation and Mathematics,
17(A):418–432, 2014.

88[KMP+ 21]

[Kob87][Koh96][Kun22][Kup05][KV10][KW19][KW22][Ler23][LL93][LLL82][LM06][LMO79][LPR13][LR12][LS22][LW17][Mic07][Mil86][MMP+ 23]

BIBLIOGRAPHY

Péter Kutas, Chloe Martindale, Lorenz Panny, Christophe Petit, and Katherine E.
Stange. Weak instances of SIDH variants under improved torsion-point attacks. In toappear in Advances in Cryptology - CRYPTO 2021, Lecture Notes in Computer Science,
2021.
Neal Koblitz. Elliptic curve cryptosystems. Mathematics of computation,
48(177):203–209, 1987.
David Kohel. Endomorphism rings of elliptic curves over finite fields. PhD thesis, University of California, Berkeley, 1996.
Sabrina Kunzweiler. Efficient computation of (2n , 2n )-isogenies. Cryptology ePrint
Archive, Paper 2022/990, 2022. https://eprint.iacr.org/2022/990.
Greg Kuperberg. A subexponential-time quantum algorithm for the dihedral hidden
subgroup problem. SIAM Journal on Computing, 35(1):170–188, 2005.
Markus Kirschmer and John Voight. Algorithmic enumeration of ideal classes for quaternion orders. SIAM Journal on Computing, 39(5):1714–1747, 2010.
Thorsten Kleinjung and Benjamin Wesolowski. A new perspective on the powers of
two descent for discrete logarithms in finite fields. In Proceedings of the Thirteenth
Algorithmic Number Theory Symposium – ANTS-XIII, volume 2, pages 343–352. The
Open Book Series, Mathematical Sciences Publishers, 2019.
Thorsten Kleinjung and Benjamin Wesolowski. Discrete logarithms in quasi-polynomial
time in finite fields of fixed characteristic. Journal of the American Mathematical Society,35(2):581–624, 2022.
Antonin Leroux. Verifiable random function from the deuring correspondence andhigher dimensional isogenies. Cryptology ePrint Archive, Paper 2023/1251, 2023.
https://eprint.iacr.org/2023/1251.
Arjen K. Lenstra and Hendrik W. Lenstra. The development of the number field sieve,
volume 1554. Springer Science & Business Media, 1993.
Arjen K. Lenstra, Hendrik W. Lenstra, Jr., and László Lovász. Factoring polynomials
with rational coefficients. Mathematische Annalen, 261(4):515–534, 1982.
Vadim Lyubashevsky and Daniele Micciancio. Generalized compact knapsacks are collision resistant. In Michele Bugliesi, Bart Preneel, Vladimiro Sassone, and Ingo Wegener,
editors, Automata, Languages and Programming – ICALP 2006 (part II), pages 144–155,
2006.
J.C. Lagarias, H.L. Montgomery, and A.M. Odlyzko. A bound for the least prime idealin the Chebotarev density theorem. Inventiones mathematicae, 54:271–296, 1979.
Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On ideal lattices and learningwith errors over rings. Journal of the ACM, 60(6):43:1–43:35, 2013. Preliminary version
in EUROCRYPT 2010.
David Lubicz and Damien Robert. Computing isogenies between abelian varieties. Compositio Mathematica, 148(5):1483–1515, 2012.
Antoine Leudière and Pierre-Jean Spaenlehauer. Hard homogeneous spaces from theclass field theory of imaginary hyperelliptic function fields. Cryptology ePrint Archive,
Report 2022/349, 2022. https://ia.cr/2022/349.
Arjen K. Lenstra and Benjamin Wesolowski. Trustworthy public randomness with sloth,unicorn, and trx. International Journal of Applied Cryptography, 3(4):330–343, 2017.
Daniele Micciancio. Generalized compact knapsacks, cyclic lattices, and efficient oneway functions. Computational Complexity, 16(4):365–411, 2007. Preliminary version in
FOCS 2002.
V. S. Miller. Use of elliptic curves in cryptography. In Hugh C. Williams, editor, Advances in Cryptology – CRYPTO ’85, volume 218 of Lecture Notes in Computer Science,
pages 417–426. Springer, 1986.
Luciano Maino, Chloe Martindale, Lorenz Panny, Giacomo Pope, and Benjamin
Wesolowski. A direct key recovery attack on SIDH. In Carmit Hazay and Martijn Stam,
editors, Advances in Cryptology – EUROCRYPT 2023, volume 14008 of Lecture Notes
in Computer Science, pages 448–471. Springer, 2023.

BIBLIOGRAPHY[Onu21][Pet17][PFH+ 17]

[Piz90][Pom87][PR06][PR23][PRS17][PS21][PW18][PW24][Reg09][RK24][Rob22][Rob23][Rón92][RS06][Sch08][SEMR23][Sho97]89

Hiroshi Onuki. On oriented supersingular elliptic curves. Finite Fields and Their Applications, 69:101777, 2021.
Christophe Petit. Faster algorithms for isogeny problems using torsion point images. In
Tsuyoshi Takagi and Thomas Peyrin, editors, Advances in Cryptology - ASIACRYPT
2017, volume 10625 of Lecture Notes in Computer Science, pages 330–353. Springer,
2017.
Thomas Prest, Pierre-Alain Fouque, Jeffrey Hoffstein, Paul Kirchner, Vadim Lyubashevsky, Thomas Pornin, Thomas Ricosset, Gregor Seiler, William Whyte, and Zhenfei
Zhang. Falcon: Fast-Fourier lattice-based compact signatures over NTRU. NIST PostQuantum Cryptography Project, 2017.
Arnold K Pizer. Ramanujan graphs and Hecke operators. Bulletin of the American
Mathematical Society, 23(1):127–137, 1990.
Carl Pomerance. Fast, rigorous factorization and discrete logarithm algorithms. In
David S. Johnson, Takao Nishizeki, Akihiro Nozaki, and Herbert S. Wilf, editors, Discrete Algorithms and Complexity, pages 119–143. Academic Press, 1987.
Chris Peikert and Alon Rosen. Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices. In Shai Halevi and Tal Rabin, editors, Theory of Cryptography Conference – TCC, pages 145–166, 2006.
Aurel Page and Damien Robert. Introducing clapoti(s): Evaluating the isogeny classgroup action in polynomial time. Cryptology ePrint Archive, Paper 2023/1766, 2023.
https://eprint.iacr.org/2023/1766.
Chris Peikert, Oded Regev, and Noah Stephens-Davidowitz. Pseudorandomness of ringlwe for any ring and modulus. In Hamed Hatami, Pierre McKenzie, and Valerie King,
editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing – STOC 2017, pages 461–473. ACM, 2017.
Alice Pellet-Mary and Damien Stehlé. On the hardness of the NTRU problem. In Mehdi
Tibouchi and Huaxiong Wang, editors, Advances in Cryptology – ASIACRYPT 2021,
Part I, volume 13090 of Lecture Notes in Computer Science, pages 3–35. Springer, 2021.
Cécile Pierrot and Benjamin Wesolowski. Malleability of the blockchain’s entropy. Cryptography and Communications, 10(1):211–233, 2018.
Aurel Page and Benjamin Wesolowski. The supersingular endomorphism ring and one
endomorphism problems are equivalent. To appear in Advances in Cryptology – EUROCRYPT 2024, 2024.
Oded Regev. On lattices, learning with errors, random linear codes, and cryptography.
Journal of the ACM, 56(6):1–40, 2009. Preliminary version in STOC 2005.
Farzin Renan and Péter Kutas. Sqiasignhd: Sqisignhd adaptor signature. Cryptology
ePrint Archive, Paper 2024/561, 2024. https://eprint.iacr.org/2024/561.
Damien Robert. Some applications of higher dimensional isogenies to elliptic curves(overview of results). Cryptology ePrint Archive, Paper 2022/1704, 2022. https://eprint.iacr.org/2022/1704.
Damien Robert. Breaking SIDH in polynomial time. In Advances in cryptology – EUROCRYPT 2023. Part V, volume 14008 of Lecture Notes in Computer Science, pages
472–503. Springer, 2023.
Lajos Rónyai. Algorithmic properties of maximal orders in simple algebras over Q.
Computational Complexity, 2(3):225–243, 1992.
Alexander Rostovtsev and Anton Stolbunov. Public-key cryptosystem based on isogenies. IACR Cryptology ePrint Archive, Paper 2006/145, 2006. https://eprint.iacr.
org/2006/145.
René Schoof. Computing arakelov class groups. Algorithmic number theory: lattices,
number fields, curves and cryptography, 44:447–495, 2008.
Maria Corte-Real Santos, Jonathan Komada Eriksen, Michael Meyer, and Krijn Reijnders. AprèsSQI: Extra fast verification for SQIsign using extension-field signing. Cryptology ePrint Archive, Paper 2023/1559, 2023. https://eprint.iacr.org/2023/1559.
Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5):1484–1509, 1997.

90[Sil86][Sim05][Sim06][SSTX09][Vél71][Voi21][Wat13][Wes19a][Wes19b][Wes20][Wes21][Wes22a][Wes22b][Wes24][WJ15][WW20][YAJ+ 17]

BIBLIOGRAPHY

Joseph H. Silverman. The Arithmetic of Elliptic Curves, volume 106 of Gradute Texts
in Mathematics. Springer-Verlag, 1986.
Denis Simon. Solving quadratic equations using reduced unimodular quadratic forms.
Mathematics of Computation, 74:1531–1543, 2005.
Denis Simon. Quadratic equations in dimensions 4, 5 and more. Preprint, 2006.
See [Wat13] for a published review.
Damien Stehlé, Ron Steinfeld, Keisuke Tanaka, and Keita Xagawa. Efficient public key
encryption based on ideal lattices. In Mitsuru Matsui, editor, Advances in Cryptology –ASIACRYPT 2009, volume 5912 of Lecture Notes in Computer Science, pages 617–635.
Springer, 2009.
J. Vélu. Isogénies entre courbes elliptiques. Comptes rendus de l’Académie des Sciences,
Séries A-B, 273:A238–A241, 1971.
John Voight. Quaternion Algebras. Springer International Publishing, 2021. Graduate
Texts in Mathematics, No. 288.
Mark Watkins. Some comments about indefinite LLL. Diophantine Methods, Lattices,and Arithmetic Theory of Quadratic Forms, 587(233):32, 2013.
Benjamin Wesolowski. Efficient verifiable delay functions. In Yuval Ishai and Vincent
Rijmen, editors, Advances in Cryptology – EUROCRYPT 2019, volume 11478 of Lecture
Notes in Computer Science, pages 379–407. Springer, 2019.
Benjamin Wesolowski. Generating subgroups of ray class groups with small prime ideals.
In Proceedings of the Thirteenth Algorithmic Number Theory Symposium – ANTS-XIII,
volume 2, pages 461–478. The Open Book Series, Mathematical Sciences Publishers,
2019.
Benjamin Wesolowski. Efficient verifiable delay functions. Journal of Cryptology,
33(4):2113–2147, 2020.
Benjamin Wesolowski. The supersingular isogeny path and endomorphism ring problems are equivalent. In 62nd IEEE Annual Symposium on Foundations of Computer
Science – FOCS 2021, pages 1100–1111. IEEE, 2021.
Benjamin Wesolowski. Orientations and the supersingular endomorphism ring problem.
In Orr Dunkelman and Stefan Dziembowski, editors, Advances in Cryptology – EUROCRYPT 2022, volume 13277 of Lecture Notes in Computer Science, pages 345–371.
Springer, 2022.
Benjamin Wesolowski. Understanding and improving the Castryck–Decru attack on
SIDH. Archive ouverte HAL, Report hal-04557845, 2022. https://hal.science/
hal-04557845.
Benjamin Wesolowski. Computing isogenies between finite Drinfeld modules. To appear
in IACR Communications in Cryptology, 2024.
Benjamin Wesolowski and Pascal Junod. Ciphertext-policy attribute-based broadcast
encryption with small keys. In Soonhak Kwon and Aaram Yun, editors, Information
Security and Cryptology – ICISC 2015, volume 9558 of Lecture Notes in Computer
Science, pages 53–68. Springer, 2015.
Ryan Williams and Benjamin Wesolowski. Lower bounds for the depth of modular
squaring. IACR Cryptology ePrint Archive, Report 2020/1461, 2020. https://eprint.
iacr.org/2020/1461.
Youngho Yoo, Reza Azarderakhsh, Amir Jalali, David Jao, and Vladimir Soukharev.
A post-quantum digital signature scheme based on supersingular isogenies. In Aggelos
Kiayias, editor, Financial Cryptography and Data Security – 21st International Conference, FC 2017, volume 10322 of Lecture Notes in Computer Science, pages 163–181.
Springer, 2017.