Cryptography Reference
In-Depth Information
Für unsere weiteren Untersuchungen ist folgende Beobachtung nützlich: Statt im Expe-
riment
für den Fall
b
=0
die Permutation
F
auf einen Schlag vollständig zu bestimmen,
kann man sie alternativ auch partiell und dynamisch bestimmen. Dazu wird im Experi-
ment
E
für den Fall
b
=0
eine Tabelle
T
mit Einträgen der Form
(
x, y
)
∈{
0
,
1
}
E
l
verwaltet, die anfangs leer ist. Es bezeichne
T
links
bzw.
T
rechts
die Menge der Bitvektoren,
die in der linken bzw. rechten Komponente der Einträge von
T
zu finden sind. Ein Tabel-
leneintrag der Form
(
x, y
)
bedeutet, dass
F
mit
x
angefragt wurde und dass als Chiffretext
y
zurückgegeben wurde. Wird nun von
U
eine neue Anfrage an
F
gestellt mit Klartext
x
, so wird zunächst geschaut, ob diese Anfrage bereits gestellt wurde, also ob
x
∈
l
×{
0
,
1
}
T
links
gilt. Existiert bereits ein
y
T
,dannwird
y
zurückgegeben. Ansonsten
wird zufällig gleichverteilt ein Element (ein Chiffretext), aus der Menge
mit
(
x
,y
)
∈
l
{
0
,
1
}
\
T
rechts
gewählt, d. h. es wird flip
(
{
0
,
1
}
\ T
rechts
)
ausgeführt (siehe dazu auch Aufgabe 4.9.12);
sei
y
das gewählte Element. Dann wird der Eintrag
(
x
,y
)
zu
T
hinzugefügt und
y
wird zurückgegeben. Man sieht nun leicht, dass diese dynamische Implementierung von
F
aus der Sicht eines Unterscheiders keinen Unterschied macht. Die Sichtweise, dass eine
Permutation
F
dynamisch gewählt wird, hat aber verschiedene Vorteile, weshalb wir im
Rest des Buches auch häufig von dieser Sichtweise ausgehen werden: Sie hilft bei Sicher-
heitsanalysen, da deutlich wird, dass Chiffretexte zu neuen Klartexten, zufällig aus der
Menge der noch nicht verbrauchten Chiffretexte gewählt werden. Außerdem erlaubt sie
eine realistischere Messung von in einem Experiment verbrauchten Ressourcen. Auf den
letzten Punkt kommen wir am Ende dieses Abschnitts noch einmal zu sprechen.
Eine einfache Überlegung zeigt, dass ein Unterscheider leicht mit Wahrscheinlich-
keit
1
/
2
das Experiment bestehen kann: Er muss dazu lediglich
b
zufällig wählen. Um
ein normiertes Ergebnis zu erhalten, könnten wir von der Gewinnwahrscheinlichkeit
Prob
l
den Wert
1
/
2
abziehen. Dann könnte ein sehr guter Angreifer aber maximal
den Wert
1
/
2
erzielen. Deshalb ziehen wir nicht nur
1
/
2
von der obigen Wahrscheinlich-
keit ab, sondern multiplizieren dann auch noch mit
2
.
Damit können wir nun die normierte Gewinnwahrscheinlichkeit eines Unterscheiders,
die wir Vorteil nennen wollen, definieren.
{
E
=1
}
Definition 4.7.3 (Vorteil eines Unterscheiders). Es sei
U
ein
l
-Unterscheider und
B
ein
l
-Block-Kryptosystem. Der
Vorteil (advantage)
von
U
bezüglich
B
ist definiert durch
adv
(
U,B
)=2
Prob
E
U
=1
−
1
2
.
(4.7.1)
Wir können direkt festhalten:
Bemerkung
4.7.1
.
Es sei
l>
0
.
1. Für jeden
l
-Unterscheider
U
und jedes
l
-Block-Kryptosystem
B
gilt adv
(
U,B
)
∈
[
1
,
1]
.
2. Für den oben beschriebenen einfachen
l
-Unterscheider
U
,der
b
zufällig wählt, und
jedes
l
-Block-Kryptosystem
−
B
gilt adv
(
U,B
)=0
.
Bevor wir uns ein Beispiel ansehen, um den Begriff des Unterscheiders und des Vorteils
