A nova matemática da criptografia quântica

A versão original de esta história apareceu em Quanta revista.

Problemas difíceis geralmente não são uma visão bem -vinda. Mas os criptografistas os amam. Isso ocorre porque certos problemas matemáticos difíceis sustentam a segurança da criptografia moderna. Qualquer truque inteligente para resolvê -los condenará a maioria das formas de criptografia.

Vários anos atrás, os pesquisadores encontraram uma abordagem radicalmente nova para a criptografia Isso não tem esse ponto fraco potencial. 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 especiais, a nova abordagem pode realizar uma gama muito mais ampla de tarefas. E poderia funcionar, mesmo que todos os problemas no coração da criptografia “clássica” comum acabassem sendo facilmente solucionáveis.

Mas essa descoberta impressionante se baseou em suposições irreais. O resultado foi “mais uma prova de conceito”, disse Firme, masum pesquisador de criptografia do Instituto Simons para a teoria da computação em Berkeley, Califórnia. “Não é uma declaração sobre o mundo real.”

Agora, a Novo papel Por dois criptografistas, estabeleceu um caminho para a criptografia quântica sem essas suposições estranhas. “Este artigo está dizendo que, se certas outras conjecturas forem verdadeiras, a criptografia quântica deve existir”, disse Ma.

Castelo no céu

Você pode pensar na criptografia moderna como uma torre com três partes essenciais. A primeira parte é a rocha profunda sob a torre, feita de problemas matemáticos difíceis. A torre em si é a segunda parte – você pode encontrar protocolos criptográficos específicos que permitem enviar mensagens particulares, assinar documentos digitais, votar votar e muito mais.

No meio, proteger aqueles aplicativos do dia-a-dia para a base matemática, é uma base feita de blocos de construção chamados funções unidirecionais. Eles são responsáveis ​​pela assimetria inerente a qualquer esquema de criptografia. “É de mão única porque você pode criptografar mensagens, mas não pode descriptografá-las”, disse Mark Zhandryum criptografista na NTT Research.

Na década de 1980, os pesquisadores provaram que a criptografia construída sobre as funções unidirecionais garantiria a segurança para muitas tarefas diferentes. Mas décadas depois, eles ainda não têm certeza de que a rocha é forte o suficiente para apoiá -la. O problema é que a rocha é feita de problemas difíceis especiais – tecnicamente conhecidos como problemas de NP – cujo recurso definidor é que é fácil verificar se alguma solução candidata está correta. (Por exemplo, dividir um número em seus principais fatores é um problema de NP: difícil de fazer para grandes números, mas fácil de verificar.)

Muitos desses problemas parecem intrinsecamente difíceis, mas cientistas da computação não consegui provar isso. Se alguém descobrir um algoritmo engenhoso para resolver rapidamente os problemas mais difíceis do NP, a rocha desmoronará e toda a torre entrará em colapso.

Infelizmente, você não pode simplesmente mover sua torre para outro lugar. A fundação da torre-uma função de caminho-pode ficar sentada apenas em uma rocha de problemas de NP.

Para construir uma torre com problemas mais difíceis, os criptografistas precisariam de uma nova base que não seja feita de funções unidirecionais. Isso parecia impossível até apenas alguns anos atrás, quando os pesquisadores perceberam que a física quântica poderia ajudar.