Análisis del Algoritmo de Shor, consecuencias en la criptografía moderna y contramedidas futuras

García Barahona, Carlos (2022). Análisis del Algoritmo de Shor, consecuencias en la criptografía moderna y contramedidas futuras. Proyecto Fin de Carrera / Trabajo Fin de Grado, E.T.S.I. de Sistemas Informáticos (UPM), Madrid.

Description

Title: Análisis del Algoritmo de Shor, consecuencias en la criptografía moderna y contramedidas futuras
Author/s:
  • García Barahona, Carlos
Contributor/s:
  • Scarpa, Giannicola
Item Type: Final Project
Degree: Grado en Ingeniería del Software
Date: July 2022
Subjects:
Freetext Keywords: Computación cuántica; Criptografía; Algoritmo de Shor
Faculty: E.T.S.I. de Sistemas Informáticos (UPM)
Department: Sistemas Informáticos
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img] PDF - Users in campus UPM only - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (822kB)

Abstract

La computación cuántica está llamada a ser la próxima revolución en el ámbito de las ciencias de la computación. Partiendo de propiedades básicas de la mecánica cuántica los ordenadores cuánticos son capaces de resolver problemas que se creen intratables para un ordenador clásico. Primero se realizará una introducción a la computación cuántica, desde las propiedades físicas que sustentan la teoría hasta la creación de puertas y algoritmos cuánticos. Después, se presentará el concepto de reducción de Turing y se desarrollaran dos reducciones de diferentes problemas a un mismo problema más general, el encontrar el periodo de una función. Los dos problemas a reducir serán el problema de factorizar un número en sus factores primos y el problema del logaritmo discreto. Para resolver ese problema más general al que hemos llegado con los problemas anteriores se desarrolla el algoritmo de Shor, haciendo hincapié en su parte cuántica y desarrollando los sub-algoritmos que hacen que funcione como la transformada cuántica de Fourier o el algoritmo de estimación de fase. A continuación, se presentan las implicaciones que tendría implementar en la actualidad el algoritmo de Shor ya que al ser capaz de resolver problemas que parecen intratables para los ordenadores clásicos, muchas tecnologías, principalmente relacionadas con la criptografía quedarían obsoletas si se consigue construir un ordenador cuántico con un número suficiente de qubits. Además, se estudian las principales contramedidas que se pueden tomar para seguir teniendo sistemas criptográficos seguros aun con ordenadores cuánticos capaces de ejecutar el algoritmo de Shor. Por último, se presenta el estado del arte en la computación cuántica, en concreto los temas relacionados con criptografía y el algoritmo de Shor. Abstract: Quantum computing is set to be the next revolution in the field of computer science. Starting from basic properties of quantum mechanics, quantum computers can solve problems that are thought to be intractable for a classical computer. First, we give an introduction to quantum computing, from the physical properties underlying the theory to the creation of quantum gates and algorithms. Then, we present the concept of Turing reduction. In particular we present and two reductions of different problems to the same more general problem which is finding the period of a function, will be developed. The two problems are the problem of factoring a number into its prime factors and the discrete logarithm problem. To show how to solve this more general problem we introduce Shor's algorithm. We detail, emphasizing its quantum part and developing the sub-algorithms that make it work, such as the quantum Fourier transform or the phase estimation algorithm. The implications of implementing Shor's algorithm today are then presented, since it can solve problems that seem intractable for classical computers, and many technologies, mainly related to cryptography, would become obsolete if a quantum computer with enough qubits could be built. In addition, we study the main countermeasures that can be taken to continue having secure cryptographic systems even with quantum computers capable of executing Shor's algorithm are studied. Finally, we present the state of the art in quantum computing is presented, in particular the topics related to cryptography and Shor's algorithm.

More information

Item ID: 71559
DC Identifier: https://oa.upm.es/71559/
OAI Identifier: oai:oa.upm.es:71559
Deposited by: Biblioteca Universitaria Campus Sur
Deposited on: 05 Sep 2022 05:26
Last Modified: 05 Sep 2022 05:26
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM