A versão original de essa história apareceu em Revista Quanta.
Todos nós sabemos devemos ter cuidado com os detalhes que compartilhamos online, mas as informações que buscamos também podem ser reveladoras. 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 que preservam a 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 trabalhado 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 Prêmio de Melhor Artigo em junho de 2023 no anual Simpósio de Teoria da Computaçãoderruba 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 Vaikuntanathan, 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 é um grande banco de dados – 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 suficientemente cuidadoso 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.
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 não havia como isso ser feito”, disse ele.
