Kryptografer udtænker en tilgang til total søgebeskyttelse | Quanta Magasinet

Vi ved alle, at vi skal være forsigtige med de detaljer, vi deler online, men den information, vi søger, kan også være afslørende. Søg efter kørselsvejledninger, og vores placering bliver langt nemmere at gætte. Tjek efter en adgangskode i et væld af kompromitterede data, og vi risikerer selv at lække det.

Disse situationer giver anledning til et nøglespørgsmål inden for kryptografi: Hvordan kan du trække information fra en offentlig database uden at afsløre noget om, hvad du har tilgået? Det svarer til at tjekke en bog ud på biblioteket, uden at bibliotekaren ved hvilken.

At sammensætte en strategi, der løser dette problem - kendt som privat informationssøgning - er "en meget nyttig byggesten i en række applikationer til beskyttelse af privatlivets fred," sagde David Wu, en kryptograf ved University of Texas, Austin. Siden 1990'erne har forskere smidt spørgsmålet væk og forbedret strategier for privat adgang til databaser. Et stort mål, som stadig er umuligt med store databaser, svarer til en privat Google-søgning, hvor du anonymt kan gennemsøge en bunke data uden at foretage tunge beregninger.

Nu har tre forskere udformet en længe søgt version af privat informationssøgning og udvidet den til at bygge en mere generel privatlivsstrategi. Værket, som fik en Pris for bedste papir i juni på det årlige Symposium om teori om computing, vælter en stor teoretisk barriere på vej til en virkelig privat eftersøgning.

"[Dette er] noget inden for kryptografi, som jeg formoder, at vi alle ville have, men som ikke helt troede på, at det eksisterede," sagde Vinod Vaikuntanathan, en kryptograf ved Massachusetts Institute of Technology, som ikke var involveret i papiret. "Det er et skelsættende resultat."

Problemet med adgang til privat database tog form i 1990'erne. Først antog forskerne, at den eneste løsning var at scanne hele databasen under hver søgning, hvilket ville være som at få en bibliotekar til at gennemsøge hver hylde, før han vendte tilbage med din bog. Når alt kommer til alt, hvis søgningen sprunget over et afsnit, ville bibliotekaren vide, at din bog ikke er i den del af biblioteket.

Den tilgang fungerer godt nok i mindre skalaer, men efterhånden som databasen vokser, vokser den tid, det tager at scanne den i det mindste proportionalt. Når du læser fra større databaser - og internettet er en ret stor - bliver processen uoverkommelig ineffektiv.

I begyndelsen af ​​2000'erne begyndte forskere at mistænke, at de kunne undvige fuld-scanningsbarrieren ved at "forbehandle" databasen. Det ville groft sagt betyde indkodning af hele databasen som en speciel struktur, så serveren kunne besvare en forespørgsel ved kun at læse en lille del af den struktur. Omhyggelig nok forbehandling kan i teorien betyde, at en enkelt server-hosting-information kun går igennem processen én gang, af sig selv, hvilket giver alle fremtidige brugere mulighed for at få fat i information privat uden yderligere besvær.

Til Daniel Wichs, en kryptograf ved Northeastern University og en medforfatter af det nye papir, der virkede for godt til at være sandt. Omkring 2011 begyndte han at forsøge at bevise, at denne form for ordning var umulig. "Jeg var overbevist om, at der ikke er nogen måde, at dette kunne lade sig gøre," sagde han.

Men i 2017 to grupper af forskere offentliggjort resultater det ændrede hans mening. De byggede de første programmer, der kunne gøre denne form for privat informationssøgning, men de var ikke i stand til at vise, at programmerne var sikre. (Kryptografer demonstrerer et systems sikkerhed ved at vise, at det at bryde det er lige så svært som at løse et eller andet hårdt problem. Forskerne var ikke i stand til at sammenligne det med et kanonisk hårdt problem.)

Så selv med håbet fornyet, antog Wichs, at enhver version af disse programmer, der var sikker, stadig var langt væk. I stedet, han og hans medforfattere - Wei-Kai Lin, nu ved University of Virginia, og Ethan Mook, også hos Northeastern - arbejdede på problemer, de troede ville være nemmere, hvilket involverede tilfælde, hvor flere servere hoster databasen.

