Cryptography Reference
In-Depth Information
Prob
Y
PRF
=
y
·
Prob
Y
PRF
=
y | C
(3
=
PRF
U
S
0
=1
|
(
y
1
,...,y
q
)
∈T
Prob
Y
PRP
=
y
Prob
Y
PRF
=
y
C
(4
=
PRP
U
S
0
=1
|
·
|
(
y
1
,...,y
q
)
∈T
Prob
Y
PRP
=
y
1
(5
=
PRP
U
S
0
=1
|
·
2
l
·
(2
l
−
1)
···
(2
l
−
(
q
−
1))
(
y
1
,...,y
q
)
∈T
Prob
Y
PRP
=
y
Prob
Y
PRP
=
y
(6
=
PRP
U
S
0
=1
|
·
(
y
1
,...,y
q
)
∈T
(7
=Prob
S
0
=1
PRP
U
(8
=
fail
PRP
(
U,
)
,
wobei (
1
) aus der Tatsache folgt, dass
Prob
Y
PRF
=
y
B
C
=0
ist, falls unter den
Funktionswerten eine Kollision auftritt, also
y
i
=
y
j
für ein
i
und ein
j
m
it
i
|
=
j
gilt. Wir erhalten (
2
) aus Lemma 3.3.3. Gleichung (
3
) gilt, da das Ereignis
C
durch
»
Y
PRF
=
y
« impliziert wird, falls unter den Funtkionswerten keine Kollision auftritt.
Aus (4.8.3) folgt direkt (
4
). Die Gleichungen (
5
), (
6
)und(
7
) ergeben sich aus einfachen
wahrscheinlichkeitstheoretischen Kalkulationen und der Tatsache, dass Orakelanfragen
unabhängig von allen anderen Zufallsentscheidungen beantwortet werden und dass für
die Werte von
Y
PRP
nie Kollisionen auftreten können.
Wir erhalten nun
fail
PRF
(
U,B
)=Prob
S
0
=1
PRF
U
=Prob
S
0
=1
| C
·
Prob
C
+
PRF
U
Prob
S
0
=1
| C
·
Prob
{C}
PRF
U
Prob
C
+
=
fail
PRP
(
U,
B
)
·
Prob
S
C
·
PRF
U
0
=1
|
Prob
{
C
}
.
Zum einen folgt mit (4.8.2) daraus
fail
PRP
(
U,B
)+
q
·
(
q
−
1)
fail
PRF
(
U,B
)
≤
.
2
l
+1
Zum anderen gilt
fail
PRP
(
U,B
)
·
Prob
C
=
fail
PRP
(
U,
fail
PRF
(
U,B
)
≥
B
)
·
(1
−
Prob
{
C
}
)
q
·
(
q
−
1)
2
l
+1
≥
fail
PRP
(
U,
B
)
−
.
