Criptografii concepe o abordare pentru confidențialitatea totală a căutării | Revista Quanta

Știm cu toții să fim atenți la detaliile pe care le distribuim online, dar informațiile pe care le căutăm pot fi și revelatoare. Căutați indicații de orientare și locația noastră devine mult mai ușor de ghicit. Verificați o parolă într-un tez de date compromise și riscăm să o scurgem singuri.

Aceste situații alimentează o întrebare cheie în criptografie: cum poți extrage informații dintr-o bază de date publică fără a dezvălui nimic despre ceea ce ai accesat? Este echivalentul cu a verifica o carte din bibliotecă fără ca bibliotecarul să știe care.

Conceperea unei strategii care să rezolve această problemă – cunoscută sub numele de regăsire a informațiilor private – este „un element de construcție foarte util într-o serie de aplicații de păstrare a confidențialității”, a spus David Wu, criptograf la Universitatea din Texas, Austin. Începând cu anii 1990, cercetătorii au renunțat la întrebare, îmbunătățind strategiile pentru accesarea privată a bazelor de date. Un obiectiv major, încă imposibil cu bazele de date mari, este echivalentul unei căutări private pe Google, în care puteți trece printr-o grămadă de date în mod anonim, fără a face nicio calculă grea.

Acum, trei cercetători au făcut-o fabricat o versiune mult căutată de regăsire a informațiilor private și a extins-o pentru a construi o strategie de confidențialitate mai generală. Lucrarea, care a primit un Premiul pentru cea mai bună hârtie în iunie la anual Simpozion de Teoria Calculului, răstoarnă o barieră teoretică majoră în drumul către o căutare cu adevărat privată.

„[Acesta este] ceva în criptografie pe care cred că ne-am dorit cu toții, dar nu prea credeam că există”, a spus Vinod Vaikuntanathan, un criptograf la Institutul de Tehnologie din Massachusetts care nu a fost implicat în lucrare. „Este un rezultat de referință.”

Problema accesului la bazele de date private a luat contur în anii 1990. La început, cercetătorii au presupus că singura soluție a fost să scaneze întreaga bază de date în timpul fiecărei căutări, ceea ce ar fi ca și cum ar fi un bibliotecar să parcurgă fiecare raft înainte de a se întoarce cu cartea. La urma urmei, dacă căutarea a omis orice secțiune, bibliotecarul ar ști că cartea ta nu se află în acea parte a bibliotecii.

Această abordare funcționează suficient de bine la scari mai mici, dar pe măsură ce baza de date crește, timpul necesar scanării crește cel puțin proporțional. Pe măsură ce citiți din baze de date mai mari - și internetul este unul destul de mare - procesul devine prohibitiv de ineficient.

La începutul anilor 2000, cercetătorii au început să suspecteze că ar putea ocoli bariera de scanare completă „preprocesând” baza de date. Aproximativ, aceasta ar însemna codificarea întregii baze de date ca o structură specială, astfel încât serverul să poată răspunde la o interogare citind doar o mică parte a acelei structuri. O preprocesare suficient de atentă ar putea, teoretic, să însemne că un singur server care găzduiește informațiile parcurge procesul o singură dată, de la sine, permițând tuturor viitorilor utilizatori să obțină informații în mod privat, fără mai mult efort.

Pentru Daniel Wichs, criptograf la Universitatea Northeastern și co-autor al noii lucrări, asta părea prea frumos pentru a fi adevărat. În jurul anului 2011, a început să încerce să demonstreze că acest gen de schemă era imposibil. „Eram convins că nu se poate face acest lucru”, a spus el.

Dar în 2017, două grupuri de cercetători publicat rezultate obținute asta i-a schimbat parerea. Ei au construit primele programe care ar putea face acest tip de recuperare a informațiilor private, dar nu au putut să arate că programele sunt sigure. (Criptografii demonstrează securitatea unui sistem arătând că distrugerea acestuia este la fel de dificilă ca și rezolvarea unei probleme dificile. Cercetătorii nu au reușit să o compare cu o problemă dificilă canonică.)

Deci, chiar și cu speranța reînnoită, Wichs a presupus că orice versiune a acestor programe care era sigură era încă departe. În schimb, el și coautorii săi - Wei-Kai Lin, acum la Universitatea din Virginia și Ethan Mook, tot la Northeastern — a lucrat la probleme pe care le credeau că ar fi mai ușoare, ceea ce a implicat cazuri în care mai multe servere găzduiesc baza de date.

