Cryptography Reference
In-Depth Information
schreiben können, wobei in
V
i
genau
i
1
Anfragen an das Verschlüsselungsorakel
H
und
in
W
i
genau
q − i
Anfragen gestellt werden, jede von der Form
y
j
=
H
(
x
j
)
.
Mit diesen Annahmen lässt sich
A
i
beschreiben:
−
l∗
→{
0
,
1
}
∗
):
{
0
,
1
}
A
i
(
H
:
{
0
,
1
}
AF
(
H
)
:
1.
Simuliere ersten Teil von
U
.
V
i
2.
Sende Angebot
x
i
=
flip
(
)
.
sende
(
x
i
,x
i
)
AG
(
H,y
i
)
:
3.
Simuliere zweiten Teil von
U
mit folgender Modifikation:
W
i
mit
y
j
=
H
(
x
j
)
ersetzt durch
y
j
= rand-
H
(
x
j
)
.
|
x
i
|
Der Angreifer
A
i
simuliert also in den ersten
i
1
Anfragen die Realwelt für
U
.Jenach
Wahl von
b
, wird die
i
-te Anfrage gemäß Real- (
b
=1
) bzw. Zufallswelt (
b
=0
) simuliert.
Für die restlichen Anfragen wird dann die Zufallswelt von
U
simuliert.
Insbesondere gilt, dass
A
q
bis zur einschließlich
(
q
−
1)
-ten Anfrage immer die Realwelt
für
U
simuliert. Ist zudem
b
=1
,dannwirdauchinder
q
-ten Anfrage die Realwelt für
U
simuliert. Es gilt also
suc
(
A
q
,S
)=Prob
−
S
A
q
b
=1
=1
=Prob
S
U
b
=1
=1
=
suc
RR
(
U,S
)
.
Analog gilt
fail
(
A
1
,S
)=Prob
S
A
1
b
=0
=1
=Prob
S
U
b
=0
=1
=
fail
RR
(
U,S
)
.
Wir können deshalb festhalten:
Lemma 5.5.3.
adv
RR
(
U,
S
)=
suc
(
A
q
,
S
)
−
fail
(
A
1
,
S
)
.
Als Nächstes beobachten wir, dass sich
A
i
in der
1
-Welt genauso wie
A
i
+1
in der
0
-Welt verhält: In der
1
-Welt werden bei
A
i
alle Anfragen ab der
(
i
+1)
-ten zufällig
beantwortet und alle davor real; genauso wie für
A
i
+1
in der
0
-Welt. Insbesondere gilt
=1
=Prob
=1
und damit:
Prob
S
A
i
S
A
i
+1
b
=1
b
=0
Lemma 5.5.4.
suc
(
A
i
,
S
)=
fail
(
A
i
+1
,
S
)
für alle
0
<i<q
.
Wir konstruieren nun aus
U
den gewünschten Angreifer
A
∗
. Dieser führt einfach zu-
fällig einen der Angreifer
A
i
aus:
