Project topics and materials
Get Complete Project Material File(s) Now! »
Mathematical preliminaries for isogeny-based cryptography
The building block for isogeny-based cryptography is elliptic curves. An elliptic curve is a smooth curve of genus one with a distinguished rational point. To un-derstand this definition we start by recalling notions about quadratic fields and ideal class groups. We then study affine and projective plane curves, along with the notions of non-singularity, dimension, function fields, divisors and genus. Having gathered the tools to properly define elliptic curves, we turn to their properties: an elliptic curve is an algebraic variety but also an algebraic group. We define the addition in this group using divisors, then scalar multiplication and torsion subgroups. Finally, we introduce the invariant differential.
After studying properties of elliptic curves we focus on morphisms between such curves, namely isogenies. We define the notions of separable isogeny, dual and degree. We give V´elu’s formulae, which are used to compute isogenies in practice, as well as a concrete example. We conclude the section with an intro-duction to modular curves an their link to isogenies. We then focus on isogenies from one curve to itself, i.e. endomorphisms, and recall how the endomorphism ring of ordinary and supersingular curves differs. We describe the Deuring corre-spondence which links the world of isogenies with the world of fractional ideals, and introduce the action of the ideal class group on different subset of elliptic curves. Finally we introduce isogeny graphs to describe the structure of isoge-nies linking curves from a given set. With graphical example we highlight the differences that arise depending on the endomorphism ring properties.
Quadratic imaginary order and class groups
We start by recalling notions of quadratic fields, orders, (integral) ideals, invert-ible and principal fractional ideals, gathering the tools to formally define the ideal class group itself.
Quadratic fields, orders and ideals
A quadratic field is Q(√d) where d �= 0, 1 is a squarefree integer. If d < 0 then the field is called an imaginary quadratic field. The discriminant of Q(√d) is D = d if d ≡ 1 (mod 4) or D = 4d otherwise.
An order in a field k containing Q is a subring R of k that is finitely generated as a Z-module and is such that R ⊗Z Q = k. An order O is maximal if every order O� such that O ⊂ O� ⊂ k is such that O� = O. Any order of a quadratic field is contained in a unique maximal order (see [BV07] Theorem 8.1.4).
Proposition 1. Let O be an order of an imaginary quadratic field k = Q(√d).
The maximal order√is Ok = Z + ωZ, where ω = 12 (1 + d) if d is congruent to 1 modulo 4 or ω = d otherwise. If O is an order of a quadratic field k, then O is a submodule of the maximal order, and can be written as O = Z + fωZ, where f = [O : Ok] is called the conductor.
Proof. See [BV07] Proposition 7.2.6 and [Gal12] Section A.12..
Proposition 2. Let I be an integral ideal of an order O = Z + fωZ in Q(√d), √ √ where ω = d if d �≡ 1 (mod 4) and ω =12 (1 + d) otherwise. We have I = c(aZ + (b + fω)Z), where a, b and c are integers such that c > 0, a > b � 0, and
• a divides b2 − d if d �≡ 1 (mod 4) ;
• a divides b(b + 1) − d−41 if d ≡ 1 (mod 4) .
Proof. See [BV07], Equation (8.8) and Proposition 8.4.5, with q = 1, and √ Δ =√ f −d.
Recall that the norm of an ideal I is defined as N(I) = |O/I| . The norm is multiplicative, i.e. N(IJ) = N(I)N(J) . An ideal I strictly included in a ring R is said to be a prime ideal if for every element a and b in R such that ab belongs to I, then a or b belongs to I. Using the link between integral ideals and integral binary quadratic forms, it is possible to show that every ideal whose norm is coprime to the conductor has unique factorization into a product of invertible prime ideals (see [BV07] Theorem 8.6.8).
Example 1. The order Ok = Z+ (1+ 2 −3) Z is a maximal order of the quadratic field k = Q(√ −3). The suborder O = Z + 5√ Z has conductor 10. Set −3 √ ω = (1+ 2 −3) . The ideal I = 5(21Z + (5 − ω)Z) is an ideal of Ok, with norm 525. It is the product of three prime ideals, namely 3Z + (1 − 2ω)Z with norm 3, 7Z + (4 + 2ω)Z with norm 7, and 5Z with norm 25.
Fractional ideals
From integral ideals we move on to fractional ideals of an order O. Since frac-tional ideals are not ideals, we will reserve the term ideal for integral ideals in order to avoid confusion. Fractional ideals will always be named as such.
A fractional ideal of an order O in a field k is a subset a of k such that aa is an (integral) ideal O of k for some positive integer a ∈ Z. A fractional ideal of an order O in a quadratic field k is said to be principal if it can be written as a = αO for some α in k. It is said to be invertible if there exist a fractional ideal b such that ab = O .
In the maximal order of a quadratic field, all nonzero fractional ideals are invertible. Moreover every principal fractional ideal is invertible (see [BV07] Corollary 8.4.15, with the second point following from the definition).
The set of fractional ideal forms an abelian semigroup under multiplication (with usual multiplication of ideals). The set of invertible fractional ideals I(O) is a subgroup, in which the set of principle ideals P r(O) is a normal subgroup (see [BV07] Proposition 8.4.10 and Theorem 8.4.13).
Example 2. Consider the quadratic imaginary field k = Q(√ −3) and its max-imal order Ok = Z + √−3Z. Consider the ideal I = 6Z + (3 + √−3)Z of Ok.
Taking α = 2 + 34 −3 ∈ Q( −3)∗, αOk and αI are fractional ideals (and not an integral ideal) of Ok.
Ideal class group
Definition 4. Let O be an order of an imaginary quadratic field. The ideal class group is Cl(O) = I(O)/P r(O) .
Intuitively, this means that we will consider equivalence classes of invertible fractional ideals up to multiplication by an non-zero element of Q(√d). For example, the fractional ideals I and αI belong to the same class.
Proposition 3. The order of the ideal class group of Ok asymptotically satisfies log(# Cl(O)) ∼ log |d| .
Proof. The is a special case of the Brauer–Siegel theorem (see [Lan94]). See also [BV07] Theorem 9.3.10.
Algebraic plane curves
This section aims to gather all the elements needed to define elliptic curves, namely the notion of affine and projective spaces, plane curves, dimensions, smoothness and genus. See [Gal12] for references of the results in this section.
Affine plane curves
Let K be a perfect field. The affine 2-space over K is the plane A2(K) = {(x, y) : x, y ∈ K}. The set of K-rational points of A2 is the set A2(K) = {(x, y) ∈ A2 : x, y ∈ K}.
An affine plane curve is defined by a single polynomial equation f(x, y). An algebraic plane curve C is defined over K if its defining polynomial is defined over K . We denote this by C/K. If C/K is a curve defined by f(x, y) = 0 with K K �/ K is an extension, then C( K �) = { (x, y) ∈ f a polynomial in ¯[x, y], and A2(K�) : f(x, y) = 0}.
Projective plane curves
Let K be a perfect field. The projective 2-space (over K ), denoted by P 2 or 2 3 ¯ such that at least one parameter is P (K) is the set of all triplets (X, Y, Z) ∈ A nonzero, modulo the equivalence relation (X, Y, Z) � (X�, Y �, Z�) if there exists a λ ¯∗ such that X = λX�, Y = λY �, Z = λZ�. ∈ K ¯∗ is denoted by (X : Y : Z), and An equivalence class (λX, λY, λZ) : λ ∈ K the individual X, Y, Z are called homogeneous coordinates for the corresponding point in P2 . The set of K-rational points in P2 is the set P2(K) = {(X : Y : Z) ∈ P2 : X,Y,Z ∈ K}.
A projective plane curve is defined by a single homogeneous polynomial equation f(X, Y, Z) = 0.1 It is defined over K if its generating polynomial is defined over K . We denote this by C/K. If C/K is a projective plane curve defined by f(X, Y, Z) = 0 with f a homogeneous polynomial in ¯[X, Y, Z], and
K K�/K is an extension, then C(K�) = {(X : Y : Z) ∈ P2(K�) : f(X, Y, Z) = 0}.
Example 3. We start with an example of an affine plane curve. Let f = x3 +7x+21−y 2 ∈ K[x, y]. Then f defines an affine plane curve C/K = {(x, y) ∈ A2 : x3 + 7x + 21 − y2 = 0}. The polynomial F = X3 + 7XZ 2 + 21Z3 − Y 2Z = Z3f(X/Z, Y /Z) ∈ K[X, Y, Z] is homogeneous, and defines a projective closure of C in P2.
Function field
Affine case
Definition 5. Let C be a affine algebraic plane curve defined over K generated by a polynomial f. The coordinate ring of C over K is K[C] = K[x, y]/(f). The function field is K(C) = {f1/f2 : f1, f2 ∈ K[C], f2 ∈/ (f)}S with the equivalence relation f1/f2 ≡ f3/f4 if and only if f1f4 − f2f3 ∈ (f), the ideal of K[C] generated by f.
In other words, K(C) is the field of fractions of the affine coordinate ring K[C] over K. Elements of K(C) are called rational functions. For a ∈ K the rational function f : V → k given by f(P ) = a is called a constant function.1 ¯ d f(X, Y, Z)
A polynomial f ∈ K[X, Y, Z] is homogeneous of degree d if f(λX, λY, λZ) = λ for all λ ¯. ∈ K
Projective case
Definition 6. Let C be a projective algebraic set defined over K. The homoge-nous coordinate ring of C over K is K[C] = K[X, Y, Z]/f. The function field is K(C) = {f1/f2 : f1, f2 ∈ K[C] homogeneous of the same degree , f2 ∈/ (f)} with the equivalence relation f1/f2 ≡ f3/f4 if and only if f1f4 − f2f3 ∈ (f).
In other words, K(C) is the field of fractions of the projective coordinate ring K[C] over K. Elements of K(C) are called rational functions.
Smooth algebraic plane curves
We study the regularity, or smoothness, of a curve. As an introduction to this notion, we provide two examples in figures 2.1 and 2.2. The first former is regular whilst the latter presents a singularity at the origin. We then formally define these two notions.
Projective case
Let C be a projective plane curve, let P ∈ C , and choose A2 ⊂ P2 with P ∈ A2. Then C is nonsingular (or smooth) at P if C ∩ A 2 is nonsingular at P . If C is nonsingular at every point, then we say that C is nonsingular.
Example 5. The curve C = {(X : Y : Z) ∈ P2 : X3 + 7XZ2 + 21Z3 −Y 2Z = 0 is a smooth projective plane curve. Indeed let P ∈ C different from the point at the infinity. Then taking an affine plane S with Z �= 0, C ∩ S = {(x, y) ∈ A2 : x3 + 7x + 21 − y 2 = 0), which is smooth. For the point at the infinity, we choose another affine plane S with Y �= 0 and proceed similarly.
Morphisms of plane curves
Let C be a plane curve and let f ∈ K(C). Then f is defined or regular at P if it can be written as f1/f2 with f2(P ) �= 0 with1f, f2 ∈ K[C].
Definition 7. Let C and C� be two plane curves defined over K. A rational map ϕ : C → C� over K which is regular at every point P ∈ C(K) is called a morphism. If there exists a morphism ψ : C� → C over K such that ϕ ◦ ψ and ψ ◦ ϕ are the identity on C� and C, respectively, then ϕ is a plane curve isomorphism.
Divisor of a function
The divisor of a function is a formal sum representing its zeros and poles counted with multiplicities. The formal definition of a divisor requires the notion of the valuation of a function at a point. The valuation carries the information of the behaviour of the function at this point: if it is a zero (resp. a pole), the valuation is equal to its multiplicity (resp. minus its multiplicity); otherwise, the valuation is simply zero. To formally define divisors of functions, we first introduce the local ring of a variety and its maximal ideal.
Definition 8. Let C be a plane curve over K. The local ring over K of C at a point P ∈ C(K) is OP,K(x,y) = {f ∈ K(x, y) : f is regular at P }. We write mP,K(x,y) = {f ∈ OP,K(x,y) : f(P ) = 0} ⊆ OP,K(x,y) for the maximal ideal of OP,K(x,y). A uniformizer for C at P is any generator of mP,K(x,y).
Definition 9. Let K be a field. A discrete valuation on K is a function v : K∗ → Z such that:
1. for all f, g ∈ K∗, v(f g) = v(f) + v(g);
2. for all f, g ∈ K∗ such that f + g �= 0, v(f + g) ≥ min(v(f), v(g));
3. there is some f ∈ K∗ such that v(f) = 1 (equivalently, v is surjective to Z).
Let C be a plane curve over K and P ∈ C(K). Let mP = mP,K(C) be as in Definition 8 and define m0P = OP,K(X). Let f ∈ OP,K(X) be such that f �= 0. Then the function f → Pv(f) = max{m ∈ N : f ∈ mmP} defines a discrete valuation. We say that vP (f) is the order of f at P . If vP (f) = 1 then f has a simple zero at P .
For each point P on the curve, let gP and hP be functions in OP,K(X)� such that gP /hP = f. The divisor of f is Div(f) = P ∈C(K) vP (gP )(P ) − � P ∈C(K) vP (hP )(P ). The divisor of a function is also called a principal divisor.
We write Prin(C) = {Div(f) : f ∈ K(C)∗}.
Divisor class group
The divisor group of a curve C defined over K, denoted by Div(C), is the free abelian group generated by the points of C. Thus a divisor D ∈ Div(C) is a formal sum D = nP (P ) , P ∈C(K) where nP ∈ Z and nP = 0 for all but finitely many P ∈ C(K). The degree of D is defined by � deg D = nP . P ∈C(K)
We write Div0(C) = {D ∈ Div(C) : deg(D) = 0} .
A divisor D = P ∈C(K) nP (P ) is effective, denoted by D ≥ 0, if nP ≥ 0 for every P ∈ C. Similarly, for any two divisors D1, D2 ∈ Div(C), we write D1 ≥ D2 to indicate that D1 − D2 is effective.
Definition 10. Let C be a curve defined over K and let D = P∈C( ) nP (P ) K ∈ K K ∈ K be a divisor on C. For σ Gal( / ) define σ(D) = C( ) nP (σ(P )).
Then D is defined over K if σ(D) = D for all σ ∈ Gal( /K)�.We write DivK(C) K for the set of divisors on C that are defined over K.
Lemma 4. Prin(C) is a subgroup of DivK0(C).
Proof. See [Gal12] Chapter 7 Section 7 Lemma 7.7.6. K 0 class group 0 is Pic0(C)
The degree zero divisor of a curve C over Div (C)/ Prin(C). We call two divisors D1, D2 ∈ Div (C) linearly equivalent and write D1 ≡ D2 if D1 −D2 ∈ Prin(C). The equivalence class (called a divisor class) of a divisor D ∈ Div0(C) under linear equivalence is denoted [D].
Table of contents :
1 Introduction
1.1 Landscape of cryptology
1.2 Computationally hard problems
1.3 Original Diffie–Hellman
1.4 Quantum revolution
1.5 Isogeny history
1.6 Problematic
1.7 Overview
I Preliminaries
2 Mathematical preliminaries for isogeny-based cryptography
2.1 Quadratic imaginary order and class groups
2.1.1 Quadratic fields, orders and ideals
2.1.2 Fractional ideals
2.1.3 Ideal class group
2.2 Algebraic plane curves
2.2.1 Affine plane curves
2.2.2 Projective plane curves
2.2.3 Function field
2.2.4 Smooth algebraic plane curves
2.2.5 Morphisms of plane curves
2.2.6 Divisor of a function
2.2.7 Divisor class group
2.2.8 Genus
2.3 Elliptic curves
2.3.1 Representation of elliptic curves
2.3.2 Algebraic group
2.3.3 Torsion
2.3.4 Invariant differential
2.4 Isogenies
2.4.1 Definitions
2.4.2 V´elu’s formulae
2.4.3 Example
2.4.4 Modular curves
2.5 Endomorphisms and curve classification
2.5.1 The endomorphism ring
2.5.2 Supersingular and ordinary cases
2.6 Deuring correspondence and the action of the ideal class group
2.6.1 Action of the ideal class group on elliptic curves
2.6.2 Deuring correspondence
2.7 Isogeny graphs
2.7.1 Ordinary case
2.7.2 Supersingular case over Fp
2.7.3 Supersingular over Fp2
3 Isogeny-based key exchange protocols
3.1 Ordinary case (CRS)
3.1.1 Security of the scheme and parameter sizes
3.1.2 Couveignes key exchange protocol
3.1.3 Rostovstev–Stolbunov key exchange protocol
3.1.4 Computation
3.2 Supersingular case over Fp2 (SIDH and SIKE)
3.2.1 Commutative diagram
3.2.2 SIDH key exchange protocol
3.2.3 Underlying security problems
3.2.4 From SIDH to SIKE
3.3 Supersingular case over Fp (CSIDH)
3.3.1 The ideal class group action
3.3.2 CSIDH key exchange protocol
3.3.3 Security of the scheme
3.3.4 Computation
3.4 Key validation
3.5 Comparison of CRS, SIDH, SIKE and CSIDH
II CSIDH implementation
4 Protecting CSIDH against side-channel attacks
4.1 Preliminaries: side-channel attacks
4.1.1 Timing attacks
4.1.2 Power consumption analysis
4.1.3 Fault injection
4.1.4 Constant-time and dummy-free algorithms
4.2 Previous constant-time implementations
4.2.1 Meyer–Campos–Reith
4.2.2 Onuki–Aikawa–Yamazaki–Takagi
4.3 Contribution: Fault-attack resistance
4.4 Contribution: Derandomized CSIDH
4.4.1 Flawed pseudorandom number generators
4.4.2 Derandomized CSIDH with dummies
4.4.3 Derandomized dummy-free CSIDH
4.5 Following constant-time implementations
III CSIDH generalization: higher-degree supersingular group actions
5 (d, �)-structures
5.1 Curves with a d-isogeny to their conjugate
5.1.1 Galois conjugates
5.1.2 (d, �)-structures
5.1.3 Isogenies of (d, �)-structures
5.1.4 Twisting
5.1.5 Involutions
5.1.6 Supersingular (d, �)-structures
5.1.7 Curves with non-integer d2-endomorphisms
5.2 Action on supersingular (d, �)-structures
5.2.1 Preliminaries on orientations
5.2.2 Action on primitive O-oriented curves
5.2.3 Natural orientation for supersingular (d, �)-structures
5.2.4 Link between natural and induced orientation
5.2.5 Free and transitive class group action
5.3 The (d, �)-supersingular isogeny graph
5.3.1 General structure
5.3.2 Examples
5.3.3 Involutions
5.3.4 Automorphism of order 3
5.4 Crossroads: curves with multiple (d, �)-structures
5.5 Map from (d, �)-structures to modular curves
5.6 Parametrization
5.6.1 Representing (2, �)-structures
5.6.2 Representing (3, �)-structures
5.6.3 Representing (5, �)-structures
5.6.4 Representing (7, �)-structures
6 HD CSIDH: Higher degree commutative supersingular Diffie–nHellman
6.1 HD CSIDH: Higher degree CSIDH
6.1.1 Hard problems
6.1.2 HD CSIDH
6.2 Practical computation
6.2.1 V´elu approach
6.2.2 Modular approach
6.3 Example
6.4 Public key compression
6.4.1 Key compression with modular curves
6.4.2 Key compression with parametrization
6.5 Public key validation
6.5.1 CSIDH versus HD CSIDH
6.5.2 Checking (d, �)-structures
6.5.3 Checking supersingularity: Sutherland’s algorithm
6.5.4 Adaptation of Sutherland algorithm
6.5.5 Determining the level
6.5.6 Validation algorithm for HD CSIDH
6.5.7 CSIDH and HD CSIDH validation comparison
IV Cryptanalysis
7 Cryptanalysis for SIDH
7.1 The Delfs–Galbraith algorithm
7.1.1 The general supersingular isogeny problem
7.2 Generalization
7.2.1 Generalized Delfs–Galbraith algorithm
7.2.2 Choosing the set D
7.2.3 Comparisons
7.3 Application to SIDH/SIKE cryptanalysis
7.3.1 Specific case: weak public keys in SIKEp434
7.3.2 General case: SIDH, shortcut
Perspectives
Bibliography
