• elliptic curves
• isogeny
• post-quantum cryptography
• supersingular

Quantum computation has drastically changed the concept of computationally hard problem. As a consequence, many classical cryptosystems turn out to be unsafe and the issue of figuring out quantum resistant protocols has given rise to an active research area. In this thesis we focus on a system proposed by David Jao and Luca De Feo based on elliptic curves over finite fields. An elliptic curve is a nonsingular projective curve of genus one with a specified base point. Without loss of generality, to a practical aim, we intend in this thesis elliptic curves as plane nonsingular cubics with fixed Weierstrass coordinates.
These varieties are particularly interesting due to the fact that they can be endowed with a group law, expressed in terms of regular morphisms.
Hence both the geometric and the algebraic structure are compatible. The maps between elliptic curves which respect this double characterization are called isogenies and they have a central role in the cryptosystem we are dealing with.
The protocol we study is a public key exchange on the model of the one purposed by Diffie and Hellman in 1976. The Diffie Hellman system (DH) allows the two parties to share a secret that can be deduced from the public keys and either of the two private keys. In its basic form, given $g$ a generator of $\F_p^*$ the private keys are two integer $a,b$, the public keys are $\alpha = g^a$ and $\beta = g^b$, and the shared secret is $g^{ab} = \alpha^b = \beta^a$.
The original method relies on the hardness of computing the discrete logarithms over finite fields. Moreover, in literature, there exist many variants also based on discrete logarithm problem over elliptic curves.
The state of art classical attacks to DH protocol run in subexponential time, in the case of finite fields, and in exponential time, in the case of elliptic curves. Shor in has proven that a quantum computer can solve the discrete logarithm problem over finite abelian group in polynomial time. This means that these protocols are not included between the quantum resistant ones.
However, such model can be adapted to produce a key exchange which is instead safe from both classical and quantum attacks: the Supersingular Isogeny Diffie Hellman key exchange (SIDH).
Let $p,\ell_A,\ell_B\in\Z$ be prime and $E_0$ a supersingular elliptic curve over $\F_{p^2}$. The private keys are two points $R_A,R_B$ of fixed (public) order $\ell_A^{e_A}$ and $\ell_B^{e_B}$ and the public keys are $E_A=E_0/<R_A>$ and $E_B=E_0/<R_B>$, i.e. the codomains of the isogenies $\phi_A and $\phi_B$ whose kernels are the fixed cyclic subgroups. The shared key is the $j$ invariant of the curve $E=E_A/<\phi_A(R_B)>=E_B/<\phi_B(R_A)>$, differently form DH to recover $E$ it is necessary that the two parties provide, as additional information in the public keys, the images of the $E_0[\ell_A^{e_A}]$ and $E_0[\ell_B^{e_B}]$, respectively.
Our aim is to deepen the theoretical bases and the mathematical background in order to investigate the actual security of this system.
In chapter 1, we collect definitions, facts and fundamental notions about elliptic curves. In chapter 2, we summarize basic knowledge of public key cryptography, % giving the formal definition of cryptosystem, we describe the Diffie Hellman protocol and we analyze and discuss the impact of quantum computation in cryptography.
The security of SIDH is based on the fact that, given two elliptic curves defined over a finite field, to find an isogeny between them is supposed to be hard, also in quantum context. In chapter 3, we describe a method to associate connected undirected multigraphs to classes of isogenous curves and we explain how to translate isogenies in terms of paths in that graphs.
We also see the connection that such graphs have with classes of ideals and the good properties deriving from it.
We distinguish the case in which the endomorphism ring is an order in a number field (ordinary curves) from the case in which it is an order in a quaternion algebra (supersingular curves).
In the first case we have a commutative ring and the graphs obtained have regular and rigid structures, in the latter case the ring is noncommutative and the graphs are more complicated.
In chapter 4, we describe the best currently known quantum algorithms to solve the general isogen problem, i.e. the problem to find an isogeny between fixed elliptic curves.
In particular, we show that the non commutativity of the endomorphism ring makes the problem harder for supersingular elliptic curves.
Finally, in chapter 5 we define the Supersingular Isogeny Diffie Hellman protocol. We discuss the parameters choice in order to maximize the security, in view of the results of the previous chapters, and we give some examples.
Indeed proving that the general isogeny problem is easy would imply that the system is not secure.
It is not certain if the vice versa is true, since during the key exchange are given additional information about the action of the isogenies over torsion points.
On this matter, we examine a recent work of Petit, who has shown that, if we consider some variations of the parameters choice, such additional information actually decrease the hardness of the problem. For the original proposal by Jao and De Feo the problem is still open.