Novas pesquisas permitem que os usuários pesquisem informações sem revelar suas dúvidas, com base em um método 30 vezes mais rápido do que as técnicas anteriores comparáveis.

Pesquisadores do MIT desenvolveram um método que permite aos usuários buscar informações em um banco de dados remoto de forma privada, sem revelar as informações que estão buscando ao servidor, cerca de 30 vezes mais rápido que outras técnicas. Créditos: Jose-Luis Olivares, MIT e iStockphoto
Pesquisar na Internet pode revelar informações que um usuário prefere manter privadas. Por exemplo, quando alguém procura sintomas médicos on-line, pode revelar suas condições de saúde ao Google, a um banco de dados médico on-line como o WebMD e talvez a centenas de anunciantes e parceiros de negócios dessas empresas.
Durante décadas, os pesquisadores criaram técnicas que permitem aos usuários pesquisar e recuperar informações de um banco de dados de forma privada, mas esses métodos permanecem muito lentos para serem usados ??efetivamente na prática.
Pesquisadores do MIT desenvolveram agora um esquema para recuperação de informações privadas que é cerca de 30 vezes mais rápido do que outros métodos comparáveis. Sua técnica permite que um usuário pesquise um banco de dados online sem revelar sua consulta ao servidor. Além disso, é conduzido por um algoritmo simples que seria mais fácil de implementar do que as abordagens mais complicadas de trabalhos anteriores.
A técnica deles pode permitir a comunicação privada, impedindo que um aplicativo de mensagens saiba o que os usuários estão dizendo ou com quem estão falando. Ele também pode ser usado para buscar anúncios online relevantes sem que os servidores de publicidade conheçam os interesses dos usuários.
“Este trabalho é realmente sobre devolver aos usuários algum controle sobre seus próprios dados. A longo prazo, gostaríamos que navegar na web fosse tão privado quanto navegar em uma biblioteca. Este trabalho ainda não alcança isso, mas começa a construir as ferramentas que nos permitem fazer esse tipo de coisa de forma rápida e eficiente na prática”, diz Alexandra Henzinger, estudante de graduação em ciência da computação e principal autora de um artigo que apresenta a técnica .
Os coautores incluem Matthew Hong, um estudante de pós-graduação em ciência da computação do MIT; Henry Corrigan-Gibbs, Professor de Desenvolvimento de Carreira Douglas Ross de Tecnologia de Software no Departamento de Engenharia Elétrica e Ciência da Computação (EECS) do MIT e membro do Laboratório de Ciência da Computação e Inteligência Artificial (CSAIL); Sarah Meiklejohn, professora de criptografia e segurança na University College London e pesquisadora do Google; e o autor sênior Vinod Vaikuntanathan, professor da EECS e pesquisador principal do CSAIL. A pesquisa será apresentada no Simpósio de Segurança USENIX de 2023.
Preservando a privacidade
Os primeiros esquemas de recuperação de informações privadas foram desenvolvidos na década de 1990, em parte por pesquisadores do MIT. Essas técnicas permitem que um usuário se comunique com um servidor remoto que contém um banco de dados e leia registros desse banco de dados sem que o servidor saiba o que o usuário está lendo.
Para preservar a privacidade, essas técnicas forçam o servidor a tocar em cada item do banco de dados, de forma que ele não saiba qual entrada o usuário está procurando. Se uma área for deixada intocada, o servidor saberá que o cliente não está interessado naquele item. Mas tocar em cada item quando pode haver milhões de entradas no banco de dados retarda o processo de consulta.
Para acelerar as coisas, os pesquisadores do MIT desenvolveram um protocolo, conhecido como Simple PIR, no qual o servidor realiza grande parte do trabalho criptográfico subjacente com antecedência, antes mesmo de um cliente enviar uma consulta. Essa etapa de pré-processamento produz uma estrutura de dados que contém informações compactadas sobre o conteúdo do banco de dados e que o cliente baixa antes de enviar uma consulta.
De certa forma, essa estrutura de dados é como uma dica para o cliente sobre o que está no banco de dados.
“Uma vez que o cliente tenha essa dica, ele pode fazer um número ilimitado de consultas, e essas consultas serão muito menores tanto no tamanho das mensagens que você está enviando quanto no trabalho que você precisa que o servidor faça. Isso é o que torna o Simple PIR muito mais rápido”, explica Henzinger.
Mas a dica pode ser relativamente grande em tamanho. Por exemplo, para consultar um banco de dados de 1 gigabyte, o cliente precisaria baixar uma dica de 124 megabytes. Isso aumenta os custos de comunicação, o que pode dificultar a implementação da técnica em dispositivos do mundo real.
Para reduzir o tamanho da dica, os pesquisadores desenvolveram uma segunda técnica, conhecida como Double PIR, que basicamente envolve executar o esquema Simple PIR duas vezes. Isso produz uma dica muito mais compacta com tamanho fixo para qualquer banco de dados.
Usando o Double PIR, a dica para um banco de dados de 1 gigabyte seria de apenas 16 megabytes.
“Nosso esquema Double PIR é um pouco mais lento, mas terá custos de comunicação muito menores. Para algumas aplicações, isso será uma compensação desejável”, diz Henzinger.
Atingindo o limite de velocidade
Eles testaram os esquemas Simple PIR e Double PIR aplicando-os a uma tarefa na qual um cliente procura auditar uma informação específica sobre um site para garantir que o site seja seguro para visitar. Para preservar a privacidade, o cliente não pode revelar o site que está auditando.
A técnica mais rápida dos pesquisadores foi capaz de preservar com sucesso a privacidade enquanto rodava a cerca de 10 gigabytes por segundo. Esquemas anteriores só conseguiam uma taxa de transferência de cerca de 300 megabytes por segundo.
Eles mostram que seu método se aproxima do limite de velocidade teórico para a recuperação de informações privadas - é quase o esquema mais rápido possível que se pode construir, no qual o servidor acessa todos os registros do banco de dados, acrescenta Corrigan-Gibbs.
Além disso, seu método requer apenas um único servidor, tornando-o muito mais simples do que muitas técnicas de alto desempenho que exigem dois servidores separados com bancos de dados idênticos. Seu método superou esses protocolos mais complexos.
“Tenho pensado nesses esquemas há algum tempo e nunca pensei que isso fosse possível nessa velocidade. O folclore era que qualquer esquema de servidor único seria muito lento. Este trabalho vira toda essa noção de cabeça para baixo”, diz Corrigan-Gibbs.
Embora os pesquisadores tenham mostrado que podem tornar os esquemas PIR muito mais rápidos, ainda há trabalho a fazer antes que eles possam implantar suas técnicas em cenários do mundo real, diz Henzinger. Eles gostariam de cortar os custos de comunicação de seus esquemas e, ao mesmo tempo, permitir que alcancem altas velocidades. Além disso, eles querem adaptar suas técnicas para lidar com consultas mais complexas, como consultas SQL gerais e aplicativos mais exigentes, como uma pesquisa geral na Wikipédia. E, a longo prazo, eles esperam desenvolver técnicas melhores que possam preservar a privacidade sem exigir que um servidor toque em todos os itens do banco de dados.
“Ouvi pessoas afirmando enfaticamente que o PIR nunca será prático. Mas eu nunca apostaria contra a tecnologia. Essa é uma lição otimista a aprender com este trabalho. Sempre há maneiras de inovar”, diz Vaikuntanathan.
“Este trabalho faz uma grande melhoria no custo prático da recuperação de informações privadas. Embora se saiba que os esquemas PIR de baixa largura de banda implicam criptografia de chave pública, que normalmente é muito mais lenta do que a criptografia de chave privada, este trabalho desenvolve um método engenhoso para preencher a lacuna. Isso é feito fazendo um uso inteligente de propriedades especiais de um esquema de criptografia de chave pública devido ao Regev para empurrar a grande maioria do trabalho computacional para uma etapa de pré-computação, na qual o servidor calcula uma pequena 'dica' sobre o banco de dados,” diz Yuval Ishai, professor de ciência da computação no Technion (Instituto de Tecnologia de Israel), que não participou do estudo. “O que torna a abordagem deles particularmente atraente é que a mesma dica pode ser usada um número ilimitado de vezes, por qualquer número de clientes.
Este trabalho é financiado, em parte, pela National Science Foundation, Google, Facebook, Fintech@CSAIL Initiative do MIT, NSF Graduate Research Fellowship, EECS Great Educators Fellowship, National Institutes of Health, Defense Advanced Research Projects Agency, the MIT-IBM Watson AI Lab, Analog Devices, Microsoft e uma bolsa de pesquisa em inovação do corpo docente da família Thornton.