Os computadores tradicionais funcionam com dígitos binários, ou bits, funcionando zero ou um (0 ou 1).

Normalmente, zero e um são representados por alguma propriedade física tradicional – um buraco perfurado em uma fita ou nenhum buraco; um disco de metal magnetizado de uma forma ou de outra por uma corrente elétrica; um capacitor eletrônico que possui uma carga ou não; e assim por diante.

Computadores quânticos não são assim – eles funcionam com qubits, que podem essencialmente representar zero ou um ao mesmo tempo. Em teoria, isso possibilita a realização de cálculos paralelos que normalmente exigiria um loop para realizá-los um de cada vez.

A idéia, falando livremente, é que para alguns tipos de algoritmo, um computador quântico pode calcular em N unidades de tempo o que de outra forma levaria 2N unidades de tempo para trabalhar. Em outras palavras, alguns problemas que convencionalmente são considerados como algoritmos de tempo exponencial se transformaria em algoritmos de tempo polinomial.

Multiplicação x exponencialização

Para explicar: Os expoentes envolvem “elevar algo ao poder de X” e as funções exponenciais crescem enormemente rapidamente. Os polinômios envolvem “multiplicar X por algo” e, embora as funções polinomiais possam crescer muito rapidamente, elas são muito mais gerenciáveis ​​do que exponenciais.

-Aqui está um experimento mental: coloque 40 folhas de papel de escritório uma em cima da outra para criar uma pilha 40 vezes mais grossa que uma folha – cerca de 4 mm no total.

-Agora imagine pegar a folha de cima e dobrá-la pela metade 40 vezes.

Que muitas dobras são impossíveis na prática, é claro, mas se você pudesse fazer isso, acabaria com um pedaço de papel com mais de 100.000 quilômetros de espessura.

Mais duas dobras e você estaria mais longe que a lua.

42 dobras dão 2(42) camadas de papel. 2(42) é 4,39 × 10(12). Se uma camada de papel tiver 0,1 mm de espessura, isso equivale a 10(-7) km, de modo que a altura total é de 4,39 x 10(5) km ou pouco menos de 440.000 km. A lua está sempre mais perto do que a terra.

Como resultado, muitas pessoas estão preocupadas com os computadores quânticos, se realmente funcionarem como reivindicados e possam ser ampliados para ter muito mais poder de processamento e memória qubit do que hoje, poderiam enfrentar com sucesso problemas que atualmente consideramos como “computacionalmente inviável ”para resolver.

O exemplo mais óbvio é quebrar a criptografia.

Se a sua segurança depende do fato de que um hacker precisaria de meses ou anos para descobrir suas chaves de descriptografia, quando já seria tarde demais, você estará em apuros se alguém encontrar uma maneira de fazê-lo em segundos ou minutos.

Código de cracking feito polinomial

Esta é a diferença entre o tempo exponencial e o tempo polinomial na medição do custo dos códigos de quebra.

Imagine que você tenha um problema criptográfico que exige 1.000.000 de loops para resolver hoje se tiver uma chave de 20 bits, mas ao dobrar a chave para 40 bits, você ajusta o esforço necessário, de modo que agora são necessários 1.000.000.000.000 de loops. (Na verdade, 240, que é aproximadamente um milhão ou um trilhão.).

Imagine que você pode fazer 1000 loops por segundo: multiplicar o tamanho da chave por 2 aumentou um milhão de vezes o tempo de quebra do seu sistema criptográfico, de 1000 segundos (menos de 20 minutos) a um bilhão de segundos (mais de 30 anos).

Agora imagine que o tempo de rachadura de um computador quântico dobrou junto com o tamanho da chave, ao invés de quadratura – sua margem de segurança de 30 anos caiu para 20 minutos extras, então uma chave que você acha que manteria seus segredos por décadas não durar uma hora.

Em outras palavras, se computadores quânticos confiáveis ​​com uma quantidade razoável de memória se tornarem realidade – não sabemos se isso é realmente possível, ou até mesmo possível, mas alguns especialistas acham que é – então qualquer coisa criptografada com os algoritmos mais fortes de hoje pode se tornar repentinamente fácil de quebrar.

TEOTWAWKI?

Este é o fim do mundo como o conhecemos, pelo menos para criptografia?

