ZipPIR: High-throughput Single-server PIR without Client-side Storage

ZipPIR è un protocollo PIR single-server ad alta velocità che elimina la necessità di archiviazione lato client comprimendo i ciphertext LWE in ciphertext Paillier più piccoli, raggiungendo prestazioni superiori a 2 GB/s e consentendo un'aggiornamento efficiente dei database dinamici senza interazione durante la fase offline.

L'essenziale

🕵️‍♂️ ZipPIR: Come chiedere un segreto senza farsi scoprire (e senza ingozzarsi di dati)

Immagina di essere in una gigantesca biblioteca (il Database) e vuoi prendere in prestito un solo libro specifico senza che il bibliotecario (il Server) sappia quale libro hai scelto. Se chiedi "Il libro X", il bibliotecario lo sa. Se chiedi "Il libro Y", lo sa anche lui.

L'obiettivo della PIR (Private Information Retrieval) è permettere al lettore di prendere il libro giusto senza che il bibliotecario capisca quale libro sia.

Il problema? Le soluzioni esistenti fino a oggi avevano due grossi difetti:

1. Erano lente: Come se il bibliotecario dovesse controllare ogni singolo libro della biblioteca uno per uno per ogni tua richiesta.
2. Richiedevano troppo spazio al lettore: Alcune soluzioni chiedevano al lettore di portare con sé una "mappa" gigante della biblioteca (un file di 100-1000 MB) che doveva essere aggiornata ogni volta che la biblioteca cambiava un libro. Chi ha uno smartphone o un browser non può permettersi di scaricare e aggiornare mappe così pesanti ogni volta.

ZipPIR è la nuova soluzione che risolve entrambi i problemi. È veloce come una Ferrari e leggera come una piuma.

---

🧩 L'Analogia della "Cassetta degli Attrezzi" vs. "Il Magazzino"

Per capire come funziona ZipPIR, immagina due scenari:

1. Il vecchio metodo (SimplePIR)

Il bibliotecario ti dà una cassetta degli attrezzi gigante (il "hint" o suggerimento) piena di chiavi, martelli e viti.

• Pro: Quando vuoi un libro, usi gli attrezzi per trovarlo velocissimamente.
• Contro: Devi portare quella cassetta pesante (128 MB) con te ovunque. Se la biblioteca cambia un libro, devi tornare a ritirare una cassetta nuova. Se hai 1000 clienti, il bibliotecario deve preparare 1000 cassette diverse. È un disastro logistico.

2. Il metodo ZipPIR

Il bibliotecario non ti dà una cassetta. Ti dà solo una piccola chiave segreta (pochi kilobyte) e una chiave pubblica (un lucchetto).

• La magia: Il bibliotecario ha un magazzino segreto (la fase "offline") dove, quando non ci sono clienti, prepara tutto il lavoro sporco.
• Il trucco: ZipPIR usa un sistema di "compressione" geniale. Immagina che il libro che vuoi sia scritto su un foglio enorme (un cifrato complesso). ZipPIR riesce a trasformare quel foglio enorme in un biglietto da visita (un cifrato piccolo) che il bibliotecario può leggere e processare velocemente.

---

⚙️ Come funziona la "Magia" (Senza termini tecnici)

ZipPIR combina due tecniche matematiche come se fossero due ingredienti in una ricetta:

1. Il Motore Potente (LWE): È come un motore a razzo. È molto sicuro e veloce per fare calcoli complessi, ma i suoi "scarichi" (i dati inviati) sono enormi e pesanti.
2. Il Compattatore (Paillier): È come un aspirapolvere industriale o un compressore per mobili. Prende oggetti grandi e li schiaccia in spazi minuscoli, ma è un po' lento a lavorare se lo fai mentre corri.

La soluzione di ZipPIR:

• Fase Offline (Il lavoro notturno): Mentre il bibliotecario è in pausa (o di notte), usa il "Compattatore" per preparare tutto il lavoro pesante. Non c'è bisogno che tu (il cliente) sia presente. Il bibliotecario prepara dei "pacchetti pronti" basati sulla tua chiave pubblica.
• Fase Online (La richiesta): Quando vuoi il libro, invii una richiesta piccolissima. Il bibliotecario prende i "pacchetti pronti" che ha già preparato e fa due semplici moltiplicazioni (come moltiplicare due numeri alla lavagna).
• Risultato: Ti risponde in un attimo, con un messaggio piccolissimo.

