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.
Search WWH ::




Custom Search