Criptógrafos desenvolvem uma abordagem para privacidade total de pesquisa | Revista Quanta

Todos sabemos que devemos ter cuidado com os detalhes que partilhamos online, mas a informação que procuramos também pode ser reveladora. Pesquise instruções de direção e nossa localização ficará muito mais fácil de adivinhar. Verifique se há uma senha em uma coleção de dados comprometidos e corremos o risco de vazá-la nós mesmos.

Essas situações alimentam uma questão-chave na criptografia: como extrair informações de um banco de dados público sem revelar nada sobre o que você acessou? É o equivalente a retirar um livro da biblioteca sem que o bibliotecário saiba qual.

Elaborar uma estratégia que resolva esse problema – conhecida como recuperação de informações privadas – é “um alicerce muito útil em uma série de aplicações de preservação de privacidade”, disse David Wu, criptógrafo da Universidade do Texas, Austin. Desde a década de 1990, os pesquisadores têm trabalhado na questão, melhorando estratégias para acesso privado a bancos de dados. Um objetivo principal, ainda impossível com grandes bancos de dados, é o equivalente a uma pesquisa privada no Google, onde você pode examinar uma pilha de dados anonimamente, sem fazer nenhum trabalho computacional pesado.

Agora, três pesquisadores Crafted uma versão há muito procurada de recuperação de informações privadas e ampliou-a para construir uma estratégia de privacidade mais geral. A obra, que recebeu Melhor Prêmio de Papel em junho na anual Simpósio de Teoria da Computação, derruba uma importante barreira teórica no caminho para uma busca verdadeiramente privada.

“[Isso é] algo em criptografia que acho que todos queríamos, mas não acreditávamos que existisse”, disse Vinod Vaikuntathan, um criptógrafo do Instituto de Tecnologia de Massachusetts que não esteve envolvido no artigo. “É um resultado marcante.”

O problema do acesso privado a bancos de dados tomou forma na década de 1990. No início, os investigadores presumiram que a única solução seria digitalizar toda a base de dados durante cada pesquisa, o que seria como ter um bibliotecário a vasculhar todas as prateleiras antes de regressar com o seu livro. Afinal, se a busca pulasse alguma seção, o bibliotecário saberia que o seu livro não está naquela parte da biblioteca.

Essa abordagem funciona bem em escalas menores, mas à medida que o banco de dados cresce, o tempo necessário para verificá-lo aumenta pelo menos proporcionalmente. À medida que você lê bancos de dados maiores – e a Internet é muito grande – o processo se torna proibitivamente ineficiente.

No início dos anos 2000, os investigadores começaram a suspeitar que poderiam contornar a barreira da verificação completa “pré-processando” a base de dados. Grosso modo, isso significaria codificar todo o banco de dados como uma estrutura especial, para que o servidor pudesse responder a uma consulta lendo apenas uma pequena parte dessa estrutura. Um pré-processamento cuidadoso o suficiente poderia, em teoria, significar que um único servidor que hospeda informações só passa pelo processo uma vez, por si só, permitindo que todos os futuros usuários obtenham informações de forma privada, sem qualquer esforço adicional.

Escolha Daniel Wichs, criptógrafo da Northeastern University e coautor do novo artigo, isso parecia bom demais para ser verdade. Por volta de 2011, ele começou a tentar provar que esse tipo de esquema era impossível. “Eu estava convencido de que não havia como isso ser feito”, disse ele.

Mas em 2017, dois grupos de investigadores publicado resultados isso o fez mudar de ideia. Eles construíram os primeiros programas capazes de fazer esse tipo de recuperação de informações privadas, mas não conseguiram demonstrar que os programas eram seguros. (Os criptógrafos demonstram a segurança de um sistema mostrando que quebrá-lo é tão difícil quanto resolver algum problema difícil. Os pesquisadores não foram capazes de compará-lo a um problema difícil canônico.)

Assim, mesmo com a esperança renovada, Wichs presumiu que qualquer versão segura desses programas ainda estava muito distante. Em vez disso, ele e seus coautores - Wei Kai Lin, agora na Universidade da Virgínia, e Ethan Mook, também na Northeastern – trabalharam em problemas que consideravam mais fáceis, que envolviam casos em que vários servidores hospedavam o banco de dados.

Nos métodos que estudaram, as informações do banco de dados podem ser transformadas em uma expressão matemática, que os servidores podem avaliar para extrair as informações. Os autores perceberam que seria possível tornar esse processo de avaliação mais eficiente. Eles brincaram com uma ideia de 2011, quando outros pesquisadores encontraram uma maneira de avaliar rapidamente tal expressão, pré-processando-a, criando tabelas de valores compactas e especiais que permitem pular as etapas normais de avaliação.

Esse método não produziu nenhuma melhoria, e o grupo esteve perto de desistir – até que se perguntaram se essa ferramenta poderia realmente funcionar no cobiçado caso de servidor único. Eles perceberam que se escolhessem um polinômio com bastante cuidado, um único servidor poderia pré-processá-lo com base no resultado de 2011 – gerando o esquema de pesquisa seguro e eficiente que Wichs ponderou durante anos. De repente, eles resolveram o problema mais difícil, afinal.

A princípio, os autores não acreditaram. “Vamos descobrir o que há de errado com isso”, Wichs se lembra de ter pensado. “Continuamos tentando descobrir onde ele quebra.”

Mas a solução funcionou: eles realmente descobriram uma maneira segura de pré-processar um banco de dados de servidor único para que qualquer pessoa pudesse extrair informações em segredo. “Está realmente além de tudo que esperávamos”, disse Yuval Ishai, um criptógrafo do Technion em Israel que não esteve envolvido neste trabalho. É um resultado que “nem tivemos coragem de pedir”, disse ele.

Depois de construir seu esquema de pesquisa secreta, os autores se voltaram para o objetivo do mundo real de uma pesquisa privada na Internet, que é mais complicada do que extrair informações de um banco de dados, disse Wichs. O esquema de pesquisa privada por si só permite uma versão de pesquisa privada semelhante à do Google, mas é extremamente trabalhoso: você mesmo executa o algoritmo do Google e extrai secretamente dados da Internet quando necessário. Wichs disse que uma busca verdadeira, onde você envia uma solicitação e fica sentado enquanto o servidor coleta os resultados, é na verdade um alvo para uma abordagem mais ampla conhecida como criptografia homomórfica, que disfarça os dados para que outra pessoa possa manipulá-los sem nunca saber nada sobre eles. .

As estratégias típicas de criptografia homomórfica enfrentariam o mesmo obstáculo que a recuperação de informações privadas, percorrendo todo o conteúdo da Internet em cada pesquisa. Mas usando seu método de pesquisa privada como andaime, os autores construíram um novo esquema que executa cálculos que são mais parecidos com os programas que usamos todos os dias, extraindo informações secretamente sem varrer toda a Internet. Isso proporcionaria um aumento de eficiência para pesquisas na Internet e quaisquer programas que precisem de acesso rápido aos dados.

Embora a criptografia homomórfica seja uma extensão útil do esquema de pesquisa privada, disse Ishai, ele vê a recuperação de informações privadas como o problema mais fundamental. A solução dos autores é o “bloco de construção mágico”, e sua estratégia de criptografia homomórfica é uma continuação natural.

Por enquanto, nenhum dos esquemas é útil na prática: o pré-processamento atualmente ajuda nos extremos, quando o tamanho do banco de dados aumenta em direção ao infinito. Mas, na verdade, implementá-lo significa que essas economias não podem se materializar e que o processo consumiria muito tempo e espaço de armazenamento.

Felizmente, disse Vaikuntanathan, os criptógrafos têm um longo histórico de otimização de resultados que inicialmente eram impraticáveis. Se trabalhos futuros puderem agilizar a abordagem, ele acredita que pesquisas privadas em bancos de dados gigantes podem estar ao nosso alcance. “Todos pensávamos que estávamos presos ali”, disse ele. “O que o resultado de Daniel dá é esperança.”

Quanta está realizando uma série de pesquisas para melhor atender nosso público. Pegue nosso pesquisa com leitores de ciência da computação e você estará inscrito para ganhar de graça Quanta mercadoria.