Decisional-Diffie-Hellman-Problem

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

Definition

Gegeben ist eine, üblicherweise multiplikativ geschriebene, endliche zyklische Gruppe $\mathbb {G}$ mit endlicher Ordnung $q$ und Erzeuger $g$ . Das bedeutet, dass es zu jedem Element $h$ der Gruppe einen Exponenten $x\in \mathbb {Z} _{q}$ gibt, so dass $h=g^{x}$ .

Es seien nun $x,y,z\in \mathbb {Z} _{q}$ Exponenten. Das Decisional-Diffie-Hellman-Problem ist nun, für ein Tripel $(g^{x},g^{y},g^{z})$ , bei dem $x$ und $y$ zufällig sind, zu erkennen, ob $x\cdot y=z$ oder ob $z$ 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 $\mathbb {G}$ 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 $g^{x}$ und $g^{y}$ das Element $g^{xy}$ 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 $g^{x}$ den Exponenten $x$ zu finden. Ist das DLog-Problem in einer Gruppe leicht lösbar, so kann durch ziehen des DLog von $g^{y}$ und berechnen von $\left[g^{x}\right]^{y}$ 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 generischen Gruppenmodell für Gruppen beweisen, sofern deren Ordnung 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 Untergruppen primer Ordnung von $\mathbb {Z} _{p}^{\times }$ mit $p$ prim.

Gilt $p=2q+1$ , so hat die Untergruppe der quadratischen Reste prime Ordnung und stellt damit einen geeigneten Kandidaten.^[1]

Andererseits ist etwa in $\mathbb {Z} _{q}^{+}$ 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 $(g,a\cdot g,b\cdot g,c\cdot g)$ prüft man, ob $a\cdot g=(c\cdot g/(b\cdot g))\cdot g$ . Dies ist der Fall, wenn $c=ab$ ist. Die Division ist zwar keine Gruppenoperation in $(\mathbb {Z} _{p},+)$ , aber aufgrund der besonderen Struktur der ganzen Zahlen dennoch möglich (sowohl die Gruppenelemente als auch die „Exponenten“ sind ganze Zahlen).