Em 2018, Aayush Jain, um estudante graduado da Universidade da Califórnia em Los Angeles, viajou ao Japão para dar uma palestra sobre uma ferramenta criptográfica poderosa que ele e seus colegas estavam desenvolvendo. Enquanto ele detalhava a abordagem da equipe para a ofuscação indistinguível (iO para abreviar), um membro da audiência levantou a mão em perplexidade.
“Mas eu pensei que iO não existisse?” ele disse.
Na época, esse ceticismo era generalizado. A ofuscação indistinguível, se pudesse ser construída, seria capaz de ocultar não apenas coleções de dados, mas o funcionamento interno de um programa de computador, criando uma espécie de ferramenta criptográfica mestre a partir da qual quase todos os outros protocolos criptográficos poderiam ser construídos. É “um primitivo criptográfico para governar todos eles”, disse Boaz Barak, da Universidade de Harvard. Mas, para muitos cientistas da computação, esse mesmo poder fazia o iO parecer bom demais para ser verdade.
Os cientistas da computação estabeleceram versões candidatas do iO a partir de 2013. Mas a intensa empolgação que essas construções geravam gradualmente se dissipou, à medida que outros pesquisadores descobriam como quebrar sua segurança. Conforme os ataques se acumulavam, “você podia ver muitas vibrações negativas”, disse Yuval Ishai, do Technion em Haifa, Israel. Os pesquisadores se perguntaram, ele disse: “Quem vai ganhar: os fabricantes ou os destruidores?”
“Havia pessoas que eram zelotes, e eles acreditavam em [iO] e continuaram trabalhando nisso”, disse Shafi Goldwasser, diretor do Instituto Simons de Teoria da Computação da Universidade da Califórnia, Berkeley. Mas com o passar dos anos, ela disse: “havia cada vez menos dessas pessoas”.
Agora, Jain – junto com Huijia Lin da Universidade de Washington e Amit Sahai, conselheiro de Jain na UCLA – plantou uma bandeira para os fabricantes. Em um artigo publicado online em 18 de agosto, os três pesquisadores mostram pela primeira vez como construir a ofuscação indistinguível usando apenas suposições de segurança “padrão”.
Todos os protocolos criptográficos baseiam-se em suposições – alguns, como o famoso algoritmo RSA, dependem da crença amplamente aceita de que os computadores padrão nunca serão capazes de fatorar rapidamente o produto de dois grandes números primos. Um protocolo criptográfico é tão seguro quanto suas suposições, e as tentativas anteriores de iO foram construídas em bases não testadas e, em última análise, instáveis. O novo protocolo, por outro lado, depende de suposições de segurança que foram amplamente usadas e estudadas no passado.
“Salvo um desenvolvimento realmente surpreendente, essas suposições permanecerão”, disse Ishai.
Embora o protocolo esteja longe de ser implantado em aplicativos do mundo real, do ponto de vista teórico ele fornece uma maneira instantânea de construir uma série de ferramentas criptográficas que antes estavam fora de alcance. Por exemplo, permite a criação de criptografia “negável”, na qual você pode convencer de forma plausível um invasor de que enviou uma mensagem totalmente diferente daquela que realmente enviou, e criptografia “funcional”, na qual você pode dar aos usuários escolhidos níveis diferentes de acesso para realizar cálculos usando seus dados.
O novo resultado deve silenciar definitivamente os céticos do IO, disse Ishai. “Agora não haverá mais dúvidas sobre a existência de ofuscação indistinguível”, disse ele. “Parece um final feliz.”
A joia da coroa
Por décadas, os cientistas da computação se perguntaram se havia alguma maneira segura e abrangente de ofuscar programas de computador, permitindo que as pessoas os usassem sem descobrir seus segredos internos. A ofuscação do programa permitiria uma série de aplicativos úteis: por exemplo, você poderia usar um programa ofuscado para delegar tarefas específicas dentro de seu banco ou contas de e-mail para outras pessoas, sem se preocupar se alguém poderia usar o programa de uma forma que não foi planejada ou leia as senhas de sua conta (a menos que o programa tenha sido projetado para gerá-las).
Mas, até agora, todas as tentativas de construir ofuscadores práticos falharam. “Os que surgiram na vida real estão ridiculamente quebrados, … normalmente, poucas horas depois de serem soltos na natureza”, disse Sahai. Na melhor das hipóteses, eles oferecem aos atacantes um redutor de velocidade, disse ele.
Em 2001, más notícias vieram também na frente teórica: a forma mais forte de ofuscação é impossível. Chamada de ofuscação de caixa preta, ela exige que os invasores não possam aprender absolutamente nada sobre o programa, exceto o que podem observar usando o programa e vendo o que ele produz. Alguns programas, como Barak, Sahai e cinco outros pesquisadores mostraram, revelam seus segredos com tanta determinação que são impossíveis de ofuscar totalmente.
Esses programas, no entanto, foram especialmente concebidos para desafiar a ofuscação e têm pouca semelhança com programas do mundo real. Portanto, os cientistas da computação esperavam que pudesse haver algum outro tipo de ofuscação que fosse fraca o suficiente para ser viável, mas forte o suficiente para esconder os tipos de segredos com os quais as pessoas realmente se importam. Os mesmos pesquisadores que mostraram que a ofuscação da caixa preta é impossível propuseram uma alternativa possível em seu trabalho: ofuscação por indistinguibilidade.
Diante disso, iO não parece um conceito especialmente útil. Em vez de exigir que os segredos de um programa sejam ocultados, ele simplesmente exige que o programa seja ofuscado o suficiente para que, se você tiver dois programas diferentes que realizam a mesma tarefa, não consiga distinguir qual versão ofuscada veio de qual versão original.
Mas iO é mais forte do que parece. Por exemplo, suponha que você tenha um programa que executa alguma tarefa relacionada à sua conta bancária, mas o programa contém sua senha não criptografada, tornando-o vulnerável a qualquer pessoa que se apossar do programa. Então – enquanto houver algum programa por aí que possa realizar a mesma tarefa, mantendo sua senha oculta – um ofuscador de indistinguibilidade será forte o suficiente para mascarar a senha com sucesso. Afinal, se não funcionasse, se você colocasse os dois programas no obfuscator, seria capaz de dizer qual versão ofuscada veio do programa original.
Ao longo dos anos, os cientistas da computação mostraram que você pode usar o iO como base para quase todos os protocolos criptográficos que você possa imaginar (exceto para ofuscação de caixa preta). Isso inclui tarefas criptográficas clássicas como criptografia de chave pública (que é usada em transações online) e estonteantes recém-chegados como criptografia totalmente homomórfica, na qual um computador em nuvem pode computar dados criptografados sem aprender nada sobre isso. E inclui protocolos criptográficos que ninguém sabia como construir, como criptografia negável ou funcional.
“É realmente a joia da coroa” dos protocolos criptográficos, disse Rafael Pass, da Cornell University. “Depois de conseguir isso, podemos obter essencialmente tudo.”
Em 2013, Sahai e cinco coautores propuseram um protocolo iO que divide um programa em algo como peças de um quebra-cabeça e, em seguida, usa objetos criptográficos chamados mapas multilineares para deturpar as peças individuais. Se as peças forem colocadas juntas corretamente, a distorção se cancela e o programa funciona conforme o planejado, mas cada peça individual parece sem sentido. O resultado foi saudado como um avanço e gerou dezenas de artigos complementares. Mas, em poucos anos, outros pesquisadores mostraram que os mapas multilineares usados no processo de distorção não eram seguros. Outros candidatos iO apareceram e foram quebrados por sua vez.
“Houve alguma preocupação de que talvez isso seja apenas uma miragem, talvez IO seja simplesmente impossível de obter”, disse Barak. As pessoas começaram a sentir, disse ele, que “talvez toda essa empresa esteja condenada”.
Escondendo menos para esconder mais
Em 2016, Lin começou a explorar se seria possível contornar os pontos fracos dos mapas multilineares simplesmente exigindo menos deles. Mapas multilineares são essencialmente apenas formas secretas de computação com polinômios – expressões matemáticas feitas de somas e produtos de números e variáveis, como 3xy + 2yz2. Esses mapas, disse Jain, envolvem algo semelhante a uma máquina de calcular polinomial conectada a um sistema de armários secretos contendo os valores das variáveis. Um usuário que insere um polinômio que a máquina aceita consegue olhar dentro de um armário final para descobrir se os valores ocultos fazem o polinômio ser avaliado como 0.
Para que o esquema seja seguro, o usuário não deve ser capaz de descobrir nada sobre o conteúdo dos outros armários ou os números que foram gerados ao longo do caminho. “Gostaríamos que isso fosse verdade”, disse Sahai. Mas em todos os mapas multilineares candidatos que as pessoas puderam fazer, o processo de abertura do armário final revelou informações sobre o cálculo que deveriam permanecer ocultas.
Uma vez que todas as máquinas de mapas multilineares propostas tinham pontos fracos de segurança, Lin se perguntou se havia uma maneira de construir iO usando máquinas que não tivessem que calcular tantos tipos diferentes de polinômios (e, portanto, seriam mais fáceis de construir com segurança). Quatro anos atrás, ela descobriu como construir iO usando apenas mapas multilineares que calculam polinômios cujo “grau” é 30 ou menos (o que significa que cada termo é um produto de no máximo 30 variáveis, contando repetições). Ao longo dos anos seguintes, ela, Sahai e outros pesquisadores descobriram gradualmente como diminuir o grau ainda mais, até que puderam mostrar como construir iO usando mapas multilineares de apenas grau 3.
No papel, parecia uma grande melhoria. Havia apenas um problema: do ponto de vista da segurança, “o grau 3 estava tão quebrado” quanto as máquinas que podem lidar com polinômios de todos os graus, disse Jain.
Os únicos mapas multilineares que os pesquisadores sabiam como construir com segurança eram aqueles que computavam polinômios de grau 2 ou menos. Lin juntou forças com Jain e Sahai para tentar descobrir como construir iO a partir de mapas multilineares de grau 2. Mas “ficamos presos por muito, muito tempo”, disse Lin.
“Foi uma época meio sombria”, lembra Sahai. “Há um cemitério cheio de ideias que não funcionaram.”
Eventualmente, porém – junto com Prabhanjan Ananth da University of California, Santa Barbara e Christian Matt do projeto blockchain Concordium – eles tiveram uma ideia para uma espécie de compromisso: já que o iO parecia precisar de mapas de grau 3, mas cientistas da computação só tinha construções seguras para mapas de grau 2, e se houvesse algo entre – uma espécie de mapa de grau 2,5?
Os pesquisadores imaginaram um sistema em que alguns dos armários tivessem janelas transparentes, para que o usuário pudesse ver os valores contidos neles. Isso libera a máquina de ter que proteger muitas informações ocultas. Para encontrar um equilíbrio entre o poder dos mapas multilineares de alto grau e a segurança dos mapas de grau 2, a máquina pode calcular com polinômios de grau superior a 2, mas há uma restrição: O polinômio deve ter grau 2 no oculto variáveis. “Estamos tentando não esconder tanto” como em mapas multilineares em geral, disse Lin. Os pesquisadores conseguiram mostrar que esses sistemas de armários híbridos podem ser construídos com segurança.
Mas, para passar desses mapas multilineares menos poderosos para o iO, a equipe precisava de um último ingrediente: um novo tipo de gerador de pseudo-aleatoriedade, algo que expande uma sequência de bits aleatórios em uma sequência mais longa que ainda parece aleatória o suficiente para enganar os computadores. Isso é o que Jain, Lin e Sahai descobriram como fazer em seu novo jornal. “Houve um mês passado maravilhoso em que tudo se encaixou em uma enxurrada de telefonemas”, disse Sahai.
O resultado é um protocolo iO que finalmente evita os pontos fracos de segurança dos mapas multilineares. “O trabalho deles está absolutamente lindo”, disse Pass.
A segurança do esquema baseia-se em quatro premissas matemáticas que foram amplamente utilizadas em outros contextos criptográficos. E mesmo a suposição que menos foi estudada, chamada de “aprendizagem paridade com ruído”, está relacionada a um problema que vem sendo estudado desde a década de 1950.
Provavelmente, apenas uma coisa poderia quebrar o novo esquema: um computador quântico, se algum dia for construído um com potência total. Uma das quatro suposições é vulnerável a ataques quânticos, mas nos últimos meses uma linha separada de trabalho surgiu em três artigos separados de Pass e outros pesquisadores que oferecem uma rota potencial diferente para o iO que pode ser segura até mesmo contra ataques quânticos. Essas versões do iO baseiam-se em suposições de segurança menos estabelecidas do que as que Jain, Lin e Sahai usaram, disseram vários pesquisadores. Mas é possível, disse Barak, que as duas abordagens possam ser combinadas nos próximos anos para criar uma versão do iO que se baseia em suposições de segurança padrão e também resiste a ataques quânticos.
A construção de Jain, Lin e Sahai provavelmente atrairá novos pesquisadores para o campo para trabalhar para tornar o esquema mais prático e desenvolver novas abordagens, previu Ishai. “Uma vez que você sabe que algo é possível em princípio, torna-se psicologicamente muito mais fácil trabalhar na área”, disse ele.
Os cientistas da computação ainda têm muito trabalho a fazer antes que o protocolo (ou alguma variação dele) possa ser usado em aplicações do mundo real. Mas isso é normal, disseram os pesquisadores. “Há muitas noções em criptografia de que, quando surgiram, as pessoas diziam: ‘Isso é apenas teoria pura, [não] tem relevância para a prática'”, disse Pass. “Então, 10 ou 20 anos depois, o Google está implementando essas coisas.”
O caminho de um avanço teórico a um protocolo prático pode ser longo, disse Barak. “Mas você pode imaginar”, disse ele, “que talvez daqui a 50 anos os livros de criptografia dirão basicamente: ‘OK, aqui está uma construção muito simples de iO, e daí derivaremos todo o resto da criptografia . ‘”
Publicado em 11/11/2020 09h39
Artigo original:
Achou importante? Compartilhe!
Assine nossa newsletter e fique informado sobre Astrofísica, Biofísica, Geofísica e outras áreas. Preencha seu e-mail no espaço abaixo e clique em “OK”: