Na década de 90, Peter Shor introduziu novos conceitos sobre a criptografia. Ele descobriu que algoritmos quânticos tem um poder de fatorar números inteiros gigantes e computar logaritmos em tempo polinomial. Essas descobertas causaram grande impacto, uma vez que as técnicas convencionais de criptografia assimétrica são baseadas nesses problemas. Ou seja, o desenvolvimento de um computador quântico de grande porte poderia comprometer as informações criptografadas nos dias de hoje.
Entretanto, existem esquemas criptográficos que são baseados em diferentes problemas computacionais que conseguem resistir a ataques de computadores quânticos. Esses esquemas passaram a ser conhecidos como sistemas criptográficos pos-quânticos e entre eles estão : criptografia baseada em látice, códigos corretores de erros, sistemas quadráticos multivariados e função hash, incluindo as construções de criptografia simétrica em geral.
Vale ressaltar que, quando se trata de custo operacional, tempos de processamento, consumo de memória e o cenário de computadores quânticos, os sistemas mencionados passam a ser muito mais atrativos que os métodos mais utilizados atualmente, como criptografia assimétrica e assinatura digital.
Em 1978, Robert J. McEliece publicou um trabalho que tinha como proposta a teoria de código corretor de erro como forma de tornar uma mensagem confidencial. Ele desenvolveu uma algoritmo de criptografia assimétrica que tinha como princípio a adição de erros ao texto. O texto encriptado é uma palavra de código no qual foram adicionados alguns erros, e somente o dono da chave privada seria capaz de remover esses erros, ou seja, conseguir decriptar a mensagem.
É importante ressaltarmos que, apesar de sua chave pública ser extremamente grande (podendo chegar a megabytes), a encriptação de McEliece apresenta uma vantagem significativa de velocidade de processamento em comparação aos esquemas usados atualmente.Na encriptação de um código de comprimento $ n $, utilizando código corretor de erro, teremos a complexidade de $ O(n^2) $, enquanto os algoritmos Diffie-Hellman e RSA alcançam complexidade de $ O(n^3) $ com chave de $ n $ bits.
♦ Criptossistema de McEliece
Em um algoritmo criptográfico $ C(n,k) $, temos que $ n $ é o numero de bits que serão utilizados para representar $ k $ bits da mensagem. Temos também a distância mínima $ d = 2t +1 $, sendo $ t $ o número de erros corrigidos. Dessa maneira, podemos gerar a matriz geradora $ G $ com dimensão $ k \times n $, que utiliza código de Goppa para a sua formação.
Além dessa matriz, o Criptossistema utiliza outras duas matrizes randômicas : uma matriz binária $ S $ de dimensão $ k \times k $ e outra matriz de permutação $ P $ de $ n \times n $. Para a geração das chaves calcula-se $ G^{pup} = SGP $. Com isso, podemos obter a chave pública $ (G^{pup}, t) $ e a chave privada $ (S, D_G, P) $, em que D_G é um algoritmo eficiente de decodificação de $ G $.
Para encriptar uma mensagem $ M $ , escolhe-se um vetor $ z $ de peso randomicamente $ t $ e gera a mensagem criptografada $ c = mG^{pub} \oplus z $. Para decriptar a mensagem $ c $ calcula-se $ cP^{-1} = (mS)G \oplus zP^{-1} $
♦ Criptossistema de Niederreiter
O criptossistema de Niederreiter é uma variação do sistema de McEliece, porém com algumas modificações. Ao em vez de representar a mensagem em forma de palavras de código, Niederreiter propôs a codificação da mensagem de forma que gerasse um vetor de erro pela funcão $ \theta(n,t) $. Essa função é bem ineficiente e possui complexidade $ O(n^2 \times log_2(n)) $. Entretanto, em termos de segurança ambos são equivalentes, um ataque que conseguir quebrar McEliece conseguirá quebrar o Niederreiter.
A criptografia assimétrica multivariada é o estudo de criptografias assimétricas em que a trapdoor one-way function (função pouco custosa para ser computada, porém difícil de achar os input por meio do resultado já computado) toma formas de polinômio quadrático multivariado definido em um espaço finito. A sua principal segurança está assegurada pelo problema NP de resolver equações não lineares em um espaço finito. Esse tipo de criptografia é um dos poucos que consegue resistir ao poder de processamento de um computador quântico.
A chave pública é geralmente formada por um conjunto de polinômios quadráticos tal que, $ p_i $ é um polinômio não linear quadrático em $ \textbf{w} = (w_1,\cdots,w_n) $ com coeficientes e variáveis em $ F_2 = \{0,1\} $, como vemos abaixo:
$ P = (p_1 (w_1, \cdots, w_n), \cdots, p_n (w_1, \cdots, w_n)) $
Dessa forma, para poder descobrir a mensagem criptografada, seria necessário inverter a função quadrática multivariada, ou seja, resolver um conjunto de equações quadráticas no espaço finito. Esse problema é, no geral, um problema NP-hard.
Entretanto, acredita-se que esse problema torna-se menos complicado a partir do momento em que as equações polinomiais não são necessariamente genéricas, mas na verdade podendo ser escolhidas. Dessa forma, quando não lidamos mais com sistemas randômicos, como no caso do RSA ou genérico, mas lidamos com sistemas que os polinômios são especificados, perdemos a garantia da existência da dificuldade NP de descobrir a mensagem criptografada.
Na criptografia quântica, quando existe uma comunicação entre duas pessoas, e uma delas deseja enviar sua chave secreta para que a outra consiga entender a mensagem criptografada, essa pessoa utiliza princípios da mecânica quântica para poder enviar essa senha de forma segura. Além disso, é necessário que Alice e Bob estejam a uma distância máxima um do outro, por volta de 70km, conectados a uma fibra ótica (cada um com seu equipamento em sua ponta da conexão) para definirem um chave secreta entre si. Vimos na página anterior que essa técnica, com as tecnologias existentes hoje, é praticamente 100% segura, isto é, é muito improvável que um intruso consiga ter acesso a essa senha.
Por outro lado, a criptografia pós-quântica é aquela que, apesar de não utilizar os princípios da mecânica quântica, não consegue ser quebrada por computadores quânticos. Ela tem os mesmos princípios de outras criptografias e é baseada em operações matemáticas de alto nível, de forma que seja impossível revertê-las, isto é, é provado matematicamente que para poder reverter essa operações e encontrar a chave pública usada, seria necessário um tempo exageradamente grande que até mesmo com um computador quântico não seria possível realizar.
Além disso, Alice e Bob não precisam estar conectados exatamente por uma fibra ótica, muito menos precisam de um equipamento específico para que possam codificar e enviar a mensagem secreta. Precisam somente executar algumas operações matemáticas e enviar os dados obtidos.
Podemos perceber então que a criptografia pós-quântica tem algumas vantagens em relação a criptografia quântica. Entre essas vantagens, a criptografia quântica requer uma rede de fibra ótica e de equipamentos que, pelo menos até o momento, são extremamente caros e a grande maioria dos usuários da internet não conseguiram obtê-lo, sendo a criptografia pós-quântica mais acessível nesse quesito.