Resumo Técnico: SHARD – Divisão de Resíduos com Chave por Célula para Alinhamento Resistente em Recuperação Densa Privada

1. Declaração do Problema

Embeddings densos são a base da recuperação semântica moderna e da Geração Aumentada por Recuperação (RAG). No entanto, um repositório de vetores vazado compromete efetivamente o texto subjacente, como demonstrado por ataques recentes, incluindo alinhamento de poucos disparos (few-shot alignment), inversão de zero disparos (zero-shot inversion) e tradução de espaço cruzado não supervisionada. Esses ataques exploram uma fraqueza fundamental nas defesas leves existentes: o repositório de vetores protegido é uma geometria global única.

As defesas atuais frequentemente dependem de uma abordagem "global-linear": comprimir embeddings via truncamento SVD, aplicar uma única rotação ortogonal secreta e usar Quantização de Produto (PQ) para indexação. O artigo argumenta que essa abordagem é frágil porque qualquer geometria global pode ser alinhada a um espaço de referência conhecido. Uma vez que o atacante recupera a rotação secreta (usando aproximadamente $k = d/2$ pares de texto plano conhecidos via Procrustes Ortogonal), a proteção colapsa, permitindo a recuperação quase exata do texto. Além disso, as defesas padrão enfrentam um compromisso (trade-off): a Privacidade Diferencial (DP) destrói a utilidade de classificação antes de fornecer privacidade significativa, enquanto a Criptografia Totalmente Homomórfica (FHE) é computacionalmente cara demais para busca top-$k$ em larga escala.

2. Metodologia: A Construção do Shard

O artigo introduz o Shard, uma transformação de embedding que preserva a recuperação, projetada para eliminar a "fraqueza do eixo" da geometria global em vez de apenas mascarar a distorção. O Shard divide o espaço de embedding em dois componentes e aplica proteções distintas a cada um:

1. Prefixo Público ($u$): O embedding é centralizado e rotacionado. Os $d_{pub}$ principais componentes (direções de alta variância) formam um prefixo público curto. Este é usado para a recuperação de Estágio 1 (ANN) via um índice de Quantização de Produto público.
2. Resíduo Privado ($r$): As dimensões restantes ($d_{priv} = d - d_{pub}$) formam o resíduo privado.
   • Divisão por Chave de Célula (Cell-Keyed Splitting): O espaço residual é particionado em $C$ células grosseiras (definidas pelo prefixo público $u$).
   • Chaves Locais: Cada célula $c$ recebe uma chave ortogonal secreta $H_c$ única (um produto de reflexões de Householder).
   • Armazenamento: O servidor armazena o prefixo $u_i$ e o fragmento de resíduo com chave $z_i = H_{c(i)} r_i$.
   • Processamento de Consulta:
     • Estágio 1: O cliente usa o prefixo público $u_q$ para recuperar uma lista curta de candidatos localmente.
     • Estágio 2 (Reclassificação/Reranking): Para cada candidato, o cliente criptografa o resíduo da consulta $r_q$ sob CKKS (criptografia homomórfica) como $H_{c(i)} r_q$. O servidor calcula o produto interno $\langle H_{c(i)} r_q, z_i \rangle$ no modo texto cifrado-texto plano.
     • Recuperação Exata: Como $H_c$ é ortogonal, as chaves se cancelam: $\langle H_c r_q, H_c r_i \rangle = \langle r_q, r_i \rangle$. O servidor retorna pontuações criptografadas que decifram para o produto interno exato dos resíduos originais.

O parâmetro $C$ interpola entre a linha de base global ($C=1$, uma chave global) e micro-chaves por documento ($C=N$, uma chave por documento).

3. Principais Contribuições

O artigo apresenta as seguintes contribuições específicas em relação ao trabalho anterior (especificamente o sistema híbrido global-linear dos autores):

• Divisão de Resíduo com Chave por Célula: Uma construção que substitui uma geometria global única por $C$ subespaços com chaves locais, impedindo que um único ataque de alinhamento recupere todo o repositório.
• Reclassificação de Dimensão Total: Ao contrário das linhas de base de truncamento SVD que reclassificam em um espaço reduzido, o Shard reclassifica no espaço de dimensão total (prefixo + resíduo), recuperando a qualidade de recuperação bruta perdida pela truncagem.
• Resistência de Alinhamento Escalável: O artigo estabelece uma lei de escala onde o custo de um ataque de alinhamento de texto plano conhecido difuso cresce por um fator de $\approx C$. Recuperar o quadro nativo requer $O(C \cdot d_{priv})$ âncoras em vez de $O(d)$.

