Cryptography Reference
In-Depth Information
2.
Ratephase
b
=
U
(
x
)
3.
Auswertung
Falls
b
=
b
,sogib
1
zurück, sonst
0
.
(
P
0
,P
1
)
U
Mit
dadurch
entsteht, dass der dritte Schritt ersetzt wird durch »gib
b
zurück«. Er wird
verkürztes
Experiment
genannt.
S
,
S
U
oder einfach
S
bezeichnen wir den Algorithmus, der aus
E
Wir definieren wie üblich Vorteil, Erfolg und Misserfolg eines Unterscheiders.
Definition 6.5.4 (Vorteil, Erfolg und Misserfolg eines Unterscheiders). Es seien
P
0
,
P
1
und
U
wie in Definition 6.5.3 gegeben. Der
Vorteil
,
Erfolg
und
Misserfolg
von
U
bezüglich
(
P
0
,P
1
)
ist definiert durch:
adv
(
U,
(
P
0
,P
1
)) = 2
Prob
=1
1
2
(
P
0
,P
1
)
U
E
−
,
(6.5.5)
suc
(
U,
(
P
0
,P
1
)) = Prob
=1
,
(
P
0
,P
1
)
U
S
b
=1
(6.5.6)
fail
(
U,
(
P
0
,P
1
)) = Prob
b
=0
=1
(
P
0
,P
1
)
U
S
.
(6.5.7)
Analog zu Lemma 4.7.1 erhalten wir:
Lemma 6.5.3.
Es seien
P
0
,
P
1
und
U
wie in Definition 6.5.3 gegeben. Dann gilt:
adv
(
U,
(
P
0
,P
1
))
1
,
1]
und
adv
(
U,
(
P
0
,P
1
)) =
suc
(
U,
(
P
0
,P
1
))
∈
[
−
−
fail
(
U,
(
P
0
,P
1
))
.
Wie üblich kann nun die (Un-)unterscheidbarkeit von Verteilungen
P
0
und
P
1
quanti-
fiziert werden.
Definition 6.5.5 (
t
-beschränkt,
(
t, ε
)
-unterscheidbar). Es seien
P
0
und
P
1
Wahrschein-
lichkeitsverteilungen über der endlichen Menge
Ω
und es sei
U
ein Unterscheider für
(
P
0
,P
1
)
. Der Unterscheider
U
heißt
t
-beschränkt
, falls die Laufzeit des zugehörigen Ex-
periments
(
P
0
,P
1
)
U
E
durch
t
beschränkt ist.
Es sei
insec
(
t,
(
P
0
,P
1
)) = sup
{
adv
(
U,
(
P
0
,P
1
))
| U
ist
t
-beschränkter Unterscheider
für
(
P
0
,P
1
)
}
.
Es sei
ε
0
eine reelle Zahl. Die Verteilungen
P
0
und
P
1
heißen
(
t, ε
)
-ununterscheidbar,
wenn insec
(
t,
(
P
0
,P
1
))
≥
≤
ε
gilt. Sie heißen
(
t, ε
)
-unterscheidbar,
wenn insec
(
t,
(
P
0
,P
1
))
≥
ε
gilt.
Es sei nun GroupGen, genau wie in Abschnitt 6.5.1, ein zufallsgesteuerter Algorithmus,
der Tupel der Form
(
G
,n,g
)
erzeugt, wobei
G
eine zyklische Gruppe ist (genauer die