🚀 Perché è rivoluzionario?

Ecco i vantaggi concreti, tradotti in linguaggio umano:

• Nessun "zaino" per il cliente: Non devi scaricare mappe giganti. Il tuo telefono o il tuo browser non devono occupare spazio. La tua "memoria" richiesta è quasi nulla (meno di 200 KB, meno di una foto!).
• Velocità pazzesca: ZipPIR può processare 3 Gigabyte al secondo. È come se il bibliotecario potesse trovare il tuo libro in una biblioteca di 1 miliardo di volumi in meno di un secondo. È 10 volte più veloce delle soluzioni che non richiedono memoria al cliente.
• Aggiornamenti silenziosi: Se la biblioteca cambia un libro (aggiornamento del database), il bibliotecario aggiorna i suoi "pacchetti pronti" da solo. Non deve chiamare tutti i clienti per dire "Ehi, scaricate la nuova mappa!". Questo rende il sistema perfetto per database che cambiano spesso.
• Scalabilità: Poiché il bibliotecario fa tutto il lavoro pesante da solo, può servire milioni di clienti contemporaneamente senza che il sistema collassi.

🎯 In sintesi

ZipPIR è come avere un servizio di consegna espresso per informazioni private.
Prima, per ordinare qualcosa di segreto, dovevi portare con te un camioncino pieno di documenti (memoria del cliente) e aspettare ore (lentezza).
Con ZipPIR, porti solo un foglietto di carta (nessuna memoria), e il corriere (il server) che ha già tutto pronto nel suo magazzino, ti consegna il pacco in un batter d'occhio.

È la prima volta che un sistema basato su crittografia "vecchia scuola" (Paillier) riesce a essere più veloce e pratico di quelli moderni basati su matematica complessa, rendendo la privacy accessibile a tutti, anche sui dispositivi più piccoli.

Sommario tecnico

Ecco una sintesi tecnica dettagliata del paper "ZipPIR: High-throughput Single-server PIR without Client-side Storage" in italiano.

1. Il Problema

Il Private Information Retrieval (PIR) consente a un client di recuperare un elemento da un database senza rivelare al server quale elemento sia stato consultato. Sebbene esistano protocolli PIR ad alta velocità (come SimplePIR basati su LWE/RLWE), questi presentano limitazioni critiche per i clienti con risorse limitate (es. browser, smartphone):

• Archiviazione lato client: I protocolli ad alta velocità richiedono spesso che il client memorizzi grandi "hint" (chiavi o stati precalcolati) dipendenti dal database (es. 128 MB per SimplePIR). Questi hint devono essere aggiornati ogni volta che il database cambia, rendendo il processo costoso e impraticabile per database dinamici.
• Costi di comunicazione: Protocolli che evitano l'archiviazione lato client (come quelli basati su chiavi specifiche del client) soffrono di una bassa velocità di trasferimento (throughput), spesso inferiore a 1 GB/s, a causa del numero elevato di operazioni crittografiche.
• Inefficienza dei sistemi additivi: I protocolli che utilizzano schemi di cifratura omomorfica additiva (come Paillier) sono storicamente considerati troppo lenti per essere competitivi con quelli basati su reticoli (Lattice-based).

L'obiettivo è costruire un protocollo PIR single-server ad alta velocità che non imponga alcun onere di archiviazione al client.

2. Metodologia: ZipPIR

ZipPIR risolve il problema combinando la compressione dei ciphertext LWE con un paradigma offline/online che sposta i costi computazionali pesanti sul server durante i tempi di inattività.

A. Compressione dei Ciphertext LWE

Il cuore della proposta è una tecnica innovativa per comprimere i ciphertext basati su LWE (Learning With Errors) o RLWE in ciphertext additivi molto più piccoli (es. Paillier).

• Principio: La fase di decrittazione LWE è lineare. Il server può calcolare omomorficamente la "fase" (un valore intermedio più piccolo del ciphertext originale) utilizzando la chiave segreta LWE, ma cifrata sotto uno schema additivo (Paillier).
• Risultato: Questo riduce la dimensione del ciphertext da diversi kilobyte (es. 6.8 KB) a poche centinaia di byte (es. 768 B), con una riduzione delle dimensioni fino al 99% per batch di ciphertext.
• Chiave di compressione: Richiede una piccola chiave di compressione riutilizzabile (la chiave segreta LWE cifrata con Paillier), che è molto più piccola degli hint tradizionali.

