Resumo Técnico: Um Benchmark Unificado para Busca Vetorial com Preservação de Privacidade

1. Declaração do Problema

A busca vetorial é uma infraestrutura fundamental para busca semântica, sistemas de recomendação e Geração Aumentada de Recuperação (RAG). No entanto, as implementações padrão carecem de privacidade: o provedor de serviço observa tanto os embeddings da consulta quanto os embeddings do corpus. Essa exposição cria riscos signific verdadeiros de privacidade, incluindo o potencial para ataques de "inversão de embedding", onde um atacante pode reconstruir o texto original ou dados sensíveis (ex: registros médicos) a partir de embeddings densos, mesmo sem acesso aos pesos internos do modelo.

Embora existam esquemas criptográficos para mitigar esse vazamento (ex: SAP, EMVP, BNTM, Tiptoe), eles têm sido historicamente avaliados de forma isolada. Cada estudo utiliza diferentes corpora, modelos de embedding, configurações de hardware, modelos de ameaça e definições de métricas. Consequentemente, os profissionais carecem de uma base defensável para escolher um esquema, pois os números de desempenho não são diretamente comparáveis. O problema central abordado é a ausência de um benchmark unificado para avaliar as trocas entre garantias de privacidade, desempenho (throughput/latência) e precisão de recuperação entre esses esquemas.

2. Metodologia

Os autores construíram um harness experimental único e uniforme para comparar cinco esquemas: uma linha de base em Texto Simples (Plaintext) e quatro mecanismos de preservação de privacidade (SAP, EMVP, BNTM e Tiptoe).

Configuração Experimental

• Corpus & Carga de Trabalho: O benchmark utiliza a coleção de passagens MS MARCO (8,8 milhões de passagens) e um subconjunto de 100 mil. As consultas são geradas a partir do conjunto de dados MS MARCO usando o modelo de embedding E5-base-v2 (768 dimensões).
• Indexação: Para garantir a comparabilidade, todos os esquemas utilizam um índice Inverted File (IVF) compartilhado com agrupamento k-means. Isso evita a incompatibilidade de índices baseados em grafos (como HNSW) com esquemas de criptografia de ponta a ponta.
• Hardware: Os experimentos rodam em um Intel Xeon Gold 6426Y de dois sockets (64 núcleos lógicos) com 128 GB de RAM e uma NVIDIA RTX 5000 Ada GPU (32 GB de VRAM).
• Métricas: O desempenho é medido via throughput (consultas/seg), latência de ponta a ponta, recall@10, custo de comunicação (configuração, online, offline) e uso de largura de banda de memória.
• Parâmetros de Segurança: Todos os esquemas criptográficos são configurados para segurança de 128 bits. O SAP usa um parâmetro de perturbação $\beta$ para ajustar a privacidade vs. o recall.

Os Esquemas Comparados

1. Plaintext (Texto Simples): Linha de base não criptografada.
2. SAP (Symmetric Additive Perturbation): Utiliza criptografia que preserva a comparação de distância. O cliente perturba os vetores antes do upload. O servidor compara as distâncias diretamente nos criptogramas. Ele esconde os valores exatos dos vetores, mas revela a geometria do corpus (distâncias relativas).
3. EMVP: Criptografa os vetores em uma matriz. O servidor computa produtos matriz-vetor (matvec) criptografados para os clusters roteados. Ele fornece indistinguibilidade computacional (esconde a consulta e o corpus), mas revela o cluster acessado.
4. BNTM: Semelhante ao EMVP, mas baseia-se na suposição de Learning Parity with Noise (LPN). Adiciona verificabilidade de servidor malicioso, permitindo que o cliente verifique a correção da resposta do servidor usando o algoritmo de Freivalds.
5. Tiptoe: Utiliza Recuperação de Informação Privada (PIR) sobre todo o corpus. O servidor realiza um matvec sobre todo o banco de dados, escondendo o padrão de acesso ao cluster específico pela consulta. Oferece a privacidade mais forte (escondendo padrões de acesso), mas incorre no maior custo computacional.

3. Contribuições Principais

1. Harness de Avaliação Unificado: Os autores construíram um único framework de software que isola a primitiva criptográfica do restante do pipeline, garantindo que as diferenças de desempenho derivem apenas das especificações do esquema, e não de artefatos de implementação.
2. Benchmarking Abrangente: O estudo avalia os esquemas através de múltiplas dimensões: trocas de recall-throughput, desempenho de CPU vs. GPU, custos de comunicação (configuração, online, offline), requisitos de largura de banda de memória e tempos de construção de índice.
3. Reprodutibilidade: Todos os artefatos experimentais, medições brutas e código são liberados publicamente para garantir transparência.

