Cryptography Reference
In-Depth Information
i
=
flip
(
{
0
,...,q
−
1
}
)
j
=0
2.
Simuliere
E
A
E
A
mit folgenden Änderungen:
a.
Schlüsselwahl
Es wird nur ein Schlüssel
k
e
=
flip
(
K
CPA
)
für
S
CPA
gewählt; Etiketten
werden mit dem Etikettierorakel
O
berechnet.
b.
Anfragen
x
von
A
an das Chiffrierorakel
c
=
E
(
x, k
e
)
t
=
O
(
c
)
S
=
S
}
gib
(
c, t
)
an den simulierten Algorithmus
A
zurück
c.
Unterbreitung eines Angebots
(
x
0
,x
1
)
von
A
b
=
flip
()
c
=
E
(
x
b
,k
e
)
t
=
O
(
c
)
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
j
=
i
, dann Ausgabe
(
c, t
)
und halt
sonst
j
=
j
+1
falls
x
existiert mit
(
x, c,t
)
∪{
(
x, c,t
)
S
,
gib
x
an den simulierten Algorithmus
A
zurück
sonst, gib
∈
⊥
an den simulierten Algorithmus
A
zurück
Wir zeigen folgende Abschätzung:
)=Prob
E
F
=1
adv
MAC
(
F,
M
Prob
E
CCA
⊥
(9.7.3)
≥
.
q
Ähnlich wie im Fall für
A
erhält man diese Abschätzung, in dem man einem Lauf
α
in
E
CCA
⊥
in offensichtlicher Weise einen korrespondierenden Lauf
α
von
E
F
zuordnet. Die
Frage ist lediglich, wie man in
α
den Index
i
wählt, den es in
α
nicht gibt: Da
α
aus
E
CCA
⊥
stammt, liefert
A
in (mindestens) einer seiner Anfragen an das Dechiffrierorakel
einen neuen und gültigen Chiffretext. Wir wählen
i
als den Index
i
der ersten solchen
Anfrage in
α
.
Man sieht leicht, dass die Abbildung
β
, die, wie beschrieben, einen Lauf
α
aus
E
CCA
⊥
auf einen Lauf
α
von
E
F
abbildet, injektiv ist.
Wir machen uns nun klar, dass die Berechnung von
F
in
α
=
β
(
α
)
erfolgreich und zu-
lässig ist, was insbesondere bedeutet, dass im Lauf
α
von
E
F
das Bit
1
ausgegeben wird:
Für alle Chiffretexte, die
A
vor der
i
-ten Anfrage an sein Dechiffrierorakel geschickt hat,
gilt gemäß der Wahl von
i
, dass sie entweder vom Chiffrierorakel geliefert wurden (und
damit in
S
gespeichert sind) oder ungültig sind (und deshalb
⊥
zurückgegeben werden
