Cryptography Reference
In-Depth Information
Insgesamt erhalten wir:
)=
1
)+
1
1
2
adv
RR
(
U,
S
2
·
adv
(
A,
S
2
−
=
1
2
·
adv
(
A,S
)
.
E
A
E
U
Manbeachte,dasssichdieLaufzeitenderExperimente
und
kaum unterschei-
den. Der wesentliche Unterschied ist, dass falls
E
U
in der Zufallswelt läuft, neben der
eigentlichen Verschlüsselung zusätzlich Klartexte zufällig gewählt werden müssen. Damit
erhöht sich die Laufzeit um maximal
c·n·l
, für eine (kleine) Konstante
c
, falls
A
insgesamt
maximal
nl
-Blöcke an sein Verschlüsselungsorakel schickt. Als unmittelbare Folgerung
aus Satz 5.5.1 erhalten wir deshalb:
Folgerung 5.5.1 (RR-Sicherheit impliziert FG-Sicherheit).
Es existiert eine kleine Kon-
stante
c
, so dass für alle natürlichen Zahlen
l
,
n
,
q
und
t
und jedes symmetrische
l
-
Kryptoschema
S
die Abschätzung
insec
(
n, q, t,S
)
≤
2
·
insec
RR
(
n, q, t
+
c
·
n
·
l,
S
)
gilt.
5.5.2
Von Unterscheidern zu Angreifern
Wir werden nun die Umkehrung zu der im vorherigen Unterabschnitt gezeigten Aussage
zeigen, nämlich dass aus der FG-Sicherheit die RR-Sicherheit folgt. Dazu konstruieren wir
aus einem gegebenen (guten) Unterscheider
U
einen (guten) Angreifer
A
. Konstruktion
und Beweis sind hier allerdings etwas aufwändiger als im vorherigen Unterabschnitt. Im
Beweis werden wir die in der Kryptographie häufig eingesetzte Hybridtechnik verwenden.
In einem ersten Schritt nehmen wir an, es wäre ein Unterscheider
U
gegeben, der in
jedem Lauf genau eine einzige Anfrage stellt. (Ein solcher Unterscheider wird in der Regel
keinen sonderlich großen Vorteil haben, aber für die Motivation der späteren Konstruk-
tion eignet er sich sehr gut.) Dann können wir uns vorstellen, dass
U
von der Form
V
;
y
=
H
(
x
)
;
W
(5.5.2)
ist, d. h., vor der Orakelanfrage führt
U
zunächst
V
aus und danach
W
. Aus einem
solchen Unterscheider
U
können wir leicht einen Angreifer
A
konstruieren:
l∗
}
∗
):
A
(
H
:
{
0
,
1
}
→{
0
,
1
{
0
,
1
}
AF
(
H
)
:
1.
Simuliere ersten Teil von
U
.
V
2.
Sende Angebot.
x
=
flip
(
)
sende
(
x
,x
)
|
x
|
