Cryptography Reference
In-Depth Information
zu illustrieren, werden wir zunächst eine Charakterisierung des Vorteils eines Unterschei-
ders durch den sogenannten Erfolg bzw. Misserfolg des Unterscheiders beweisen. Dadurch
erhalten wir zum einen einen etwas anderen Blickwinkel auf die bisherige Definition. Zum
anderen ist die äquivalente Darstellung bei Sicherheitsanalysen häufig leichter zu handha-
ben. Erfolg und Misserfolg werden in der folgenden Definition präzise gefasst. Die Idee ist
die folgende: Der Erfolg gibt die Wahrscheinlichkeit dafür an, dass, unter der Bedingung,
dass der Unterscheider in der Realwelt läuft, er dies auch vermutet, also
1
ausgibt. Um-
gekehrt gibt der Misserfolg die Wahrscheinlichkeit dafür an, dass, unter der Bedingung,
dass der Unterscheider in der Zufallswelt läuft, er trotzdem vermutet in der Realwelt zu
laufen, also
1
ausgibt.
Definition 4.7.4 (Erfolg und Misserfolg). Es sei
U
ein
l
-Unterscheider auf ein Block-
Kryptosystem
S
U
das zugehörige verkürzte Experiment.
Der
Erfolg (success)
und der
Misserfolg (failure)
von
U
bzgl.
B
und
S
=
B
sind gegeben durch
suc
(
U,
B
)=Prob
{
S
b
=1
=1
}
und
fail
(
U,B
)=Prob
{
S
b
=0
=1
}
,
wobei wir die in Abschnitt 4.6.2 eingeführte Schreibweise verwenden.
Der Vorteil eines Unterscheiders ist nun einfach die Differenz zwischen Erfolg und
Misserfolg.
Lemma 4.7.1 (Vorteil, Erfolg, Misserfolg).
ES sei
l>
0
.Fürjeden
l
-Unterscheider
U
und jedes
l
-Block-Kryptosystem
B
gilt
adv
(
U,
B
)=
suc
(
U,
B
)
−
fail
(
U,
B
)
.
E = E
U
S = S
U
Beweis.
Mit
und
erhalten wir:
(1
=Prob
Prob
{
E
=1
}
{
S
=
b
}
(2
=Prob
{
S
=
b, b
=1
}
+Prob
{
S
=
b, b
=0
}
(3
=Prob
{
S
=
b
|
b
=1
}·
Prob
{
b
=1
}
+
Prob
{
S
=
b
|
b
=0
}·
Prob
{
b
=0
}
1
2
+Prob
1
2
(4
=Prob
{
S
b
=1
=1
}·
{
S
b
=0
=0
}·
1
2
+(1
−
Prob
{
S
b
=0
=1
}
)
·
1
2
(5
=Prob
{
S
b
=1
=1
}·
1
2
+(1
1
2
(6
=
suc
(
U,
B
)
·
−
fail
(
U,
B
))
·
,
wobei sich die Gleichungen wie folgt ergeben: (
1
) folgt direkt aus der Definition von
E
und
S
(siehe auch Abschnitt 4.6.2)
sowie aus der Tatsache, dass
Prob
{b
=1
}
=Prob
{b
=0
}
=1
/
2
gilt; (6) gilt wegen
Definition 4.7.4; alle anderen Gleichungen sind elementare Wahrscheinlichkeitstheorie.
;(
4
) folgt aus der Definition von
S
b
=1
bzw.
S
b
=0
