Please use this identifier to cite or link to this item: http://hdl.handle.net/2445/164891
Title: Criptografia basada en isogènies
Author: Florit Zacarías, Enric
Director/Tutor: Guitart Morales, Xavier
Seguí Mesquida, Santi
Fernández, Ramsès
Keywords: Xifratge (Informàtica)
Treballs de fi de grau
Ordinadors quàntics
Corbes el·líptiques
Varietats abelianes
Data encryption (Computer science)
Bachelor's thesis
Quantum computers
Elliptic curves
Abelian varieties
Issue Date: 19-Jan-2020
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.
Note: Treballs Finals de Grau de Matemàtiques, Facultat de Matemàtiques, Universitat de Barcelona, Any: 2020, Director: Xavier Guitart Morales, Santi Seguí Mesquida i Ramsès Fernández
URI: http://hdl.handle.net/2445/164891
Appears in Collections:Programari - Treballs de l'alumnat
Treballs Finals de Grau (TFG) - Matemàtiques

Files in This Item:
File Description SizeFormat 
codi.zipCodi font436.81 kBzipView/Open
164891.pdfMemòria3.45 MBAdobe PDFView/Open


This item is licensed under a Creative Commons License Creative Commons