Cryptography Reference
In-Depth Information
Analog zum Hash-then-MAC-Ansatz erhalten wir folgendes Lemma.
Lemma 10.3.1.
Wenn
F
ineinemLaufvon
E
S
F
erfolgreich ist (im Sinne von Defi
ni
-
tion 10.1.2), dann ist auch
F
im korrespondierenden Lauf von
E
F
erfolgreich.
Wie im Fall des Hash-then-MAC-Ansatzes muss die zu einer zulässigen Berechnung
von
F
korrespondierende Berechnung von
F
nicht notwendigerweise auch zulässig sein,
da Kollisionen für
h
k
h
auftreten können. In dem Fall ist aber ein entsprechend definierter
Kollisionsfinder
C
erfolgreich:
C
(
k
h
:
K
H
):
X
×
X
1.
Wähle Schlüsselpaar für Signieralgorithmus des Basisschemas
S
zufällig.
(
k,k
)=
G
()
2.
Initialisiere Menge mit Hashwerten.
S
=
∅
3.
Simuliere
F
.
F
mit öffentlichem Schlüssel
(
k
h
,k
)
und folgenden Änderungen:
a. Eine Anfrage
x
von
F
an das Signierorakel wird wie folgt beantwortet:
v
=
h
k
h
(
x
)
x
=
p
(
v
)
t
=
T
(
x
, k
)
S
=
S
}
gib
t
zurück an den simulierten Algorithmus
F
b. Wenn
F
das NSP
(
x, t
)
ausgibt, ersetze die Ausgabe wie folgt:
i.
Bestimme Hashwert.
v
=
h
k
h
(
x
)
ii.
Überprüfe, ob Kollision vorliegt.
falls
v ∈{v
|
∪{
(
x, v
)
es gibt ein
x
mit
(
x
,v
)
∈ S}
Bestimme
x
, so dass
(
x
,v
)
∈
S
.
gib
(
x, x
)
zurück
sonst
gib
(
x, x
)
zurück
Wie im Hash-then-MAC-Ansatz können wir folgendes Lemma zeigen.
E
S
F
die Berechnung von
F
zulässig, aber die
Berechnung von
F
im korrespondierenden Lauf von
Lemma 10.3.2.
Ist in einem Lauf
α
von
E
F
ist nicht zulässig, dann liefert
E
C
C
im zu
α
korrespondierenden Lauf von
eine Kollision für die Familie
H
v
on
Hashfunktionen.
Aus den beiden vorangehenden Lemmas erhalten wir, analog zum Hash-then-MAC-
Ansatz, folgenden Satz.
S
=
HashSign
[
H ,p,S
]
ein Hash-then-Sign-Schema gemäß Defi-
nition 10.3.1. Weiter sei
F
ein Fälscher für
Satz 10.3.1.
Es sei
S
und seien
F
und
C
wie oben definiert.
Dann gilt:
adv
Sig
(
F
,
S
)
≤
adv
Sig
(
F,
S
)+
adv
Coll
(
C,
H
)
.
