Cryptography Reference
In-Depth Information
S
eine Kollision im obigen
Es bezeichne
Coll
das Ereignis, dass in einem Lauf von
Sinne auftritt; formal ist
S
, in denen eine Kollision
auftritt. Das folgende Lemma erlaubt uns, die Wahrscheinlichkeit
Prob
Coll
also die Menge der Läufe von
{Coll}
für eine
Kollision abzuschätzen.
Lemma 5.4.1.
Es seien
l,q,n
1
,...,n
q
>
0
. Es bezeichne
P
die Gleichverteilung auf
dem
q
-fachen kartesischen Produkt
Ω
=
l
l
über
l
. Das Ereignis
{
0
,
1
}
×···×{
0
,
1
}
{
0
,
1
}
C
enthalte ein Tupel
(
r
1
,...,r
q
)
∈
Ω
genau dann, wenn
{
r
q
+
2
l
0
,...,r
q
+
2
l
(
n
q
−
1)
}∩
q−
1
i
=1
{
gilt. (Wir sprechen dann von einer Kollision.) Für
die Wahrscheinlichkeit einer Kollision gilt dann:
r
i
+
2
l
0
,...,r
i
+
2
l
(
n
i
−
1)
}
=
∅
qn
2
l
P
(
C
)
≤
,
mit
n
=
n
1
+
+
n
q
.
Beweis.
Es sei
S
=
q−
1
···
i
=1
{r
i
−
2
l
(
n
q
−
1)
,...,r
i
+
2
l
0
,...,r
i
+
2
l
(
n
i
−
1)
}
. Man sieht sofort:
(
r
1
,...,r
q
)
∈
C
genau dann, wenn
r
q
∈
S
. Weiter gilt
|
S
|≤
n
1
+
···
+
n
q−
1
+(
q
−
1)
·
n
q
≤
qn
. Damit folgt nun leicht die Behauptung.
S
die für die Beantwortung der Orakelanfragen (einschließlich des
Angebots) gewählten Zähler zufällig und unabhängig vom Rest des Laufes gewählt wer-
den, folgt nun leicht (siehe auch Aufgabe 5.7.8):
Da in Läufen von
Prob
{Coll}≤
P
(
C
)
(5.4.4)
qn
2
l
≤
.
(5.4.5)
Diese Abschätzung gilt auch, wenn der
l
-Angreifer
A
weniger als
q
Orakelanfragen macht
und/oder diese insgesamt kürzer als
n
sind, da dies die Wahrscheinlichkeit für eine Kol-
lision lediglich mindert.
Mit dem bisher Gezeigten erhalten wir für den Misserfolg von
U
:
=Prob
S
=1
,
Coll
+Prob
{
S
=1
{
S
=1
,
Prob
}
Coll}
Prob
S
=1
,
Coll
+Prob
≤
{Coll}
Prob
S
=1
,
Coll
+
qn
2
l
≤
.
(5.4.6)
Es bleibt also, den Misserfolg für den Fall zu betrachten, dass keine Kollision auftritt.
Wie bereits angedeutet, sollte der
l
-Angreifer
A
in diesem Fall nicht zwischen der Ver-
schlüsselung der linken und rechten Angebotshälfte unterscheiden können. In der Tat
werden wir nun
Prob
S
=1
| Coll
=
1
2
(5.4.7)
zeigen.
Dar
aus erhalten wir insbesondere
Prob
S
=1
,
| Coll
·
Prob
Coll
≤
2
. Mit (5.4.6) ergibt sich damit als Abschätzung für den Misserfolg von
Coll
=Prob
S
=1
