Truques de criptografia tornam um problema difícil um pouco mais fácil | Revista Quanta

Qual é a melhor maneira de resolver problemas difíceis? Essa é a questão central de um subcampo da ciência da computação chamado teoria da complexidade computacional. É uma pergunta difícil de responder, mas inverta-a e ficará mais fácil. A pior abordagem é quase sempre tentativa e erro, que envolve inserir soluções possíveis até que uma funcione. Mas para alguns problemas, parece que simplesmente não existem alternativas – a pior abordagem é também a melhor.

Os pesquisadores há muito se perguntam se esse é realmente o caso, disse Rahul Ilango, um estudante de pós-graduação que estuda teoria da complexidade no Instituto de Tecnologia de Massachusetts. “Você poderia perguntar: 'Existem problemas para os quais adivinhar e verificar é ideal?'”

Os teóricos da complexidade estudaram muitos problemas computacionais, e mesmo os mais difíceis muitas vezes admitem algum tipo de procedimento inteligente, ou algoritmo, que torna a descoberta de uma solução um pouco mais fácil do que pura tentativa e erro. Entre as poucas exceções estão os chamados problemas de compressão, onde o objetivo é encontrar a descrição mais curta de um conjunto de dados.

Mas em Novembro passado, dois grupos de investigadores independentemente descoberto outro algoritmo para problemas de compactação - um que é um pouco mais rápido do que verificar todas as respostas possíveis. A nova abordagem funciona adaptando um algoritmo inventado por criptógrafos há 25 anos para atacar um problema diferente. Há apenas uma restrição: você precisa adaptar o algoritmo ao tamanho do seu conjunto de dados.

“São resultados realmente lindos e importantes”, disse Eric Allender, um cientista da computação teórico da Rutgers University.

Definindo Dureza

Os novos resultados são os mais recentes a investigar uma questão estudada pela primeira vez na União Soviética, muito antes do advento da teoria da complexidade. “Antes de eu estar na escola primária, as pessoas na Rússia formulavam isso”, disse Allender.

O problema computacional específico estudado por esses pesquisadores soviéticos, denominado problema do tamanho mínimo do circuito, é semelhante àquele que os projetistas de hardware de computador enfrentam o tempo todo. Se você receber especificações completas de como um circuito eletrônico deve se comportar, você conseguirá encontrar o circuito mais simples que fará o trabalho? Ninguém sabia como resolver este problema sem “perebor” – uma palavra russa aproximadamente equivalente a “pesquisa exaustiva”.

O problema do tamanho mínimo do circuito é um exemplo de problema de compressão. Você pode descrever o comportamento de um circuito com uma longa sequência de bits – 0s e 1s – e então perguntar se existe uma maneira de reproduzir esse mesmo comportamento usando menos bits. A verificação de todos os layouts de circuito possíveis levaria um tempo que aumenta exponencialmente com o número de bits na string.

Esse tipo de crescimento exponencial é a característica definidora de um problema computacional difícil. Mas nem todos os problemas difíceis são igualmente difíceis – alguns têm algoritmos que são mais rápidos do que a pesquisa exaustiva, embora os seus tempos de execução ainda cresçam exponencialmente. Em termos modernos, a questão central é se existem tais algoritmos para problemas de compressão.

Em 1959, um pesquisador proeminente chamado Sergey Yablonsky afirmou ter provado que a pesquisa exaustiva era realmente a única maneira de resolver o problema do tamanho mínimo do circuito. Mas sua prova deixou algumas lacunas. Alguns pesquisadores notaram as falhas na época, mas Yablonsky foi influente o suficiente para desencorajar a maioria dos outros de trabalhar na questão do perebor.

Nas décadas que se seguiram, poucos pesquisadores estudaram problemas de compressão, e a questão do perebor ficou conhecida principalmente como uma nota de rodapé na pré-história da teoria da complexidade. A atenção generalizada à questão surgiu apenas recentemente, depois que pesquisadores descobriram uma curiosa ligação entre problemas de compressão e os fundamentos da criptografia.

Mão única

A criptografia moderna usa problemas computacionais difíceis para proteger mensagens secretas. Mas a dureza computacional só é útil se for assimétrica – se for difícil decifrar mensagens codificadas, mas não for difícil codificar mensagens em primeiro lugar.

Em todo esquema de criptografia, a origem dessa assimetria é um objeto matemático chamado função unidirecional, que transforma sequências de bits de entrada em sequências de saída do mesmo comprimento. Dada uma entrada para uma função unidirecional, é fácil calcular a saída, mas dada uma saída é difícil inverter a função - isto é, fazer engenharia reversa e recuperar a entrada.

“Os criptógrafos realmente gostariam de ter funções unidirecionais computáveis ​​de maneira muito eficiente e que fossem muito, muito difíceis de inverter”, disse Allender. Muitas funções matemáticas parecem ter esta propriedade, e a dificuldade de inverter essas funções decorre da aparente dificuldade de resolver diferentes problemas computacionais.

