Cryptography Reference
In-Depth Information
Beschreibung einer solchen Gruppe) sowie
n
die Ordnung und
g
ein Erzeuger dieser
Gruppe.
Das
Die-Hellman-Entscheidungsproblem
(kurz:
DDH-Problem
, für »Decisional Die-
Hellman«) bzgl. GroupGen besteht nun darin, die beiden folgenden Wahrscheinlichkeits-
verteilungen, welche durch zufallsgesteuerte Algorithmen beschrieben werden, zu unter-
scheiden.
1.
Gleichverteilung,
Un[
GroupGen
]
:
Un[
GroupGen
]
a.
Wähle Gruppe.
(
,n,g
)=
GroupGen
()
b.
Wähle zufällig drei Elemente aus
G
G
(siehe Bemerkung unten).
a
=
flip
(
Z
n
)
b
=
flip
(
Z
n
)
c
=
flip
(
Z
n
)
c.
Ausgabe.
(
G,n,g,g
a
,g
b
,g
c
)
2.
Die-Hellman-Verteilung,
DH[
GroupGen
]
:
DH[
GroupGen
]
a.
Wähle Gruppe.
(
,n,g
)=
GroupGen
()
b.
Wähle zufällig zwei Elemente aus
G
G
(siehe Bemerkung unten).
Z
n
)
b
=
flip
(
Z
n
)
c.
Ausgabe.
(
a
=
flip
(
,n,g,g
a
,g
b
,g
a·b
)
Wir werden im Folgenden häufig statt
(
G,n,g,g
a
,g
b
,g
c
)
und
(
G,n,g,g
a
,g
b
,g
a·b
)
einfach
(
g
a
,g
b
,g
c
)
bzw.
(
g
a
,g
b
,g
a·b
)
schreiben und von Tripeln sprechen. Wir nennen ein Tripel
der Form
(
g
a
,g
b
,g
a·b
)
ein
DH-Tripel
.
In den Definitionen der obigen Verteilungen haben wir ein Element
a
zufällig gleichver-
teilt aus
G
Z
n
gewählt und dann
g
a
ausgegeben. Dies ist äquivalent dazu, ein Element aus
G
zufällig gleichverteilt zu wählen und auszugeben, da die Abbildung, die jedes
a ∈
Z
n
auf
g
a
abbildet, eine Bijektion von
ist (siehe Aufgabe 6.7.18 und Lemma 6.3.3).
In
Un[
GroupGen
]
werden also drei Gruppenelemente aus
G
zufällig gleichverteilt und un-
abhängig voneinander gewählt. Dagegen hängt in
DH[
GroupGen
]
die letzte Komponente
des Tripels eindeutig von den ersten beiden ab.
Die Annahme, die wir für den Beweis der Sicherheit des ElGamal-Kryptoschemas
treffen werden, ist, dass das DDH-Problem schwer zu lösen ist. Genauer werden wir
folgende Annahme treffen.
Annahme 6.5.1 (Die-Hellman-Annahme). Die
(decisional) Die-Hellman-Annahme
(auch kurz:
DDH-Annahme
) bzgl. GroupGen sowie den Parametern
t
und
ε
besagt, dass
die Verteilungen
Un[
GroupGen
]
und
DH[
GroupGen
](
t, ε
)
-ununterscheidbar sind gemäß
Definition 6.5.5.
Z
n
nach
G
