Private Informationsabfrage

Öffentlich zugängliche Datenbanken sind eine unverzichtbare Ressource für die Beschaffung aktueller Informationen. Sie stellen jedoch auch ein erhebliches Risiko für die Privatsphäre des Nutzers dar, da ein neugieriger Datenbankbetreiber die Anfragen des Nutzers verfolgen und daraus Rückschlüsse auf dessen Interessen ziehen kann. Tatsächlich sind Nutzer, deren Absichten geheim bleiben sollen, oft vorsichtig beim Zugriff auf die Datenbank. Es lässt sich zeigen, dass beim Zugriff auf eine einzelne Datenbank, um die Privatsphäre des Nutzers vollständig zu gewährleisten, die gesamte Datenbank heruntergeladen werden muss; das heißt, n Bits kommuniziert werden sollten (wobei n die Anzahl der Bits in der Datenbank ist). In dieser Arbeit untersuchen wir, ob durch die Replikation der Datenbank effizientere Lösungen für das Problem der privaten Abfrage erzielt werden können. Wir beschreiben Verfahren, die es einem Nutzer ermöglichen, k replizierte Kopien einer Datenbank (k ≥ 2) zuzugreifen und Informationen aus der Datenbank privat abzurufen. Dies bedeutet, dass jeder einzelne Server (der eine replizierte Kopie der Datenbank hält) keine Informationen über die Identität des vom Nutzer abgerufenen Elements erhält. Unsere Verfahren nutzen die Replikation, um erhebliche Einsparungen zu erzielen. Insbesondere stellen wir ein Zwei-Server-Verfahren mit Kommunikationskomplexität O(n^{1/3}) vor.