Semantische Sicherheit

[dalinger]

Hallo,

ich störe mich an der Definition von semantischer Sicherheit für Public-Key-Verfahren. Wir habe definiert:

Ein Public-Key-Verfahren \(\mathcal{E}\) ist semantisch sicher, wenn für alle effektiven Algorithmen \(\mathcal{A}\) ein effektiver Algorithmus \(\mathcal{S}\) existiert, so dass für alle effektiven Verteilungen \(\mathcal{M}\) und alle effektiven Funktionen \(f\) gilt [...].

Ist es nicht sinnvoller zu definieren: Ein Public-Key-Verfahren \(\mathcal{E}\) ist semantisch sicher, wenn für alle effektiven Verteilungen \(\mathcal{M}\), alle effektiven Funktionen \(f\) und alle effektiven Algorithmen \(\mathcal{A}\) ein effektiver Algorithmus \(\mathcal{S}\) existiert, so dass gilt [...]?

Salopp gesagt versuchen ja \(\mathcal{A}\) und \(\mathcal{S}\) den Funktionswert \(f(pk,m)\) zu erraten. Aber dazu sollten diese Algorithmen in Abhängigkeit von \(f\) gewählt werden.

[fischlin]

Hm, ich sehe schon, ich übertreibe es mit den Abkürzungen: eff. = effizient, nicht effektiv.

Die Motivation dieser Quantorenreihenfolge (mit M,f "hinten") ist, dass sie stärker ist: Der Simulator
muss genauso gut sein, egal welche Information der Angreifer später aus einem Ciphertext vielleicht
herausfiltern möchte. Im anderen Fall (M,f "vorne") würde der Simulator eine spezielle Information
für eine spezielle Verteilung "schützen". Es ist hoffentlich klar, dass die erste Version "hinten" die
zweite "vorne" impliziert.

Soviel zur Philosophie dahinter. Technisch macht es aber gar keinen Unterschied; beide Varianten sind
äquivalent. (Das ist nicht leicht zu sehen, sondern folgt mit etwas Arbeit aus der Sicherheitsdefinition
der Ununterscheidbarkeit für Verschlüsselungssysteme, die wir heute oder nächste Woche kennenlernen.)