A nova matemática da criptografia quântica

A versão original desta história apareceu na Quanta Magazine .

Problemas complexos geralmente não são uma visão bem-vinda. Mas os criptógrafos os adoram. Isso porque certos problemas matemáticos complexos sustentam a segurança da criptografia moderna. Qualquer truque inteligente para resolvê-los condenará a maioria das formas de criptografia.

Há vários anos, pesquisadores descobriram uma abordagem radicalmente nova para a criptografia que não apresenta esse potencial ponto fraco. A abordagem explora as características peculiares da física quântica. Mas, diferentemente dos esquemas anteriores de criptografia quântica, que funcionam apenas para algumas tarefas específicas, a nova abordagem pode realizar uma gama muito mais ampla de tarefas. E poderia funcionar mesmo que todos os problemas no cerne da criptografia "clássica" comum se revelem facilmente solucionáveis.

Mas essa descoberta impressionante baseou-se em suposições irrealistas. O resultado foi "mais uma prova de conceito", disse Fermi Ma , pesquisador de criptografia do Instituto Simons para a Teoria da Computação em Berkeley, Califórnia. "Não é uma afirmação sobre o mundo real."

Agora, um novo artigo de dois criptógrafos traçou um caminho para a criptografia quântica sem essas suposições absurdas. "Este artigo afirma que, se certas outras conjecturas forem verdadeiras, então a criptografia quântica deve existir", disse Ma.

Você pode pensar na criptografia moderna como uma torre com três partes essenciais. A primeira parte é a base rochosa abaixo da torre, composta por problemas matemáticos complexos. A própria torre é a segunda parte — lá você encontra protocolos criptográficos específicos que permitem enviar mensagens privadas, assinar documentos digitais, votar em cédulas secretas e muito mais.

No meio, protegendo essas aplicações cotidianas com base matemática, existe uma base composta por blocos de construção chamados funções unidirecionais . Elas são responsáveis ​​pela assimetria inerente a qualquer esquema de criptografia. "É unidirecional porque você pode criptografar mensagens, mas não pode descriptografá-las", disse Mark Zhandry , criptógrafo da NTT Research.

Na década de 1980, pesquisadores provaram que a criptografia construída sobre funções unidirecionais garantiria a segurança para diversas tarefas. Mas, décadas depois, eles ainda não têm certeza de que a base seja forte o suficiente para suportá-la. O problema é que a base é composta por problemas complexos especiais — tecnicamente conhecidos como problemas NP — cuja característica definidora é a facilidade de verificar se qualquer solução candidata está correta. (Por exemplo, decompor um número em seus fatores primos é um problema NP: difícil de fazer para números grandes, mas fácil de verificar.)

Muitos desses problemas parecem intrinsecamente difíceis, mas os cientistas da computação não conseguiram comprová-los . Se alguém descobrir um algoritmo engenhoso para resolver rapidamente os problemas de NP mais difíceis, a base ruirá e a torre inteira desabará.

Infelizmente, você não pode simplesmente mover sua torre para outro lugar. A base da torre — funções unidirecionais — só pode se apoiar em uma base sólida de problemas NP.

Para construir uma torre sobre problemas mais complexos, os criptógrafos precisariam de uma nova base que não fosse feita de funções unidirecionais. Isso parecia impossível até alguns anos atrás, quando pesquisadores perceberam que a física quântica poderia ajudar.

Tudo começou com um artigo de 2021 de um estudante de pós-graduação chamado William Kretschmer , que chamou a atenção para um problema estranho sobre as propriedades dos sistemas quânticos. Pesquisadores logo demonstraram que o problema de Kretschmer poderia substituir funções unidirecionais como base para uma nova torre de protocolos criptográficos . No ano seguinte, Kretschmer e outros provaram que essa abordagem alternativa poderia funcionar mesmo sem problemas NP complexos. De repente, parecia possível construir uma fortaleza criptográfica muito mais robusta.

