Cryptography Reference
In-Depth Information
die zufällige Funktion beantworten, was höchstens
c
l
)
zusätzliche Schritte
benötigt, für eine Konstante
c
:Bei
n
Orakelanfragen müssen maximal
n
Funktionswerte
zufällig bestimmt werden, also
n
·
(
q
·
log(
q
)
·
l
+
n
·
l
Zufallsbits erzeugt werden. Um festzustellen, ob die
zufällige Funktion mehrfach an der gleichen Stelle ausgewertet wird, muss der Abstand
zwischen benachbarten initialen Zählern bestimmt werden, was höchstens
c
·
·
q
·
log(
q
)
·
l
viele Rechenschritte benötigt. Dies schließt den Beweis von Satz 5.4.1 ab.
5.5
Ein alternativer Sicherheitsbegriff
Der bislang für Kryptoschemen benutzte Sicherheitsbegriff wird in der Literatur häufig
als »Find-then-Guess« bezeichnet, da ein Angreifer in einer Findungsphase zunächst ein
Angebot finden muss und dann raten muss, welche Angebotshälfte verschlüsselt wurde.
Durch verschiedene Beispiele und Plausibilitätsbetrachtungen haben wir einige Indizien
dafür gesammelt, dass dieser Sicherheitsbegriff, den wir im Folgenden auch kurz mit FG-
Sicherheit bezeichnen wollen, sinnvoll ist. Um weiteres Vertrauen in diesen Sicherheitsbe-
griff zu gewinnen, werden wir in diesem Abschnitt einen alternativen Sicherheitsbegriff
studieren, den wir mit
RR-Sicherheit
(»Real-or-Random«) bezeichnen, und zeigen, dass
beide Sicherheitsbegriffe - FG- und RR-Sicherheit - im Wesentlichen zu den gleichen
Ergebnissen führen.
Dem neuen Sicherheitsbegriff liegt die folgende abstrakte Überlegung zugrunde. Bei ei-
nem guten symmetrischen Kryptoschema sollte es dem Angreifer nicht gelingen, zwischen
der Verschlüsselung von durch den Angreifer gewählten Nachrichten und der Verschlüs-
selung zufälliger Nachrichten zu unterscheiden. Dies kann, wie wir sehen werden, leicht
als Spiel zwischen einem Unterscheider (Eva) und dem Verschlüsselungsorakel (Charlie)
formuliert werden. Die RR-Sicherheit erinnert ein wenig an den Sicherheitsbegriff für
Block-Kryptosysteme, bei dem ein Unterscheider zwischen der Interaktion mit dem ei-
gentlichen Block-Kryptosystem und einer zufälligen Permutation unterscheiden musste.
Allerdings ist, wie bereits zu Beginn von Kapitel 5 erwähnt, der Sicherheitsbegriff für
Block-Kryptosysteme für Kryptoschemen nicht geeignet.
Wir werden nun zunächst die RR-Sicherheit definieren und in den beiden folgenden
Unterabschnitten die Äquivalenz zur FG-Sicherheit beweisen.
Definition 5.5.1 (Unterscheider). Ein
l
-Unterscheider
für symmetrische
l
-Kryptosche-
men ist ein zufallsgesteuerter Algorithmus der Form
U
(
H
:
l∗
→{
}
∗
):
{
0
,
1
}
0
,
1
{
0
,
1
}
,
dessen Laufzeit durch eine Konstante nach oben beschränkt ist.
Das erwähnte Spiel formalisieren wir nun wieder als Experiment.
Definition 5.5.2 (Experiment zu einem Unterscheider). Es sei
U
ein
l
-Unterscheider
und
=(
K,E,D
)
ein symmetrisches
l
-Kryptoschema. Die
Zufallsvariante
eines Ver-
schlüsselungsorakels
H
(
x
:
S
l∗
):
}
∗
ist definiert durch
{
0
,
1
}
{
0
,
1
l∗
):
{
0
,
1
}
∗
rand-
H
(
x
:
{
0
,
1
}
1.
x
=
flip
(
|x|
)
2.
y
=
H
(
x
)
3. gib
y
zurück
