Cryptography Reference
In-Depth Information
Experimentes (siehe unten), wird
AG
die Berechnung in der Konfiguration fortsetzen, in
der
AF
angehalten hat. Wir verlangen, dass die Laufzeiten von
AF
und
AG
bei beliebigen
Argumenten durch Konstanten nach oben beschränkt sind.
Das in Abbildung 5.4 dargestellte Spiel formulieren wir nun präziser als Experiment
in folgender Definition. Wir führen zudem den Begriff eines verkürzten Experimentes
ein. Obwohl wir mit den Begriffen »Experiment« und »verkürztes Experiment« dieselbe
Terminologie wie im Abschnitt 4.7 verwenden, sollte jeweils immer klar sein, auf welches
Experiment wir uns beziehen.
Definition 5.3.2 (Experiment zu einem Angreifer). Es sei
A
=(
AF
,
AG
)
ein
l
-Angreifer
E
A
,
und
S
=(
K,E,D
)
ein
l
-Kryptoschema. Das zugehörige
Experiment
,daswirmit
E
A
oder einfach
E
bezeichnen, ist der folgende Algorithmus:
E
:
}
1.
Chiffrewahl
k
=
flip
(
K
)
;
H
=
E
(
·,k
)
2.
Findungsphase
(
z
0
,z
1
)=
{
0
,
1
AF
(
H
)
3.
Auswahl
b
=
flip
()
;
y
=
H
(
z
b
)
4.
Ratephase
b
=
(
H,y
)
5.
Auswertung
falls
b
=
b
,sogib
1
, sonst
0
zurück
AG
In diesem Experiment werden
AF
und
AG
das Verschlüsselungsorakel
H
als Parameter
übergeben,
AG
erhält zusätzlich die Probe
y
als Parameter. Außerdem setzt
AG
seine
Berechnung in der Konfiguration fort, in der
AF
die Berechnung beendet hat.
S
A
,
dadurch entsteht,
dass der fünfte Schritt ersetzt wird durch »gib
b
zurück«. Er wird
verkürztes Experiment
genannt.
Mit
S
A
oder einfach
S
bezeichnen wir den Algorithmus, der aus
E
Die Wahrscheinlichkeit, dass Eva das beschriebene und in Abbildung 5.4 dargestellte
Spiel gewinnt, lässt sich nun schreiben als
Prob
{
E
=1
}
, d. h., die Wahrscheinlichkeit,
dass der Algorithmus
die Zahl
1
ausgibt.
Eine einfache Überlegung zeigt, dass Eva leicht mit Wahrscheinlichkeit
1
/
2
das Spiel
gewinnen kann: Eva muss dazu lediglich
b
E
zufällig wählen. Formal ist der zugehörige
l
-Angreifer
A
=(
AF
,
AG
)
wie folgt definiert:
(
H
)=
sende
(0
l
,
0
l
)
AF
(5.3.2)
AG
(
H,y
)=
b
=
flip
()
;gib
b
zurück
.
(5.3.3)
Analog zur Definition des Vorteils eines Unterscheiders für Block-Kryptosysteme, moti-
viert dies die folgende Definition des Vorteils eines
l
-Angreifers. Erfolg und Misserfolg
eines
l
-Angreifers sind ebenfalls analog zu Abschnitt 4.7 definiert.