I de metoder, de har undersøgt, kan informationen i databasen transformeres til et matematisk udtryk, som serverne kan evaluere for at udtrække informationen. Forfatterne regnede med, at det kunne være muligt at gøre denne evalueringsproces mere effektiv. De legede med en idé fra 2011, hvor andre forskere havde fundet en måde, hvorpå de hurtigt kunne evaluere et sådant udtryk ved at forbehandle det og lave specielle, kompakte værditabeller, der giver dig mulighed for at springe de normale evalueringstrin over.

Den metode gav ingen forbedringer, og gruppen var tæt på at give op - indtil de spekulerede på, om dette værktøj faktisk kunne fungere i den eftertragtede enkeltserver-case. Vælg et polynomium omhyggeligt nok, så de, og en enkelt server kunne forbehandle det baseret på 2011-resultatet - hvilket gav det sikre, effektive opslagsskema, Wichs havde overvejet i årevis. Pludselig havde de trods alt løst det sværere problem.

Først troede forfatterne ikke på det. "Lad os finde ud af, hvad der er galt med det her," huskede Wichs, at han tænkte. "Vi blev ved med at prøve at finde ud af, hvor det bryder sammen."

Men løsningen holdt: De havde virkelig opdaget en sikker måde at forbehandle en enkelt-server-database, så enhver kunne trække information i hemmelighed. "Det er virkelig ud over alt, hvad vi havde håbet på," sagde Yuval Ishai, en kryptograf ved Technion i Israel, som ikke var involveret i dette arbejde. Det er et resultat "vi var ikke engang modige nok til at bede om," sagde han.

Efter at have opbygget deres hemmelige opslagsskema, vendte forfatterne sig mod det virkelige mål med en privat internetsøgning, som er mere kompliceret end at trække informationer fra en database, sagde Wichs. Den private opslagsordning i sig selv giver mulighed for en version af privat Google-lignende søgning, men den er ekstremt arbejdskrævende: Du kører selv Googles algoritme og trækker i al hemmelighed data fra internettet, når det er nødvendigt. Wichs sagde, at en ægte søgning, hvor du sender en anmodning og læner dig tilbage, mens serveren indsamler resultaterne, virkelig er et mål for en bredere tilgang kendt som homomorf kryptering, som skjuler data, så en anden kan manipulere dem uden nogensinde at vide noget om det .

Typiske homomorfe krypteringsstrategier ville ramme den samme hage som privat informationshentning, idet de trasker gennem hele internettets indhold for hver søgning. Men ved at bruge deres private opslagsmetode som stillads, konstruerede forfatterne et nyt skema, som kører beregninger, der ligner de programmer, vi bruger hver dag, og trækker information skjult uden at feje hele internettet. Det ville give et effektivitetsløft for internetsøgninger og alle programmer, der har brug for hurtig adgang til data.

Mens homomorf kryptering er en nyttig forlængelse af den private opslagsordning, sagde Ishai, så ser han privat informationssøgning som det mere grundlæggende problem. Forfatternes løsning er den "magiske byggesten", og deres homomorfe krypteringsstrategi er en naturlig opfølgning.

Indtil videre er ingen af ​​skemaerne praktisk anvendelige: Forbehandling hjælper i øjeblikket i ekstremerne, når databasestørrelsen balloner mod det uendelige. Men faktisk at implementere det betyder, at disse besparelser ikke kan realiseres, og processen ville æde for meget tid og lagerplads.

Heldigvis, sagde Vaikuntanathan, har kryptografer en lang historie med at optimere resultater, der oprindeligt var upraktiske. Hvis fremtidigt arbejde kan strømline tilgangen, mener han, at private opslag fra gigantiske databaser kan være inden for rækkevidde. "Vi troede alle, at vi sad fast der," sagde han. "Det, Daniels resultat giver, er håb."

Quanta gennemfører en række undersøgelser for bedre at kunne betjene vores publikum. Tag vores datalogisk læserundersøgelse og du vil være med til at vinde gratis Quanta varer.