Os pesquisadores provaram que a criptografia quântica segura é possível em um mundo sem problemas difíceis.
Digamos que você queira enviar uma mensagem privada, votar secretamente ou assinar um documento com segurança.
Se você realizar qualquer uma dessas tarefas em um computador, estará contando com a criptografia para manter seus dados seguros.
Essa criptografia precisa resistir a ataques de decifradores de código com seus próprios computadores; portanto, os métodos modernos de criptografia dependem de suposições sobre quais problemas matemáticos são difíceis de serem resolvidos pelos computadores.
Mas à medida que os criptógrafos estabeleceram as bases matemáticas para esta abordagem à segurança da informação na década de 1980, alguns investigadores descobriram que a dureza computacional não era a única forma de salvaguardar segredos.
A teoria quântica, originalmente desenvolvida para compreender a física dos átomos, revelou ter conexões profundas com a informação e a criptografia.
Os pesquisadores encontraram maneiras de basear a segurança de algumas tarefas criptográficas específicas diretamente nas leis da física.
Mas essas tarefas eram estranhas – para todas as outras, parecia não haver alternativa à abordagem computacional clássica.
No final do milênio, os pesquisadores da criptografia quântica pensavam que esse era o fim da história.
Mas apenas nos últimos anos, o campo passou por outra mudança sísmica.
“Houve um rearranjo daquilo que acreditamos ser possível com a criptografia quântica”, disse Henry Yuen, teórico da informação quântica da Universidade de Columbia.
Numa série de artigos recentes, os investigadores demonstraram que a maioria das tarefas criptográficas ainda poderia ser realizada com segurança, mesmo em mundos hipotéticos onde praticamente toda a computação é fácil.
Tudo o que importa é a dificuldade de um problema computacional especial sobre a própria teoria quântica.
“As suposições de que você precisa podem ser muito, muito mais fracas”, disse Fermi Ma, criptógrafo quântico do Instituto Simons de Teoria da Computação em Berkeley, Califórnia.
“Isso está nos dando novos insights sobre a própria dureza computacional.”
Esta mensagem se autodestruirá
A história começa no final da década de 1960, quando um estudante de física chamado Stephen Wiesner começou a pensar sobre a natureza destrutiva da medição na teoria quântica.
Meça qualquer sistema governado pelas regras da física quântica e você alterará o estado quântico que descreve matematicamente sua configuração.
Esta perturbação na medição quântica foi um obstáculo para a maioria dos físicos.
Wiesner, que adotou uma visão pouco ortodoxa da teoria quântica centrada na informação, questionou-se se ela poderia ser útil.
Talvez pudesse servir como uma forma de proteção integrada contra adulteração para dados confidenciais.
Mas as ideias de Wiesner estavam muito à frente de seu tempo e ele deixou a academia após a pós-graduação.
Felizmente, ele discutiu suas ideias com seu amigo e colega físico Charles Bennett, que durante uma década tentou, sem sucesso, interessar outras pessoas pelo assunto.
Finalmente, em 1979, Bennett conheceu o cientista da computação Gilles Brassard enquanto nadava na costa de Porto Rico durante uma conferência.
Juntos, eles escreveram um artigo inovador descrevendo uma nova abordagem para uma importante tarefa criptográfica.
Seu protocolo baseava-se em distúrbios de medição quântica e não precisava de suposições sobre a dificuldade de quaisquer problemas computacionais.
“A própria natureza da informação quântica parece um tanto criptográfica”, disse Ma.
A descoberta de Bennett e Brassard deixou os pesquisadores otimistas de que truques quânticos semelhantes poderiam gerar segurança perfeita para outras tarefas criptográficas.
Os pesquisadores se concentraram principalmente em uma tarefa chamada comprometimento de bits, que é útil por si só e também é um componente-chave da maioria dos protocolos criptográficos avançados.
Para entender a ideia básica por trás do comprometimento de bits, imagine um jogo para dois jogadores em que você deve tomar uma decisão secreta que mais tarde será revelada.
Uma maneira de fazer isso é anotar a decisão em um pedaço de papel e colocá-la em um envelope lacrado.
Dessa forma, você não poderá mudar sua decisão mais tarde, e seu oponente não poderá espiar o resultado prematuramente.
Agora imagine que você está jogando o mesmo jogo online.
Para impossibilitar a trapaça, é necessário lacrar a decisão em uma espécie de envelope digital que nenhum jogador consegue abrir sozinho.
É aí que entra a criptografia.
Em 1981, o pioneiro cientista da computação Manuel Blum construiu o primeiro protocolo de comprometimento de bits – uma maneira de construir envelopes efetivamente invioláveis a partir de problemas computacionais difíceis.
Mas quão difícil é difícil? Pesquisadores no campo da teoria da complexidade computacional estudam muitos tipos diferentes de problemas difíceis, e nem todos são úteis para criptógrafos.
O comprometimento de bits e todos os outros protocolos criptográficos baseiam-se em problemas de uma classe que os teóricos da complexidade chamam de “NP”, cuja característica definidora é que é fácil verificar se uma solução candidata está correta.
Infelizmente, os pesquisadores não conseguiram provar que quaisquer problemas de NP sejam realmente difíceis.
Ainda pode haver algum procedimento ou algoritmo inteligente e não descoberto para resolver até mesmo aqueles que parecem mais difíceis.
Se houvesse, então toda a criptografia clássica seria quebrada.
Tais considerações animaram a procura de garantias de segurança baseadas em quantum.
Mas em 1997, dois artigos provaram que os esquemas de comprometimento de bits nunca poderiam ser completamente seguros se fossem baseados apenas nas leis da física quântica.
Os artigos implicavam que algum tipo de dureza computacional seria necessária para quase todas as tarefas criptográficas.
Essa foi a última palavra sobre os fundamentos teóricos dos compromissos de bits quânticos por quase 25 anos.
Então, em 2021, um artigo de um estudante de pós-graduação chamado William Kretschmer levou os pesquisadores a confrontar uma questão que ninguém havia pensado em fazer.
A dureza computacional era claramente necessária para compromissos de bits e para a maioria das outras formas de criptografia, mas exatamente que tipo de dureza? A resposta seria mais estranha do que se imaginava.
Consulting Oracles
O artigo de 2021 surgiu da luta de Kretschmer para compreender uma versão específica de um problema que parece conceitualmente simples: quão difícil é distinguir ou discriminar entre dois estados quânticos que parecem superficialmente semelhantes? Kretschmer, que agora é pesquisador de pós-doutorado no Simons Institute, inicialmente se interessou pelo problema por razões que nada tinham a ver com o comprometimento dos bits.
“A criptografia nem estava no meu radar”, disse ele.
O problema da discriminação era interessante em parte porque nem sequer era claro como descrevê-lo utilizando uma linguagem matemática familiar.
Os teóricos da complexidade tradicionalmente estudam problemas com diferentes entradas possíveis representadas por sequências de bits, ou 0s e 1s.
Para o problema de decomposição de números grandes em seus fatores primos, por exemplo, esta sequência representa o número sendo fatorado.
Mesmo depois de os investigadores terem começado estudando como a física quântica poderia ser aproveitada para a computação, continuaram a concentrar-se nesses problemas de “entrada clássica”.
Algoritmos quânticos típicos começam com uma sequência de bits clássica comum e depois a processam usando truques quânticos.
Mas em problemas de “entrada quântica? como o de Kretschmer, as entradas não são sequências de bits – são estados quânticos que são facilmente interrompidos pela computação e pela medição.
“A linguagem com a qual descrevemos os cálculos quânticos na teoria tradicional da complexidade não pode falar diretamente sobre esses problemas”, disse Yuen.
A princípio, Kretschmer pensou que só precisava traduzir o problema para uma linguagem mais padronizada, mas não conseguia descobrir como.
Então ele fez o que os teóricos da complexidade costumam fazer quando estão desesperados: recorreu a um oráculo.
Na teoria da complexidade, o termo “oráculo? refere-se a um dispositivo hipotético que pode resolver instantaneamente um problema específico.
Um computador com acesso a um oráculo pode ser capaz de resolver outros problemas mais facilmente consultando o oráculo como uma etapa intermediária em um algoritmo.
É claro que os oráculos não existem realmente no mundo real, mas estudá-los ajuda os teóricos da complexidade a compreender as relações entre os níveis de dificuldade de diferentes problemas.
Kretschmer se perguntou que tipo de oráculo poderia facilitar a distinção entre dois estados quânticos – o chamado problema de discriminação de estado.
Ele decidiu começar com um oráculo especial que aumentaria o poder dos algoritmos quânticos normais, aqueles que usam truques quânticos para resolver problemas com entradas clássicas de sequências de bits.
Esses algoritmos podem resolver alguns problemas muito difíceis para os clássicos, como fatorar números grandes, mas não são onipotentes – muitos outros problemas estão além do seu alcance.
O acesso ao oráculo de Kretschmer permitiria que tais algoritmos resolvessem certos problemas de entrada clássicos muito difíceis para computadores quânticos reais.
Kretschmer presumiu que seria um exagero, mas, para sua surpresa, provou que o problema da discriminação estatal ainda poderia confundir esses algoritmos quânticos aprimorados.
“Fiquei realmente fascinado pelo artigo de William”, disse Luowen Qian, estudante de pós-graduação que estuda criptografia na Universidade de Boston.
“Na verdade, pensei que devia estar errado, porque é muito contra-intuitivo.” Qian, Yuen e outros logo provaram que, se o problema de discriminação estatal de Kretschmer fosse realmente difícil, esquemas seguros de comprometimento de bits quânticos seriam possíveis.
Isso, por sua vez, implicaria segurança para uma série de protocolos criptográficos mais avançados.
O escopo da criptografia quântica era muito mais amplo do que os pesquisadores da década de 1990 imaginavam, e tudo se resumia à dificuldade de um problema.
Quão difícil poderia ser”
O resultado de Kretschmer veio com uma grande ressalva – para fazer a prova funcionar, ele teve que confiar em um oráculo incomum que apenas algoritmos quânticos poderiam consultar.
Talvez um oráculo mais familiar facilitaria seu problema de discriminação de estado e, portanto, tornaria impossíveis compromissos seguros de bits quânticos? Em 2022, Kretschmer e Qian começaram trabalhando juntos para ver o que poderiam provar sobre um oráculo que todos pudessem entender: um que pudesse resolver qualquer problema de NP instantaneamente.
Num mundo com tais oráculos, toda a criptografia clássica seria impossível.
Kretschmer logo percebeu que o problema da discriminação estatal estava matematicamente relacionado a um problema superficialmente diferente na teoria da complexidade quântica e contou com a ajuda de dois especialistas na área, os teóricos da complexidade Avishay Tal e Makrand Sinha.
“William era realmente como um gerente e nós éramos empreiteiros”, disse Tal.
Trabalhando juntos, os quatro pesquisadores provaram rapidamente que o problema de discriminação estatal de Kretschmer ainda poderia ser intratável mesmo para computadores que pudessem recorrer a este oráculo NP.
Isso significa que praticamente toda a criptografia quântica poderia permanecer segura, mesmo que todos os problemas subjacentes à criptografia clássica se revelassem fáceis.
A criptografia clássica e a criptografia quântica pareciam cada vez mais dois mundos totalmente separados.
O resultado chamou a atenção de Ma, e ele começou a se perguntar até onde poderia levar a linha de trabalho iniciada por Kretschmer.
Poderia a criptografia quântica permanecer segura mesmo com oráculos mais estranhos – aqueles que poderiam resolver instantaneamente problemas computacionais muito mais difíceis do que aqueles em NP? “Os problemas em NP não são os problemas clássicos mais difíceis que se possa imaginar”, disse Dakshita Khurana, criptógrafa da Universidade de Illinois, Urbana-Champaign.
“Há dureza além disso.” Ma começou a debater a melhor forma de abordar essa questão, juntamente com Alex Lombardi, criptógrafo da Universidade de Princeton, e John Wright, pesquisador de computação quântica da Universidade da Califórnia, Berkeley.
“Foi tão fascinante e alucinante que fiquei imediatamente fisgado”, disse Wright.
Depois de pensar um pouco sobre a questão e não chegar a lugar nenhum, Ma sugeriu que considerassem o caso mais extremo possível: um oráculo que pudesse resolver instantaneamente qualquer problema computacional com entradas clássicas.
Isso incluiria todos os problemas que os teóricos da complexidade têm estudado tradicionalmente, mesmo aqueles que se sabe serem insolúveis no mundo real.
“Pareceu um pouco insano para mim”, disse Lombardi.
Mas a questão revelou-se extraordinariamente frutífera. c
Depois de trabalhar nisso por quase um ano, eles finalmente publicaram um resultado impressionante.
Nenhum algoritmo autorizado a consultar esse oráculo todo-poderoso exatamente uma vez pode distinguir os dois estados quânticos, como é necessário para minar um esquema de comprometimento de bits quânticos.
Limitar algoritmos a uma única consulta é menos restritivo do que pode parecer, porque os algoritmos quânticos podem efetivamente pedir ao oráculo para resolver vários problemas simultaneamente, explorando o fenômeno chamado superposição.
Algoritmos que podem fazer múltiplas consultas sequencialmente poderiam ser mais poderosos, porque podem usar as respostas do oráculo a consultas anteriores para decidir o que perguntar a seguir.
Se esses algoritmos são igualmente limitados permanece uma questão em aberto.
O artigo de Ma, Lombardi e Wright também foi significativo por outro motivo.
Enquanto os três investigadores lutavam com o seu problema, perceberam que este estava intimamente ligado a um grande problema aberto colocado 16 anos antes pelo teórico da complexidade Scott Aaronson e pelo matemático Greg Kuperberg, sobre a dificuldade de transformar um estado quântico noutro.
O novo artigo foi o primeiro passo significativo para resolver essa questão.
“É um resultado muito forte e também muito surpreendente”, disse Tomoyuki Morimae, pesquisador de criptografia quântica do Instituto Yukawa de Física Teórica em Kyoto.
A série de resultados recentes sugere que o problema aparentemente inócuo de distinguir dois estados quânticos não é apenas difícil, mas quase inconcebivelmente difícil – muito além do alcance dos algoritmos quânticos normais e ainda mais exóticos.
Isso é uma boa notícia para a criptografia, mas também tem implicações mais amplas para problemas computacionais cujas entradas são estados quânticos.
A teoria tradicional da complexidade parece incapaz de resolver estes problemas.
Compreendê-los verdadeiramente pode exigir uma estrutura teórica radicalmente nova.
“Parece que há algo fundamentalmente diferente no modo como a informação quântica se comporta”, disse Andrea Coladangelo, criptógrafa quântica da Universidade de Washington.
“É provável que haja conexões que também vão além da criptografia.”
Publicado em 12/06/2024 21h14
Artigo original: