Cientistas encontram solução para um antigo problema de privacidade na internet; entenda

QUANTA MAGAZINE - Todos nós sabemos que devemos ter cuidado com os detalhes que compartilhamos online, mas as informações que buscamos também podem ser reveladoras. Pesquise direções para dirigir, e nossa localização se torna muito mais fácil de adivinhar. Se procurarmos uma senha em um conjunto de dados comprometidos, corremos o risco de vazá-la.

Essas situações alimentam uma questão fundamental na criptografia: Como é possível obter informações de um banco de dados público sem revelar nada sobre o que foi acessado? É o equivalente a retirar um livro da biblioteca sem que o bibliotecário saiba qual é o livro.

Leia também

Computação quântica: cientistas tentam entender o que tornam essas máquinas tão poderosas

A criação de uma estratégia que resolva esse problema - conhecida como recuperação de informações privadas - é “um componente muito útil em vários aplicativos de preservação da privacidade”, disse David Wu, criptógrafo da Universidade do Texas, em Austin. Desde a década de 1990, os pesquisadores têm se debruçado sobre a questão, aprimorando as estratégias de acesso privado a bancos de dados. Um dos principais objetivos, ainda impossível com grandes bancos de dados, é o equivalente a uma pesquisa privada no Google, em que você pode examinar um monte de dados anonimamente sem fazer nenhum trabalho pesado de computação.

Agora, três pesquisadores criaram uma versão há muito procurada da recuperação de informações privadas e a ampliaram para criar uma estratégia de privacidade mais geral. O trabalho, que recebeu o prêmio de melhor artigo em junho no Simpósio anual de Teoria da Computação, derrubou uma importante barreira teórica no caminho para uma pesquisa realmente privada.

“Isso é algo na criptografia que todos nós queríamos, mas não acreditávamos que existisse”, disse Vinod Vaikuntanathan, criptógrafo do Instituto de Tecnologia de Massachusetts que não participou do estudo. “É um resultado histórico.”

O problema do acesso privado a bancos de dados tomou forma na década de 1990. No início, os pesquisadores supunham que a única solução era examinar todo o banco de dados durante cada pesquisa, o que seria como pedir a um bibliotecário que vasculhasse todas as prateleiras antes de devolver seu livro. Afinal, se a pesquisa pulasse alguma seção, o bibliotecário saberia que 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 digitalizá-lo aumenta pelo menos proporcionalmente. À medida que você lê em bancos de dados maiores - e a internet é um banco de dados bastante grande - o processo se torna proibitivamente ineficiente.

No início dos anos 2000, os pesquisadores começaram a suspeitar que poderiam contornar a barreira da varredura completa “pré-processando” o banco de dados. Grosso modo, isso significaria codificar todo o banco de dados como uma estrutura especial, de modo 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 passaria pelo processo apenas uma vez, permitindo que todos os futuros usuários obtivessem informações de forma privada sem nenhum esforço adicional.

Para 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 isso não poderia ser feito de forma alguma”, disse ele.

Mas em 2017, dois grupos de pesquisadores publicaram resultados que o fizeram mudar de ideia. Eles criaram os primeiros programas que poderiam fazer esse tipo de recuperação de informações privadas, mas não conseguiram demonstrar que os programas eram seguros.

Portanto, mesmo com a esperança renovada, Wichs presumiu que qualquer versão desses programas que fosse segura ainda estava muito longe de ser desenvolvida. Em vez disso, ele e seus coautores - Wei-Kai Lin, atualmente na Universidade da Virgínia, e Ethan Mook, também na Northeastern - trabalharam em problemas que acreditavam ser 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 imaginaram que seria possível tornar esse processo de avaliação mais eficiente. Eles experimentaram com uma ideia de 2011, quando outros pesquisadores descobriram uma maneira de avaliar rapidamente essa expressão fazendo seu pré-processamento, criando tabelas especiais e compactas de valores 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 perguntou se essa ferramenta poderia realmente funcionar no cobiçado caso de um único servidor. Escolher um polinômio com bastante cuidado e um único servidor poderia pré-processá-lo com base no resultado de 2011, produzindo o esquema de pesquisa seguro e eficiente que Wichs havia ponderado durante anos. De repente, eles resolveram o problema mais difícil.

No início, os autores não acreditaram. “Vamos descobrir o que há de errado com isso”, lembra Wichs. “Ficamos tentando descobrir onde ele se rompe.”

Mas a solução foi mantida: Eles realmente haviam descoberto uma maneira segura de pré-processar um banco de dados de servidor único para que qualquer pessoa pudesse obter informações em segredo. “Isso vai muito além do que esperávamos”, disse Yuval Ishai, criptógrafo da Technion, em Israel, que não participou desse trabalho. É um resultado que “nem mesmo tivemos coragem de pedir”, disse ele.

Depois de criar seu esquema de pesquisa secreta, os autores se voltaram para o objetivo real de uma pesquisa privada na internet, que é mais complicada do que extrair bits de 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 afirma que uma pesquisa verdadeira, em que 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 para cada pesquisa. No entanto, usando seu método de pesquisa privada como suporte, os autores criaram um novo esquema que executa cálculos mais parecidos com os programas que usamos todos os dias, obtendo informações secretamente sem varrer toda a internet. Isso aumentaria a eficiência das pesquisas online e de todos os programas que precisam de acesso rápido aos dados.

Embora a criptografia homomórfica seja uma extensão útil do esquema de pesquisa privada, diz 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: No momento, o pré-processamento ajuda nos extremos, quando o tamanho do banco de dados se aproxima do infinito. Mas, ao implementá-lo de fato, essas economias não se concretizam, e 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 no futuro o trabalho puder simplificar a abordagem, ele acredita que as pesquisas privadas em bancos de dados gigantes podem estar ao alcance. “Todos nós pensamos que estávamos meio que presos a isso”, disse ele. “O que o resultado de Daniel nos dá esperança.”

História original republicada com permissão da Quanta Magazine, uma publicação editorialmente independente apoiada pela Simons Foundation. Leia o conteúdo original em “Cryptographers Solve Decades-Old Privacy Problem”.