De originele versie van dit verhaal verscheen in Quanta-tijdschrift.
We weten allemaal We moeten voorzichtig 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 stapel gecompromitteerde gegevens en loop het risico deze zelf te lekken.
Deze situaties roepen een belangrijke vraag op in de cryptografie: hoe kun je informatie uit een openbare database halen zonder iets te onthullen over waartoe je toegang hebt gekregen? Het is hetzelfde als een boek uit de bibliotheek lenen 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”, zegt David Wu, een cryptograaf aan de Universiteit van Texas in Austin. Sinds de jaren negentig hebben onderzoekers dit probleem aangepakt en strategieën voor particuliere toegang tot databases verbeterd. Een van de belangrijkste doelen, wat nog steeds onmogelijk is bij grote databases, is het equivalent van een privé-zoekopdracht op Google, waarbij je anoniem door een hele reeks gegevens kunt bladeren zonder veel rekenwerk.
Nu hebben drie onderzoekers een lang gezochte versie van het ophalen van privé-informatie overgenomen en deze uitgebreid om een meer algemene privacystrategie op te bouwen. Het artikel, dat in juni 2023 de Best Paper Award won op het jaarlijkse symposium over de theorie van computergebruik, doorbreekt een grote theoretische barrière voor echt particuliere activiteiten.
“[This is] iets in de cryptografie dat we waarschijnlijk allemaal wilden, maar waarvan we niet echt geloofden dat het bestond”, zegt Vinod Vaikuntanathan, een cryptograaf aan het Massachusetts Institute of Technology die niet bij het werk betrokken was. “Het is een significant resultaat.”
Het probleem van de toegang tot een particuliere database ontstond in de jaren negentig. In eerste instantie gingen de onderzoekers ervan uit dat de enige oplossing was om bij elke zoekopdracht de hele database te scannen, wat hetzelfde zou zijn als een bibliothecaris die elke plank scant voordat hij terugkomt met je boek. Als bij de zoekopdracht een sectie wordt overgeslagen, weet de bibliothecaris immers dat uw boek niet in die sectie van de bibliotheek staat.
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 uiterst inefficiënt.
Begin jaren 2000 begonnen onderzoekers te vermoeden dat ze de volledige scanbarrière konden omzeilen door de database te “voorbewerken”. Dit zou grofweg betekenen dat de gehele database als een aparte structuur wordt gecodeerd, zodat de server op een vraag kan reageren door slechts een klein deel van die structuur te lezen. Zorgvuldig genoeg voorbewerken zou in theorie kunnen betekenen dat informatie die op een enkele server wordt gehost, het proces maar één keer doorloopt, waardoor alle toekomstige gebruikers de informatie zonder enige moeite privé kunnen bemachtigen.
Voor Daniel Wichs, cryptograaf aan de Northeastern University en co-auteur van het nieuwe artikel, leek het te mooi om waar te zijn. Rond 2011 begon hij te bewijzen dat een dergelijk plan onmogelijk was. “Ik was ervan overtuigd dat er geen manier was om dit te doen”, zei hij.