Riepilogo Tecnico: SHARD – Cell-Keyed Residual Splitting per l'Allineamento-Resistente Private Dense Retrieval

1. Definizione del Problema

Gli embedding densi sono la base della moderna ricerca semantica e della Retrieval-Augmented Generation (RAG). Tuttavia, un vector store compromesso espone efficacemente il testo sottostante, come dimostrato da recenti attacchi che includono l'allineamento few-shot, l'inversione zero-shot e la traslazione cross-space non supervisionata. Questi attacchi sfruttano una debolezza fondamentale nelle difese leggere esistenti: il vector store protetto è una singola geometria globale.

Le difese attuali si affidano spesso a un approccio "globale-lineare": compressione degli embedding tramite troncamento SVD, applicazione di una singola rotazione ortogonale segreta e utilizzo della Product Quantization (PQ) per l'indicizzazione. Il paper sostiene che questo approccio sia fragile perché qualsiasi singola geometria globale può essere allineata a uno spazio di riferimento noto. Una volta che l'attaccante recupera la rotazione segreta (utilizzando circa $k = d/2$ coppie di testo in chiaro note tramite Orthogonal Procrustes), la protezione crolla, permettendo il recupero quasi esatto del testo. Inoltre, le difese standard affrontano un compromesso: la Differential Privacy (DP) distrugge l'utilità del ranking prima di fornire una privacy significativa, mentre la Fully Homomorphic Encryption (FHE) è troppo costosa dal punto di vista computazionale per la ricerca top-$k$ su larga scala.

2. Metodologia: La Costruzione di Shard

Il paper introduce Shard, una trasformazione di embedding che preserva il retrieval, progettata per eliminare la "debolezza dell'asse" dell'allineamento globale piuttosto che mascherare la distorsione. Shard divide lo spazio degli embedding in due componenti e applica protezioni distinte a ciascuna:

1. Prefisso Pubblico ($u$): L'embedding viene centrato e ruotato. I primi $d_{pub}$ componenti principali (direzioni ad alta varianza) formano un breve prefisso pubblico. Questo viene utilizzato per il recupero grossolano Stage-1 (ANN) tramite un indice di Product Quantization pubblico.
2. Residuo Privato ($r$): Le dimensioni rimanenti ($d_{priv} = d - d_{pub}$) formano il residuo privato.
   • Cell-Keyed Splitting: Lo spazio residuo è partizionato in $C$ celle grossolane (definite dal prefisso pubblico $u$).
     • Chiavi Locali: Ogni cella $c$ riceve una chiave ortogonale segreta unica $H_c$ (un prodotto di riflessioni di Householder).
     • Storage: Il server memorizza il prefisso $u_i$ e lo shard residuo con chiave $z_i = H_{c(i)} r_i$.
     • Elaborazione della Query:
     • Stage 1: Il client utilizza il prefisso pubblico $u_q$ per recuperare localmente una lista ristretta di candidati.
     • Stage 2 (Reranking): Per ogni candidato, il client cripta il residuo della query $r_q$ sotto CKKS (omomorfismo cifrato) come $H_{c(i)} r_q$. Il server calcola il prodotto scalare $\langle H_{c(i)} r_q, z_i \rangle$ in modalità ciphertext-plaintext.
     • Recupero Esatto: Poiché $H_c$ è ortogonale, le chiavi si annullano: $\langle H_c r_q, H_c r_i \rangle = \langle r_q, r_i \rangle$. Il server restituisce punteggi criptati che decriptano nell'esatto prodotto scalare dei residui originali.

Il parametro $C$ interpola tra il baseline globale ($C=1$, una chiave globale) e le micro-chiavi per documento ($C=N$, una chiave per documento).

3. Contributi Chiave

Il paper apporta i seguenti contributi specifici rispetto al lavoro precedente (nello specifico, il precedente sistema ibrido globale-lineare degli autori):

• Cell-Keyed Residual Splitting: Una costruzione che sostituisce una singola geometria globale con $C$ sottospazi con chiave locale, impedendo a un singolo attacco di allineamento di recuperare l'intero store.
• Reranking a Piena Dimensionalità: A differenza dei baseline di troncamento SVD che effettuano il reranking in uno spazio ridotto, Shard effettua il reranking nello spazio a dimensione intera (prefisso + residuo), recuperando la qualità del retrieval grezzo persa con il troncamento.
• Resistenza all'Allineamento Scalabile: Il paper stabilisce una legge di scala in cui il costo di un attacco di allineamento diffuso con testo in chiaro noto cresce di un fattore $\approx C$. Recuperare il frame nativo richiede $O(C \cdot d_{priv})$ anchor invece di $O(d)$.
• Riduzione della Leakage Pubblica: Esporre solo un prefisso breve ($d_{pub} \ll d$) invece di metà dello spazio riduce significativamente la fuga della struttura dei vicini.
• Valutazione Consapevole dell'Attacco: Il paper valuta Shard contro famiglie di attaccanti più forti (learned-linear, MLP non lineare e unsupervised) e lo confronta con difese basate sulla distorsione (rumore DP), dimostrando che l'uso di chiavi fornisce resistenza dove il rumore fallisce.