Mas onde construí-lo? O problema quântico que Kretschmer utilizou como base envolvia dispositivos computacionais hipotéticos chamados oráculos, capazes de responder instantaneamente a perguntas específicas. Oráculos podem ser ferramentas teóricas úteis, mas na realidade não existem. As provas de Kretschmer eram como um projeto para a construção de um castelo no céu. Haveria uma maneira de trazê-lo de volta à Terra?

No outono de 2022, essa questão chamou a atenção de Dakshita Khurana , uma criptógrafa da Universidade de Illinois em Urbana-Champaign e da NTT Research. Khurana e seu aluno de pós-graduação Kabir Tomer decidiram construir uma nova torre de criptografia. Seu primeiro passo foi construir uma nova fundação usando blocos de construção quânticos em vez de funções unidirecionais clássicas. Ela então precisaria provar que essa nova fundação poderia suportar uma torre de outros protocolos criptográficos. Uma vez que ela provasse que a fundação poderia suportar a torre, ela teria que encontrar um lugar sólido para a coisa toda se assentar — uma base de problemas do mundo real que parecem ainda mais difíceis do que os problemas NP usados ​​na criptografia clássica.

Na primeira etapa, Khurana e Tomer se concentraram em uma versão quântica de uma função unidirecional, chamada gerador de estados unidirecional , que satisfizesse as três propriedades que tornam as funções unidirecionais úteis. Primeiro, a função deve ser executada rapidamente para que seja possível gerar facilmente uma fechadura criptográfica e a chave correspondente para abri-la para cada mensagem que se deseja enviar. Segundo, cada fechadura deve ser segura, exigindo grande esforço para ser aberta sem a chave correta. Por fim, cada fechadura deve ser fácil de abrir com a chave correta.

A diferença crucial residia na natureza das travas. Funções unidirecionais clássicas geram travas matemáticas feitas de bits — os 0s e 1s que armazenam informações em um computador clássico. Geradores quânticos de estados unidirecionais, por sua vez, gerariam travas feitas de unidades de informação quântica chamadas qubits. Essas travas quânticas poderiam potencialmente permanecer seguras mesmo que todas as travas clássicas fossem fáceis de quebrar. Khurana e Tomer esperavam começar com essa nova base quântica e construir uma torre de protocolos criptográficos sobre ela. "Isso acabou sendo bastante difícil", disse Khurana. "Ficamos presos por muitos e muitos meses."

Em julho de 2023, Khurana estava com quase nove meses de gravidez e planejando a licença-maternidade. Tomer estava sem ideias. "Sou muito mais pessimista do que Dakshita", disse ele. "Ela é sempre aquela que acredita que as coisas vão dar certo."

Então, eles fizeram um grande avanço. O passo crucial foi definir outro bloco de construção matemático que servia como algo como um porão: uma estrutura que conectaria a fundação de geradores de estados unidirecionais a uma torre de protocolos criptográficos. Quando Khurana e Tomer calcularam quais propriedades esse bloco de construção precisaria ter, descobriram que ele se assemelhava a uma função unidirecional com uma mistura desconcertante de características quânticas e clássicas. Como em uma função unidirecional comum, tanto as fechaduras quanto as chaves eram feitas de bits clássicos, mas o procedimento para gerar essas fechaduras e chaves só seria executado em um computador quântico. Mais estranho ainda, o novo bloco de construção satisfazia as duas primeiras propriedades definidoras de funções unidirecionais, mas não a terceira: era fácil gerar fechaduras e chaves, e toda fechadura era difícil de arrombar. Mas uma chave não abriria facilmente sua fechadura.

Khurana e Tomer apelidaram esses novos e desconcertantes blocos de construção de quebra-cabeças unidirecionais. Intuitivamente, é difícil imaginar como eles poderiam ser úteis: de que serve uma chave que você nunca poderá usar? Mas os dois criptógrafos mostraram que quebra-cabeças unidirecionais, combinados com outros truques quânticos, na verdade permitiriam muitos protocolos criptográficos . Se for possível gerar fechaduras e chaves que se encaixem em princípio, não importa se o procedimento de desbloqueio é extremamente ineficiente.

“Basta saber que existe um algoritmo que pode ser arbitrariamente lento”, disse Kretschmer, que agora é pesquisador no Instituto Simons. “Isso é muito surpreendente.”

