Riepilogo Tecnico: SPIDER e baseSPIDER

Enunciato del Problema

Il documento affronta la sfida di implementare il Recupero Informato Privato (PIR) in due ambienti web distinti ma critici:

1. Scalabilità per Voci di Grandi Dimensioni: I server web moderni servono oggetti massivi (immagini, video, grandi record). Gli schemi PIR a server singolo con stato esistenti soffrono spesso di fattori costanti elevati nella comunicazione e nel calcolo, che diventano proibitivi quando le voci del database ($\beta$) sono grandi.
2. Il Vincolo del Server Predefinito: La maggior parte degli schemi PIR a server singolo efficienti recenti richiede un server "cooperativo" che esegua operazioni specifiche (ad esempio, XOR degli elementi recuperati) o mantenga metadati specifici per il PIR. Tuttavia, i servizi web reali (ad esempio, Wikidata, le reti di distribuzione dei contenuti standard) sono server "predefiniti": offrono solo accesso in sola lettura basato su indici, non possono essere modificati e non forniscono API specializzate. Le soluzioni PIR esistenti non possono operare in questo contesto non cooperativo senza violare il modello di business o i vincoli tecnici del server.

Metodologia

Il documento introduce due protocolli: baseSPIDER (per server cooperativi) e SPIDER (per server predefiniti). Entrambi si basano su un client con stato che esegue una fase di pre-elaborazione una tantum per memorizzare "suggerimenti" per le query future.

1. Meccanismo Principale: Suggerimenti Basati su Multinsiemi

A differenza di lavori precedenti (ad esempio, PIANO, RMS) che partizionano il database in frammenti, baseSPIDER e SPIDER utilizzano una nuova costruzione di suggerimenti basata su multinsiemi.

• Generazione dei Suggerimenti: Durante la pre-elaborazione, il client campiona $m$ suggerimenti. Ogni suggerimento è un multinsieme di $k \approx \sqrt{n}$ indici selezionati uniformemente a caso da tutti i possibili multinsiemi di dimensione $\sqrt{n}$ sul database di dimensione $n$.
• Memorizzazione Compatta: Invece di memorizzare l'elenco completo degli indici, il client memorizza un seme a 64 bit e l'XOR precalcolato delle corrispondenti voci del database. Il seme permette la ricostruzione deterministica del multinsieme tramite una biiezione "stelle e barre".
• Proprietà di Oscuramento: L'idea chiave è che se un multinsieme scelto uniformemente ha un elemento rimosso (oscurato), il restante $(k-1)$-multinsieme è distribuito uniformemente e indipendentemente dall'elemento rimosso. Ciò garantisce che il server non possa distinguere quale elemento fosse l'obiettivo della query.

2. baseSPIDER (Server Cooperativo)

• Operazione: Il client seleziona un suggerimento contenente l'indice target $i$, lo "oscura" rimuovendo $i$ dal multinsieme e invia i restanti $k-1$ indici al server.
• Ruolo del Server: Il server calcola l'XOR delle voci a questi $k-1$ indici e restituisce un singolo valore.
• Recupero: Il client esegue l'XOR della risposta del server con il suggerimento memorizzato (che contiene l'XOR di tutte le $k$ voci) per recuperare la voce target $i$.
• Rifornimento dei Suggerimenti: Per impedire al server di inferire i modelli di accesso nel tempo, i suggerimenti utilizzati vengono scartati. Il client mantiene un pool di suggerimenti e utilizza una strategia di sostituzione (scambiando un indice utilizzato in un suggerimento sopravvissuto casuale) per mantenere la copertura senza pregiudizi.

3. SPIDER (Server Predefinito)

• Trasformazione: SPIDER adatta baseSPIDER per non richiedere calcoli lato server oltre al recupero standard.
• Operazione: Invece di chiedere al server di eseguire l'XOR delle voci, il client richiede le voci grezze corrispondenti agli indici oscurati.
• Ruolo del Client: Il client esegue l'operazione XOR localmente.
• Aggiornamento Continuo: Poiché il client scarica $k-1$ voci per query, può utilizzare queste voci grezze per costruire nuovi suggerimenti in background, consentendo query continue senza una fase di pre-elaborazione distinta e pesante.

