Cryptography Reference
In-Depth Information
zur Verschlüsselung gewählte Angebotshälfte,
z
=
z
1
−c
(
α
)
sei die andere Angebotshälfte
und
r
q
der zur Verschlüsselung von
z
gewählte initiale Zähler. Damit hat die in diesem
Lauf zurückgelieferte Probe
y
=
y
(
α
)
, also der Chiffretext zu
z
,dieForm
y
=
r
q
·
(
F
(
r
q
)
⊕ z
(0)
)
· ··· ·
(
F
(
r
q
+
2
l
(
n
q
−
1))
⊕ z
(
n
q
−
1)
)
.
Es sei nun
α
=
β
(
α
)
der Lauf, der genau mit
α
übereinstimmt, bis auf die folgenden
Änderungen. Das Bit
c
(
α
)
werde gekippt, für
α
gelte also
c
(
α
)=1
c
(
α
)
. Außerdem
sei die in
α
gewählte Chiffre
F
=
F
(
α
)
wie folgt definiert:
F
(
j
)=
F
(
j
)
für alle
j∈{r
q
,r
q
+
2
l
1
,...,r
q
+
2
l
(
n
q
−
1)
}
−
und
F
(
r
q
+
2
l
i
)=
F
(
r
q
+
2
l
i
)
z
[
i
⊕
z
[
i
·
l,
(
i
+1)
·
l
)
⊕
·
l,
(
i
+1)
·
l
)
(5.4.10)
für alle
i
∈{
0
,
...,
n
q
−
1
}
.
Wegen
α ∈ Coll
gilt offensich
tlich
auch
α
∈ Coll
, da die Zähler in
α
genauso gewählt
sind wie in
α
. Die Annahme
α
r
q
,r
q
+
2
l
1
,...,r
q
+
2
l
n
q
−
1
}
für die Beantwortung des Angebots an keiner anderen Stelle auftreten. Der Wechsel
von
F
(in
α
)hinzu
F
(in
α
) hat also auf die gelieferten Antworten für die von
A
gestellten Orakelanfragen keinerlei Auswirkung. Insbesondere ist die Sicht von
A
bis zur
Unterbreitung des Angebots in
α
und
α
identisch. Folglich liefert
A
in beiden Läufen
dasselbe Angebot. Gemäß der Definition von
α
wird im Lauf
α
die Angebotshälfte
z
,
statt
z
, verschlüsselt. Nach Konstruktion von
F
ist aber die zurückgelieferte Probe, also
der Chiffretext zu
z
, genau die für
z
im Lauf
α
gelieferte Probe, nämlich
y
.Demnach
bleibt die Sicht von
A
auch nach Unterbreitung des Angebots gleich. Folglich liefert
A
dieselbe Ausgabe, d. h., es gilt
c
(
α
)=
c
(
α
)
.Aberdain
α
∈ Coll
bedeutet, dass die Zähler
{
das Bit
c
gekippt ist, d. h.,
c
(
α
)=1
c
(
α
)
, erhalten wir, wie gewünscht, dass
c
(
α
)=
c
(
α
)
gilt, genau dann,
wenn
−
c
(
α
)
=
c
(
α
)
gilt. Es bleibt noch zu zeigen, dass
β
eine bijektive Abbildung von
Coll
nach
ist. Davon kann man sich aber leicht überzeugen (siehe Aufgabe 5.7.9).
Mit (5.4.2) und (5.4.8) ergibt sich nun für den Vorteil von
U
:
Coll
adv
PRF
(
U,
B
)=
suc
PRF
(
U,
B
)
−
fail
PRF
(
U,
B
)
adv
(
A,
S
)+1
(
1
2
+
qn
≥
−
2
l
)
2
=
adv
(
A,
S
)
qn
2
l
−
.
2
Mit Hilfe des PRP/PRF-Switching Lemmas (Lemma 4.8.1) folgt sofort
n
2
2
l
+1
adv
(
A,
S
)
qn
2
l
−
adv
PRP
(
U,B
)
≥
−
2
2
qn
+
n
2
2
l
+1
adv
(
A,
S
)
≥
−
2
und damit (5.4.1).
Nach Konstruktion ist auch klar, dass
U
höchstens
n
Orakelanfragen macht. Außerdem
ist die Laufzeit von
E
A
,dienach
Annahme durch
t
beschränkt ist. In der Zufallswelt werden Orakelanfragen in
E
U
,wenn
U
in der Realwelt läuft, gleich zur Laufzeit von
E
U
durch