Kryptografer utarbeider en tilnærming for totalt søkevern | Quanta Magazine

Vi vet alle å være forsiktige med detaljene vi deler på nettet, men informasjonen vi søker kan også være avslørende. Søk etter veibeskrivelser, og plasseringen vår blir mye lettere å gjette. Se etter et passord i en haug med kompromitterte data, og vi risikerer å lekke det selv.

Disse situasjonene gir et sentralt spørsmål innen kryptografi: Hvordan kan du hente informasjon fra en offentlig database uten å avsløre noe om hva du har fått tilgang til? Det tilsvarer å sjekke ut en bok fra biblioteket uten at bibliotekaren vet hvilken.

Å lage en strategi som løser dette problemet - kjent som privat informasjonsinnhenting - er "en veldig nyttig byggestein i en rekke personvernbevarende applikasjoner," sa David Wu, en kryptograf ved University of Texas, Austin. Siden 1990-tallet har forskere sløyfet spørsmålet og forbedret strategier for privat tilgang til databaser. Et hovedmål, som fortsatt er umulig med store databaser, tilsvarer et privat Google-søk, hvor du kan sile gjennom en haug med data anonymt uten å gjøre noen tunge beregningsmessige løft.

Nå har tre forskere gjort det utformet en lenge ettersøkt versjon av privat informasjonsinnhenting og utvidet den til å bygge en mer generell personvernstrategi. Verket, som fikk en Pris for beste papir i juni på den årlige Symposium om datateori, velter en stor teoretisk barriere på veien til et virkelig privat søk.

"[Dette er] noe innen kryptografi som jeg antar at vi alle ønsket, men som ikke helt trodde at det eksisterer," sa Vinod Vaikuntanathan, en kryptograf ved Massachusetts Institute of Technology som ikke var involvert i avisen. – Det er et landemerkeresultat.

Problemet med privat databasetilgang tok form på 1990-tallet. Til å begynne med antok forskerne at den eneste løsningen var å skanne hele databasen under hvert søk, som ville være som å la en bibliotekar gjennomsøke hver hylle før han returnerte med boken din. Tross alt, hvis søket hoppet over en del, ville bibliotekaren vite at boken din ikke er i den delen av biblioteket.

Den tilnærmingen fungerer godt nok i mindre skalaer, men etter hvert som databasen vokser, vokser tiden som kreves for å skanne den i det minste proporsjonalt. Når du leser fra større databaser - og internett er en ganske stor - blir prosessen uoverkommelig ineffektiv.

På begynnelsen av 2000-tallet begynte forskere å mistenke at de kunne unngå fullskanningsbarrieren ved å "forbehandle" databasen. Grovt sett vil dette bety å kode hele databasen som en spesiell struktur, slik at serveren kan svare på et spørsmål ved å lese bare en liten del av den strukturen. Forsiktig nok forhåndsbehandling kan i teorien bety at en enkelt server-vertsinformasjon bare går gjennom prosessen én gang, av seg selv, slik at alle fremtidige brukere kan hente informasjon privat uten mer innsats.

Til Daniel Wichs, en kryptograf ved Northeastern University og en medforfatter av det nye papiret, som virket for godt til å være sant. Rundt 2011 begynte han å prøve å bevise at denne typen opplegg var umulig. "Jeg var overbevist om at det ikke er mulig at dette kan gjøres," sa han.

Men i 2017, to grupper av forskere publisert resultater som endret mening. De bygde de første programmene som kunne gjøre denne typen privat informasjonsinnhenting, men de klarte ikke å vise at programmene var sikre. (Kryptografer demonstrerer et systems sikkerhet ved å vise at å bryte det er like vanskelig som å løse et eller annet vanskelig problem. Forskerne var ikke i stand til å sammenligne det med et kanonisk vanskelig problem.)

Så selv med håpet fornyet, antok Wichs at enhver versjon av disse programmene som var sikker fortsatt var langt unna. I stedet, han og hans medforfattere - Wei-Kai Lin, nå ved University of Virginia, og Ethan Mook, også på Northeastern — jobbet med problemer de trodde ville være enklere, som involverte tilfeller der flere servere er vert for databasen.

