Sintesi Tecnica: Limiti Inferiori per il PIR con Preprocessing da Blackbox Cryptography

1. Definizione del Problema

Il documento investiga i limiti fondamentali del Private Information Retrieval (PIR) a server singolo nel modello di preprocessing. In questo scenario, un client esegue una fase offline per memorizzare una piccola quantità di stato ($s$ bit) riguardante un database di $n$ bit, consentendo query online più efficienti. Sebbene recenti progressi abbiano dimostrato schemi di PIR a server singolo con computazione e comunicazione delle query sublineari sfruttando il preprocessing (ad esempio, [CHK22, ZPZS24, LMW23]), i confini teorici di queste costruzioni rimangono poco chiari.

Nello specifico, gli autori affrontano se sia possibile costruire schemi di PIR a server singolo che:

1. Raggiungano una computazione online ammortizzata sublineare (specificamente $o(n/s)$).
2. Si affidino alla blackbox cryptography (modellata tramite crypto-oracoli, inclusi oracoli casuali, virtual blackbox obfuscation e gruppi multilineari generici).
3. Supportino il Symmetric PIR (SPIR) (dove il client apprende solo l'elemento interrogato) utilizzando solo funzioni unidirezionali (OWF) durante la fase online.

I precedenti limiti inferiori per il PIR con preprocessing erano limitati a classi ristrette di schemi (ad esempio, richiedenti server non-encoding, query database-oblivious o interazioni a singolo roundtrip) o si basavano su assunzioni di complessità non provate. Questo lavoro mira a fornire limiti inferiori incondizionati per una classe più ampia di schemi che fanno uso blackbox della crittografia.

2. Metodologia

Il nucleo della metodologia del documento è l'introduzione di un nuovo primitivo chiamato Dual PIR e una riduzione dal PIR standard con preprocessing a questo primitivo.

2.1 Dual Private Information Retrieval (Dual PIR)

Gli autori definiscono il Dual PIR come un'inversione del modello di preprocessing PIR standard:

• Fase di Advice: Prima che le query siano note, il client genera una stringa di advice di $t$ bit (transcript) basata sul database.
• Fase di Hint: Dato il database, un batch di $k$ indici di query e l'advice, il client genera un hint di $s$ bit.
• Ricostruzione: Utilizzando solo gli indici di query, l'advice e l'hint (ma senza accesso al database), il client deve ricostruire le voci del database interrogate.

Questa formulazione trasforma il problema dell'efficienza del PIR in un problema di compressione. Se uno schema PIR è troppo efficiente (ovvero $t = o(n)$ e $s < k$), implica l'esistenza di un Dual PIR che comprime $k$ bit di informazione in $s$ bit utilizzando solo $t$ bit di advice condivisa, il che è informazionalmente impossibile sotto certe condizioni.

2.2 Riduzione da PIR a Dual PIR

Gli autori costruiscono una riduzione dimostrando che qualsiasi schema PIR sicuro con preprocessing può essere trasformato in uno schema Dual PIR.

• Advice: Simula l'esecuzione del PIR per una query fissa per generare un transcript di comunicazione e un insieme di query al crypto-oracolo del server.
• Hint: Ri-randomizza lo stato del client per corrispondere al transcript fisso per una differente query. Fondamentalmente, per gestire la natura blackbox della crittografia, l'algoritmo di Hint campiona nuovi crypto-oracoli che sono coerenti con le query precedenti del server (utilizzando un oracolo casuale condiviso per garantire la coerenza).
• Ricostruzione: Simula la parte client della query PIR utilizzando lo stato campionato e il transcript fisso.

2.3 Connessione alla Predizione della Subkey

Per dimostrare l'impossibilità di un Dual PIR efficiente, gli autori collegano il problema alla predizione della subkey nella crittografia resistente alle perdite (leakage-resilient cryptography) ([BKR16]). Dimostrano che un Dual PIR corretto ed efficiente permetterebbe a un avversario di predire $k$ bit casuali di una chiave di $n$ bit data una perdita di $t$ bit, con una probabilità di successo superiore ai noti limiti informazionali. Nello specifico, se $t < n/2$ e $k = \Omega(s)$, la probabilità di corretta ricostruzione è limitata da $2^{s - \Omega(k)}$.

3. Contributi Chiave e Risultati

3.1 Limiti Inferiori di Computazione

Il documento stabilisce che per ogni PIR a server singolo con preprocessing del client che fa uso blackbox della crittografia:

• Teorema 1.1: È impossibile ottenere sia una comunicazione online ammortizzata $o(n/s)$ che una computazione criptografica del server ammortizzata $o(n/s)$.
• Implicazione: Qualsiasi tale schema deve soddisfare almeno uno dei seguenti punti:
  1. La comunicazione online ammortizzata è $\Omega(n/s)$ bit.
  2. Il server esegue $\Omega(n/s)$ operazioni di bit criptografiche.
• Strettezza (Tightness): Questo limite è ottimale. Gli schemi esistenti (ad esempio, [WR25]) ottengono $O(n/s)$ di comunicazione senza operazioni criptografiche del server, mentre altri (ad esempio, [ZPZS24]) ottengono $O(n/s)$ di comunicazione senza operazioni criptografiche del server ma richiedono il refresh dello stato del client. Il limite inferiore conferma che non si possono aggirare entrambi i colli di bottiglia simultaneamente.

3.2 Doubly Efficient PIR (DEPIR)

Gli autori escludono l'esistenza di Doubly Efficient PIR (dove sia il client che il server hanno tempi sublineari) costruito tramite blackbox cryptography.

• Teorema 1.2: Non esiste un DEPIR a server singolo con computazione della query sublineare ($t = o(n)$) per una singola query, anche se il server esegue un encoding arbitrario.
• Questo risultato si applica al DEPIR a chiave pubblica e migliora i precedenti risultati di impossibilità che erano limitati a query a singolo roundtrip con server passivi.

3.3 Limiti Inferiori di Comunicazione

Il documento deriva limiti inferiori di comunicazione specifici per classi ristrette di PIR:

• Teorema 1.4: Se uno schema PIR soddisfa una qualsiasi delle seguenti condizioni, richiede $\Omega(n/s)$ di comunicazione ammortizzata:
  1. Il server esegue $o(n/s)$ operazioni criptografiche.
  2. Le operazioni criptografiche del server dipendono solo dal transcript di comunicazione (uso della crittografia database-oblivious).
  3. Lo schema offre privacy perfetta in un modello idealizzato.

3.4 Symmetric PIR (SPIR)

Il documento affronta la costruzione di Symmetric PIR (SPIR) con preprocessing del client, dove il client apprende solo l'elemento interrogato.

• Costruzione (Teorema 1.5): Gli autori presentano una costruzione di SPIR con preprocessing del client che si affida solo a Funzioni Unidirezionali (OWF) durante la fase di query online. Lo schema raggiunge $\tilde{O}(n/s)$ di comunicazione e computazione, supportando $\tilde{O}(s)$ query per fase offline.
• Limitazione (Teorema 1.6): Nel modello dell'oracolo casuale, nessun tale schema SPIR può supportare più di $k > s$ query per fase offline. Ciò contrasta con il PIR non simmetrico, che può supportare query illimitate tramite il refresh dello stato. Gli autori dimostrano che supportare $k > s$ query richiede crittografia a chiave pubblica o comunicazione lineare.

3.5 Weak PIR

I limiti inferiori si estendono a schemi "weak" PIR che forniscono privacy solo contro avversari che effettuano un numero polinomiale di query all'oracolo criptografico (similmente ai Merkle puzzles).

• Teorema 1.3 & 1.5: Anche per avversari deboli, la computazione della query online sublineare è impossibile per il PIR a server singolo con preprocessing se le parti oneste e l'avversario effettuano un numero comparabile di query all'oracolo.

4. Significato e Rivendicazioni

Il documento sostiene di aver risolto la questione aperta della migliore efficienza possibile per il PIR a server singolo con preprocessing sotto assunzioni di blackbox cryptography.

• Risultati Incondizionati: A differenza del lavoro precedente (ad esempio, [ISW24]) che si basava su assunzioni di complessità (come la separazione tra SZK e BPP) o limitava il modello di query (database-oblivious, singolo roundtrip), questi limiti inferiori sono incondizionati e si applicano a una classe molto più ampia di schemi, inclusi quelli con molteplici round e query dipendenti dal database.
• Ottimalità delle Costruzioni Correnti: I risultati validano che le recenti costruzioni che ottengono $\tilde{O}(n/s)$ di comunicazione o computazione sono essenzialmente ottimali; non è possibile minimizzare simultaneamente entrambi i parametri (comunicazione e computazione del server) al di sotto di questa soglia senza violare le assunzioni di blackbox cryptography.
• Fattibilità di SPIR: Il lavoro dimostra che il Symmetric PIR è realizzabile con sole OWF nella fase online, a patto che il numero di query sia limitato alla dimensione dello stato memorizzato dal client ($s$). Ciò chiarisce il compromesso tra simmetria (privacy dei dati) e capacità di query nel modello di preprocessing.
• Impossibilità di DEPIR: Il documento esclude definitivamente l'esistenza di un DEPIR a chiave pubblica con computazione della query sublineare derivante da blackbox cryptography, risolvendo un importante problema aperto nel campo.

In sintesi, il documento stabilisce che i "colli di bottiglia" identificati nelle recenti costruzioni di PIR (ovvero l'alta comunicazione o l'alta computazione del server) sono limitazioni fondamentali intrinseche alla blackbox cryptography, e non semplici artefatti delle attuali tecniche di costruzione.