O impacto da computação quântica na criptografia moderna

Abstract

Quantum computing emerged from quantum physics as a new computational model. In a quantum computer, data is encoded directly in the physical state of a quantum system, and data-operations are transformations governed by the dynamics of quantum mechanics. The computational model obtained differ significantly from their classical counterpart, allowing to solve efficiently problems that are believed not to possess efficient solutions in classical computers. This fact has a deep effect in cryptography, since the security of most modern cryptographic schemes rely on hardness assumptions of particular problems, such as integer factorization or discrete logarithm. This work aims to provide a comprehensive study of Quantum Computation and its mathematical foundation. Moreover, we will focus on the interaction between quantum computation and cryptography. Specifically, we will address: (1) the impact of some proposed quantum algorithms to the hardness assumptions of widely used cryptographic schemes, (2) new cryptographic ”hard-problems”that are believed to be resilient to quantum computers, and (3) the exploitation of quantum effects in the design of new cryptographic schemes (quantum cryptography). The SAGE open source mathematics software system (www.sagemath.com) will be used to prototype/animate the concepts studied.

A computação quântica emergiu da física quântica como um novo modelo computacional. Num computador quântico, a informação é codificada diretamente no estado físico de um sistema quântico, sendo as transformações deste, governadas pela dinâmica da física quântica. O modelo computacional obtido difere então de forma significativa do seu homólogo clássico, permitindo resolver de forma e ciente problemas, que se acredita não possuírem uma solução e ciente em computadores clássicos. Este facto produz um efeito profundo na criptografiaa, uma vez que a segurançaa da maior parte dos esquemas criptográficos modernos, baseia-se em assunções sobre a dificuldade de resolver determinados problemas no atual modelo computacional, como a fatorização de inteiros ou o logaritmo discreto. Este trabalho procura então proporcionar um estudo abrangente sobre a computação quântica, bem como a sua fundamentação matemática. Além disso, vamos focar atenções na interação entre computação quântica e criptogra fia. Especificamente, vamos analisar (1) o impacto de alguns algoritmos quânticos, em assunções sobre a dificuldade de alguns esquemas criptográficos mais em uso atualmente, (2) novos esquemas criptográficos "problemas difíceis", que se acredita serem resistentes a computadores quânticos, e (3) explorar os efeitos quânticos no design de novos esquemas criptográficos - criptogra a quântica. O sistema de software open source matemático SAGE (www.sagemath.com) será usado por forma a protótipar/animar alguns conceitos estudados.