We weten allemaal dat we voorzichtig moeten zijn met de details die we online delen, maar de informatie die we zoeken kan ook onthullend zijn. Zoek naar een routebeschrijving en onze locatie wordt veel gemakkelijker te raden. Controleer op een wachtwoord in een grote hoeveelheid gecompromitteerde gegevens, en we lopen het risico dit zelf te lekken.

Deze situaties voeden een belangrijke vraag in de cryptografie: hoe kun je informatie uit een openbare database halen zonder iets te onthullen over waartoe je toegang hebt gehad? Het is het equivalent van het uitchecken van een boek uit de bibliotheek zonder dat de bibliothecaris weet welk boek.

Het bedenken van een strategie die dit probleem oplost – bekend als het ophalen van privé-informatie – is “een zeer nuttige bouwsteen in een aantal privacybeschermende toepassingen”, aldus David Wu, een cryptograaf aan de Universiteit van Texas, Austin. Sinds de jaren negentig hebben onderzoekers deze vraag aangepakt en de strategieën voor particuliere toegang tot databases verbeterd. Een belangrijk doel, dat nog steeds onmogelijk is bij grote databases, is het equivalent van een privézoekopdracht op Google, waarbij je anoniem door een hoop gegevens kunt bladeren zonder veel rekenwerk te hoeven doen.

Nu hebben drie onderzoekers dat gedaan bewerkte een lang gezochte versie van het ophalen van privé-informatie en breidde deze uit om een ​​meer algemene privacystrategie op te bouwen. Het werk, dat een Prijs voor beste papier in juni op de jaarlijkse Symposium over de theorie van computers, haalt een belangrijke theoretische barrière omver op weg naar een werkelijk private zoektocht.

"[Dit is] iets in de cryptografie dat we waarschijnlijk allemaal wilden, maar niet helemaal geloofden dat het bestond", zei Vinod Vaikuntanathan, een cryptograaf aan het Massachusetts Institute of Technology die niet bij de krant betrokken was. “Het is een mijlpaalresultaat.”

Het probleem van de toegang tot particuliere databases kreeg vorm in de jaren negentig. In eerste instantie gingen onderzoekers ervan uit dat de enige oplossing was om bij elke zoekopdracht de hele database te scannen, wat hetzelfde zou zijn als een bibliothecaris elke plank laten doorzoeken voordat hij terugkomt met je boek. Als bij de zoekopdracht een sectie wordt overgeslagen, weet de bibliothecaris immers dat uw boek zich niet in dat deel van de bibliotheek bevindt.

Die aanpak werkt goed genoeg op kleinere schaal, maar naarmate de database groeit, groeit de tijd die nodig is om deze te scannen op zijn minst proportioneel. Als je uit grotere databases leest – en het internet is behoorlijk groot – wordt het proces onbetaalbaar inefficiënt.

Begin jaren 2000 begonnen onderzoekers te vermoeden dat ze de barrière van volledige scan konden omzeilen door de database te ‘voorbewerken’. Grofweg zou dit betekenen dat de hele database als een speciale structuur wordt gecodeerd, zodat de server een vraag kan beantwoorden door slechts een klein deel van die structuur te lezen. Zorgvuldig genoeg voorbewerken zou in theorie kunnen betekenen dat een enkele server die informatie host, het proces slechts één keer op zichzelf doorloopt, waardoor alle toekomstige gebruikers zonder enige moeite privé informatie kunnen bemachtigen.

Voor Daniël Wichs, een cryptograaf aan de Northeastern University en co-auteur van het nieuwe artikel, leek dat te mooi om waar te zijn. Rond 2011 begon hij te bewijzen dat dit soort plannen onmogelijk was. “Ik was ervan overtuigd dat dit op geen enkele manier mogelijk was”, zei hij.

Maar in 2017 waren er twee groepen onderzoekers gepubliceerde dat veranderde van gedachten. Ze bouwden de eerste programma's die dit soort privé-informatie konden ophalen, maar ze konden niet aantonen dat de programma's veilig waren. (Cryptografen demonstreren de veiligheid van een systeem door te laten zien dat het breken ervan net zo moeilijk is als het oplossen van een moeilijk probleem. De onderzoekers konden het niet vergelijken met een canoniek moeilijk probleem.)

Dus zelfs met hernieuwde hoop ging Wichs ervan uit dat een veilige versie van deze programma's nog ver weg was. In plaats daarvan hebben hij en zijn co-auteurs – Wei-Kai Lin, nu aan de Universiteit van Virginia, en Ethan Mook, ook bij Northeastern – werkten aan problemen waarvan zij dachten dat die gemakkelijker zouden zijn, waarbij gevallen betrokken waren waarbij meerdere servers de database hosten.

