Cryptography Reference
In-Depth Information
E
M
F
E
F
definiert werden und umgekehrt:
1
Es sei also
α
ein Lauf von
. Der korrespon-
dierende Lauf
α
von
E
F
ist derjenige Lauf, bei dem die Schlüssel
k
h
und
k
m
wie in
α
gewählt werden. Zudem werden in der Simulation von
F
in
α
die gleichen Zufallsbits
verwendet wie für
F
im Lauf
α
. Die Abbildung
β
,dieeinenLauf
α
wie beschrieben auf
einen Lauf
α
abbildet, ist offensichtlich eine Bijektion von der Menge der Läufe von
E
M
F
E
F
. Zudem ist die Wahrscheinlichkeit für das Auftreten von
α
gleich der Wahrscheinlichkeit des korrespondierenden Laufs
β
(
α
)
.
Des Weiteren ist leicht zu sehen, dass, wenn
F
in einem Lauf
α
von
in die Menge der Läufe von
E
M
F
erfolgreich ist,
im Sinne von Definition 9.2.1 (über die Zulässigkeit machen wir zunächst keine Aussage),
dann ist es auch
F
im korrespondierenden Lauf
α
:Wenn
F
das Paar
(
x, t
)
zurückgibt
und die Berechnung erfolgreich ist, dann gilt
t
=
T
(
x,
(
k
h
,k
m
)) =
T
(
p
(
h
k
h
(
x
))
,k
m
)
.Da
F
in diesem Fall
(
p
(
h
k
h
(
x
))
,t
)
zurückgibt, ist
F
ebenfalls erfolgreich. Diese Beobachtung
halten wir im folgenden Lemma fest.
E
M
F
Lemma 9.4.1.
Wenn
F
ineinemLaufvon
erfolgreich ist, dann ist es auch
F
i
m
E
F
korrespondierenden Lauf von
.
Was allerdings nicht stimmen muss, ist folgende Aussage: Wenn eine Berechnung von
F
zulässig ist, dann auch die korrespondierende Berechnung von
F
. Wir werden aber
nun sehen, dass wir in einem solchen Fall eine Kollision für
h
k
h
finden können. Dazu
betrachten wir den folgenden Kollisionsfinder
C
, der, ähnlich wie
F
,dasExperiment
E
M
F
simuliert. Wiederum wird die Schlüsselwahl nur teilweise simuliert: Der Schlüssel
k
h
für die Hashfunktion wird von
C
nicht selbst erzeugt. Zur Simulation der Hashfunktion
verwendet
C
sein Hashorakel. Den Schlüssel
k
m
für den MAC erzeugt
C
selbst. Genauer
ist
C
wie folgt definiert:
}
≤L
1.
Wähle Schlüssel für Etikettieralgorithmus zu
}
≤L
n
):
}
≤L
C
(
H
:
{
0
,
1
→{
0
,
1
}
{
0
,
1
×{
0
,
1
M
zufällig.
k
m
=
flip
(
K
M
)
2.
Initialisiere Menge mit Hashwerten.
S
=
∅
3.
Simuliere
F
.
F
mit folgenden Änderungen:
a. Eine Anfrage
x
von
F
an das Etikettierorakel wird wie folgt beantwortet:
v
=
H
(
x
)
x
=
p
(
v
)
t
=
T
(
x
,k
m
)
S
=
S
}
gib
t
zurück an den simulierten Algorithmus
F
b. Wenn
F
das NE-Paar
(
x, t
)
ausgibt, ersetze die Ausgabe wie folgt:
i.
Bestimme Hashwert.
v
=
H
(
x
)
∪{
(
x, v
)
1 Zur Erinnerung: Wir fassen dabei die Wahrscheinlichkeitsräume der Experimente, wie in Ab-
schnitt 4.6.2 besprochen und wie bereits häufiger in anderen Beweisen dieser Art gesehen, als
Produkträume auf. Läufe dieser Experimente werden wie üblich als Elemente (also Tupel) dieser
Produkträume repräsentiert.
