Cryptography Reference
In-Depth Information
Die Operation flip
. Wir werden in Pseudocode der oben eingeführten Form ne-
ben den Operationen flip
()
und flip
(
l
)
zudem Operationen der Form flip
(
M
)
für eine
endliche Menge
M
erlauben. Bei Aufruf von flip
(
M
)
soll zufällig ein Element aus
M
gewählt und zurückgeliefert werden. Formal wird flip
(
M
)
durch einen zufallsgesteuer-
ten Algorithmus
A
flip(
M
)
()
realisiert, der nur die Operation flip
()
verwendet. Ist
(
M
)
|
allerdings keine Zweierpotenz, dann kann der Algorithmus
A
flip(
M
)
()
, da seine maximale
Laufzeit durch eine Konstante beschränkt ist, nicht genau die Gleichverteilung auf
M
realisieren. Durch die Wahl genügend vieler Zufallsbits kann aber jedes Element von
M
mit einer Wahrscheinlichkeit, die sehr nahe bei
1
/|M|
liegt, gewählt werden (siehe dazu
auch Aufgabe 4.9.12). Eine geringe Abweichung von
1
/
|
M
ist unproblematisch, weil die
Aussagen, die wir treffen werden, einen »stetigen« Charakter besitzen. Wir werden hier
deshalb einfach annehmen, dass flip
(
M
)
(genauer
A
flip(
M
)
()
) genau die Gleichverteilung
auf
M
realisiert.
Wird flip
(
M
)
im Pseudocode der oben besprochenen Form verwendet, so wird deshalb
die zugehörige Komponente im Produktraum die Menge
M
sein. Um dies zu illustrieren,
betrachten wir nochmals Beispiel 4.6.6, wobei nun die Zuweisung »
y
1
=
flip
(
l
1
)
«durch
»
y
1
=
flip
(
M
)
« ersetzt wird. Dann ist der zugehörige Produktraum von der Form:
|
M
|
Ω
prod
A
l
2
t
B
.
=
{
0
,
1
}×M ×{
0
,
1
}
×{
0
,
1
}
Bzgl. dieses Produktraumes wird nun flip
(
M
)
in der Tat als Operation interpretiert, die
ein Element aus
M
gemäß der Gleichverteilung auf
M
liefert. Während die eigentliche
Realisierung
A
flip(
M
)
()
von flip
(
M
)
von dieser Gleichverteilung etwas abweichen kann, ist,
wie gesagt, diese Ungenauigkeit vernachlässigbar.
4.6.3
Prozedurparameter
Wir wollen zulassen, dass Algorithmen andere Funktionen oder Algorithmen zur Eingabe
haben können, zum Beispiel dann, wenn wir einem Algorithmus eine Blockchiffre zur
Verfügung stellen. Wir sprechen dann von einem
Prozedurparameter
oder einem
Orakel
.
Steht einem Algorithmus ein Orakel zur Verfügung, so kann er dieses mit entsprechenden
Eingaben aufrufen und den Rückgabewert entgegennehmen; er kann aber nicht dessen
Programmtext oder sonstige Repräsentation inspizieren.
Sollte das Orakel selbst zufallsgesteuert sein, so kann man sich zum einen vorstellen,
dass es auf dieselbe Zufallsfolge wie der gegebene Algorithmus zugreift, allerdings in einer
Weise, dass jedes Zufallsbit, wie üblich, nur einmal genutzt wird. Insbesondere wird das
Zufallsbit entweder von dem aufrufenden Algorithmus oder dem Orakel verwendet, aber
nicht von beiden.
Zum anderen kann man sich aber auch vorstellen, und diese Sichtweise werden wir
typischerweise einnehmen, dass ein Orakel auf seine eigenen Zufallsbits zugreift. Betrach-
ten wir genauer Algorithmen mit Orakeln in Pseudocode der oben besprochenen Form,
dann wird die Anzahl der maximal möglichen Orakelaufrufe immer durch eine Konstante
nach oben beschränkt sein. Der zugehörige Produktraum wird dann für jeden möglichen
Orakelaufruf eine entsprechende Komponente enthalten, die die Menge der möglichen
Zufallsfolgen für den jeweiligen Orakelaufruf enthält.