Contributi Chiave

1. Comunicazione Ottimizzata per Voci di Grandi Dimensioni (baseSPIDER):

   • baseSPIDER raggiunge la complessità di comunicazione asintoticamente ottimale di $\tilde{O}(\sqrt{n} \cdot \beta)$ migliorando al contempo i fattori costanti.
   • Riduce la comunicazione per query da $2 \cdot \beta$ (nel più avanzato RMS-24) a esattamente $1 \cdot \beta$. Questo è un miglioramento pratico significativo per database con voci di grandi dimensioni.
   • Offre un design concettualmente più semplice rispetto ai precedenti approcci basati su frammentazione.

2. Primo PIR a Server Singolo per Server Predefiniti (SPIDER):

   • SPIDER è la prima costruzione che raggiunge la privacy PIR su un server che non esegue operazioni specifiche per il PIR e non mantiene stati specifici per il PIR.
   • Richiede solo API standard di recupero indicizzato.
   • Sebbene comporti un calcolo client più elevato (XOR di $\sqrt{n}$ voci) e un download per query più elevato ($\sqrt{n} \cdot \beta$), abilita il PIR su infrastrutture web esistenti e non modificate.

3. Trasformazione Generale:

   • Il documento dimostra che la trasformazione da un contesto cooperativo a uno di server predefinito può essere applicata ampiamente ad altri schemi PIR recenti (PIANO-23/24, RMS-24, WR-25), adattandoli al paradigma del server predefinito.

Risultati e Valutazione

• Analisi della Complessità:
  • Comunicazione: baseSPIDER raggiunge $1 \cdot \beta$ per query (amortizzato $\sqrt{n} \cdot \beta$). SPIDER raggiunge $\sqrt{n} \cdot \beta$ per query (amortizzato $\sqrt{n} \cdot \beta$).
  • Memoria: La memoria del client è $O(\sqrt{n} \cdot \log n \cdot \beta)$ per entrambi gli schemi.
  • Calcolo: Il calcolo del server è $O(\sqrt{n})$ per query (dominato dall'I/O). Il calcolo del client comporta $O(\sqrt{n})$ XOR per query in SPIDER.
• Risultati Sperimentali:
  • Nel contesto cooperativo, baseSPIDER supera RMS-24 nella latenza end-to-end, in particolare all'aumentare della dimensione della voce ($\beta$), grazie al dimezzamento del traffico di rete.
  • La latenza di ricerca dei suggerimenti (scansione lineare) è un collo di bottiglia per le voci piccole, ma diventa trascurabile rispetto alla latenza di rete e I/O per le voci grandi.
  • SPIDER è stato integrato con successo con Wikidata, dimostrando che lo schema funziona su un endpoint SPARQL reale e non cooperativo senza modificare il server.

Significato e Affermazioni

Il documento afferma che SPIDER e baseSPIDER affrontano le due principali barriere rimanenti per il deployment pratico del PIR sul web aperto:

1. Prestazioni: Migliorando i fattori costanti, baseSPIDER rende il PIR fattibile per il recupero di dati su larga scala dove la larghezza di banda è un vincolo critico.
2. Deployabilità: Rimuovendo la necessità di cooperazione del server, SPIDER abilita il recupero che preserva la privacy sul web "predefinito", dove i server sono non cooperativi e non possono essere modificati.

Gli autori notano che, sebbene SPIDER scambi la comunicazione ottimale per query con la compatibilità del server, abilita "query continue e ininterrotte" sfruttando i dati scaricati per il rifornimento dei suggerimenti. Il lavoro stabilisce che un recupero privato ad alte prestazioni è possibile anche sotto i vincoli più rigorosi del web moderno, a condizione che il client sia con stato e disposto a eseguire calcoli locali aggiuntivi.