0
0
Durante anos, uma ferramenta mestra chamada ofuscação indistinguibilidade parecia boa demais para ser verdade. Três pesquisadores descobriram que pode funcionar.
Em 2018, AAYUSH Jain, um estudante de pós-graduação da Universidade da Califórnia, Los Angeles, viajou para o Japão para dar uma palestra sobre uma poderosa ferramenta criptográfica que ele e seus colegas estavam desenvolvendo. Enquanto detalhava a abordagem da equipe à ofuscação indistinguibilidade (iO para abreviar), um membro da plateia levantou a mão em perplexidade.
“Mas eu pensei que o IO não existe?”, Disse ele.
Na época, tal ceticismo era generalizado. A ofuscação indistinguibilidade, se pudesse ser construída, seria capaz de esconder não apenas coleções de dados, mas o funcionamento interno de um programa de computador em si, criando uma espécie de ferramenta mestre criptográfica 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 fez com que o IO parecesse bom demais para ser verdade.
Cientistas da computação estabeleceram versões candidatas do IO a partir de 2013. Mas a intensa excitação que essas construções geraram gradualmente diminuiu, à medida que outros pesquisadores descobriram como quebrar sua segurança. À medida que 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 disjuntores?”
“Havia as pessoas que eram os fanáticos, e eles acreditavam [iO] e continuavam trabalhando nisso”, disse Shafi Goldwasser, diretor do Instituto Simons para a 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 – juntamente 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 ofuscação de indistinguibilidade usando apenas suposições de segurança “padrão”.
Todos os protocolos criptográficos repousam em suposições — alguns, como o famoso algoritmo RSA, dependem da crença amplamente sustentada 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 tentativas anteriores de IO foram construídas em fundações não testadas e, em última instância, instável. O novo protocolo, em contrapartida, depende de premissas de segurança que foram amplamente utilizadas e estudadas no passado.
“Salvo um desenvolvimento realmente surpreendente, essas suposições permanecerão”, disse Ishai.
Embora o protocolo esteja longe de estar pronto para ser implantado em aplicações 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, ele permite a criação de criptografia “inegável”, na qual você pode plausivelmente convencer um invasor de que você enviou uma mensagem totalmente diferente da que você realmente enviou, e criptografia “funcional”, na qual você pode dar aos usuários escolhidos diferentes níveis de acesso para executar 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 indistinguibilidade”, disse ele. “Parece um final feliz.”A Joia da Coroa
Durante décadas, os cientistas da computação se perguntaram se há 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 suas contas bancárias ou de e-mail para outros indivíduos, sem se preocupar que alguém poderia usar o programa de uma maneira que não era destinado ou ler as senhas da sua conta (a menos que o programa fosse projetado para desfee com eles).
Mas até agora, todas as tentativas de construir ofuscadores práticos falharam. “Os que saíram na vida real estão ridiculamente quebrados, … tipicamente, poucas horas após a libertação na natureza”, disse Sahai. Na melhor das hipóteses, eles oferecem aos atacantes uma lombada, disse ele.
Em 2001, a má notícia veio na frente teórica também: A forma mais forte de ofuscação é impossível. Chamado de ofuscação da caixa preta, ele exige que os atacantes não sejam capazes de aprender absolutamente nada sobre o programa, exceto o que eles podem observar usando o programa e vendo o que ele produz. Alguns programas, Barak, Sahai e outros cinco pesquisadores mostraram,revelam seus segredos tão determinadamente que são impossíveis de ofuscar totalmente.
Esses programas, no entanto, foram especialmente inventados para desafiar a ofuscação e ter pouca semelhança com programas do mundo real. Então, os cientistas da computação esperavam que houvesse 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 que as pessoas realmente se importam. Os mesmos pesquisadores que mostraram que a ofuscação da caixa preta é impossível propôs uma possível alternativa em seu artigo: a ofuscação indistinguibilidade.
Diante disso, o IO não parece um conceito especialmente útil. Em vez de exigir que os segredos de um programa sejam escondidos, ele simplesmente exige que o programa seja ofuscado o suficiente para que se você tiver dois programas diferentes que executam a mesma tarefa, você não pode distinguir qual versão ofuscada veio da qual versão original.
Mas o IO é mais forte do que parece. Por exemplo, suponha que você tenha um programa que realize 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 receba o programa. Então — desde que haja algum programa lá fora que possa executar a mesma tarefa enquanto mantém sua senha oculta — um ofuscador indistinguável será forte o suficiente para mascarar com sucesso a senha. Afinal, se não, então se você colocar ambos os programas através do ofuscador, você seria capaz de dizer qual versão ofuscada veio do seu programa original.
Ao longo dos anos, cientistas da computação mostraram que você pode usar o IO como base para quase todos os protocolos criptográficos que você poderia imaginar (exceto a ofuscação da caixa preta). Isso inclui tanto tarefas criptográficas clássicas como criptografia de chave pública (que é usada em transações online) e recém-chegados deslumbrantes como criptografia totalmente homomórfica, na qual um computador em nuvem pode calcular dados criptografados sem aprender nada sobre isso. E inclui protocolos criptográficos que ninguém sabia construir, como criptografia inegável ou funcional.
“É realmente uma espécie de joia da coroa” dos protocolos criptográficos, disse Rafael Pass, da Universidade de Cornell. “Uma vez que você 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 quebra-cabeça, em seguida, usa objetos criptográficos chamados mapas multilineares para desarmar as peças individuais. Se as peças forem montadas corretamente, o garbling é cancelado e o programa funciona como planejado, mas cada peça individual parece sem sentido. O resultado foi saudado como um avanço e levou dezenas de trabalhos de acompanhamento. Mas em poucos anos, outros pesquisadores mostraram que os mapas multilineares usados no processo de garbling não eram seguros. Outros candidatos do IO vieram e foram quebrados por sua vez.
“Havia alguma preocupação de que talvez isso seja apenas uma miragem, talvez o IO seja simplesmente impossível de obter”, disse Barak. As pessoas começaram a sentir, ele disse, que “talvez toda esta empresa esteja condenada.”Escondendo menos para esconder mais
Em 2016, Lin começou a explorar se seria possível contornar as fraquezas dos mapas multilineares simplesmente exigindo menos deles. Mapas multilineares são essencialmente apenas formas secretas de computação com polinômias — expressões matemáticas compostas de somas e produtos de números e variáveis, como 3xy +2 yz2. Esses mapas, disse Jain, envolvem algo semelhante a uma máquina de cálculo polinomial conectada a um sistema de armários secretos contendo os valores das variáveis. Um usuário que cai em um polinômial que a máquina aceita consegue olhar dentro de um armário final para descobrir se os valores ocultos fazem o polinômial avaliar para 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 poderiam vir com, o processo de abertura do armário final revelou informações sobre o cálculo que deveria permanecer escondido.
Como as máquinas de mapa multilinear propostas tinham fraquezas de segurança, Lin se perguntou se havia uma maneira de construir iO usando máquinas que não têm que calcular tantos tipos diferentes de polinômias (e, portanto, poderia ser mais fácil de construir com segurança). Quatro anos atrás, ela descobriu como construir iO usando apenas mapas multilineares que computam polinômias cujo “grau” é de 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 gradualmente descobriram como baixar o grau ainda mais baixo, até que eles foram capazes de mostrar como construir iO usando apenas mapas multilineares grau 3.
No papel, parecia uma grande melhoria. Havia apenas um problema: do ponto de vista da segurança, o “grau 3 estava realmente tão quebrado” quanto as máquinas que podem lidar com polinômias de todos os graus, disse Jain.
Os únicos mapas multilineares que os pesquisadores sabiam construir com segurança foram aqueles que computavam polinômias de grau 2 ou menos. Lin uniu forças com Jain e Sahai para tentar descobrir como construir iO a partir de mapas multilineares grau 2. Mas “ficamos presos por muito, muito tempo”, disse Lin.
“Foi uma época sombria”, lembrou Sahai. “Há um cemitério cheio de todas as ideias que não funcionaram.”
Eventualmente, porém , juntamente com Prabhanjan Ananth da Universidade da Califórnia, Santa Barbara, e Christian Matt do projeto blockchain Concordium – eles tiveram uma ideia para uma espécie de compromisso: Uma vez que o IO parecia precisar de mapas de grau 3, mas os cientistas da computação só tinham construções seguras para mapas de grau 2, e se houvesse algo no meio – uma espécie de mapa grau 2,5?
Os pesquisadores visualizaram um sistema no qual alguns dos armários têm janelas claras, para que o usuário possa ver os valores contidos dentro. Isso liberta a máquina de ter que proteger muitas informações ocultas. Para encontrar um equilíbrio entre o poder dos mapas multilineares de maior grau e a segurança dos mapas de grau 2, a máquina é autorizada a calcular com polinômias de grau superior a 2, mas há uma restrição: o polinômial deve ser grau 2 nas variáveis ocultas. “Estamos tentando não nos esconder tanto” quanto em mapas multilineares em geral, disse Lin. Os pesquisadores foram capazes de mostrar que esses sistemas de armários híbridos podem ser construídos com segurança.
Mas para ir 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 série de bits aleatórios em uma cadeia mais longa que ainda parece aleatória o suficiente para enganar computadores. Isso é o que Jain, Lin e Sahai descobriram como fazer em seu novo jornal. “Houve um mês maravilhoso no mês passado, onde tudo se juntou em uma enxurrada de telefonemas”, disse Sahai.
O resultado é um protocolo iO que finalmente evita as fraquezas de segurança de mapas multilineares. “Seu trabalho parece absolutamente lindo”, disse Pass.
A segurança do esquema baseia-se em quatro suposições matemáticas que têm sido amplamente utilizadas em outros contextos criptográficos. E mesmo a suposição que tem sido menos estudada, chamada de suposição de “paridade de aprendizagem com ruído”, está relacionada a um problema que vem sendo estudado desde a década de 1950.
Há provavelmente apenas uma coisa que poderia quebrar o novo esquema: um computador quântico,se um de potência total for construído. Uma das quatro suposições é vulnerável a ataques quânticos, mas nos últimos meses uma linha de trabalho separada surgiu em três artigos separados pela Pass e outros pesquisadores oferecendo uma rota potencial diferente para o IO que pode ser segura até mesmo de ataques quânticos. Essas versões do IO repousam 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 repousa 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 em 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 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 sobre ele) possa ser usado em aplicações do mundo real. Mas isso é par para o curso, disseram os pesquisadores. “Há muitas noções na criptografia que, quando saíram pela primeira vez, as pessoas estavam dizendo: ‘Isso é pura teoria, [ela] não tem relevância para praticar”, disse Pass. “Então, 10 ou 20 anos depois, o Google está implementando essas coisas.”
O caminho de um avanço teórico para um protocolo prático pode ser longo, disse Barak. “Mas você pode imaginar”, disse ele, “que talvez daqui a 50 anos os livros didáticos basicamente dirão: ‘OK, aqui está uma construção muito simples de IO, e a partir disso vamos agora derivar todo o resto da criptomoeda.'”
História original reimpressa com permissão da Quanta Magazine, uma publicação editorialmente independente da Fundação Simons cuja missão é melhorar a compreensão pública da ciência, cobrindo desenvolvimentos de pesquisa e tendências em matemática e ciências físicas e da vida.
FONTE: WIRED