Cryptography Reference
In-Depth Information
(kleine) Konstante
c
, so dass für alle
t>
0
gilt:
insec
(
t,
S
)
≤
2
·
insec
(
t
+
c,
(Un[
GroupGen
]
,
DH[
GroupGen
]))
.
Insbesondere gilt unter der DDH-Annahme bzgl.
GroupGen
sowie den Parametern
t
+
c
und
ε
:
insec
(
t,
S
)
≤
2
·
ε.
S
ist
(
t,
2
· ε
)
-sicher.
Mit anderen Worten,
Beweis von Satz 6.5.1.
Es sei GroupGen wie im Satz gegeben. Wir schreiben im Folgen-
den kurz
Un
und
DH
für
Un[
GroupGen
]
bzw.
DH[
GroupGen
]
.
Es seien
t>
0
und
A
ein
t
-beschränkter Angreifer wie im Satz. Man sieht leicht, dass
man unabängig von
t
und
A
eine (kleine) Konstante
c
wählen kann, so dass
U
(
t
+
c
)
-
beschränkt ist.
Für den Beweis von (6.5.8) beobachten wir zunächst, dass
(Un
,
DH)
U
S
b
=1
genau dem
E
A
entspricht. Folglich erhalten wir:
suc
(
U,
(Un
,
DH)) = Prob
Experiment
=1
(Un
,
DH)
U
S
b
=1
=Prob
E
A
=1
=
adv
(
A,
(6.5.9)
S
)
+
1
2
.
2
(Un
,
DH)
U
S
=
Betrachten wir nun den Misserfolg von
U
.Dazusei
S
b
=0
. Wir interes-
sieren uns also für die Wahrscheinlichkeit
Prob
{
S
=1
S
}
. Im verkürzten Experiment
E
A
simuliert, allerdings wird das Angebot mit Hilfe des Tripels
(
u, v, w
)
verschlüs-
selt, welches aus der Verteilung
Un
stammt. Insbesondere wurde
w
unabhängig von
u
und
v
gewählt. Deshalb ist zu erwarten, dass
A
aus
(
v,z
c
· w
)
keine Information darüber
gewinnen kann, ob
z
0
oder
z
1
verschlüsselt wurde: Die beiden Komponenten des Chiffre-
textes sind nämlich zwei unabhängig gewählte zufällige Elemente der Gruppe. Wir wollen
zeigen, dass tatsächlich
wird
fail
(
U,
(Un
,
DH)) = Prob
{
S
=1
}
=1
/
2
(6.5.10)
gilt.
Dazu definieren wir, ähnlich wie im Beweis von Satz 5.4.1, eine Bijektion
β
auf Läufen
von
S
, so dass im Lauf
α
der Angreifer
A
das Experiment erfolgreich besteht, im Lauf
β
(
α
)
aber nicht und umgekehrt. Daraus (und aus der Tatsache, dass
α
und
β
(
α
)
die glei-
che Wahrscheinlichkeit besitzen) folgt dann das Gewünschte, denn offensichtlich besteht
dann
A
das Experiment in genau der Hälfte aller Fälle.
Es sei
α
ein Lauf von
S
. Es bezeichne
(
u, v, w
)
das im Lauf
α
an
U
übergebene Tripel
und
(
z
0
,z
1
)
das im Lauf
α
unterbreitete Angebot. Wir konstruieren daraus einen neuen
Lauf
β
(
α
)=
α
wie folgt: Der Lauf
α
stimme bis auf folgende Änderungen mit
α
überein.
In
α
wird das Bit
c
gekippt, d. h., es gilt
c
(
α
)=1
c
(
α
)
. Außerdem wird in
α
die an
−
(
z
1
−c
(
α
)
)
−
1
·
U
übergebene dritte Komponente
w
durch
w
·
z
c
(
α
)
ersetzt.
