Cryptography Reference
In-Depth Information
q
Orakelanfragen macht und
A
∗
der oben konstruierte Angreifer. Dann gilt
)=
1
adv
(
A
∗
,
S
q
·
adv
RR
(
U,
S
)
.
(5.5.4)
Beweis.
Es gilt
q
)
(1
=
1
adv
(
A
∗
,
S
q
·
adv
(
A
j
,
S
)
j
=1
q
(2
=
1
q
·
(
suc
(
A
j
,
S
)
−
fail
(
A
j
,
S
))
j
=1
q−
1
(3
=
1
fail
(
A
1
,S
)) +
1
q
·
(
suc
(
A
q
,S
)
−
q
·
(
suc
(
A
i
,S
)
−
fail
(
A
i
+1
,S
))
i
=1
(4
=
1
q
·
adv
RR
(
U,S
)
,
wobei (
1
) aufgrund von Lemma 5.5.5 gilt, (
2
) aus Lemma 5.3.1 folgt, (
3
) durch einfach
es
Umordnen entsteht und (
4
) sowohl Lemma 5.5.3 wie auch Lemma 5.5.4 nutzt.
E
U
genauer und
berücksichtigt man dabei auch den Fall, dass
U
weniger als
q
Orakelanfragen macht, so
kann man mit Hilfe (des Beweises) von Satz 5.5.2 die folgende Implikation zwischen der
FG- und der RR-Sicherheit zeigen.
E
A
∗
und
Untersucht man die maximalen Laufzeiten der Experimente
Folgerung 5.5.2 (FG-Sicherheit impliziert RR-Sicherheit).
Es existiert eine Konstante
c
, so dass für alle natürlichen Zahlen
l,n,q,t >
0
und jedes symmetrische
l
-Kryptoschema
S
gilt:
insec
RR
(
n, q, t,S
)
≤ q ·
insec
(
n, q, t
+
c · q,S
)
.
Der Beweis zu dieser Folgerung soll in Aufgabe 5.7.12 geführt werden.
Hybridtechnik. Wie am Anfang von Abschnitt 5.5.2 angedeutet, haben wir im Beweis
zu Satz 5.5.2 die sogenannte
Hybridtechnik
(auch
Hybridargument
genannt) verwendet.
Wir wollen hier noch verdeutlichen, was genau die Hybridtechnik ist und wann sie übli-
cherweise eingesetzt wird.
Die Hybridtechnik wird meist benutzt, wenn in einem Sicherheitsbeweis ein »komple-
xer Sachverhalt« auf einen »einfachen Sachverhalt« reduziert werden muss. Sie stellt somit
ein wichtiges Hilfsmittel bei Reduktionsbeweisen dar. Dabei kann ein »komplexer Sach-
verhalt« eine Aussage über die Sicherheit komplexer kryptographischer Primitive sein,
welche man auf die Sicherheit anderer einfacherer kryptographischer Primitive reduzie-
ren will, wobei im Rahmen der komplexen kryptographischen Primitive die einfachen
kryptographischen Primitive evtl. sogar mehrfach angewendet werden. Ein Beispiel da-
für werden wir in Abschnitt 6.6 kennenlernen, in dem es um die hybride Verschlüsselung
