Dieser Ansatz teilt die Datenmenge faktisch so auf zwei Datenbanken auf, dass keine allein ausreicht, um an irgendwelche Daten zu kommen. Konsequenz: Für reguläre Abfragen muss auf beide DBs zugegriffen werden. Somit sind beide potentiell angreifbar.

Fazit: Es wird lediglich der Aufwand erhöht, weil jetzt doppelt so viele DBs geknackt werden müssen. Die Verwendung verschlüsselter Daten, mit dem Schlüssel auf dem Client, ist einfacher, effektiver, und nicht mit einer Datenexplosion verbunden.

--
GPL ist der Versuch, den Ring gegen Sauron einzusetzen.

Dem Prinzip zugrunde liegt, dass es nur eine physische Datenbank gibt, die alle Informationen enthält, die nicht interessieren.

Beispiel: eine Datenbank mit allen Einwohnern; um das Beispiel einigermassen simpel zu halten gibt's nur einen Einwohner, der Hans Muster heisst.

Unsere (negative) Datenbank enthält nun alle Strings, die nicht "hans muster" sind:

aaaaaaaaaaa
aaaaaaaaaab
...
hans musteq
hans mustes
...
seppi meieq
seppi meier
seppi meies
...
zzzzzzzzzzz

Will man herausfinden, ob Seppi Meier zu den Einwohnern zählt, so ergibt eine Datenbankabfrage (a la "select name from population where name = 'seppi meier'") ein positives Resultat -> Seppi Meier ist kein Einwohner.

Auf der anderen Seite ergibt dieselbe Abfrage für Hans Muster ein negatives Resultat -> Hans Muster ist Einwohner.

So weit ist es nur die Umkehrung einer normalen Datenbank; durch die spezielle Repräsentation der "negativen Datenbank" ist eines der Hauptmerkmale jedoch, dass man vom physischen Datenbankinhalt (alle negativen Einträge, inkl. der Repräsentation von Seppi Meier) nicht so einfach auf den effektiven Datenbankinhalt (Hans Muster) schliessen kann. Somit kann der, der die ganze physische Datenbank besitzt (Intruder, Insider), die Daten nicht ohne Weiteres abschöpfen.

Dem Prinzip zugrunde liegt, dass es nur eine physische Datenbank gibt, die alle Informationen enthält, die nicht interessieren.

Nope. Man braucht auf jeden Fall noch eine zweite Datenbank mit allen Möglichkeiten. Ohne diese ist die Datenmenge nicht mehr zu verwalten. Alleine um einen Namen abzuspeichern mit, sagen wir, maximal 20 alphabetischen Zeichen ohne Umlaute, erhalten wir 53^20 Varianten. Das sind etwa 3*10^34.

Somit kann der, der die ganze physische Datenbank besitzt (Intruder, Insider), die Daten nicht ohne Weiteres abschöpfen.

Eben doch. Sind alle möglichen Einträge und alle tatsächlichen, negativen Einträge bekannt, so ist es trivial, die positiven Einträge zu erhalten. Schwierig wird es erst, wenn nur die tatsächlichen Einträge bekannt sind, nicht aber, was überhaupt möglich ist. Da letztere Information aber für die regulären Abfragen bekannt sein muss, existiert sie irgendwo, und kann folglich prinzipiell auch beschafft werden.

--
GPL ist der Versuch, den Ring gegen Sauron einzusetzen.

Man braucht auf jeden Fall noch eine zweite Datenbank mit allen Möglichkeiten.

Theoretisch sind natürlich immer alle Möglichkeiten als Menge vorhanden; effektiv physisch gespeichert müssen die einzelnen Mitglieder dieser Menge jedoch nicht werden. Sie können aber jederzeit generiert werden (z.B. durch den Intruder/Insider).

Sind alle möglichen Einträge und alle tatsächlichen, negativen Einträge bekannt, so ist es trivial, die positiven Einträge zu erhalten.

Vordergründig betrachtet ist dies der Fall. Esponda weist aber nach (vgl. Kapitel 3, Reversibility: "In what follows we turn our attention to the goal of making DB hard to reconstruct. First we establish that the representation is potentially difficult to reverse, and then we present an algorithm which indeed produces hard to reverse instances."), dass wenn die negative Datenbank einer speziellen Repräsentation folgt, es nicht trivial, sondern NP-Schwer ist.

Theoretisch sind natürlich immer alle Möglichkeiten als Menge vorhanden; effektiv physisch gespeichert müssen die einzelnen Mitglieder dieser Menge jedoch nicht werden.

Falls du den im Kapitel 2 erwähnten Repräsentationsalgorithmus meinst: Der skaliert miserabel. Bei jedem neuen, positiven Eintrag wird nicht nur mindestens ein neuer Eintrag in NDB nötig, sondern es besteht für jeden, bestehenden Eintrag eine gewisse Wahrscheinlichkeit, dass er ungültig wird, und durch mindestens zwei neue Einträge ersetzt werden muss. Je mehr Einträge also existieren, desto mehr wächst NDB mit jedem neuen, positiven Eintrag an. Der vorgestellte Prefix-Algorithmus entschärft das Problem vielleicht, beseitigt es aber sicher nicht. Das Theorem 2.1.1 ist völlig unzureichend belegt, da die verwendeten Laborwerte sich eindeutig im unproblematischen Bereich befinden.

Vordergründig betrachtet ist dies der Fall. Esponda weist aber nach, dass wenn die negative Datenbank einer speziellen Repräsentation folgt, es nicht trivial, sondern NP-Schwer ist.

Seine Beweisführung geht davon aus, dass der Angreifer nicht weiss, wie NDB generiert wurde. In der Praxis darf man sich auf solche Annahmen nicht stützen. Nur schon darum, weil die meisten Angriffe von Insidern kommen. Ist der Algorithmus zur Generierung von NDB einmal bekannt, lässt sich der Vorgang problemlos umkehren. Dieses Problem wird vom Author in Kapitel 4 sogar ausdrüklich anerkannt, ohne aber eine befriedigende Lösung anzubieten. Der alternative Algorithmus ist nicht schwieriger umzukehren, sondern nur schwieriger zu erkennen.

--
GPL ist der Versuch, den Ring gegen Sauron einzusetzen.