4. Resultados Principais

Trocas entre Desempenho e Privacidade

• SAP: Alcança um desempenho quase idêntico à linha de base de Texto Simples (overhead negligenciável), mas fornece apenas privacidade de "instantâneo"; o servidor ainda pode inferir a geometria relativa do corpus.
• EMVP: Fornece forte indistinguibilidade criptográfica (escondendo tanto a consulta quanto o corpus), mas incorre em uma penalidade de throughput de 4× em comparação ao Texto Simples na CPU.
• BNTM: Adiciona verificabilidade de servidor malicioso às garantias do EMVP. Isso introduz um custo de latência mediana de 22× adicional em relação ao Texto Simples (ou aproximadamente 22× mais lento que o EMVP em alguns contextos, embora o resumo note um custo de 22× sobre o Texto Simples).
• Tiptoe: Esconde totalmente o padrão de acesso ao cluster. No entanto, é proibitivamente lento, incorrendo em um custo de 190× por consulta em comparação ao Texto Simples em um subconjunto de 100k. Seu recall também é significativamente menor devido à quantização e à restrição de pesquisar apenas um cluster por consulta.

Aceleração de Hardware (GPU)

• Texto Simples e SAP: Beneficiam-se significativamente da aceleração por GPU (aceleração de 1,8–1,9×) porque suas operações de pontuação são limitadas por computação (compute-bound) e paralelizáveis.
• EMVP e BNTM: Não se beneficiam de GPUs; de fato, o EMVP performa pior em GPU. Esses esquemas são limitados pela largura de banda de memória (memory-bandwidth bound). As matrizes criptografadas são grandes demais para caber na memória da GPU (ex: 91 GB para o corpus de 8,8M para o EMVP), forçando os dados a fluírem pelo barramento PCIe, o que anula as vantagens de computação da GPU.
• Tiptoe: Não foi avaliado em GPU neste benchmark devido a restrições arquiteturais.

Comunicação e Memória

• Rede vs. Memória: Os esquemas ranqueiam de forma diferente dependendo da métrica. O BNTM tem o menor tráfego de rede (tamanho de resposta pequeno), mas exige a leitura de quantidades massivas de dados da memória do servidor (comparável ao EMVP).
• Detalhamento de Latência:
  • Texto Simples/SAP são limitados pelo processamento do servidor (server-compute bound).
  • EMVP e BNTM são limitados pela decodificação do cliente (client-side decode bound) (decodificação de respostas criptografadas).
  • Tiptoe é limitado pela descompressão de resposta (response decompression bound) (descriptografia de resultados de PIR).

Tempo de Construção do Índice

Os tempos de construção do índice são relativamente comparáveis (dentro de uma banda de 2,5×), dominados pela etapa de agrupamento k-means (10,5s para 100k). Os overheads de criptografia para EMVP e Tiptoe adicionam cerca de 10–15 segundos ao tempo de construção.

5. Significância e Alegações

O artigo desafia a crença predominante de que a privacidade criptográfica para busca vetorial é "inacessível". Os autores demonstram que:

• A privacidade não é uma penalidade plana: Existem esquemas em uma fronteira de Pareto. Profissionais podem escolher um nível de privacidade (ex: esconder apenas a consulta vs. esconder padrões de acesso) com um custo correspondente e quantificável.
• A implementação importa: O desempenho de um esquema depende fortemente de detalhes de implementação, particularmente padrões de acesso à memória. Um esquema com baixo tráfego de rede (como o BNTM) pode ainda ser lento devido aos altos requisitos de largura de banda de memória, o que também dita a adequação à GPU.
• Orientação Acionável: Os resultados fornecem "pontos de ação" concretos para profissionais:
  • Use SAP se não for necessário esconder a geometria do corpus, mas os valores dos vetores precisarem ser protegidos (custo quase zero).
  • Use EMVP se for necessária a criptografia total da consulta e do corpus (custo de 4×).
  • Use BNTM se a honestidade do servidor não puder ser assumida (adiciona custo de verificação).
  • Use Tiptoe apenas se esconder o padrão de acesso (qual cluster é consultado) for crítico, aceitando penalidades massivas de latência.

O trabalho conclui que, embora a privacidade tenha um custo, ela não é uma barreira intransponível, e a escolha do esquema deve ser impulsionada por modelos de ameaça específicos e restrições de hardware, em vez de uma suposição generalizada de inviabilidade.