Cryptography Reference
In-Depth Information
Man beachte, dass die bedingte Wahrscheinlichkeit definiert ist, da
Prob
{
y
=
c
}
>
0
gilt.
Es sei auch darauf hingewiesen, dass
A
(
x
)
y
=
c
und
A
(
x
)
unterschiedliche Algorithmen
mit potentiell unterschiedlichen maximalen Laufzeiten und damit auch unterschiedliche
Zufallsvariablen mit (potentiell) unterschiedlichen Wahrscheinlichkeitsräumen sind. Dies
ist gemäß der in Abschnitt 3.3 beschriebenen Verwendung des Symbols
Prob
{·}
erlaubt.
Beispiel 4.6.3 (Beispiel 4.6.1 fortgef.). Für den Algorithmus
A
aus Beispiel 4.6.1 gilt of-
fensichtlich
Prob
wird
b
0
auf
1
gesetzt, womit ga-
rantiert ist, dass
x
(0)
,also
1
, ausgegeben wird. Wegen (4.6.4) gilt
Prob
{
A
b
0
=1
=1
}
=1
,dennin
A
b
0
=1
{
A
=1
|
b
0
=1
}
=
Prob
{Ab
0
=1
=1
}
und damit
Prob
{A
=1
| b
0
=1
}
=1
. Letzteres kann man auch
leicht direkt nachrechnen.
nicht definiert ist, falls
y
lediglich
höchstens
einmal,
statt
genau
einmal einen Wert zugewiesen bekommt. Natürlich könnte man die Definition
von
A
(
x
)
Es sei betont, dass
A
(
x
)
y
=
c
aus
A
gewinnt, indem
man,
falls
die Zuweisung
y
=
flip
(
l
)
ausgeführt wird, stattdessen die Zuweisung
y
=
c
ausführt. In diesem Fall würde aber (4.6.4) im Allgemeinen nicht mehr gelten (siehe
Aufgabe 4.9.15).
Wir schreiben kurz
A
(
x
)
y
=
c
erweitern und festlegen, dass man
A
(
x
)
y
=
c
y
1
=
c
1
,y
2
=
c
2
,...,y
l
=
c
l
für
(
···
((
A
(
x
)
y
1
=
c
1
)
y
2
=
c
2
)
···
)
y
l
=
c
l
,
unter der Voraussetzung, dass
(
···
((
A
(
x
)
y
1
=
c
1
)
y
2
=
c
2
)
···
)
y
i
=
c
i
für alle
i
∈
{
y
1
=
c
1
der Variablen
y
2
genau einmal ein Wert zugewiesen werden. Man beachte, dass dies nicht
zwingend bedeutet, dass dies auch für
A
(
x
)
gilt.
Per Induktion erhalten wir aus (4.6.4) für alle
c
∈{
0
,
1
}
∗
:
1
,...,l
}
definiert ist. Insbesondere sollte, zum Beispiel, in jedem Lauf von
A
(
x
)
Prob
{A
(
x
)
y
1
=
c
1
,...,y
l
=
c
l
=
c
}
=Prob
{A
(
x
)=
c
| y
1
=
c
1
,...,y
l
=
c
l
} .
(4.6.5)
Beispiel 4.6.4. Wir betrachten die folgende Variante
A
des Algorithmus
A
aus Bei-
spiel 4.6.1:
A
:
{
}
x
= 1110 (
0
,
1
}
4
)
∈{
0
,
1
b
0
=
flip
()
falls
b
0
=1
,sogib
x
(0)
aus und halte
b
1
=
flip
()
falls
b
1
=1
,sogib
x
(1)
aus und halte
b
2
=
flip
()
falls
b
2
=1
,sogib
x
(2)
aus und halte
b
3
=
flip
()
falls
b
3
=1
,sogib
x
(3)
aus und halte
gib
1
aus.