Semantische Sicherheit

Moderator: Einführung in die Kryptographie

dalinger
Neuling
Neuling
Beiträge: 5
Registriert: 23. Mai 2009 20:01

Semantische Sicherheit

Beitrag von dalinger » 19. Nov 2011 19:37

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
Moderator
Moderator
Beiträge: 54
Registriert: 11. Mai 2006 17:14

Re: Semantische Sicherheit

Beitrag von fischlin » 30. Nov 2011 11:28

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

Antworten

Zurück zu „Einführung in die Kryptographie“