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

Resumen

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.