Project topics and materials
Get Complete Project Material File(s) Now! »
Computationally hard problems
Protocols in cryptography rely on computationally hard problems, i.e. problems that are assumed not to be solvable efficiently by a computer unless the under-lying secret is known. This is crucial to ensure that the secret key in symmetric cryptography, or the private key in asymmetric cryptography, remain secret. Otherwise the protocol is corrupted and an attacker can decrypt messages or usurp the identity of someone else. An example of a hard computational prob-lem used in symmetric protocols is to compute preimages of hash functions, but from now on we will focus on asymmetric protocols.
Widely used computationally hard problems for asymmetric cryptography include factorization and discrete logarithm. Note that algorithms to solve these two problems are known, but that their requirements in time or memory grow sub-exponentially or exponentially with the size of the input, making them unpractical for the sizes used in cryptography.
Factorization Let p and q be two (large) primes. Given their product pq only, the factorization problem is to recover the factors p and q.
For this problem, the computational effort needed to find the answer grows subexponentially with the size of the integer pq to be factored. Hence, for p and q sufficiently large, factorizing their product becomes computationally infeasible (in the sense that the time needed would be greater than the age of the universe). The factorization problem is the underlying building block for the security of the widely used RSA scheme.
Discrete logarithm problem
Definition 1 (Discrete Logarithm Problem). Let (G, ×) be a group and g a generator. Let e be a secret integer. Given ge only, the discrete logarithm problem is to find e.
For this problem, the computational effort needed to find the answer depends on the underlying group G: it is quasi-polynomial or subexponential in finite fields, but exponential on elliptic curves. The discrete logarithm problem is the building block for elliptic curve cryptography.
Hard Homogeneous Spaces The discrete logarithm problem has been gen-eralized by Couveignes [Cou06] as an instance of a Hard Homogeneous Space (HHS). Hard Homogeneous Spaces are the kind of settings that allow key ex-change protocols.
Definition 2 (Homogeneous space). Let G be a finite commutative group. A homogeneous space H for G is a finite set H of the same cardinality S = #H = #G which is acted on freely and transitively by G.
This definition means that there is a single orbit and for any g ∈ G not the identity, the permutation of H induced by g has no fixed points. In other words, for two elements h1, h2 ∈ H there is a unique g in G that maps h1 to h2. The homogeneous spaces of interest for us are the ones where the following computational problems are easy:
• Group operations for G: Given strings encoding of group elements g1 and g2, decide if they represent elements in G and if these elements are equal. Given g1, g2 ∈ G compute g1g2, g1−1 and decide if g1 = g2.
• Random element for G: Find a random element in G with uniform prob-ability.
• Membership for H: Given a string h decide if h represents an element in H.
• Equality in H: Given h1, h2 ∈ H decide if h1 = h2.
• Action of G on H: Given g ∈ G and h ∈ H compute the action of g on h.
For cryptographic purposes, we are interested in homogeneous spaces having additional hard computational problems. We consequently define the notion of hard homogeneous spaces.
Definition 3 (Hard homogeneous space or HHS). A hard homogeneous space H for G is a homogeneous space for which the following problems are hard:
• Vectorization: Given h1, h2 ∈ H, find g ∈ G such that h2 is the result of the action of g on h1 .
• Parallelization: Let δ(h2, h1) be the unique group element mapping h1 to h2. Given h1, h2, h3 ∈ H, compute the unique h4 such that δ(h4, h3) = δ(h2, h1) .
It is conjectured (and proven in quantum settings) that parallelization and vectorization are equivalent, in the sense that if we can solve one problem effi-ciently, we can then use it to solve the other problem efficiently too.
Original Diffie–Hellman
We now present the original version of the Diffie–Hellman key exchange from [DH76] in Figure 1.1. It requires a finite cyclic group G of order n, and a generating element g in G.
Alice and Bob both choose random integers as private keys. They derive their public keys by exponentiating the group generator by their private keys. Both of them can compute a shared secret by applying their own private key to the counterpart’s public key, thanks to the group commutativity.
Note that a passive attacker observing the information exchanged between Alice and Bob would not be able to obtain any information on the private keys. The security depends on the hardness of the Diffie–Hellman problem, which is analogous to Parallelization in a HHS, and on the Discrete Logarithm Problem, which is analogous to Vectorization.
Quantum revolution
Contemporary cryptography faces a major threat: the arrival of quantum com-puters. The publication in 1994 of Shor’s algorithm [Sho94] has been a game changer. Shor proves that with a quantum computer, his algorithm can solve the factorization and discrete logarithm problem in polynomial time in the size of the input. This means that while these two building blocks problems remain hard against an attacker having only classical resources, they are no longer safe to be used against an attacker having access to a quantum computer.
Note that when Shor first published his algorithm, there were no quantum computers available yet. However after years of research, the development of quantum computers is rapidly growing. While bits on a classical computer have two distinct states 0 or 1, quantum bits, or qubits, can be in a superposition of both states 0 and 1. This allows new type of algorithms to be developed, namely quantum algorithms, that outperform classical ones on several computational problems, including several problems on which current cryptography is based.
Today, these quantum computers are not powerful enough to break currently used cryptography, but they might be in the near future. Current attempts are far from being enough to implement the quantum algorithm of Shor on integers of cryptographic size, which would need about 100 logical qubits, scaling up to thousands of physical qubits due to the need for error corrections. Nonetheless the power of quantum machines is rapidly growing, and large quantum machines capable of running interesting instances of Shor’s algorithm could be operational in five to ten years according to some experts, rendering obsolete many of the algorithms used in cryptology. While most symmetric cryptosystems can be patched by roughly doubling the size of the keys, the current state-of-the-art in asymmetric cryptography, including elliptic-curve based cryptography, will completely collapse, because the factorization and discrete logarithm problems would be rendered easy enough to solve.
The consequences of the availability of a fully operational quantum computer would be disastrous: secure communications, digital signatures, and online pay-ments, among others would not be safe to use any more. Considering this threat, there is an urgent need to find new protocols that would be resistant against quantum attacks. This is exactly what post-quantum cryptography is: algo-rithms, possibly running on classical computers, that can resist both classical and quantum adversaries.
The potential post-quantum cryptosystems have five dominant underlying mathematical techniques:
� Lattice-based systems, which rely on the hardness of problems such as finding a short vector in a given lattice;
� Code-based systems, which rely on hard problems from the theory of error correcting codes;
� Multivariate systems, which rely on the difficulty of solving various kinds of polynomial systems;
� Hash-based systems, which rely on the difficulty of inverting cryptographic hash functions;
� Isogeny-based systems, which take advantage of the hardness of finding paths in the graph of isogenies between ordinary or supersingular elliptic curves.
These problems are currently believed to be hard even for an attacker equipped with a quantum computer. To encourage efforts in post-quantum research, NIST (the American National Institute of Standards and Technology) has launched in 2017 a five-year-program, aiming to standardize a portfolio of quantum-resistant cryptosystems. The isogeny-based key encapsulation candidate, SIKE [JAC+17], is one of the alternate third round finalists.
Isogeny history
Elliptic curve cryptography has been used for years due to its efficiency and compactness. However it relies on the discrete logarithm problem which can be solved efficiently by quantum computers, triggering the need for a replacement.
Isogenies are morphisms between elliptic curves (preserving the point at in-finity). In that sense isogeny-based systems naturally evolve from elliptic curve cryptography. Isogenies have been historically studied for point counting algo-rithms or endomorphism ring computation on elliptic curves. However, while the underlying hard problems for elliptic-curve-based systems are easily attack-able by a quantum computer, the problem of finding an isogeny between two given elliptic curves remains conjecturally hard for both classical and quantum attackers. This makes isogenies a suitable candidate for post-quantum cryptog-raphy.
Isogeny-based cryptography is the youngest of post-quantum paradigm. How-ever it benefits from years of studies made on elliptic curve cryptography, which prepared a fertile soil for its growth. It first appeared in 1996, when Couveignes proposed a key-exchange protocol based on the action of the ideal class group on an isogeny class of ordinary elliptic curves [Cou06]. Although his discovery did not spark much interest at the time, a few years later in 2004 the same scheme was independently rediscovered by Rostovstev and Stolbunov [RS06] who claimed its post-quantum security. This time it captured more attention, or at least enough attention for a quantum subexponential attack on the scheme to be published. Indeed, Childs, Jao and Soukharev showed in 2010 the exis-tence of a quantum subexponential attack [CJS14]. This attack, added with the fact that the scheme is inconveniently slow, despite recent steps towards greater practicability of the scheme in [DKS18], seemed to temporarily end interest on the use of isogenies between ordinary elliptic curves for cryptographic purposes.
In order to avoid the quantum subexponential attack on the ordinary case, De Feo, Jao and Plˆut proposed in [JD11] and [DJP14] to use isogenies be-tween supersingular elliptic curves over Fp2 instead of ordinary ones. Indeed, the attack of [CJS14] strongly relies on the fact that the endomorphism ring of ordinary elliptic curves is commutative, which is not the case for supersin-gular curves over Fp2 . Using a commutative diagram to replace the missing commutativity, they provide a quantum-resistant key exchange protocol a` la Diffie–Hellman, named SIDH for Supersingular Isogeny Diffie–Hellman.
The SIDH protocol later lead to SIKE (Supersingular Isogeny Key Encapsu-lation), the isogeny-based proposal for the post-quantum NIST contest. It has moved on through the competition to reach the alternate third-round pool. It offers the shortest key sizes, perhaps the only one being in accessible range for practical use in some applications (less than kilobytes versus megabytes). Attempting to improve the ordinary case key exchange protocols of CRS, Castryck, Lange, Martindale, Panny and Renes had the idea of using supersin-gular curves defined over Fp (instead of Fp2 in SIKE). The endomorphism ring over Fp then happens to be an order in a quadratic field, which is commutative, exactly as in the ordinary case. Using ideas from De Feo, Kieffer and Smith initially intended to accelerate the ordinary case protocol [DKS18], they pro-posed in [CLM+18] a key exchange protocol with efficient public-key validation, and without sending additional torsion points. This scheme, named CSIDH for Commutative Supersingular Isogeny Diffie–Hellman still suffers from the subex-ponential quantum attack, but it offers a nice and complementary alternative to SIKE with an acceptable running time and the hope that it offers more flex-ibility to derive other primitives. Note that the existence of a subexponential quantum attack does not necessarily mean that the protocol is unusable: the extensively used RSA protocol also has a subexponential attack, and it is the most currently-used cryptographic protocol.
A growing number of isogeny-based protocols are being developed and stud-ied, offering a portfolio of quantum-resistant cryptographic primitives. We give a non-exhaustive list of such primitives to give an idea of the variety of possi-bilities:
• Hash functions: Charles–Goren–Lauter [CLG09];
• Key exchange protocols: Couveignes [Cou06], Rostovtsev–Stolbunov [RS06], SIDH [JD11], CSIDH [CLM+18], CSURF [CD20], BSIDH [Cos20], OS-IDH [CK20], CTIDH [BBC+21];
• Key encapsulation protocol: SIKE [JAC+17];
• Signatures: SeaSign [DG18], CSI–FiSh [BKV19], SQISign [DKL+20];
• Verifiable delay functions: [Wes20], [DMPS19];
• Oblivious Transfer: [Vit19];
• Threshold schemes: [DM20];
Isogeny-based cryptosystems benefit from being the natural successor of el-liptic curves cryptography, taking full advantage of the years of research and confidence on curves. It is also the only post-quantum system offering a close analogue of the Diffie–Hellman key exchange protocol, as opposed to key encap-sulation only.
On the downside, isogeny-based cryptography is criticised for being slower than other post-quantum families, meaning that much effort on implementations is needed to make protocols practicable. Since isogeny-based cryptography is a young field, more research is needed to increase the confidence in the underlying hard problems.
Problematic
Considering the advantages and drawbacks of isogeny-based cryptography de-scribed above, our problematic is the following: how can we increase confi-dence in the security and practicability of isogeny-based key exchange protocols?
We base our argumentation on four axes of confidence:
• Mitigating weaknesses: implementation to make key exchange fast and secure;
• Re-enforcing strengths: key management to provide protocols with effi-cient public key compression and validation;
• Constructive approach: generalization of existing protocols to cover the different needs of cryptography;
• Destructive approach: cryptanalysis to test and estimate the resistance of isogeny-based key exchanges.
Overview
We start by recalling in Chapter 2 the necessary mathematical preliminaries to study isogeny-based protocols. We first gather notions on quadratic fields in order to define the ideal class group in Section 2.1. Then, from algebraic plane curves in Section 2.2, we gather the tools to properly define elliptic curves in Section 2.3. We then define the morphisms between these curves, namely isogenies, in Section 2.4, and the classification of curves that arise from the structure of their endomorphism ring in Section 2.5. We make precise the action of the ideal class group in the case of ordinary and supersingular elliptic curves in Section 2.6, which allows us to detail the structure of isogeny graphs in Section 2.7.
In Chapter 3 we introduce isogeny-based key exchanges. We detail three ex-isting key exchange protocols : the ordinary case (CRS [Cou06, RS06, Sto10]) in Section 3.1 , the supersingular case of Fp2 (SIDH [JD11][DJP14]) in Section 3.2 and the supersingular case over Fp (CSIDH [CLM+18]) in Section 3.3. Eventu-ally, we compare these schemes in Section 3.5 and we briefly introduce notions of key management in cryptography in Section 3.4.
After these introductory chapters we study in Chapter 4 the constant-time implementation of the CSIDH key exchange protocol. We start by recalling several models of side-channel attacks in Section 4.1, and previous works on this subject in Section 4.2. Having gathered the necessary notions, we present a dummy-free fault-attack-resistant constant-time implementation of CSIDH in Section 4.3, as well as a derandomized variant implementation in Section 4.4. These two results are part of the joint work in [CCC+19]. For completeness, we present the results published by the research community after [CCC+19] in Section 4.5.
We then move on to a generalization of the CSIDH group action in Chap-ter 5. The results of this section have been published in [CS21]. The chapter begins with the study of curves having a degree-d isogeny to their Galois conju-gate in Section 5.1. We call these (d, �)-structures. Next we prove in Section 5.2 that there is a free and transitive action of the ideal class group of Q(√−dp) on isogeny classes of (d, �)-structures. This result allows us to prove and de-scribe the structure of the isogeny graph of (d, �)-structures in Section 5.3. We eventually show how these structures can be parametrized via modular curves in Section 5.5 and Section 5.6.
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
Notations and conventions
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 DiffieHellman
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