Infelizmente, os criptógrafos não sabem ao certo se alguma dessas funções é realmente difícil de inverter – na verdade, é possível que não existam funções unidirecionais verdadeiras. Esta incerteza persiste porque os teóricos da complexidade lutou por 50 anos para provar que problemas aparentemente difíceis são realmente difíceis. Se não forem, e se os pesquisadores descobrirem algoritmos super-rápidos para esses problemas, isso seria desastroso para a criptografia – semelhante a direcionar repentinamente carros em alta velocidade em ambas as direções em uma rua de mão única.

Embora uma compreensão abrangente da dureza computacional permaneça indefinida, os criptógrafos fizeram recentemente um progresso emocionante em direção a uma teoria unificada de funções unidirecionais. Um grande passo foi dado em 2020, quando o criptógrafo da Universidade de Tel Aviv Passe Rafael e seu aluno de pós-graduação Yan Yi Liu provou que funções unidirecionais são intimamente conectado para um problema de compressão específico denominado problema de complexidade de Kolmogorov limitado no tempo.

Se esse problema for realmente difícil de resolver para a maioria das entradas, então o resultado de Pass e Liu produz uma receita de como construir uma função unidirecional comprovadamente difícil - uma que seja garantidamente segura mesmo que outros problemas computacionais se revelem muito mais fáceis do que os pesquisadores esperavam. Mas se houver um algoritmo rápido para resolver o problema de complexidade de Kolmogorov limitado no tempo, então a criptografia está condenada e qualquer função pode ser facilmente invertida. Uma função unidirecional baseada na dureza deste problema é a função mais segura possível – uma função unidirecional para governar todos eles.

Construindo em Estruturas de Dados

A descoberta de Pass e Liu foi o capítulo mais recente de uma longa linha de pesquisa que utiliza a teoria da complexidade para compreender melhor os fundamentos da criptografia. Mas também sugeriu uma forma de inverter essa relação: a equivalência entre o problema de complexidade de Kolmogorov limitado no tempo e a inversão de função implica que as percepções sobre qualquer um dos problemas podem revelar mais sobre o outro. Os criptógrafos estudam algoritmos de inversão de funções há décadas para entender melhor os pontos fracos de seus métodos de criptografia. Os pesquisadores começaram a se perguntar se esses algoritmos poderiam ajudar a responder questões antigas da teoria da complexidade.

Como muitos problemas computacionais, a inversão de função pode ser resolvida por meio de uma pesquisa exaustiva. Dada uma string de saída, simplesmente insira todas as entradas possíveis na função até encontrar aquela que produza a resposta correta.

Em 1980, o criptógrafo Martin Hellman começou a estudar se era possível fazer algo melhor – a mesma pergunta que os matemáticos soviéticos tinham feito sobre problemas de compressão décadas antes. Homen do inferno descoberto isso sim, é possível - contanto que você esteja disposto a fazer algum trabalho extra com antecedência, usando objetos matemáticos chamados estruturas de dados.

Uma estrutura de dados é essencialmente uma tabela que armazena informações sobre a função a ser invertida, e a construção de uma requer o cálculo das saídas da função para certas entradas estrategicamente escolhidas. Todos esses cálculos “podem levar muito tempo”, disse Ryan Williams, um teórico da complexidade do MIT. “Mas a ideia é que isso seja feito de uma vez por todas.” Se você estiver tentando inverter a mesma função com muitas saídas diferentes - digamos, decodificar muitas mensagens diferentes criptografadas da mesma maneira - pode valer a pena fazer esse trabalho com antecedência.

É claro que armazenar essas informações extras requer espaço, então leve essa estratégia ao extremo e você poderá acabar com um programa rápido que não cabe em nenhum computador. Hellman projetou uma estrutura de dados inteligente que permitiu ao seu algoritmo inverter a maioria das funções um pouco mais rápido do que uma pesquisa exaustiva, sem ocupar muito mais espaço. Então, em 2000, os criptógrafos Amos Fiat e Moni Naor opção Argumentos de Hellman para todas as funções.

Após a descoberta de Pass e Liu em 2020, esses resultados antigos tornaram-se subitamente relevantes. O algoritmo Fiat-Naor poderia inverter funções arbitrárias mais rapidamente do que uma pesquisa exaustiva. Também poderia funcionar para problemas de compactação?

Fora do Uniforme

Os primeiros pesquisadores a levantar a questão foram o teórico da complexidade Rahul Santhanam da Universidade de Oxford e seu aluno de graduação Han Lin Ren. Eles fizeram isso em um papel 2021 provando que os problemas de compressão e inversão de função estavam ainda mais interligados do que os pesquisadores imaginavam.