0. Redução de Vazamento Público: Ao expor apenas um prefixo curto ($d_{pub} \ll d$), o índice público vaza significativamente menos estrutura de vizinhança.

• Avaliação Consciente de Ataques: O artigo avalia o Shard contra famílias de atacantes mais fortes (linear aprendido, MLP não linear e não supervisionado) e o compara com defesas de distorção (ruído DP), demonstrando que o uso de chaves fornece resistência onde o ruído falha.

4. Resultados Experimentais

Experimentos foram conduzidos em embeddings em cache de cinco codificadores (incluindo multilingual-E5 e BGE-M3) através de BEIR, MIRACL e um corpus de 1 milhão de documentos da Wikipedia russa.

• Utilidade (nDCG@10): O Shard recupera o teto de classificação do espaço bruto. Em tarefas BEIR onde o truncamento SVD causou uma queda de 2 a 8 pontos no nDCG@10, o Shard igualou a linha de base bruta (ex: 0,638 vs 0,637 bruto) enquanto expunha um canal público de apenas 1/4 a 1/2 da largura.
• Resistência de Alinhamento:
  • Linha de Base Global: Recuperada com ~200 âncoras (para $d=384$).
  • Shard ($C=64$): Requeriu ~25.600 âncoras.
  • Shard ($C=256$): Requeriu ~102.400 âncoras (mediana).
  • Robustez do Atacante: Atacantes lineares aprendidos, MLP não linear e não supervisionados não tiveram desempenho melhor que o ataque padrão de Procrustes Ortogonal; nenhum superou o limiar de âncoras $d_{priv}$ para uma única célula.
• Vazamento de Índice Público: O prefixo público revelou significativamente menos estrutura de vizinhança do que a linha de base. Para um prefixo $d/4$, o NN-overlap@10 caiu de 0,76 (linha de base) para 0,55 (Shard).
• Limite de Micro-Chave: Quando $C=N$ (chaves por documento), o vazamento do grafo residual cai para 0,00, e o sistema torna-se inlinkável (AUC de re-chaveamento $\approx 0,5$).
• Comparação com Ruído DP: Uma defesa de distorção consciente de DP igualou a utilidade do Shard apenas em $\sigma=0$ (sem ruído), onde a desanonimização era de 100%. Qualquer ruído adicionado para reduzir a desanonimização degradou a utilidade abaixo do desempenho do Shard. O Shard alcançou alta utilidade com 0% de desanonimização.
• Limitações Observadas:
  • Ataques Direcionados: Um atacante direcionado concentrando âncoras em uma célula específica de uma vítima precisa de apenas $\approx d_{priv}$ âncoras, independentemente de $C$.
  • Referência de Sobreposição: Se um atacante possuir um corpus de referência sobreposto, o prefixo público (mesmo que chaveado com uma única chave global) permite a desanonimização uma vez que essa chave seja recuperada.
  • Padrões de Acesso: Como a linha de base, o Shard não esconde os padrões de acesso (quais documentos estão sendo reclassificados).

5. Significância e Alegações

O artigo posiciona o Shard como uma defesa geométrica consciente de ataques, afirmando explicitamente que ele não é uma garantia criptográfica para os documentos armazenados.

• Conquista Central: O Shard altera o compromisso entre privacidade/precisão ao remover a vulnerabilidade de "geometria global única". Ele permite a reclassificação exata de dimensão total (preservando a utilidade) enquanto torna o alinhamento do resíduo privado computacionalmente caro para atacantes difusos.
• Filosofia de Design: O trabalho move a privacidade de embedding da otimização contra um substituto de distorção ($\sigma_{rec}$) para o endurecimento contra superfícies de ataque específicas (alinhamento e vazamento de índice).
• Alegações Modestas: Os autores são explícitos sobre o que o Shard não faz:
  • Não protege contra ataques direcionados que concentram âncoras em uma única célula.
  • Não evita a desanonimização via corpora de referência sobrepostos se a chave do prefixo público for recuperada.
  • Não esconde padrões de acesso.
  • A rotação secreta é uma camada de obscuridade empírica, não um primitivo criptográfico.

O artigo conclui que o Shard oferece uma família ajustável de transformações (via parâmetro $C$) que podem ser revogadas ao nível da célula, fornecendo uma defesa prática e mensurada contra ataques de alinhamento modernos em sistemas de recuperação densa, desde que o sistema seja composto com outros primitivos (como PIR) para lidar com padrões de acesso e sobreposições de referência.