Die Originalversion von diese Geschichte erschien in Quanta-Magazin.
Wir wissen alle Wir müssen mit den Details, die wir online teilen, vorsichtig sein, aber die Informationen, nach denen wir suchen, können auch aufschlussreich sein. Wenn Sie nach Wegbeschreibungen suchen, ist es viel einfacher, unseren Standort zu erraten. Suchen Sie nach einem Passwort in einem Fundus kompromittierter Daten, und wir riskieren, es selbst preiszugeben.
Diese Situationen werfen eine Schlüsselfrage in der Kryptographie auf: Wie können Sie Informationen aus einer öffentlichen Datenbank abrufen, ohne etwas darüber preiszugeben, worauf Sie zugegriffen haben? Es ist so, als würde man ein Buch aus der Bibliothek ausleihen, ohne dass der Bibliothekar weiß, welches.
Die Ausarbeitung einer Strategie zur Lösung dieses Problems – bekannt als Private Information Retrieval – ist „ein sehr nützlicher Baustein in einer Reihe von Anwendungen zum Schutz der Privatsphäre“, sagte er David Wu, ein Kryptograf an der University of Texas, Austin. Seit den 1990er Jahren haben sich Forscher dieser Frage angenommen und Strategien für den privaten Zugriff auf Datenbanken verbessert. Ein wichtiges Ziel, das bei großen Datenbanken immer noch unmöglich ist, ist das Äquivalent einer privaten Google-Suche, bei der Sie anonym und ohne großen Rechenaufwand einen Datenhaufen durchsuchen können.
Jetzt haben drei Forscher gefertigt eine seit langem gesuchte Version des privaten Informationsabrufs und erweiterte sie, um eine allgemeinere Datenschutzstrategie zu entwickeln. Die Arbeit, die einen erhielt Best Paper Award im Juni 2023 auf der Jahrestagung Symposium zur Computertheorieüberwindet eine große theoretische Hürde auf dem Weg zu einer wirklich privaten Suche.
„[This is] „Etwas in der Kryptographie, das wir wohl alle wollten, aber nicht ganz glaubten, dass es existiert“, sagte er Vinod Vaikuntanathan, ein Kryptograph am Massachusetts Institute of Technology, der nicht an der Arbeit beteiligt war. „Es ist ein bahnbrechendes Ergebnis.“
Das Problem des privaten Datenbankzugriffs nahm in den 1990er Jahren Gestalt an. Zuerst gingen die Forscher davon aus, dass die einzige Lösung darin bestehe, bei jeder Suche die gesamte Datenbank zu scannen, was so wäre, als würde ein Bibliothekar jedes Regal durchsuchen, bevor er mit seinem Buch zurückkommt. Wenn bei der Suche ein Abschnitt übersprungen würde, wüsste der Bibliothekar schließlich, dass sich Ihr Buch nicht in diesem Teil der Bibliothek befindet.
Dieser Ansatz funktioniert in kleineren Maßstäben recht gut, aber wenn die Datenbank wächst, nimmt die zum Scannen erforderliche Zeit zumindest proportional zu. Wenn Sie aus größeren Datenbanken lesen – und das Internet ist eine ziemlich große Datenbank – wird der Prozess unerschwinglich ineffizient.
In den frühen 2000er Jahren begannen Forscher zu vermuten, dass sie die Vollscan-Barriere umgehen könnten, indem sie die Datenbank „vorverarbeiten“. Grob gesagt würde dies bedeuten, die gesamte Datenbank als spezielle Struktur zu kodieren, sodass der Server eine Anfrage beantworten könnte, indem er nur einen kleinen Teil dieser Struktur liest. Eine ausreichend sorgfältige Vorverarbeitung könnte theoretisch dazu führen, dass ein einzelner Server, der Informationen hostet, den Prozess nur einmal für sich durchläuft, sodass alle zukünftigen Benutzer ohne weiteren Aufwand privat auf Informationen zugreifen können.
Für Daniel Wichs, einem Kryptografen an der Northeastern University und Mitautor der neuen Arbeit, schien das zu schön, um wahr zu sein. Um 2011 begann er zu beweisen, dass ein solches Vorhaben unmöglich sei. „Ich war davon überzeugt, dass das auf keinen Fall möglich ist“, sagte er.