Se você passar 256 soluções possíveis para um problema usando um algoritmo convencional e 16 delas estiverem corretas, você acabará com uma lista de todas as 16 possibilidades, descartando assim, de maneira confiável, 240 delas.

A partir daí, você pode continuar a se aprofundar no problema, sabendo que acabará resolvendo isso, porque acabará experimentando todos os caminhos válidos para a resposta.

Mas com computadores quânticos, mesmo que você possa fazer uma carga inteira de cálculos em paralelo, porque os qubits estão em múltiplos estados quânticos ao mesmo tempo, você pode apenas ler uma das respostas válidas, quando todas as outras respostas desaparecem um sopro de colapso quântico.

Você pode calcular e “armazenar” várias respostas simultaneamente, mas depois não é possível enumerar todas as respostas válidas. Se você já ouviu falar do gato de Erwin Schrödinger, você reconhecerá esse problema.

“O gato de Schrödinger é um experimento mental no qual um “gato quântico” escondido fora da vista dentro de uma caixa pode estar simultaneamente vivo e morto, porque gatos quânticos podem estar em ambos os estados ao mesmo tempo, desde que você não esteja olhando para eles. Mas assim que você abre a caixa para ver essa incrível criatura na vida real, ela imediatamente adota uma das possibilidades – então abrir a caixa pode matar o gato instantaneamente. Você não pode descobrir com antecedência se é seguro – seguro para o gato, isto é – abrir a caixa”.

Então, se o seu computador quântico pode fazer, digamos, 256 cálculos em paralelo, você precisa ter certeza de que há apenas uma resposta correta que pode surgir antes de passar para o próximo estágio do algoritmo, ou você pode ter descartado o caminho que leva à resposta certa mais tarde.

Em outras palavras, você pode ser capaz de “resolver” cada estágio de um problema muito mais rápido do que antes, mas dificilmente obterá a resposta correta, o que significa que você está preso a repetir seus cálculos “rápidos” repetidamente até chegar sorte todo o caminho e acabam na solução genuína.

Como resultado desse obstáculo, nem todos os algoritmos de criptografia estarão vulneráveis ​​ao craqueamento quântico, mesmo se um computador quântico viável for construído.

Quais algoritmos estão em risco?

Infelizmente, os cálculos computacionais quânticos baseados em um processo conhecido como algoritmo de Shor servem apenas para fornecer soluções super rápidas para vários problemas matemáticos no qual, atualmente, dependem da criptografia moderna.

Algoritmos como o SHA-256 (usado no hash, por exemplo para armazenar senhas com segurança) e o AES (usado para criptografar arquivos e discos rígidos com segurança) não podem ser quebrados com o algoritmo de Shor.

Mas os algoritmos amplamente usados ​​hoje em dia para criptografia de chave pública – como configuramos conexões seguras e autenticadas, por exemplo – podem ser atacados rapidamente com um computador quântico.

Quando se criptografa dados por meio de uma conexão segura com a Web, normalmente usamos um algoritmo não-quantum-crackable, como o AES, para manter os dados em segredo, depois de concordarmos com uma chave AES aleatória primeiro.

Até agora, tudo bem, exceto pelo fato de usarmos algoritmos de chave pública, como RSA e criptografia de curva elíptica (ECC), para fazer nosso acordo inicial de chave AES, e esses algoritmos de chave pública podem ser atacados usando o algoritmo de Shor.

Em outras palavras, a computação quântica não consegue decifrar a criptografia AES, mas não precisa, porque pode decifrar a chave AES e depois descriptografar os dados do AES diretamente.

O que fazer?

Alguns especialistas duvidam que os computadores quânticos possam ser poderosos o suficiente para executar o algoritmo de Shor em chaves criptográficas do mundo real.

Eles sugerem que há um limite operacional em computadores quânticos, integrados à física, que eternamente limitará o número máximo de respostas que eles podem calcular com segurança ao mesmo tempo – e esse limite superior em sua capacidade de processamento paralelo significa que eles sempre serão qualquer uso para resolver problemas de brinquedo.

Outros dizem: “É apenas uma questão de tempo e dinheiro”

Em vez de simplesmente apostar que o primeiro grupo está certo, o órgão de padrões dos EUA NIST está atualmente executando uma competição para projetar, analisar e escolher um conjunto de novos algoritmos para criptografia de chave pública que são considerados incontáveis ​​mesmo se um supercomputador quântico for construído.

