Os criptógrafos querem saber em qual dos cinco mundos possíveis habitamos, o que revelará se a criptografia verdadeiramente segura é possível.
Muitos cientistas da computação se concentram em superar problemas computacionais difíceis. Mas há uma área da ciência da computação em que a dureza é um trunfo: a criptografia, onde você quer obstáculos difíceis entre seus adversários e seus segredos.
Infelizmente, não sabemos se a criptografia segura realmente existe. Ao longo de milênios, as pessoas criaram cifras que pareciam inquebráveis até serem quebradas. Hoje, nossas transações na Internet e segredos de estado são protegidos por métodos de criptografia que parecem seguros, mas podem falhar a qualquer momento.
Para criar um método de criptografia verdadeiramente seguro (e permanente), precisamos de um problema computacional que seja difícil o suficiente para criar uma barreira comprovadamente intransponível para os adversários. Sabemos de muitos problemas computacionais que parecem difíceis, mas talvez não tenhamos sido inteligentes o suficiente para resolvê-los. Ou talvez alguns deles sejam difíceis, mas sua dureza não é do tipo que se presta à criptografia segura. Fundamentalmente, os criptógrafos se perguntam: existe dureza suficiente no universo para tornar a criptografia possível?
Em 1995, Russell Impagliazzo, da Universidade da Califórnia, em San Diego, dividiu a questão da dureza em um conjunto de subquestões que os cientistas da computação poderiam abordar uma por vez. Para resumir o estado do conhecimento nessa área, ele descreveu cinco mundos possíveis – fantasiosamente chamados de Algorithmica, Heuristica, Pessiland, Minicrypt e Cryptomania – com níveis crescentes de dureza e possibilidade criptográfica. Qualquer um desses pode ser o mundo em que vivemos.
Algoritmica
Neste mundo, as questões computacionais mais naturais são todas fáceis, o que torna a criptografia impossível. Aqui, o conjunto de problemas com soluções eficientes – um conjunto chamado P – não contém apenas os problemas que já descobrimos como resolver. Também inclui todos os problemas em outro conjunto chamado NP, que consiste nos problemas para os quais é fácil verificar uma solução proposta se alguém a entregar a você.
À primeira vista, P e NP parecem categorias diferentes. Por exemplo, tome o problema de decidir se suas malas comportarão todos os itens que você deseja embalar para uma viagem. Se um amigo fizer as malas para você, é fácil verificar se ele encaixou tudo – basta verificar os itens que ele perdeu. Portanto, o problema de empacotar a mala está em NP. Mas fazer as malas sozinho é muito mais difícil – você pode ter que tentar muitos arranjos diferentes. Não está claro se existe um algoritmo eficiente que resolva esse problema para todas as combinações possíveis de itens e malas. Ou seja, não sabemos se esse problema está em P.
O problema de descriptografar um esquema de criptografia também está em NP. Afinal, se você tem uma mensagem criptografada e um amigo afirma tê-la descriptografado, você pode verificar alimentando a mensagem descriptografada na máquina de criptografia e vendo se a saída corresponde à sua mensagem criptografada original. (Claro, você deve possuir uma das máquinas de criptografia para fazer isso, mas os criptógrafos não consideram um esquema seguro a menos que possa resistir a ataques de um inimigo que se apodere de uma das máquinas.)
Em Algorithmica, P e NP são o mesmo conjunto de problemas. Uma prova disso seria uma bonança algorítmica, pois significaria que existem algoritmos rápidos para coisas como fazer malas e todos os outros problemas aparentemente difíceis em NP. Mas seria um desastre para os criptógrafos, pois um dos problemas que poderíamos resolver com eficiência é a descriptografia.
A maioria dos cientistas da computação acredita que P é diferente de NP, pela simples razão de que existem tantos problemas em NP que não conseguimos resolver com eficiência. Mas ninguém jamais foi capaz de provar (ou refutar) isso, embora a questão “P versus NP” tenha sido considerada o problema mais famoso da ciência da computação teórica por cinco décadas. Por outro lado, disse Yuval Ishai do Technion em Haifa, Israel, “além do fracasso constante das pessoas mais inteligentes, não temos evidências de que seja difícil mostrar que P não é igual a NP”.
Heurística
Neste mundo, existem problemas em NP que não são fáceis de resolver, mas todo problema em NP é fácil “em média”, o que significa que pode ser resolvido de forma eficiente na maioria dos casos. Por exemplo, se estivermos no Heuristica, existe um algoritmo eficiente de empacotamento de malas que quase sempre é bem-sucedido, mas pode falhar para algumas combinações raras de malas e itens para empacotar. (Esses algoritmos rápidos e geralmente bem-sucedidos são comumente chamados de “heurísticas”.)
Do ponto de vista da criptografia, não há uma grande diferença entre Heuristica e Algorithmica. Se chegarmos a um esquema de criptografia no Heuristica, haverá algum método de descriptografia rápido que pode lidar com quase todas as mensagens, tornando o esquema inútil para fins práticos.
Pessilândia
Este é o pior de todos os mundos possíveis. Em Pessiland, alguns problemas em NP são difíceis, mesmo em média. Para esses problemas, qualquer algoritmo eficiente falhará não apenas ocasionalmente, mas com frequência. No entanto, esses problemas difíceis não são do tipo útil para esconder informações secretas.
“Definitivamente, não queremos morar em Pessiland”, disse Eric Allender, da Rutgers University. “Aqui temos todos os aspectos ruins da complexidade [computacional], mas sem nenhuma das vantagens como criptografia.”
Minicripta
Neste mundo, alguns problemas em NP são difíceis, em média, e essa dureza é suficiente para construir o bloco de construção mais fundamental da criptografia: uma “função unidirecional”, que é uma função que pode ser executada de forma eficiente, mas não pode ser revertida com eficiência. Os criptógrafos mostraram que a criptografia segura requer funções unidirecionais. E se os tivermos, obteremos uma variedade de itens criptográficos, como criptografia de chave secreta, assinaturas digitais e geradores de números pseudoaleatórios.
“A existência de funções unidirecionais é, sem dúvida, o problema mais importante na criptografia”, disse Rafael Pass, da Cornell University e da Cornell Tech. “Se não os tivermos, todas essas coisas podem ser quebradas.”
Criptomania
Neste mundo, temos dureza suficiente para criar tudo no Minicrypt, além de protocolos criptográficos ainda mais avançados, como criptografia de chave pública (na qual as pessoas podem enviar mensagens criptografadas sem conhecer a chave secreta).
Eliminando Mundos
A maioria dos criptógrafos, disse Ishai, acredita que pelo menos alguma criptografia existe, então provavelmente vivemos em Cryptomania ou Minicrypt. Mas eles não esperam uma prova disso tão cedo. Tal prova exigiria descartar os outros três mundos – e descartar a Algorithmica por si só já exige resolver o problema “P versus NP”, com o qual os cientistas da computação lutam há décadas.
Recentemente, porém, Pass e seu aluno de doutorado Yanyi Liu encontraram uma nova abordagem para vasculhar esses mundos. Pela primeira vez, eles identificaram um problema natural – chamado de complexidade de Kolmogorov limitada no tempo, ou Kt – cujo nível de dificuldade cria uma linha divisória brilhante entre os mundos que incluem criptografia e os mundos que não incluem. Se Kt é fácil em média, mostraram Liu e Pass, então a criptografia segura não pode existir, então estamos em Algorithmica, Heuristica ou Pessiland. Mas se Kt é difícil em média, então podemos fazer funções unidirecionais, então estamos pelo menos no Minicrypt e possivelmente na Cryptomania.
Esse novo resultado significa que os cientistas da computação podem eliminar Pessiland – o pior mundo – se puderem provar mais uma afirmação: se Kt é fácil em média, então todos os problemas em NP também são. Nesse caso, teremos reduzido as coisas para os mundos em que Kt é difícil em média (Minicrypt e Cryptomania) e aqueles em que Kt – e todos os outros problemas em NP – são fáceis em média (Algorithmica e Heuristica).
Os pesquisadores estão trabalhando na Pessiland há algum tempo, disse Ryan Williams, do Instituto de Tecnologia de Massachusetts. “Acho que o consenso geral é que Pessiland pode ser descartado, mas se vamos fazer isso mais cedo ou mais tarde, não sei.”
Os criptógrafos também gostariam de eliminar a Heuristica, o que envolveria provar que, se Kt é fácil em média, então todo problema em NP é fácil em todos os casos (não apenas na média). Descartar esses dois mundos significaria que ou vivemos em Algorithmica, onde tudo é fácil o tempo todo, ou temos dureza suficiente para criptografia básica.
Os criptógrafos referem-se amplamente a esse objetivo como o santo graal do campo. Ishai não espera ver isso provado em sua vida, mas mesmo isso é incerto. “Quando problemas difíceis são resolvidos, às vezes vemos isso chegando, mas às vezes não”, disse ele. “Definitivamente, nossa melhor chance é essa nova linha de trabalho.”
Publicado em 21/04/2022 10h19
Artigo original: