Kryptographen entwickeln einen Ansatz für vollständigen Datenschutz bei der Suche | Quanta-Magazin

Wir alle wissen, dass wir mit den Details, die wir online teilen, vorsichtig sein müssen, 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 – sei „ein sehr nützlicher Baustein in einer Reihe von Anwendungen zum Schutz der Privatsphäre“, sagte er David Wu, ein Kryptograph 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 Auszeichnung für das beste Papier im Juni beim jährlichen Symposium zur Theorie des Rechnens, überwindet eine große theoretische Hürde auf dem Weg zu einer wirklich privaten Suche.

„[Das ist] 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.

Aussichten 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.

Aber im Jahr 2017 zwei Gruppen von Forschern veröffentlicht Ergebnisse das änderte seine Meinung. Sie entwickelten die ersten Programme, die diese Art des Abrufs privater Informationen ermöglichten, konnten jedoch nicht nachweisen, dass die Programme sicher waren. (Kryptographen demonstrieren die Sicherheit eines Systems, indem sie zeigen, dass es genauso schwierig ist, es zu knacken, wie ein schwieriges Problem zu lösen. Die Forscher konnten es nicht mit einem kanonischen schwierigen Problem vergleichen.)

Trotz neuer Hoffnung ging Wichs davon aus, dass eine sichere Version dieser Programme noch in weiter Ferne lag. Stattdessen haben er und seine Co-Autoren – Wei-Kai Lin, jetzt an der University of Virginia, und Ethan Mook, ebenfalls bei Northeastern, arbeiteten an Problemen, von denen sie dachten, sie seien einfacher, darunter Fälle, in denen mehrere Server die Datenbank hosten.

Mit den von ihnen untersuchten Methoden können die Informationen in der Datenbank in einen mathematischen Ausdruck umgewandelt werden, den die Server auswerten können, um die Informationen zu extrahieren. Die Autoren gingen davon aus, dass dieser Bewertungsprozess möglicherweise effizienter gestaltet werden könnte. Sie spielten mit einer Idee aus dem Jahr 2011, als andere Forscher einen Weg gefunden hatten, einen solchen Ausdruck schnell auszuwerten, indem sie ihn vorverarbeiteten und spezielle, kompakte Wertetabellen erstellten, mit denen man die normalen Auswertungsschritte überspringen konnte.

Diese Methode brachte keine Verbesserungen und die Gruppe war kurz davor, aufzugeben – bis sie sich fragten, ob dieses Tool im begehrten Einzelserver-Fall tatsächlich funktionieren könnte. Wählen Sie ein Polynom sorgfältig genug aus, stellten sie fest, und ein einzelner Server konnte es auf der Grundlage des Ergebnisses von 2011 vorverarbeiten – was zu dem sicheren, effizienten Suchschema führte, über das Wichs jahrelang nachgedacht hatte. Plötzlich hatten sie doch das schwierigere Problem gelöst.

Die Autoren glaubten es zunächst nicht. „Lasst uns herausfinden, was daran falsch ist“, erinnerte sich Wichs. „Wir haben ständig versucht herauszufinden, wo es kaputt geht.“

Aber die Lösung hielt fest: Sie hatten wirklich eine sichere Möglichkeit gefunden, eine Einzelserver-Datenbank vorzuverarbeiten, sodass jeder heimlich Informationen abrufen konnte. „Es übertrifft wirklich alles, was wir uns erhofft hatten“, sagte er Yuval Ishai, ein Kryptograf am Technion in Israel, der an dieser Arbeit nicht beteiligt war. Es sei ein Ergebnis, „dass wir nicht einmal den Mut hatten, danach zu fragen“, sagte er.

Nachdem sie ihr geheimes Suchschema entwickelt hatten, wandten sich die Autoren dem realen Ziel einer privaten Internetsuche zu, die komplizierter ist als das Abrufen von Informationsschnipseln aus einer Datenbank, sagte Wichs. Das private Suchschema allein ermöglicht zwar eine Version der privaten Google-ähnlichen Suche, ist jedoch äußerst arbeitsintensiv: Sie führen den Google-Algorithmus selbst aus und rufen bei Bedarf heimlich Daten aus dem Internet ab. Wichs sagte, dass eine echte Suche, bei der man eine Anfrage sendet und sich zurücklehnt, während der Server die Ergebnisse sammelt, tatsächlich ein Ziel für einen umfassenderen Ansatz ist, der als homomorphe Verschlüsselung bekannt ist und Daten verschleiert, sodass jemand anderes sie manipulieren kann, ohne jemals etwas darüber zu wissen .

Typische homomorphe Verschlüsselungsstrategien stoßen auf das gleiche Problem wie das Abrufen privater Informationen und durchforsten bei jeder Suche alle Inhalte des Internets. Aber indem sie ihre private Suchmethode als Gerüst nutzten, konstruierten die Autoren ein neues Schema, das Berechnungen durchführt, die eher den Programmen ähneln, die wir täglich verwenden, und Informationen heimlich abruft, ohne das gesamte Internet zu durchsuchen. Dies würde eine Effizienzsteigerung bei Internetsuchen und allen Programmen bedeuten, die schnellen Zugriff auf Daten benötigen.

Während die homomorphe Verschlüsselung eine nützliche Erweiterung des privaten Suchschemas sei, sieht Ishai den Abruf privater Informationen als das grundlegendere Problem. Die Lösung der Autoren ist der „magische Baustein“, und ihre homomorphe Verschlüsselungsstrategie ist eine natürliche Fortsetzung.

Im Moment ist keines der beiden Schemata praktisch nützlich: Die Vorverarbeitung hilft derzeit im Extremfall, wenn die Datenbankgröße in Richtung Unendlich steigt. Die tatsächliche Bereitstellung bedeutet jedoch, dass diese Einsparungen nicht realisiert werden können und der Prozess zu viel Zeit und Speicherplatz verschlingen würde.

Glücklicherweise, so Vaikuntanathan, haben Kryptografen eine lange Tradition darin, Ergebnisse zu optimieren, die zunächst unpraktisch waren. Wenn zukünftige Arbeiten den Ansatz rationalisieren können, glaubt er, dass private Suchvorgänge in riesigen Datenbanken in greifbare Nähe gerückt sein könnten. „Wir dachten alle, wir stecken da fest“, sagte er. „Daniels Ergebnis gibt Hoffnung.“

Wie viel führt eine Reihe von Umfragen durch, um unser Publikum besser zu bedienen. Nimm unser Leserbefragung Informatik und Sie nehmen an der kostenlosen Verlosung teil Wie viel Waren.