În metodele pe care le-au studiat, informațiile din baza de date pot fi transformate într-o expresie matematică, pe care serverele o pot evalua pentru a extrage informația. Autorii s-au gândit că ar putea fi posibil ca procesul de evaluare să fie mai eficient. S-au jucat cu o idee din 2011, când alți cercetători au găsit o modalitate de a evalua rapid o astfel de expresie prin preprocesarea ei, creând tabele de valori speciale, compacte, care vă permit să săriți peste pașii normali de evaluare.

Metoda respectivă nu a produs nicio îmbunătățire, iar grupul a fost aproape de a renunța – până când s-au întrebat dacă acest instrument ar putea funcționa într-adevăr în râvnitul caz cu un singur server. Ei au văzut că alegeți un polinom suficient de atent și un singur server l-ar putea preprocesa pe baza rezultatului din 2011 - obținând schema de căutare sigură și eficientă pe care a gândit-o ani de zile. Deodată, rezolvaseră problema mai grea, până la urmă.

La început, autorii nu au crezut. „Să ne dăm seama ce e în neregulă cu asta”, își amintea că se gândise Wichs. „Am tot încercat să ne dăm seama unde se defectează.”

Dar soluția a rămas: ei au descoperit într-adevăr o modalitate sigură de a preprocesa o bază de date cu un singur server, astfel încât oricine să poată extrage informații în secret. „Este cu adevărat dincolo de tot ceea ce am sperat”, a spus Yuval Ishai, un criptograf la Technion din Israel care nu a fost implicat în această lucrare. Este un rezultat „nu am fost nici măcar îndeajuns de curajoși să-l cerem”, a spus el.

După ce și-au construit schema secretă de căutare, autorii s-au orientat către obiectivul real al unei căutări private pe internet, care este mai complicată decât extragerea unor fragmente de informații dintr-o bază de date, a spus Wichs. Schema de căutare privată în sine permite o versiune a căutării private asemănătoare Google, dar este extrem de laborioasă: rulați singur algoritmul Google și extrageți în secret date de pe internet atunci când este necesar. Wichs a spus că o căutare adevărată, în care trimiți o solicitare și stai pe loc în timp ce serverul colectează rezultatele, este într-adevăr o țintă pentru o abordare mai largă cunoscută sub numele de criptare homomorfă, care maschează datele astfel încât altcineva să le poată manipula fără să știe vreodată nimic despre asta. .

Strategiile obișnuite de criptare homomorfă s-ar atinge de aceeași problemă ca și regăsirea informațiilor private, parcurgând tot conținutul internetului pentru fiecare căutare. Dar folosind metoda lor de căutare privată ca schelă, autorii au construit o nouă schemă care rulează calcule care seamănă mai mult cu programele pe care le folosim în fiecare zi, trăgând informații pe ascuns fără a mătura întregul internet. Acest lucru ar oferi un spor de eficiență pentru căutările pe internet și pentru orice program care necesită acces rapid la date.

În timp ce criptarea homomorfă este o extensie utilă a schemei de căutare privată, a spus Ishai, el consideră că recuperarea informațiilor private este problema fundamentală. Soluția autorilor este „blocul de construcție magic”, iar strategia lor de criptare homomorfă este o continuare naturală.

Deocamdată, nicio schemă nu este practic utilă: preprocesarea ajută în prezent la extreme, când dimensiunea bazei de date se ridică spre infinit. Dar implementarea efectivă înseamnă că aceste economii nu se pot materializa, iar procesul ar consuma prea mult timp și spațiu de stocare.

Din fericire, a spus Vaikuntanathan, criptografii au o istorie lungă de optimizare a rezultatelor care au fost inițial nepractice. Dacă lucrările viitoare pot eficientiza abordarea, el crede că căutările private din baze de date gigantice pot fi la îndemână. „Toți am crezut că suntem oarecum blocați acolo”, a spus el. „Ceea ce dă rezultatul lui Daniel este speranță.”

Cuante efectuează o serie de sondaje pentru a servi mai bine publicul nostru. Ia-ne sondaj cititor de informatică și vei fi înscris pentru a câștiga gratuit Cuante mărfuri.