Cryptography Reference
In-Depth Information
Für den Erfolg können wir direkt
suc
PRP
(
U,
B
)=
suc
PRF
(
U,
B
)
(4.8.1)
PR
U
für den Fall
b
=1
völlig gleich verhalten.
Wir wenden uns nun dem Misserfolg von
U
zu. Im Folgenden schreiben wir kurz
PRF
U
festhalten, da sich
S
und
S
PRF
U
PRF
U
PRP
U
PRP
U
S
.
Zur Abschätzung des Misserfolgs betrachten wir das verkürzte Experiment
0
für
S
b
=0
und
S
0
für
S
b
=0
PRF
U
S
0
PRF
U
in der Zufallswelt. Es bezeichne
C
das Ereignis, dass in einem Lauf von
das
Orakel für zwei verschiedene Orakelanfragen (und damit verschiedene Klartexte) den
gleichen Funktionswert zurückgeliefert hat; da wir nun zufällige
Funktionen
betr
ac
hten,
kann es in der Tat vorkommen, dass Funktionswerte kollidieren. Es bezeichne
C
das
Gegenereignis zu
C
. Wir bezeichnen mit
Y
PRF
i
S
0
,
i
∈{
1
,...,q
}
, die Zufallsvariable, die für
PRF
U
einen Lauf von
den Wert des Funktionswertes annimmt, den das Orakel für die
i
-te Orakelanfrage zurückgeliefert hat. Entsprechend definieren wir
Y
PRP
i
S
0
für Läufe von
S
.
Nun können wir zunächst feststellen, dass Kollisionen (von Funktionswerten) nur mit
geringer Wahrscheinlichkeit auftreten. Mit Lemma 3.3.4 und der Sichtweise, dass zufällige
Funktionen partiell und dynamisch gewählt werden, erhalten wir sofort:
PRP
U
0
q
·
(
q
−
1)
Prob
{
C
}≤
.
(4.8.2)
2
l
+1
=
y
q
«mit»
Y
PRF
Im Folgenden kürzen wir »
Y
PRF
1
=
y
1
,...,Y
PRF
=
y
« und
q
=
y
1
,...,Y
PR
q
=
y
q
«mit»
Y
PRP
=
y
«ab.
Es ist leicht zu sehen, dass
Prob
»
Y
PRP
1
Y
PRF
=
y
=Prob
Y
PRP
=
y
PRF
U
PRP
U
S
0
=1
|
S
0
=1
|
(4.8.3)
gilt, falls
y
i
=
j
: Liegen die Antworten der Orakelanfragen bereits fest
und sind diese paarweise verschieden, dann verhalten sich
=
y
j
für alle
i
S
PRF
U
0
und
S
PRP
U
0
nämlich
gleich (siehe auch Aufgabe 4.9.24). Daraus können wir
Prob
S
C
=Prob
S
=1
PRF
U
PRP
U
0
=1
|
0
=
fail
PRP
(
U,
B
)
l
,y
i
folgern, denn mit
T
=
{
(
y
1
,...,y
q
)
|
y
i
∈{
0
,
1
}
=
y
j
für alle
i
=
j
}
gilt:
Prob
C
Prob
S
C
(1
=
=1
, Y
PRF
=
y
PRF
U
PRF
U
0
=1
|
S
0
|
(
y
1
,...,y
q
)
∈T
Prob
C, Y
PRF
=
y
(2
=
PRF
U
S
0
=1
|
·
(
y
1
,...,y
q
)
∈T
Prob
Y
PRF
=
y
C
|