In de methoden die ze hebben bestudeerd, kan de informatie in de database worden omgezet in een wiskundige uitdrukking, die de servers kunnen evalueren om de informatie te extraheren. De auteurs dachten dat het mogelijk zou zijn om dat evaluatieproces efficiënter te maken. Ze speelden met een idee uit 2011, toen andere onderzoekers een manier hadden gevonden om zo'n uitdrukking snel te evalueren door deze voor te verwerken, waardoor speciale, compacte waardentabellen ontstonden waarmee je de normale evaluatiestappen kunt overslaan.

Die methode leverde geen enkele verbetering op, en de groep gaf het bijna op, totdat ze zich afvroegen of deze tool wel zou kunnen werken in het felbegeerde geval van één server. Ze zagen dat ze een polynoom zorgvuldig genoeg kozen, en een enkele server kon deze voorbewerken op basis van het resultaat van 2011 – wat het veilige, efficiënte opzoekschema opleverde waar Wichs al jaren over had nagedacht. Plots hadden ze het moeilijkere probleem toch opgelost.

Aanvankelijk geloofden de auteurs het niet. 'Laten we uitzoeken wat hier mis mee is,' herinnerde Wichs zich dat hij dacht. “We bleven proberen erachter te komen waar het kapot ging.”

Maar de oplossing hield stand: ze hadden echt een veilige manier ontdekt om een ​​database met één server voor te bewerken, zodat iedereen in het geheim informatie kon opvragen. “Het overtreft echt alles waar we op hadden gehoopt,” zei Yuval Ishai, een cryptograaf bij het Technion in Israël die niet bij dit werk betrokken was. Het is een resultaat waar we niet eens om durfden te vragen, zei hij.

Na het opzetten van hun geheime opzoekschema, richtten de auteurs zich op het echte doel van een privé-zoekopdracht op internet, wat ingewikkelder is dan het ophalen van stukjes informatie uit een database, zei Wichs. Het privé-opzoekschema op zichzelf maakt een versie van privé-Google-achtig zoeken mogelijk, maar het is uiterst arbeidsintensief: u voert het algoritme van Google zelf uit en haalt in het geheim gegevens van internet wanneer dat nodig is. Wichs zei dat een echte zoekopdracht, waarbij je een verzoek verzendt en achterover leunt terwijl de server de resultaten verzamelt, in werkelijkheid een doelwit is voor een bredere aanpak die bekend staat als homomorfe encryptie, waarbij gegevens worden vermomd zodat iemand anders deze kan manipuleren zonder er ooit iets van te weten. .

Typische homomorfe encryptiestrategieën zouden op hetzelfde probleem stuiten als het ophalen van privé-informatie, waarbij bij elke zoekopdracht de hele inhoud van het internet moet worden doorzocht. Maar door hun private lookup-methode als basis te gebruiken, construeerden de auteurs een nieuw schema dat berekeningen uitvoert die meer lijken op de programma's die we dagelijks gebruiken, waarbij heimelijk informatie wordt verzameld zonder het hele internet te overspoelen. Dat zou een efficiëntieverbetering opleveren voor zoekopdrachten op internet en voor programma's die snelle toegang tot gegevens nodig hebben.

Hoewel homomorfe encryptie een nuttige uitbreiding is van het private lookup-systeem, ziet Ishai het ophalen van privé-informatie als het fundamentelere probleem. De oplossing van de auteurs is de 'magische bouwsteen', en hun homomorfe encryptiestrategie is een natuurlijk vervolg.

Voorlopig is geen van beide schema's praktisch bruikbaar: voorverwerking helpt momenteel bij de extremen, wanneer de databasegrootte naar het oneindige stijgt. Maar als je het daadwerkelijk inzet, kunnen die besparingen niet gerealiseerd worden en zou het proces te veel tijd en opslagruimte in beslag nemen.

Gelukkig, zei Vaikuntanathan, hebben cryptografen een lange geschiedenis in het optimaliseren van resultaten die aanvankelijk onpraktisch waren. Als toekomstig werk de aanpak kan stroomlijnen, denkt hij dat privé-zoekopdrachten uit gigantische databases binnen handbereik kunnen zijn. ‘We dachten allemaal dat we daar een beetje vastzaten’, zei hij. “Wat Daniëls resultaat geeft, is hoop.”

Quanta voert een reeks onderzoeken uit om ons publiek beter van dienst te zijn. Neem onze lezersenquête informatica en je doet mee om gratis te winnen Quanta handelswaar.