Com a peça que faltava no lugar, eles rapidamente terminaram a prova em 4 de agosto. A filha de Khurana nasceu poucos dias depois.

Em novembro, Khurana estava de volta ao trabalho e pronta para tentar a segunda fase de seu plano. Ela e Tomer haviam demonstrado que muitos tipos de criptografia poderiam ser construídos sobre quebra-cabeças unidirecionais, e que esses quebra-cabeças, por sua vez, poderiam ser construídos sobre uma nova base quântica composta de geradores de estados unidirecionais. O próximo passo em seu plano original era conectar essa base quântica a uma nova base — um conjunto relativamente inexpugnável de problemas matemáticos ainda mais intratáveis ​​do que aqueles em NP.

Mas, enquanto Khurana e Tomer lutavam com essa tarefa, eles decidiram adotar uma abordagem mais direta: esquecer os geradores de estados unidirecionais e, em vez disso, ancorar os quebra-cabeças unidirecionais diretamente na base matemática.

De certa perspectiva, parecia uma escolha estranha. Quebra-cabeças unidirecionais eram peculiaridades matemáticas que Khurana e Tomer usaram em uma etapa intermediária de sua demonstração.

No entanto, os quebra-cabeças unidirecionais tinham algumas vantagens. Por um lado, embora fossem quânticos, as fechaduras e chaves que geravam eram clássicas. Khurana imaginou que isso poderia facilitar sua conexão com um fundamento da matemática clássica. Além disso, os quebra-cabeças unidirecionais geram chaves que são muito difíceis de manejar para realmente abrir fechaduras. Isso poderia facilitar sua associação a problemas tão complexos que até mesmo a verificação de soluções parece irremediavelmente difícil.

Mas quais problemas específicos funcionariam? Khurana tinha um candidato em mente: calcular uma combinação específica de entradas em uma tabela de números chamada matriz. Esse problema, conhecido como o problema da permanente da matriz, é notoriamente difícil de resolver para matrizes grandes, e não há uma maneira simples de verificar se um cálculo está correto. O problema da permanente da matriz também possui outras propriedades matemáticas especiais que os criptógrafos consideram interessantes.

“Este seria um belo problema para basear a criptografia”, disse Khurana.

O problema da matriz permanente também se conecta a um problema diferente que os computadores quânticos podem resolver facilmente, mas os computadores clássicos aparentemente não . Pesquisadores estão trabalhando para comprovar essa vantagem computacional quântica em um sentido teórico preciso. Khurana e Tomer demonstraram que tal prova também lhes permitiria construir quebra-cabeças unidirecionais seguros — e, portanto, toda a torre da criptografia quântica — sobre o problema permanente.

"Eles conseguiram fazer isso partindo de premissas bem estudadas", disse Kretschmer. "Fiquei muito feliz em ver isso."

Com seu novo resultado, Khurana e Tomer reduziram efetivamente dois problemas em aberto a um. Se os pesquisadores comprovarem que os computadores quânticos realmente superam os clássicos em uma tarefa específica, isso automaticamente colocará a criptografia quântica em uma base teórica muito mais sólida do que praticamente qualquer tipo de criptografia clássica.

Infelizmente, você não poderá usar a nova abordagem de Khurana e Tomer para enviar mensagens secretas tão cedo. Apesar do progresso recente , a tecnologia da computação quântica ainda não está madura o suficiente para colocar suas ideias em prática. Enquanto isso, outros pesquisadores desenvolveram métodos de criptografia quântica que poderão ser usados ​​em breve , embora mais trabalho seja necessário para estabelecer se são realmente seguros.

A criptografia quântica já se mostrou repleta de surpresas, e os pesquisadores só recentemente começaram a explorar as possibilidades. "Estamos apenas tentando entender esse novo cenário que realmente existiu o tempo todo", disse Zhandry.

História original reimpressa com permissão da Quanta Magazine , uma publicação editorialmente independente da Fundação Simons cuja missão é aumentar a compreensão pública da ciência cobrindo desenvolvimentos e tendências de pesquisa em matemática e ciências físicas e biológicas.