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 mit Erzeuger g. Das bedeutet, dass es zu jedem Element f der Gruppe eine ganze Zahl z gibt, so dass f = g^z. Beispiel für eine solche Gruppe sind $(\mathbb{Z}_p, +)$, die (additive) Gruppe der ganzen Zahlen modulo einer Primzahl p, und $(\mathbb{Z}_p^\times, \cdot)$, die zugehörige multiplikative Gruppe.

Das Computational-Diffie-Hellman-Problem ist das Problem, in einer solchen Gruppe zu zwei Elementen g^a und g^b das Element g^ab zu finden. Ein solches Tripel (g^a,g^b,g^ab) heißt Diffie-Hellman-Tripel. Wenn in einer Gruppe DLOG leicht ist, ist auch CDH leicht. Man kann aus g^a a berechnen und daraus (g^b)^a = g^ab.

Beim Decisional-Diffie-Hellman-Problem hat man ein Tripel (g^a,g^b,g^c) gegeben und muss entscheiden, ob es sich um ein Diffie-Hellman-Tripel handelt, ob also g^c = g^ab ist. Wenn in einer Gruppe CDH leicht ist, ist DDH auch leicht. Dann kann man aus (g^a,g^b) g^ab berechnen und mit dem gegebenen g^c vergleichen.

Beispiele

In $(\mathbb{Z}_p, +)$ ist DDH leicht, weil dort auch DLOG leicht ist. Da es sich um eine additive Gruppe handelt, 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). Das ist ein Beispiel für einen Algorithmus, der im generischen Gruppenmodell, in dem nur Gruppenoperationen erlaubt sind, nicht möglich ist.

Es wird angenommen, dass DDH in $\mathbb{Z}_p^\times$ schwer ist.

Weblinks

• Dan Boneh, The Decision Diffie–Hellman Problem, ANTS 1998, pp. 48–63 [1].