Cryptography Reference
In-Depth Information
b
=
O
(
y
)
falls
b
=
x
(0)
,gib
1
zurück, sonst
0
.
Wir betrachten den folgenden Unterscheider, den wir auch kurz mit
U
bezeichnen
werden.
UnterscheiderErstesBit(
F
:
l
l
):
{
0
,
1
}
→{
0
,
1
}
{
0
,
1
}
1.
Wähle zufälligen Klartext.
x
=
flip
(
l
)
2.
Verschlüssel diesen Klartext durch Aufruf von
F
.
y
=
F
(
x
)
3.
Bestimme das erste Bit des Klartextes durch Aufruf von
O
.
b
=
O
(
y
)
4.
Gib Vermutung zurück.
falls
b
=
x
(0)
,gib
1
, sonst
0
zurück
Die Intuition ist wie folgt: Läuft
U
in der Realwelt, ist
F
also eine Chiffre von
,dann
sollte
O
mit großer Wahrscheinlichkeit, d. h., einer Wahrscheinlichkeit deutlich über
1
/
2
,
x
(0)
richtig bestimmen. Aus diesem Grund gibt
U
in einem Lauf
1
aus, d. h., »Realwelt«,
falls in diesem Lauf
O
das Bit
x
(0)
richtig bestimmt hat. Läuft
U
dagegen in der Zu-
fallswelt, so sollte die Wahrscheinlichkeit dafür, dass
O
das Bit
x
(0)
richtig bestimmt,
klein, d. h., etwa
1
/
2
, sein. Bestimmt
O
in einem Lauf das Bit
x
(0)
falsch, so vermutet
U
deshalb in der Zufallswelt zu laufen.
Wir schätzen nun Erfolg und Misserfolg von
U
ab, um seinen Vorteil zu bestimmen.
Es bezeichne im Folgenden
B
S
U
und
U
gehörende verkürzte Experiment.
Der Erfolg von
U
lässt sich leicht bestimmen. Offensichtlich gilt:
S
=
das zu
B
suc
(
U,
B
)=Prob
{
S
b
=1
=1
}
=Prob
{
E
bit
=1
}
3
4
≥
,
denn
E
bit
beschreiben dieselben Experimente.
Betrachten wir nun den Misserfolg von
U
.Ist
z ∈{
0
,
1
}
S
b
=1
und
l
, dann bezeichnen wir mit
z
denBitvektor,denmanaus
z
erhält, indem man das erste Bit kippt. Ist z. B.
z
= 0100
,
dann ist
z
= 1100
.Ist
π ∈P
{
0
,
1
}
l
l
, dann bezeichnen wir
mit
π
z
die Permutation, die man aus
π
durch Vertauschen der Werte an
z
und
z
erhält.
Es sei nun
z
eine Permutation über
{
0
,
1
}
l
,
π
S
=
∈{
0
,
1
}
∈P
{
0
,
1
}
l
und
S
b
=0
. Wir bezeichnen mit
α
(
z,π
)
den
S
,indem
x
=
z
und
F
=
π
gewählt wird.
4
Man sieht nun leicht, dass
Lauf von
S
(
α
(
z,π
)) = 1
−
S
(
α
(
z,π
z
))
(4.7.2)
4 Zur Erinnerung: Gemäß den Ausführungen in Abschnitt 4.6.2 und Abschnitt 4.6.3 können wir den
Wahrscheinlichkeitsraum zu
S
als Produktraum der Form
{
0
,
1
}
l
×P
{
0
,
1
}
l
auffassen. (Man beach-
te, dass
laut Annahme ein deterministischer Algorithmus ist, also keine Zufallsbits verwendet.)
Damit entspricht
O
α
(
z,π
)
dem Tupel
(
z,π
)
. Betrachtet man die partielle und dynamische Wahl von
S
lediglich einmal (mit
F
, wie nach Definition 4.7.2 beschrieben, und da
F
in
x
) aufgerufen wird,
S
auch alternativ den Produktraum
{
0
,
1
}
l
×{
0
,
1
}
l
betrachten, wobei die erste Kom-
kann man zu
ponente die Wahl von
x
festlegt und die zweite den Chiffretext zu
x
. Daraus ergeben sich noch
einfachere Beweise für die Bestimmung des Misserfolgs von
U
(siehe Aufgabe 4.9.18).
