Cryptography Reference
In-Depth Information
Anhand des folgenden Beispiels werden wir den Umgang mit zufallsgesteuerten Al-
gorithmen einüben und dabei weitere Notation einführen, die für den Rest des Buches
wichtig sein wird.
Beispiel 4.6.1 (einfacher zufallsgesteuerter Algorithmus). Wir betrachten den folgenden
Algorithmus ohne Eingabe und Laufzeit
t ≥
4
(der genaue Wert von
t
spielt keine Rolle):
A
:
{
0
,
1
}
x
= 1110 (
∈{
0
,
1
}
4
)
b
0
=
flip
()
b
1
=
flip
()
b
2
=
flip
()
b
3
=
flip
()
falls
b
0
=1
,sogib
x
(0)
aus und halte
falls
b
1
=1
,sogib
x
(1)
aus und halte
falls
b
2
=1
,sogib
x
(2)
aus und halte
falls
b
3
=1
,sogib
x
(3)
aus und halte
gib
1
aus.
Für diesen Algorithmus gilt zum Beispiel
A
0100
w
=1
,
(4.6.1)
A
0001
w
=0
,
(4.6.2)
A
0000
w
=1
(4.6.3)
t−
4
,dennimLaufvon
A
in (4.6.1) ist
b
0
=0
und
b
1
=0
, in (4.6.2) ist
b
0
=
b
1
=
b
2
=0
und
b
3
=1
, in (4.6.3) ist
b
0
=
b
1
=
b
2
=
b
3
=0
.
Weiter gilt, zum Beispiel:
für alle
w ∈{
0
,
1
}
=Prob
{
t−
4
mit
w
= 0001
w
}
t
es gibt ein
w
∈{
Prob
{
A
=0
}
w
∈{
0
,
1
}
|
0
,
1
}
1
16
=
.
Häufig werden in einem zufallsgesteuerten Algorithmus Variablen mit Zufallsbits be-
legt. Im obigen Beispiel etwa
b
0
,...,b
3
. Diese Variablen kann man, genau wie den zu-
fallsgesteuerten Algorithmus selbst, als Zufallsvariablen über der Menge der Läufe des
Algorithmus auffassen. Um dies zu präzisieren, nehmen wir an, dass ein Algorithmus
A
(
x
)
mit Eingabe
x
gegeben ist, dessen Laufzeit durch
t
beschränkt ist. Damit kann
A
(
x
)
, wie besprochen, als Zufallsvariable über
t
aufgefasst werden. Wir nehmen
nun weiter an, dass in jedem Lauf von
A
(
x
)
der Variablen
y
höchstens einmal
ein Wert
zugewiesen wird, nämlich durch eine Zuweisung der Form
y
=
flip
(
l
)
. Damit kann auch
y
als Zufallsvariable über
{
0
,
1
}
{
0
,
1
}
t
t
aufgefasst werden: Für alle
α
∈{
0
,
1
}
ist entweder
l
oder
y
(
α
)=
y
(
α
)
∈{
0
,
1
}
⊥
,d.h.,
y
(
α
)
ist undefiniert. Für den Fall, dass in jedem Lauf
t
von
A
(
x
)
die Zuweisung
y
=
flip
(
l
)
genau einmal
ausgeführt wird, gilt für je-
des
c ∈{
0
,
1
}
α
∈{
0
,
1
}
l
:
Prob
{y
=
c}
=Prob
y
−
1
(
c
)
=Prob
{{α ∈{
0
,
1
}
t
| y
(
α
)=
c}}
=1
/
2
l
(siehe auch Aufgabe 4.9.13).