4. Risultati Sperimentali

Gli esperimenti sono stati condotti su embedding in cache da cinque encoder (inclusi multilingual-E5 e BGE-M3) su BEIR, MIRACL e un corpus di 1 milione di documenti di Wikipedia russa.

• Utilità (nDCG@10): Shard recupera il tetto del ranking dello spazio grezzo. Nei compiti BEIR dove il troncamento SVD causava un calo di 2–8 punti in nDCG@10, Shard ha eguagliato il baseline grezzo (es. 0.638 vs 0.637 grezzo) esponendo un canale pubblico solo da 1/4 a 1/2 della larghezza.
• Resistenza all'Allineamento:
  • Baseline Globale: Recuperato con ~200 anchor (per $d=384$).
  • Shard ($C=64$): Richiesti ~25.600 anchor.
  • Shard ($C=256$): Richiesti ~102.400 anchor (mediana).
  • Robustezza dell'Attaccante: Gli attaccanti learned-linear, non lineare MLP e unsupervised non hanno performato meglio dello standard attacco Orthogonal Procrustes; nessuno ha superato la soglia di $d_{priv}$ anchor per una singola cella.
• Leakage dell'Indice Pubblico: Il prefisso pubblico ha rivelato significativamente meno struttura di vicinato rispetto al baseline. Per un prefisso $d/4$, l'NN-overlap@10 è sceso da 0.76 (baseline) a 0.55 (Shard).
• Limite Micro-Key: Quando $C=N$ (chiavi per documento), la fuga del grafo residuo scende a 0.00 e il sistema diventa non collegabile (re-keying AUC $\approx 0.5$).
• Confronto con Rumore DP: Una difesa DP consapevole della distorsione ha eguagliato l'utilità di Shard solo a $\sigma=0$ (assenza di rumore), dove la de-anonimizzazione era del 100%. Qualsiasi rumore aggiunto per ridurre la de-anonimizzazione degradava l'utilità al di sotto delle prestazioni di Shard. Shard ha ottenuto un'alta utilità con lo 0% di de-anonimizzazione.
• Limitazioni Osservate:
  • Attacchi Mirati: Un attaccante mirato che concentra gli anchor in una specifica cella vittima ha bisogno solo di $\approx d_{priv}$ anchor, indipendentemente da $C$.
  • Riferimento di Sovrapposizione: Se un attaccante possiede un corpus di riferimento sovrapposto, il prefisso pubblico (anche se con una chiave globale singola) permette la de-anonimizzazione una volta recuperata tale chiave.
  • Pattern di Accesso: Come il baseline, Shard non nasconde i pattern di accesso (quali documenti vengono sottoposti a reranking).

5. Significato e Dichiarazioni

Il paper posiziona Shard come una difesa geometrica consapevole dell'attacco, dichiarando esplicitamente che non è una garanzia crittografica per i documenti memorizzati.

• Risultato Centrale: Shard sposta il compromesso privacy/accuratezza eliminando la vulnerabilità della "singola geometria globale". Permette un reranking esatto a dimensione intera (preservando l'utilità) rendendo al contempo l'allineamento del residuo privato computazionalmente costoso per attaccanti diffusi.
• Filosofia del Design: Il lavoro sposta la privacy degli embedding dall'ottimizzazione di un surrogato della distorsione ($\sigma_{rec}$) all'indurimento contro specifiche superfici di attacco (allineamento e leakage dell'indice).
• Dichiarazioni Modeste: Gli autori sono espliciti su ciò che Shard non fa:
  • Non protegge da attacchi mirati che si concentrano su una singola cella.
  • Non previene la de-anonimizzazione tramite corpora di riferimento sovrapposti se la chiave del prefisso pubblico viene recuperata.
  • Non nasconde i pattern di accesso.
  • La rotazione segreta è uno strato di offuscamento empirico, non un primitivo crittografico.

Il paper conclude che Shard offre una famiglia di trasformazioni regolabili (tramite il parametro $C$) che possono essere revocate a livello di cella, fornendo una difesa pratica e misurata contro i moderni attacchi di allineamento nei sistemi di dense retrieval, a condizione che il sistema sia composto con altri primitivi (come PIR) per gestire i pattern di accesso e le sovrapposizioni di riferimento.