Cryptography Reference
In-Depth Information
a.
Schlüsselwahl
Es wird nur ein Schlüssel
k
m
=
flip
(
K
MAC
)
für
gewählt; die Verschlüs-
selung mit dem Basisschema wird von
O
übernommen.
b.
Anfragen
x
von
A
an das Chiffrierorakel
c
=
O
(
x
)
t
=
T
(
c, k
m
)
S
=
S ∪{
(
x, c,t
)
}
gib
(
c, t
)
an den simulierten Algorithmus
A
zurück
c.
Unterbreitung eines Angebots
(
x
0
,x
1
)
von
A
Liefert
A
ein Angebot
(
x
0
,x
1
)
,soliefert
A
eben dieses Angebot an sein
Orakel. Ist
c
die Probe, die
A
als Antwort zurückbekommt, dann fährt
A
wie folgt fort:
t
=
T
(
c, k
m
)
S
=
S ∪{
(
x, c,t
)
}
gib
(
c, t
)
an den simulierten Algorithmus
A
zurück
d.
Anfragen
(
c, t
)
von
A
an das Dechiffrierorakel
falls
x
existiert mit
(
x, c,t
)
∈ S
,gib
x
an den simulierten Algorithmus
A
zurück
sonst, falls
t
=
T
(
c, k
m
)
,gib
M
⊥
an den simulierten Algorithmus
A
zurück
sonst, Ausgabe
0
und halt
(»Gib auf.«)
Es bezeichne
E
CPA
giveup
A
der Angreifer
A
eine
Anfrage an das Dechiffrierorakel nicht beantwor
ten ka
nn (letzter Fall in d.). Man sieht
leicht, da
ss ein
Lauf im Ereignis »
E
S
CPA
das Ereignis, dass in einem Lauf von
E
S
CPA
A
=1
, E
CPA
giveup
« genau einem Lauf im Ereignis
E
A
=1
, E
CCA
⊥
»
« entspricht. In der Tat ist es leicht, eine Bijektion zwischen den Läufen
dieser Ereignisse anzugeben, so dass korrespondierende Läufe i) die gleiche Wahrschein-
lichkeit haben, ii) die Sichten von
A
genau gleich sind und (deshalb) iii) die Ausgaben
der Experimente übereinstimmen (siehe Aufgabe 9.8.12). Damit folgt:
Prob
=Prob
giveup
E
S
CPA
A
E
A
=1
, E
CCA
⊥
=1
,E
CPA
≤
Prob
=1
.
(9.7.2)
E
S
CPA
A
Wir wenden uns nun der Abschätzung von
Prob
E
CCA
⊥
zu. Der erwähnte Fälscher
F
simuliert ähnlich wie
A
das Experiment
E
A
. Anders als
A
hofft
F
aber darauf, dass das
Ereignis
E
CCA
⊥
eintritt. Der Fälscher
F
rät, in welcher Anfrage von
A
an das Dechiffrier-
orakel ein neuer und gültiger Chiffretext geliefert wird. Tritt das Ereignis
E
CCA
⊥
ein und
rät
F
korrekt, dann hat
F
den MAC erfolgreich »gebrochen«.
Genauer ist der Fälscher
F
, der Zugriff auf das Etikettierorakel
O
des MACs
M
hat,
wie folgt definiert, wobei, wie oben bereits festgelegt,
q
die maximale Anzahl der Anfragen
bezeichnet, die
A
an sein Dechiffrierorakel stellt:
}
∗
×{
}
∗
F
(
O
):
{
0
,
1
0
,
1
1.
Initialisierung
S
=
∅
