Criptografia basada en isogènies

Abstract

[en] One of the central concepts in cryptography is encryption, which can be classified as symmetric or asymmetric depending on whether the used keys are shared by the implicated parts or not. The most used ciphers are symmetric, but they require the parts to agree on the key to be used. To satisfy this need, Diffie and Hellman proposed their key exchange protocol, based on the difficulty of solving the discrete logarithm problem in a cyclic group. With the foreseeable creation of sufficiently powerful quantum computers, this and other problems could become solvable in polynomial time. This creates the need of introducing new key exchange methods that are resistant to quantum cryptanalysis. In this project we study the SIDH/SIKE protocol, a candidate for the postquantum cryptography standardization process by NIST, which is based on the problem of finding isogenies between two elliptic curves. An elliptic curve is a plane curve defined by a cubic equation. These curves have the property of being both algebraic curves and abelian groups. Nonconstant morphisms between elliptic curves that maintain both structures are called isogenies, and they can be computed in linear time in the size of their kernel. In our case, all curves and morphisms are defined over a finite field \mathbb{F}_{p^{2}}, as we are working with supersingular elliptic curves. We obtain a key exchange system in which a private key is a subgroup of an elliptic curve, and its associated public key is the image curve of the isogeny that has such subgroup as kernel. In addition, the image of two auxiliary points by the secret isogeny is revealed to make an exchange. To break an SIDH key one needs to find the isogeny connecting the protocol's initial curve with the public key. The best classical attack to do this requires $O(\sqrt[4]{p})$ memory space and $O(\sqrt[4]{p})$ isogeny evaluations, and the best known quantum attack requires $O(\sqrt[6]{p})$ isogeny evaluations. Therefore, the SIDH protocol is considered secure. However, in a key reuse situation, Galbraith et al. have given an attack through which one learns a private key in only $\frac{1}{2} \log _{2} p$ steps, by maliciously modifying the auxiliary points. The SIKE protoool is introduced to avoid this kind of attacks.