Cryptography Reference
In-Depth Information
E
A
, wobei er
(
er das Experiment
,n,g,u
)
als öffentlichen Schlüssel verwendet; im Fol-
genden werden wir statt
(
G,n,g,u
)
kurz
u
schreiben. Die Beantwortung des Angebots
von
A
geschieht mit
v
und
w
:Eswird
z
b
zu
(
v,z
b
·
G
w
)
verschlüsselt. Ist
(
u, v,w
)
ein
DH-Tripel, so entspricht diese Verschlüsselung genau der Verschlüsselung durch
S
mit
öffentlichem Schlüssel
u
. In diesem Fall sollte
A
also (gut) zwischen der Verschlüsselung
von
z
0
und
z
1
unterscheiden können. Ist
(
u, v,w
)
jedoch kein DH-Tripel, so wurde
w
unabhängig von
u
und
v
gewählt. In diesem Fall sollte es
A
deshalb schwer fallen, zu
unterscheiden, ob
z
0
oder
z
1
verschlüsselt wurde. Der Unterscheider
U
macht deshalb
seine Ausgabe davon abhängig, ob
A
richtig bestimmt, ob
z
0
oder
z
1
verschlüsselt wurde.
Falls
A
richtig liegt, dann gibt
U
das Bit
1
aus und sonst
0
. Die genaue Beschreibung
des Unterscheiders
U
folgt:
U
((
u, v, w
))
1.
Chiffrewahl, abgewandelt im Vergleich zu
E
A
.
k
=
u
2.
Simuliere
AF
mit öffentlichem Schlüssel
u
.
(
k
)
3.
Simuliere Auswahlschritt.
c
=
flip
()
y
=(
v,z
c
·
(
z
0
,z
1
)=
AF
w
)
AG
, wieder mit öffentlichem Schlüssel
u
.
4.
Simuliere
c
=
(
k,y
)
5.
Überprüfe Antwort
c
von
AG
AG
.
falls
c
=
c
,so
gib
1
zurück
sonst
gib
0
zurück
Der folgende Satz beschränkt, wie gewünscht, den Vorteil von
A
durch (zweimal)
denjenigen von
U
und zeigt, dass
A
und
U
ähnliche Laufzeiten haben.
Satz 6.5.1 (beweisbare Sicherheit ElGamal).
Es sei, wie üblich,
GroupGen
ein zufallsge-
steuerter Algorithmus zur Erzeugung von Gruppen. Dann existiert eine (kleine) Konstan-
te
c
, so dass für alle
t>
0
und
t
-beschränkten Angreifer
A
auf das
GroupGen
-ElGamal-
Kryptoschema
S
gilt:
adv
(
A,S
)=2
·
adv
(
U,
(Un[
GroupGen
]
,
DH[
GroupGen
]))
,
(6.5.8)
wobei
U
der oben aus dem Angreifer
A
konstruierte Unterscheider für
(Un[
GroupGen
]
,
DH[
GroupGen
])
ist. Dieser ist
(
t
+
c
)
-beschränkt.
Bevor wir diesen Satz beweisen, können wir aus diesem Satz direkt folgern, dass unter
der DDH-Annahme das GroupGen-ElGamal-Kryptoschema sicher ist:
Folgerung 6.5.1.
Es sei
GroupGen
ein zufallsgesteuerter Algorithmus zur Erzeugung
von Gruppen und es sei
S
das
GroupGen
-ElGamal-Kryptoschema. Dann existiert eine
