Cryptography Reference
In-Depth Information
U
:
{
S
=1
fail
PRF
(
U,
B
)=Prob
}
1
2
+
qn
≤
.
(5.4.8)
2
l
Um nun (5.4.7) zu beweisen, reicht es offensichtlich zu zeigen, dass
Prob
S
=1
,Coll
=
Prob
Coll
2
(5.4.9)
gilt. Dazu sei
c
die durch die in
U
verwendete Variable
c
induzierte Zufallsvariable über
der Menge der Läufe von
S
,d.h.,
c
ist
1
, falls in dem von
U
simulierten Experiment
E
S
A
die rechte Angebotshälfte verschlüsselt wird, und
0
sonst. Entsprechend bezeichne
c
die Zufallsvariable, die die Ausgabe von
A
im von
U
simulierten Experiment
E
S
A
liefert.
S
, nämlich
F
,
z
0
,
z
1
,und
y
,
Ebenso verwenden wir, wie üblich, die anderen Variablen in
als Zufallsvariablen über der Menge der Läufe von
S
.
Offensichtlich gilt:
Prob
S
=1
,Coll
=Prob
c
=
c,Coll
.
Wir konstruieren nun eine bijektive Abbildung
β
von der Menge
.
Die Abbildung
β
bildet also einen Lauf
α
von
S
, in dem keine Kollision aufgetreten ist,
auf einen (anderen) Lauf
β
(
α
)
von
Coll
in die Menge
Coll
S
ab, den wir häufig kurz mit
α
bezeichnen, in dem
ebenfalls keine Kollision aufgetreten ist. Dabei werden wir
β
so konstruieren, dass die
Bedingung »
c
=
c
«in
α
gilt, d.h.,
c
(
α
)=
c
(
α
)
, genau dann, wenn sie in
α
=
β
(
α
)
nicht
gilt, d.h.,
c
(
α
)
S
gleichverteilt
sind, also insbesondere
α
und
α
mit gleicher Wahrscheinlichkeit auftreten, folgt sofort
(5.4.9).
Die Idee der Konstruktion von
α
aus
α
ist, dass wir
c
in
α
komplementieren und
ansonsten
α
so angepassen, dass die Sichten von
A
in
α
und
α
gleich sind. Insbesondere
wird
A
deshalb in
α
dieselbe Vermutung
c
wie in
α
zurückliefern, womit die gewünschte
Beziehung zwischen
α
und
α
gilt, nämlich
c
(
α
)=
c
(
α
)
genau dann, wenn
c
(
α
)
=
c
(
α
)
.
Genauer sieht die
Kon
struktion von
α
=
β
(
α
)
aus
α
wie folgt aus.
2
=
c
(
α
)
. Mit einer solchen Abbildung und da Läufe von
Es sei
α
ein
S
Lauf von
. Es bezeichne
F
=
F
(
α
)
die in diesem Lauf gewählte Chiffre,
(
z
0
,z
1
)=(
z
0
(
α
)
,z
1
(
α
))
sei das in diesem Lauf unterbreitete Angebot,
z
=
z
c
(
α
)
sei die
mit
α ∈ Coll
S
als Produktraum
2 Zur Erinnerung: Gemäß Abschnitt 4.6.2 kann der Wahrscheinlichkeitsraum von
der Form
Ω
S
=
F
{
0
,
1
}
l
×{
0
,
1
}
t
A
×{
0
,
1
}×{
0
,
1
}
l
×···×{
0
,
1
}
l
q
aufgefasst werden, wobei die Komponenten - von links nach rechts - der Wahl von
F
, der Wahl der
Zufallsbits für
A
(maximale Laufzeit
t
A
angenommen), der Wahl von
c
und der Wahl der initialen
S
wird also
Zähler für die (maximal)
q
Orakelanfragen von
A
entsprechen. Ein Lauf
α ∈ Ω
S
von
als Tupel repräsentiert. (Da
F
maximal auf
nl
-Blöcke angewendet wird, könnte man
F
{
0
,
1
}
l
auch
{
0
,
1
}
l
ersetzen.)
durch ein
n
-faches kartesisches Produkt über