O projeto é muito parecido com as competições de criptografia anteriores que o NIST realizou, com uma motivação semelhante.

Na década de 1990, o NIST organizou um concurso para selecionar o AES, necessário para substituir o algoritmo DES, que já não é suficientemente seguro.

Nos anos 2000, o alvo competitivo era o SHA-3, um algoritmo de hashing criptográfico que foi padronizado apenas no caso de alguém encontrar uma maneira de decifrar o SHA-256, e precisamos de um substituto confiável com pressa.

Este último concurso é conhecido como o PQC Standardization Challenge, onde PQC significa Post-Quantum-Cryptography.

O processo está em andamento desde abril de 2016, quando o NIST começou a aceitar propostas e entrou em sua primeira etapa de avaliação em novembro de 2017, quando o NIST parou de aceitar novos algoritmos para consideração.

Em 30 de janeiro de 2019, o projeto entrou na 2ª Rodada, com o NIST anunciando que 26 das 69 inscrições originais passaram para o que chamou de “semifinais”.

O NIST espera que o próximo estágio da avaliação demore de 12 a 18 meses, após os quais pode haver uma terceira rodada, e então os algoritmos padrão oficiais serão escolhidos.

Por que tão longe?

O processo está demorando muito, porque a criptoanálise é difícil.

A revisão por pares, a avaliação imparcial e um processo transparente para escolher padrões abertos não podem ser apressados, até porque decidir que um algoritmo criptográfico não tem lacunas está provando ser negativo.

Se você encontrar um buraco, então sua busca terminou e seu trabalho está terminado; se você não fizer isso, supondo que você não tenha uma prova matemática formal de segurança, há sempre a chance de que, com um pouco mais de esforço, você encontre algo que tenha perdido antes.

Além disso, apressar o processo acabaria inevitavelmente criando preocupações de que o NIST, que é uma organização do governo dos EUA, estava interessado em aprovar algo que sabia que poderia quebrar, mas imaginou que outros países não poderiam.

Por fim, o NIST está tentando cobrir muitas bases com seus novos padrões, como explicou o matemático do NIST Dustin Moody:

“Queremos ver como esses algoritmos funcionam não apenas em computadores grandes e smartphones, mas também em dispositivos com capacidade limitada do processador. Cartões inteligentes, pequenos dispositivos para uso na Internet das Coisas e microchips individuais também precisam de proteção. Queremos algoritmos resistentes a quântica que possam executar esse tipo de criptografia leve. ”

Além de considerar a multiplicidade de tipos de dispositivos em potencial que poderiam usar os algoritmos, a equipe do NIST está se concentrando em várias abordagens de proteção. Como ninguém sabe ao certo quais serão as capacidades de um computador quântico funcional, disse Moody, os 26 candidatos são um grupo diversificado.

Quem vai ganhar?

Os 17 algoritmos semifinalistas para criptografia de chave pública e acordo de chave são:

  BIKE
   Classic McEliece
   CRYSTALS-KYBER
   FrodoKEM
   HQC
   LAC
   LEDAcrypt
   NewHope
   NTRU
   NTRU Prime
   NTS-KEM
   ROLLO
   Round5
   RQC
   SABER
   SIKE
   Three Bears

Os nove algoritmos semifinalistas para assinaturas digitais são:

  CRYSTALS-DILITHIUM
   FALCON
   GeMSS
   LUOV
   MQDSS
   Picnic
   qTESLA
   Rainbow
   SPHINCS+

Alguns dos algoritmos propostos existem há anos, mas nunca foram descobertos porque não eram tão convenientes quanto RSA ou ECC.

O algoritmo McEliece, por exemplo, foi inventado pelo matemático norte-americano Robert McEliece em 1978, mas ficou em segundo plano na RSA e, mais recentemente, na ECC, porque requer chaves criptográficas com vários megabits de comprimento.

As chaves RSA são normalmente de alguns milhares de bits e as chaves ECC são apenas algumas centenas, tornando o uso do McEliece em uma conexão de rede muito mais trabalhoso do que as alternativas convencionais.

Mas no momento em que um supercomputador quântico rompendo RSA é construído, provavelmente vamos considerar alguns megabits de largura de banda como insignificantes, até agora…