Cryptography Reference
In-Depth Information
Definition 4.7.1. Ein
l
-Unterscheider
ist ein zufallsgesteuerter Algorithmus der Form
U
(
F
:
{
0
,
1
}
l
→{
0
,
1
}
l
):
{
0
,
1
}
, dessen Laufzeit durch eine Konstante nach oben be-
schränkt ist.
Ein Unterscheider erhält also ein Orakel
F
. Dieses Orakel ist eine Funktion, welche
er mit Bitvektoren der Länge
l
befragen kann und welche Bitvektoren der Länge
l
als
Antwort zurückliefert.
Wir lassen den Unterscheider nun in einem Experiment in einer von zwei unterschiedli-
chen sogenannten Welten laufen. In der ersten Welt, der sogenannten
Realwelt
,wirddem
Unterscheider eine zufällig gewählte Chiffre des betrachteten Block-Kryptosystems als
Orakel gegeben. In der zweiten Welt, der sogenannten
Zufallswelt
, wird dem Angreifer ei-
ne zufällig gewählte Substitutionschiffre als Orakel gegeben. Der Unterscheider muss dann
entscheiden, in welcher der beiden Welten er glaubt zu laufen. Wir vereinbaren, dass er
1
für »Realwelt« und
0
für »Zufallswelt« ausgibt. Die Güte des Unterscheiders wird dann ein-
fach nach seiner »Gewinnwahrscheinlichkeit« bemessen, also danach wie gut er zwischen
den beiden Welten unterscheiden kann. Wir werden später ein Block-Kryptosystem si-
cher nennen, wenn die Gewinnwahrscheinlichkeit jedes (geeignet) ressourcenbeschränkten
Unterscheiders klein ist.
Das beschriebene Experiment formalisieren wir nun wie folgt, wobei
P
{
0
,
1
}
l
die Menge
l
, also die Menge aller Substitutionschiffren auf
l
,
aller Permutationen auf
{
0
,
1
}
{
0
,
1
}
bezeichnet.
Definition 4.7.2 (Experiment zu einem Unterscheider und einem Block-Kryptosystem).
Es sei
l>
0
,
U
ein
l
-Unterscheider und
ein
l
-Block-Kryptosystem mit Schlüsselraum
K
. Das zugehörige
Experiment
,
3
das wir mit
B
E
U
,
E
U
oder einfach
E
bezeichnen, ist der
Algorithmus, der gegeben ist durch:
E
:
}
1.
Wähle Real- oder Zufallswelt.
b
=
flip
()
falls
b
=1
, so setze
k
=
flip
(
K
)
und
F
=
E
(
{
0
,
1
·
,k
)
, sonst setze
F
=
flip
(
P
{
0
,
1
}
l
)
2.
Ratephase
b
=
U
(
F
)
3.
Auswertung
falls
b
=
b
,sogib
1
zurück, sonst
0
.
S
U
,
Mit
S
U
oder einfach
S
bezeichnen wir den Algorithmus, der aus
E
dadurch entsteht,
dass der dritte Schritt ersetzt wird durch »gib
b
zurück«. Wir nennen
S
U
das
verkürzte
E
U
).
Experiment
(zu
also erfolgreich, wenn seine Vermutung
b
mit dem tatsächlich gewählten
b
übereinstimmt, er also korrekt bestimmt hat, in welcher
Welt er läuft. Die Wahrscheinlichkeit dafür lässt sich nun schreiben als
Prob
Ein Unterscheider besteht das Experiment
E
{
E
=1
}
,
d. h., die Wahrscheinlichkeit, dass der Algorithmus
E
die Zahl
1
ausgibt.
3 In der kryptographischen Literatur spricht man manchmal auch von einem Spiel (
game
).