B. Architettura Offline/Online

Per evitare che le costose operazioni di Paillier (come l'elevamento a potenza modulare) rallentino la fase online, ZipPIR le sposta nella fase offline:

1. Fase Offline (Silenziosa):
   • Il client genera una chiave pubblica Paillier e un seme crittografico.
   • Il server, durante i tempi di inattività, precalcola le componenti necessarie (hint compressi) utilizzando la chiave pubblica del client.
   • Nessuna comunicazione è richiesta tra client e server in questa fase, tranne l'invio iniziale della chiave pubblica e del seme. Il server può aggiornare gli hint in caso di modifiche al database senza interagire con il client.
2. Fase Online (Efficiente):
   • Il client invia una query composta da un vettore di selezione LWE e un "offset" (la differenza tra la chiave segreta LWE e la componente precalcolata).
   • Il server esegue due semplici moltiplicazioni matrice-vettore (una sul database, una sull'hint) usando aritmetica modulare (spesso ottimizzata con RNS - Residue Number System).
   • Il server invia la risposta compressa al client.
   • Il client decifra e ricostruisce il dato.

3. Contributi Chiave

• Primo PIR Paillier ad alte prestazioni: ZipPIR è il primo protocollo PIR che utilizza Paillier (storicamente inefficiente) e raggiunge velocità competitive con i migliori protocolli basati su reticoli (Lattice-based).
• Zero archiviazione lato client: Elimina la necessità per il client di memorizzare hint grandi e dinamici, risolvendo il problema della gestione degli aggiornamenti del database.
• Fase offline "silenziosa": Il server può generare e aggiornare gli hint per tutti i clienti in modo autonomo e silenzioso, senza richiedere interazione o risorse computazionali al client.
• Tecnica di compressione generale: La tecnica di compressione dei ciphertext LWE in ciphertext additivi è un contributo indipendente applicabile a molte altre applicazioni oltre al PIR.

4. Risultati Sperimentali

Gli autori hanno implementato ZipPIR in C++ e hanno condotto test su un database di 1 GB e 2 GB.

• Throughput: ZipPIR raggiunge un throughput di 3 GB/s per un database da 1 GB e 3.5 GB/s per 2 GB.
• Confronto:
  • È fino a 10 volte più veloce rispetto ai protocolli PIR senza archiviazione lato client esistenti (es. PIR-with-keys).
  • È fino a 2.2 volte più veloce rispetto a protocolli simili come HintlessPIR e YPIR.
  • Le prestazioni sono paragonabili a SimplePIR (che richiede 128 MB di storage lato client), ma ZipPIR non richiede tale storage.
• Storage e Comunicazione:
  • Storage lato server: Solo ~120 KB per client (per un database da 1 GB), che è molto inferiore ai megabyte richiesti da altri protocolli.
  • Storage lato client: Costante e minimo (solo la chiave privata Paillier e il seme, < 200 KB totali).
  • Comunicazione offline: Minima (circa 400 byte per l'invio iniziale della chiave pubblica e del seme).

5. Significato e Impatto

ZipPIR rappresenta un passo avanti significativo verso l'adozione pratica del PIR in scenari reali con risorse limitate:

• Scalabilità: Permette di servire un gran numero di clienti su database dinamici senza il collo di bottiglia della sincronizzazione degli hint lato client.
• Privacy e Utilità: Abilita applicazioni come la verifica di credenziali compromesse, la scoperta di contatti privati e l'audit di timestamp di certificati (SCT) senza sacrificare la privacy o richiedere capacità di storage elevate agli utenti finali.
• Sfatare i miti: Dimostra che gli schemi di cifratura additiva, se combinati strategicamente con tecniche di compressione e un'architettura offline/online, possono essere efficienti quanto le moderne tecniche basate su reticoli.

In sintesi, ZipPIR offre un compromesso ottimale tra velocità, sicurezza e requisiti di risorse, rendendo il PIR single-server una soluzione praticabile per applicazioni su larga scala.