Cryptography Reference
In-Depth Information
Beispiel 4.6.6. Zum Beispiel könnte ein solcher Pseudocode wie folgt aussehen:
A
:
{
0
,
1
}
y
0
=
flip
()
falls
y
0
=1
, so setze
y
1
=
flip
(
l
1
)
, sonst setze
y
1
=
flip
(
l
2
)
y
3
=
B
(
Parameter
)
gib
y
3
aus
Dabei bezeichnet
B
einen beliebigen zufallsgesteuerten Algorithmus, dessen Laufzeit pa-
rameterunabhängig durch eine Konstante
t
B
nach oben beschränkt ist. Mit »
«
bezeichnen wir mögliche Parameter, die
B
übergeben werden. Wie diese genau aussehen,
spielt hier keine Rolle. Man beachte, dass die drei im Pseudocode explizit genannten
Flipoperationen, wie gefordert, in jedem Lauf von
A
höchstens einmal ausgeführt wer-
den.
Parameter
Bezeichnet
t
A
die maximale Laufzeit eines durch Pseudocode spezifizierten zufallsge-
steuerten Algorithmus
A
der oben betrachteten Form, so war bisher der zu
A
gehörende
Wahrscheinlichkeitsraum definiert als die Gleichverteilung auf
t
A
. Dabei greifen so-
wohl alle im Pseudocode genannten, aber nicht weiter spezifizierten zufallsgesteuerten Al-
gorithmen, also auch die genannten Flipoperationen, auf die in einem Lauf
α ∈{
0
,
1
}
{
0
,
1
}
t
A
festgelegten Zufallsbits zu. In Beispiel 4.6.6 greifen also sowohl die drei im Pseudoco-
de erwähnten Flipoperationen als auch der zufallsgesteuerte Algorithmus
B
auf diese
Zufallsbits zu.
In Beweisen ist es allerdings häufig bequemer, den Wahrscheinlichkeitsraum zu
A
als
gleichverteilten Produktraum der Form
r
1
r
n
zu begreifen, der eine
{
0
,
1
}
×···×{
0
,
1
}
r
i
für jeden im Pseudocode von
A
erwähnten und nicht weiter spezi-
fizierten zufallsgesteuerten Algorithmus sowie für jede im Pseudocode von
A
erwähnte
Flipoperation enthält.
Für Algorithmus
A
aus Beispiel 4.6.6 bedeutet dies, dass der zugehörige Wahrschein-
lichkeitsraum die Gleichverteilung über
{
0
,
1
}
Komponente
Ω
prod
A
l
1
l
2
t
B
=
{
0
,
1
}×{
0
,
1
}
×{
0
,
1
}
×{
0
,
1
}
ist, wobei die Komponenten in offensichtlicher Weise den Flipoperationen bzw. dem Algo-
rithmus
B
zugeordnet sind. Ein Tupel
(1
,z
1
,z
2
,z
B
)
∈ Ω
pro
A
entspricht also einem Lauf
von
A
, indem
y
0
den Wert
1
und
y
1
den Wert
z
1
zugewiesen bekommt sowie
B
seine
Zufallsbits gemäß
z
B
wählt; entsprechend würde in einem Lauf zu
(0
,z
1
,z
2
,z
B
)
der Va-
riablen
y
0
der Wert
0
und der Variablen
y
1
der Wert
z
2
zugewiesen werden und
B
würde
seine Zufallsbits wie zuvor gemäß
z
B
wählen.
Man überzeugt sich leicht davon, dass ein solcher Produktraum die Verteilung der
Ausgabe eines Algorithmus im Vergleich zur ursprünglich eingeführten Gleichverteilung
auf Mengen der Form
t
nicht ändert; die Argumentation ist ähnlich wie diejenige in
Aufgabe 4.9.13. Da die Aussagen, die wir beweisen werden, lediglich die Verteilung der
Ausgaben von Algorithmen betreffen, können wir demnach ohne Einschränkung den Pro-
duktraum zugrunde legen, was wir im Rest des Buches für Pseudocode der betrachteten
Form auch meist tun werden.
{
0
,
1
}