Pass e Liu provaram que se o problema de complexidade de Kolmogorov limitado no tempo é difícil, então a inversão de função também deve ser difícil, e vice-versa. Mas os problemas podem ser difíceis e ainda assim admitir soluções um pouco melhores do que uma busca exaustiva. Santhanam e Ren mostraram que existe uma estreita ligação entre a necessidade de uma pesquisa exaustiva para um problema e se é necessária para o outro.

O resultado deles teve implicações diferentes para duas grandes classes de algoritmos que os pesquisadores frequentemente estudam, chamados algoritmos “uniformes” e “não uniformes”. Algoritmos uniformes seguem o mesmo procedimento para cada entrada – um programa uniforme para ordenar listas de números, por exemplo, funcionará da mesma maneira quer haja 20 entradas na lista ou 20,000. Em vez disso, algoritmos não uniformes usam procedimentos diferentes para entradas de comprimentos diferentes.

As estruturas de dados utilizadas pelo algoritmo Fiat-Naor são sempre adaptadas para uma função específica. Para inverter uma função que embaralha uma string de 10 bits, você precisa de uma estrutura de dados diferente daquela necessária para inverter uma função que embaralha uma string de 20 bits, mesmo que a mistura seja feita de maneira semelhante. Isso torna o Fiat-Naor um algoritmo não uniforme.

O resultado de Santhanam e Ren sugeriu que poderia ser possível transformar o algoritmo Fiat-Naor em um algoritmo para resolver problemas de compressão. Mas adaptar o algoritmo de um problema para outro não foi simples e eles não levaram a questão adiante.

Pass teve a mesma ideia um ano depois, depois de ouvir a Fiat dar uma palestra sobre o algoritmo clássico em um workshop que celebrava as contribuições de Naor para a criptografia. “Essa ideia de usar a inversão de funções estava na minha mente desde então”, disse ele. Mais tarde, ele começou a trabalhar seriamente no problema com o pesquisador da Universidade de Tel Aviv. Noam Mazor.

Enquanto isso, Ilango foi inspirado a atacar o problema após discussões com outros pesquisadores, incluindo Santhanam, durante uma visita ao Instituto Simons de Teoria da Computação em Berkeley, Califórnia. “Isso surgiu de uma dessas conversas fortuitas em que você está apenas jogando coisas ao redor”, disse Santhanam. Ilango mais tarde juntou forças com Williams e Shuichi Hirahara, um teórico da complexidade do Instituto Nacional de Informática de Tóquio.

A parte difícil foi descobrir como incorporar a estrutura de dados central do algoritmo Fiat-Naor em um algoritmo não uniforme para resolver problemas de compressão. Existe um procedimento padrão para fazer esse tipo de incorporação, mas isso tornaria o algoritmo mais lento, eliminando sua vantagem sobre a pesquisa exaustiva. As duas equipes encontraram maneiras mais inteligentes de incorporar a estrutura de dados Fiat-Naor e obtiveram algoritmos para problemas de compressão que funcionaram em todas as entradas e permaneceram mais rápidos do que uma pesquisa exaustiva.

Os detalhes dos dois algoritmos diferem ligeiramente. O de Ilango e seus coautores é mais rápido do que a pesquisa exaustiva, mesmo se você restringir a pesquisa às possibilidades mais simples, e se aplica a todos os problemas de compressão - complexidade de Kolmogorov limitada no tempo, problema de tamanho mínimo de circuito e muitos outros. Mas a ideia central era a mesma para ambos os algoritmos. As técnicas de criptografia provaram seu valor neste novo domínio.

Convergência de Inversão

A nova prova para algoritmos não uniformes levanta uma questão natural: e os algoritmos uniformes? Existe uma maneira de resolver problemas de compactação mais rapidamente do que uma pesquisa exaustiva usando-os?

A recente série de resultados implica que qualquer algoritmo desse tipo seria equivalente a um algoritmo uniforme para inverter funções arbitrárias – algo que os criptógrafos têm procurado sem sucesso durante décadas. Por causa disso, muitos pesquisadores consideram a possibilidade improvável.

“Eu ficaria muito surpreso”, disse Santhanam. “Isso exigiria uma ideia completamente nova.”

Mas Allender disse que os pesquisadores não deveriam descartar essa possibilidade. “Para mim, uma boa hipótese de trabalho é que, se existe uma forma não uniforme de fazer alguma coisa, muito provavelmente existe uma forma uniforme”, disse ele.

De qualquer forma, o trabalho fez com que os teóricos da complexidade se interessassem novamente por velhas questões da criptografia. Yuval Ishai, criptógrafo do Technion em Haifa, Israel, disse que é isso que torna tudo mais emocionante.

“Estou muito feliz em ver esta convergência de interesses entre diferentes comunidades”, disse ele. “Acho que é ótimo para a ciência.”