imported>Thomas Dresler: Format

2025-07-02T07:06:50Z

Format

Neue Seite

Das '''Decisional-Diffie-Hellman-Problem''' (kurz ''DDH'') ist eine Variante des [[Diffie-Hellman#Diffie-Hellman-Problem|Computational-Diffie-Hellman-Problems]] (''CDH''), bei dem es um die Schwierigkeit geht, zu entscheiden, ob eine Zahl eine bestimmte Form hat. Für bestimmte [[Gruppe (Mathematik)|Gruppen]] wird angenommen, dass dieses Problem schwer ist, also nicht von einem [[BPP (Komplexitätsklasse)|probabilistischen Polynomialzeitalgorithmus mit kleiner Fehlerwahrscheinlichkeit]] gelöst werden kann. Diese DDH-Annahme spielt in der [[Kryptographie]] und speziell der [[Asymmetrisches Kryptosystem|Public-Key-Kryptographie]] eine große Rolle als Ausgangspunkt für [[Beweisbare Sicherheit|Sicherheitsbeweise]]. Das Decisional-Diffie-Hellman-Problem ist verwandt mit dem [[Diskreter Logarithmus|diskreten Logarithmus]] (''DLOG'').

== Definition ==

Gegeben ist eine, üblicherweise multiplikativ geschriebene, endliche zyklische Gruppe <math>\mathbb{G}</math> mit endlicher [[Ordnung (Mathematik)|Ordnung]] <math>q</math> und [[Erzeuger (Algebra)|Erzeuger]] <math>g</math>. Das bedeutet, dass es zu jedem Element <math>h</math> der Gruppe einen Exponenten <math>x \in \Z_q</math> gibt, so dass <math>h = g^x</math>.

Es seien nun <math>x, y, z \in \Z_q</math> Exponenten. Das Decisional-Diffie-Hellman-Problem ist nun, für ein Tripel <math>(g^x, g^y, g^z)</math>, bei dem <math>x</math> und <math>y</math> zufällig sind, zu erkennen, ob <math>x\cdot y = z</math> oder ob <math>z</math> ebenfalls zufällig ist, wenn beide Fälle mit Wahrscheinlichkeit je ½ auftreten.

Durch reines Raten kann offensichtlich eine Erfolgswahrscheinlichkeit von ½ erreicht werden. Gibt es in einer Gruppe <math>\mathbb{G}</math> keinen effizienten Algorithmus, der das Problem substantiell besser löst, so sagt man, dass in dieser Gruppe die '''Decisional-Diffie-Hellman-Annahme''' gilt.

== Voraussetzungen ==

Das Computational-Diffie-Hellman-Problem (CDH) ist das Problem, in einer solchen Gruppe zu zwei Elementen <math>g^x</math> und <math>g^y</math>
das Element <math>g^{xy}</math> zu finden. Falls dieses Problem in einer Gruppe leicht ist, so ist offensichtlich auch das DDH-Problem leicht lösbar und die DDH-Annahme in dieser Gruppe folglich unwahr. Die Umkehrung dieser Aussage (also dass aus der CDH-Annahme die DDH-Annahme folgen würde) folgt hieraus ''nicht'' und es sind Gruppen bekannt, in denen CDH schwer zu sein scheint, DDH allerdings leicht lösbar ist.

Das Diskrete-Logarithmus-Problem (DLog) ist das Problem, zu einem Gruppenelement <math>g^x</math> den Exponenten <math>x</math> zu finden. Ist das DLog-Problem in einer Gruppe leicht lösbar, so kann durch ziehen des DLog von <math>g^y</math> und berechnen von <math>\left[g^x\right]^y</math> das CDH-Problem und damit auch das DDH-Problem leicht gelöst werden. In diesem Fall sind also sowohl die DDH-Annahme als auch die analog definierte CDH-Annahme unwahr.

Alle drei Annahmen lassen sich im [[generisches Gruppenmodell|generischen Gruppenmodell]] für Gruppen beweisen, sofern deren Ordnung [[Primzahl|prim]] oder geheim ist. Dies bedeutet allerdings nur, dass es keine Angriffe gibt, die lediglich die Gruppenoperation verwenden, schließt allerdings keine Angriffe aus, die eine darüber hinausgehende Struktur der fraglichen Gruppe nutzen.

== Beispiele ==

Das klassische Beispiel für eine Gruppe, in der die meisten Kryptologen von der Gültigkeit der DDH-Annahme ausgehen, sind [[Untergruppe]]n [[Primzahl|primer]] Ordnung von <math>\Z_p^\times</math> mit <math>p</math> prim.

Gilt <math>p = 2q+1</math>, so hat die [[Untergruppe]] der [[Quadratischer Rest|quadratischen Reste]] prime Ordnung und stellt damit einen geeigneten Kandidaten.<ref>{{Literatur | Autor= Jonathan Katz und Yehuda Lindell | Titel= Introduction to modern cryptography | Auflage= 1 | Verlag= Chapman & Hall/CRC | Jahr= 2008 | Kapitel= Kapitel 7.3.3 | ISBN= 978-1-584-88551-1}}</ref>

Andererseits ist etwa in <math>\Z_q^+</math> DDH leicht, weil dort auch DLOG leicht ist. Da es sich um eine additive Gruppe handelt, entspricht die Exponentiation hier der [[Multiplikation]]. Somit ist DLOG lediglich die Division. Gegeben <math>(g, a \cdot g, b \cdot g, c \cdot g)</math> prüft man, ob <math>a \cdot g = (c \cdot g / (b \cdot g)) \cdot g</math>. Dies ist der Fall, wenn <math>c = ab</math> ist. Die Division ist zwar keine Gruppenoperation in <math>(\mathbb{Z}_p, +)</math>, aber aufgrund der besonderen Struktur der [[Ganze Zahl|ganzen Zahlen]] dennoch möglich (sowohl die Gruppenelemente als auch die „Exponenten“ sind ganze Zahlen).

== Einzelnachweise ==
<references />

== Weblinks ==
* [http://crypto.stanford.edu/~dabo/abstracts/DDH.html Dan Boneh: ''The Decision Diffie–Hellman Problem'', ANTS 1998, pp. 48–63].

[[Kategorie:Kryptologie]]

Decisional-Diffie-Hellman-Problem - Versionsgeschichte

imported>Thomas Dresler: Format