Cryptography Reference
In-Depth Information
Genauer konstruieren wir den
l
-Unterscheider
U
wie folgt. Es sei
l>
0
und
A
=
(
AF,AG
)
ein
l
-Angreifer.
l∗
}
∗
):
U
(
H
:
{
0
,
1
}
→{
0
,
1
{
0
,
1
}
1.
Simuliere Findungsphase.
(
z
0
,z
1
)=
(
H
)
2.
Wähle Angebotshälfte aus.
c
=
flip
()
y
=
H
(
z
c
)
3.
Simuliere Ratephase.
c
=
AF
(
H,y
)
4.
Gib Ergebnis zurück.
falls
c
=
c
,gib
1
, sonst
0
zurück
AG
E
A
nicht simuliert. Dies ist auch nicht nötig, denn
Man beachte, dass
U
die Chiffrewahl in
E
U
. In diesem Experiment wird eine Chiffre
H
(richtig oder
zufällig) bestimmt und
U
übergeben. Mit dieser Chiffre simuliert
U
das Experiment
U
läuft selbst im Experiment
E
A
.
Wir zeigen nun, dass der Vorteil von
U
dem Vorteil von
A
entspricht.
Satz 5.5.1.
Es seien
l>
0
,
A
ein
l
-Angreifer,
ein symmetrisches
l
-Kryptoschema
und
U
der oben konstruierte Unterscheider. Dann gilt
S
adv
RR
(
U,S
)=
1
2
·
adv
(
A,S
)
.
E
A
Beweis.
Zuerst können wir festhalten, dass
U
in der Realwelt genau das Experiment
simuliert. Wir erhalten also:
suc
RR
(
U,
S
)=Prob
{
S
U
b
=1
=1
}
=Prob
E
A
=1
=
1
adv
(
A,S
)+
1
2
2
·
.
Läuft
U
in der Zufallswelt (also
b
=0
), dann wird im vom
U
simulierten Experiment
E
A
das Verschlüsselungsorakel
rand-
H
verwendet. Also unabhängig davon, ob
c
=0
oder
c
=1
ist, wird
z
c
immer auf gleiche Weise verschlüsselt; es wird nämlich ein zufällig
gewählter Bitvektor
x
der Länge
|
z
0
|
(
=
|
z
1
|
) verschlüsselt. Die Sicht von
A
ist also in
S
S
S
=
, gleich verteilt. Deshalb wird
A
nicht zwi-
schen der Verschlüsselung der linken und rechten Angebotshälfte unterscheiden können.
Insbesondere wird sich
A
genau in der Hälfte der Fälle für die richtige/falsche Angebots-
hälfte entscheiden. Demnach wird die Wahrscheinlichkeit, dass im vom
U
simulierten
Experiment
1
ausgeben wird,
1
/
2
sein (siehe Aufgabe 5.7.11). Damit folgt:
c
=0
und
c
=1
,mit
S
U
b
=0
fail
RR
(
U,S
)=Prob
{
S
=1
}
=
1
2
.
(5.5.1)
