I crittografi escogitano un approccio per la privacy totale della ricerca | Rivista Quanti

Sappiamo tutti che dobbiamo stare attenti ai dettagli che condividiamo online, ma le informazioni che cerchiamo possono anche essere rivelatrici. Cerca indicazioni stradali e la nostra posizione diventa molto più facile da indovinare. Cerca una password in una serie di dati compromessi e rischieremo di perderla noi stessi.

Queste situazioni alimentano una domanda chiave nella crittografia: come puoi estrarre informazioni da un database pubblico senza rivelare nulla su ciò a cui hai avuto accesso? È l'equivalente di prendere un libro dalla biblioteca senza che il bibliotecario sappia quale.

Elaborare una strategia che risolva questo problema, nota come recupero di informazioni private, è “un elemento molto utile in una serie di applicazioni che preservano la privacy”, ha affermato David Wu, un crittografo dell'Università del Texas, Austin. A partire dagli anni ’1990, i ricercatori hanno risolto il problema, migliorando le strategie per l’accesso privato ai database. Uno degli obiettivi principali, ancora impossibile con database di grandi dimensioni, è l’equivalente di una ricerca privata su Google, in cui è possibile vagliare un mucchio di dati in modo anonimo senza eseguire pesanti operazioni computazionali.

Ora, tre ricercatori lo hanno fatto artigianale una versione a lungo ricercata di recupero delle informazioni private e l’ha estesa per costruire una strategia di privacy più generale. L'opera, che ha ricevuto un Premio per la migliore carta nel mese di giugno all'annuale Simposio sulla teoria dell'informatica, abbatte un'importante barriera teorica sulla strada verso una ricerca veramente privata.

"[Questo è] qualcosa nella crittografia che immagino tutti noi desiderassimo ma che non credevamo del tutto che esistesse", ha detto Vinod Vaikuntanathan, un crittografo del Massachusetts Institute of Technology che non era coinvolto nell'articolo. “È un risultato fondamentale”.

Il problema dell’accesso privato ai database ha preso forma negli anni ’1990. Inizialmente, i ricercatori presumevano che l’unica soluzione fosse scansionare l’intero database durante ogni ricerca, il che sarebbe come avere un bibliotecario che fruga ogni scaffale prima di tornare con il tuo libro. Dopotutto, se la ricerca saltasse una sezione, il bibliotecario saprebbe che il tuo libro non si trova in quella parte della biblioteca.

Questo approccio funziona abbastanza bene su scala più piccola, ma man mano che il database cresce, il tempo necessario per scansionarlo aumenta almeno proporzionalmente. Mentre leggi da database più grandi – e Internet è piuttosto grande – il processo diventa proibitivamente inefficiente.

All’inizio degli anni 2000, i ricercatori iniziarono a sospettare di poter aggirare la barriera della scansione completa “preelaborando” il database. In parole povere, ciò significherebbe codificare l'intero database come una struttura speciale, in modo che il server possa rispondere a una query leggendo solo una piccola parte di quella struttura. Una preelaborazione sufficientemente attenta potrebbe, in teoria, significare che un singolo server che ospita le informazioni esegue il processo solo una volta, da solo, consentendo a tutti i futuri utenti di acquisire informazioni in privato senza ulteriori sforzi.

Nel Daniele Wichs, crittografo della Northeastern University e coautore del nuovo articolo, sembrava troppo bello per essere vero. Intorno al 2011, ha iniziato a provare a dimostrare che questo tipo di schema era impossibile. "Ero convinto che non fosse possibile farlo", ha detto.

Ma nel 2017, due gruppi di ricercatori pubblicato sul risultato questo gli ha fatto cambiare idea. Costruirono i primi programmi in grado di eseguire questo tipo di recupero di informazioni private, ma non furono in grado di dimostrare che i programmi fossero sicuri. (I crittografi dimostrano la sicurezza di un sistema dimostrando che violarlo è difficile quanto risolvere un problema difficile. I ricercatori non sono stati in grado di confrontarlo con un problema difficile canonico.)

Quindi, anche con la speranza rinnovata, Wichs presumeva che qualsiasi versione sicura di questi programmi fosse ancora molto lontana. Invece, lui e i suoi coautori — Wei-Kai Lin, ora presso l'Università della Virginia, e Ethan Mook, sempre presso la Northeastern, hanno lavorato su problemi che ritenevano sarebbero stati più semplici, che riguardavano casi in cui più server ospitavano il database.

Nei metodi studiati, le informazioni nel database possono essere trasformate in un'espressione matematica, che i server possono valutare per estrarre le informazioni. Gli autori hanno pensato che sarebbe stato possibile rendere il processo di valutazione più efficiente. Hanno giocato con un’idea del 2011, quando altri ricercatori avevano trovato un modo per valutare rapidamente un’espressione del genere preelaborandola, creando tabelle di valori speciali e compatte che consentono di saltare i normali passaggi di valutazione.

Questo metodo non ha prodotto alcun miglioramento e il gruppo è stato sul punto di arrendersi, finché non si sono chiesti se questo strumento potesse effettivamente funzionare nell’ambito caso a server singolo. Hanno visto che scegliendo un polinomio con sufficiente attenzione, un singolo server avrebbe potuto preelaborarlo in base al risultato del 2011, ottenendo lo schema di ricerca sicuro ed efficiente su cui Wichs aveva riflettuto per anni. All'improvviso, dopo tutto, avevano risolto il problema più difficile.

Inizialmente gli autori non ci credevano. "Cerchiamo cosa c'è che non va in questo", ricordava di aver pensato Wichs. "Abbiamo continuato a cercare di capire dove si rompe."

Ma la soluzione reggeva: avevano davvero scoperto un modo sicuro per preelaborare un database a server singolo in modo che chiunque potesse estrarre informazioni in segreto. "È davvero oltre tutto ciò che avevamo sperato", ha detto Yuval Ishai, un crittografo del Technion in Israele che non è stato coinvolto in questo lavoro. È un risultato che "non abbiamo nemmeno avuto il coraggio di chiedere", ha detto.

Dopo aver costruito il loro schema di ricerca segreta, gli autori si sono rivolti all'obiettivo reale di una ricerca privata su Internet, che è più complicata che estrarre informazioni da un database, ha detto Wichs. Lo schema di ricerca privata da solo consente una versione di ricerca privata simile a Google, ma è estremamente laboriosa: esegui tu stesso l'algoritmo di Google e estrai segretamente i dati da Internet quando necessario. Wichs ha affermato che una vera ricerca, in cui si invia una richiesta e ci si siede mentre il server raccoglie i risultati, è in realtà un bersaglio per un approccio più ampio noto come crittografia omomorfica, che maschera i dati in modo che qualcun altro possa manipolarli senza mai sapere nulla al riguardo. .

Le tipiche strategie di crittografia omomorfica incorrerebbero nello stesso intoppo del recupero di informazioni private, arrancando attraverso tutti i contenuti di Internet per ogni ricerca. Ma utilizzando il loro metodo di ricerca privata come impalcatura, gli autori hanno costruito un nuovo schema che esegue calcoli più simili ai programmi che usiamo ogni giorno, estraendo informazioni di nascosto senza spazzare l’intera Internet. Ciò fornirebbe un aumento di efficienza per le ricerche su Internet e per tutti i programmi che necessitano di un rapido accesso ai dati.

Sebbene la crittografia omomorfica sia un'utile estensione dello schema di ricerca privata, Ishai ha affermato di considerare il recupero delle informazioni private come il problema più fondamentale. La soluzione degli autori è il “mattone magico” e la loro strategia di crittografia omomorfa è un naturale seguito.

Per ora, nessuno dei due schemi è praticamente utile: la preelaborazione attualmente aiuta negli estremi, quando le dimensioni del database si gonfiano verso l’infinito. Ma in realtà implementarlo significa che questi risparmi non possono concretizzarsi e il processo consumerebbe troppo tempo e spazio di archiviazione.

Fortunatamente, ha detto Vaikuntanathan, i crittografi hanno una lunga storia di ottimizzazione di risultati inizialmente poco pratici. Se il lavoro futuro riuscirà a semplificare l’approccio, ritiene che le ricerche private da database giganti potrebbero essere a portata di mano. “Pensavamo tutti di essere bloccati lì”, ha detto. "Ciò che dà il risultato di Daniel è speranza."

Quanta sta conducendo una serie di sondaggi per servire meglio il nostro pubblico. Prendi il nostro Sondaggio tra i lettori di informatica e potrai partecipare alla vincita gratuita Quanta merce.