I metodene de studerte kan informasjonen i databasen transformeres til et matematisk uttrykk, som serverne kan evaluere for å trekke ut informasjonen. Forfatterne regnet med at det kunne være mulig å gjøre den evalueringsprosessen mer effektiv. De lekte med en idé fra 2011, da andre forskere hadde funnet en måte å raskt evaluere et slikt uttrykk ved å forhåndsbehandle det, lage spesielle, kompakte verditabeller som lar deg hoppe over de vanlige evalueringstrinnene.

Den metoden ga ingen forbedringer, og gruppen var nær ved å gi opp - helt til de lurte på om dette verktøyet faktisk kunne fungere i den ettertraktede enkeltserversaken. Velg et polynom nøye nok, så de, og en enkelt server kunne forhåndsbehandle det basert på 2011-resultatet – noe som gir det sikre, effektive oppslagsskjemaet Wichs hadde tenkt på i årevis. Plutselig hadde de tross alt løst det vanskeligere problemet.

Først trodde ikke forfatterne på det. "La oss finne ut hva som er galt med dette," husket Wichs at han tenkte. "Vi fortsatte å prøve å finne ut hvor det bryter sammen."

Men løsningen holdt: De hadde virkelig oppdaget en sikker måte å forhåndsbehandle en enkeltserverdatabase slik at hvem som helst kunne hente informasjon i hemmelighet. "Det er virkelig over alt vi hadde håpet på," sa Yuval Ishai, en kryptograf ved Technion i Israel som ikke var involvert i dette arbeidet. Det er et resultat "vi var ikke engang modige nok til å be om," sa han.

Etter å ha bygget sitt hemmelige oppslagsopplegg, vendte forfatterne seg til det virkelige målet med et privat internettsøk, som er mer komplisert enn å hente biter av informasjon fra en database, sa Wichs. Den private oppslagsordningen i seg selv tillater en versjon av privat Google-lignende søk, men det er ekstremt arbeidskrevende: Du kjører Googles algoritme selv og henter i all hemmelighet data fra internett når det er nødvendig. Wichs sa at et ekte søk, der du sender en forespørsel og lene deg tilbake mens serveren samler inn resultatene, virkelig er et mål for en bredere tilnærming kjent som homomorf kryptering, som skjuler data slik at noen andre kan manipulere dem uten å vite noe om det. .

Typiske homomorfe krypteringsstrategier vil treffe den samme ulempen som privat informasjonsinnhenting, og gå gjennom alt innholdet på Internett for hvert søk. Men ved å bruke deres private oppslagsmetode som stillas, konstruerte forfatterne et nytt opplegg som kjører beregninger som ligner mer på programmene vi bruker hver dag, og trekker informasjon skjult uten å sveipe hele internett. Det vil gi et effektivitetsløft for internettsøk og alle programmer som trenger rask tilgang til data.

Mens homomorf kryptering er en nyttig utvidelse av det private oppslagsskjemaet, sa Ishai, ser han på privat informasjonsinnhenting som det mer grunnleggende problemet. Forfatternes løsning er den "magiske byggesteinen", og deres homomorfe krypteringsstrategi er en naturlig oppfølging.

Foreløpig er ingen av ordningene praktisk nyttige: Forbehandling hjelper for øyeblikket i ytterpunktene, når databasestørrelsen ballonger mot det uendelige. Men å implementere det betyr at disse besparelsene ikke kan realiseres, og prosessen vil spise opp for mye tid og lagringsplass.

Heldigvis, sa Vaikuntanathan, har kryptografer en lang historie med å optimalisere resultater som i utgangspunktet var upraktiske. Hvis fremtidig arbeid kan effektivisere tilnærmingen, tror han private oppslag fra gigantiske databaser kan være innen rekkevidde. "Vi trodde alle at vi var litt fast der," sa han. "Det Daniels resultat gir er håp."

Quanta gjennomfører en serie undersøkelser for å tjene publikum bedre. Ta vår informatikk leserundersøkelse og du vil bli registrert for å vinne gratis Quanta handelsvarer.