Cryptography Reference
In-Depth Information
E
A
man leicht sieht, genau das Experiment
simuliert. Unter der Annahme, dass
A
ein
guter Angreifer auf
E
A
das Bit
1
mit einer Wahrschein-
lichkeit deutlich größer als
1
/
2
ausgegeben. Damit ist auch die Wahrscheinlichkeit, dass
U
das Bit
1
ausgibt, also vermutet, in der Realwelt zu laufen, groß. Läuft dagegen
U
in der Zufallswelt, dann ist
F
eine zufällig gewählte Funktion. Es wird demnach das
Experiment
S
ist, wird im Experiment
E
S
A
S
das R-CTR-Kryptoschema bezeichnet, bei dem
das Block-Kryptosystem die zufällige Funktion ist. Ähnlich wie für zufällige Permuta-
tionen (Substitutionskryptosysteme) kann man bei einer zufälligen Funktion von einem
»optimalen« Block-Kryptosystem sprechen (obwohl formal eine zufällige Funktion kein
Block-Kryptosystem ist). Wenn die R-CTR-Betriebsart überhaupt sicher ist, dann erst
recht in Verbindung mit einer zufälligen Funktion. Der Angreifer
A
sollte in diesem Fall
also nur mit sehr geringer Wahrscheinlichkeit im durch
U
simulierten Experiment
simuliert, wobei
E
S
A
erfolgreich sein. Die Wahrscheinlichkeit, dass dieses Experiment
1
ausgibt wird folglich
etwa
1
/
2
sein. Der Unterscheider
U
wird, im Vergleich zur Realwelt, also seltener ver-
muten, in der Realwelt zu laufen. Insgesamt wird der Vorteil von
U
, der ein Maß dafür
ist, wie gut
U
zwischen Real- und Zufallswelt unterscheiden kann, recht hoch sein. Wir
werden dieses informelle Argument nun präzisieren.
Dazu schauen wir uns zunächst den Erfolg von
U
an, also die Wahrscheinlichkeit, dass
U
das Bit
1
ausgibt, was der Vermutung »Realwelt« entspricht, falls
U
tatsächlich in der
Realwelt läuft. Dies sollte, wie gesagt, der Wahrscheinlichkeit entsprechen, dass
E
A
das
Bit
1
liefert. In der Tat können wir direkt Folgendes festhalten:
)
(1
=Prob
S
=1
PRF
U
suc
PRF
(
U,
B
b
=1
(2
=Prob
E
A
=1
(3
=
adv
(
A,
S
)+1
.
(5.4.2)
2
PRF
U
E
A
Dabei erhalten wir
(2)
,dain
S
b
=1
genau
simuliert wird und
U
das Bit
1
E
A
der Fall ist. Man beachte,
ausgibt, genau dann, wenn dies in der Simulation von
E
A
,die
U
nicht direkt simuliert, in
PRF
U
dass die Chiffrewahl in
S
b
=1
erfolgt. Die
Gleichungen
(1)
und
(3)
ergeben sich direkt aus den Definitionen.
Wenden wir uns nun dem Misserfolg fail
PRF
(
U,
B
)
von
U
zu, also der Wahrscheinlich-
S
S
A
simuliert, wobei
S
das R-CTR-Kryptoschema bezeichnet, bei dem als Block-Kryptosystem die zufällige
Funktion verwendet wird. Wir wollen uns nun klar machen, dass die Wahrscheinlichkeit,
dass
A
richtig bestimmt, ob die linke oder rechte Angebotshälfte verschlüsselt wurde,
lediglich
keit
Prob
{
S
=1
}
S
= S
PRF
U
S
wird das Experiment
,mit
b
=0
.In
{
S
=1
1
/
2
.
Um dies zu beweisen, überlegen wir uns zunächst, von welcher Form die Antworten
sind, die der (simulierte) Angreifer
A
vom (simulierten) Verschlüsselungsorakel
Sim(
≈
1
/
2
ist. Damit ist dann auch
Prob
}≈
·
,F
)
geliefert bekommt. In einem Lauf von
S
stellt
A
gemäß Annahme höchstens
q
1
Ora-
kelanfragen, plus einem Angebot, im Umfang von insgesamt höchstens
nl
-Blöcken. Wir
gehen im Folgenden der Einfachheit halber davon aus, dass
A
genau
q
−
1
Orakelanfra-
gen, plus einem Angebot, macht. Alle Abschätzungen gelten ebenso, wenn
A
weniger
Orakelanfragen macht. Es bezeichnen im Folgenden
x
1
,...,x
q−
1
∈{
−
l∗
die von
A
0
,
1
}
