A busca por criptografia à prova de computação quântica acaba de dar um salto à frente
Computação

A busca por criptografia à prova de computação quântica acaba de dar um salto à frente

Os computadores quânticos podem tornar a criptografia uma coisa do passado, mas 15 concorrentes estão tentando provar que têm o que é preciso para proteger seus dados.

Muitas das coisas que você faz online todos os dias são protegidas por criptografia para que ninguém mais possa espionar. Seus serviços bancários online e mensagens para seus amigos provavelmente são criptografados, por exemplo – assim como segredos do governo. Mas essa proteção está correndo perigo por conta do desenvolvimento de computadores quânticos, que ameaçam tornarem inúteis os métodos modernos de criptografia.

As máquinas quânticas funcionam de uma maneira fundamentalmente diferente dos computadores clássicos que usamos hoje. Ao invés de usarem o código binário tradicional, que representa informações com 0s e 1s, eles usam bits quânticos, ou qubits. As propriedades incomuns dos qubits tornam os computadores quânticos muito mais poderosos para alguns tipos de cálculos, incluindo os problemas matemáticos que sustentam grande parte da criptografia moderna.

“Os pesquisadores sabem há décadas que, se um computador quântico em grande escala pudesse ser construído, ele poderia fazer alguns cálculos que colocariam em risco os criptossistemas dos quais contamos hoje para a segurança”, diz Dustin Moody, matemático do NIST, o Instituto Nacional de Padrões e Tecnologia dos Estados Unidos.

Embora as máquinas quânticas ainda estejam muito longe de serem capazes de quebrar a criptografia moderna, em 2016 o NIST deu início a uma competição para desenvolver novos padrões criptográficos que fossem mais resistentes à computação quântica. A corrida é longa e o resultado dos vencedores está previsto para ser anunciado em 2022, mas no final de julho a organização comunicou que havia reduzido o grupo inicial de 69 candidatos para apenas 15.

E até agora uma única abordagem para a “criptografia pós-quântica” está sendo usada pela maioria dos finalistas: criptografia baseada em reticulados.

Como funciona

A criptografia de chave pública, também conhecida como criptografia assimétrica, usa matemática tradicional para codificar dados, desbloqueando-os apenas para aqueles que têm a chave – ou que conseguem decifrá-las. Ao contrário, a criptografia baseada em reticulados usa grades enormes com bilhões de pontos individuais em milhares de dimensões. Quebrar o código significa ir de um ponto específico a outro – o que é essencialmente impossível, a menos que você conheça a rota.

Até mesmo a Agência de Segurança Nacional, a agência de espionagem dos EUA que há muito tempo alerta sobre a ameaça representada por computadores quânticos, recentemente, expressou confiança em abordagens baseadas em reticulados.

No entanto, o que conta não é apenas quão impenetrável ou complexa é a matemática. As abordagens pós-quânticas só funcionarão se puderem ser usadas em todos os lugares em que a criptografia de alto nível será necessária. Por exemplo, o tamanho da chave necessária para descriptografar os dados é importante: imagine o que será possível dentro de um equipamento médico que tem pouca memória e uma largura de banda severamente limitada. Se a matemática for tão complexa a ponto de que abrir a fechadura exige uma chave enorme, a solução pode não passar no teste de usabilidade.

Cinco dos candidatos pré-selecionados anunciados no final de julho usam abordagens reticuladas que não têm solução quântica conhecida, e o novo relatório de status do NIST diz que eles são “os algoritmos de uso geral mais promissores” na lista.

Mas essa lista inclui abordagens alternativas que também podem ser um sucesso – especialmente se os sistemas de reticulados se revelarem insuficientes. Essas outras opções são geralmente menos maduras, menos estudadas e muito mais distantes de serem usadas no mundo real, levando a maioria dos observadores a acreditar que esses sistemas reticulados triunfarão quando dois vencedores forem escolhidos em 2022.

“O que o NIST pensa é que os problemas de reticulados são realmente difíceis”, diz Elena Kirshanova, matemática e pesquisadora de criptoanálise da Universidade Federal do Báltico de Immanuel Kant (em inglês, I.Kant Baltic Federal University), na Rússia. “Embora esses problemas sejam difíceis, eles parecem bastante eficientes em termos de tempo para gerar chaves, para construir assinaturas e também eficientes em termos de memória.”

Quando o quantum chegará?

Se tanto tempo e esforço estão sendo empregados para evitar um desastre de segurança, quando veremos um computador quântico que pode fazer tudo isso?

No ano passado, o Google se gabou de ter alcançado a “supremacia quântica” ao encontrar uma tarefa que um computador quântico poderia fazer e que era essencialmente impossível para um computador clássico. A empresa anunciou que havia usado seu computador quântico Sycamore de 53 bits para resolver um problema de matemática em 200 segundos, enquanto que um computador clássico levaria 10.000 anos.

Foi um marco importante, mas não deu início a uma nova era da computação quântica, e especialistas da indústria e da academia rapidamente criticaram a empresa por uma série de razões.

Na realidade, provavelmente estamos a uma década ou mais de distância de um computador quântico que pode resolver problemas úteis – o que dá ao NIST tempo para tomar uma decisão para que a transição para a criptografia quântica segura possa começar.

“Leva muito tempo para padronizar e implementar algoritmos criptográficos em produtos”, diz Moody, do NIST. “Pode levar 10 ou 20 anos. Precisamos que esse processo seja feito antes que um computador quântico apareça, então estaremos à frente do jogo”.

No entanto, nem todo mundo está convencido de que o tempo será bem gasto.

“A próxima etapa são os computadores quânticos resolvendo um problema útil, o que eles ainda não fizeram”, diz Vadim Lyubashevsky, um criptógrafo da IBM que trabalhou no algoritmo CRYSTALS que agora é finalista da competição do NIST. “Se isso não acontecer logo, acho que as empresas vão esquecer o burburinho atual e implementar o sistema mais frágil que sairá do NIST até que, de uma hora para outra, sejam lembradas do problema em 30 anos”.

Nossos tópicos