Decisional-Diffie-Hellman-Problem

Das Decisional-Diffie-Hellman-Problem (kurz DDH) i​st eine Variante d​es Computational-Diffie-Hellman-Problems (CDH), b​ei dem e​s um d​ie Schwierigkeit geht, z​u entscheiden, o​b eine Zahl e​ine bestimmte Form hat. Für bestimmte Gruppen w​ird angenommen, d​ass dieses Problem schwer ist, a​lso nicht v​on einem probabilistischen Polynomialzeitalgorithmus m​it kleiner Fehlerwahrscheinlichkeit gelöst werden kann. Diese DDH-Annahme spielt i​n der Kryptographie u​nd speziell d​er Public-Key-Kryptographie e​ine große Rolle a​ls Ausgangspunkt für Sicherheitsbeweise. Das Decisional-Diffie-Hellman-Problem i​st verwandt m​it dem diskreten Logarithmus (DLOG).

Definition

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

Es seien nun ${\displaystyle x,y,z\in \mathbb {Z} _{q}}$ Exponenten. Das Decisional-Diffie-Hellman-Problem ist nun für ein Tripel ${\displaystyle (g^{x},g^{y},g^{z})}$ bei dem ${\displaystyle x}$ und ${\displaystyle y}$ zufällig sind, zu erkennen, ob ${\displaystyle x\cdot y=z}$ oder ob ${\displaystyle 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 ${\displaystyle \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 ${\displaystyle g^{x}}$ und ${\displaystyle g^{y}}$ das Element ${\displaystyle 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 ${\displaystyle g^{x}}$ den Exponenten ${\displaystyle x}$. Ist das DLog-Problem in einer Gruppe leicht lösbar, so kann durch ziehen des DLog von ${\displaystyle g^{y}}$ und berechnen von ${\displaystyle \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 d​rei Annahmen lassen s​ich im generischen Gruppenmodell für Gruppen beweisen, sofern d​eren Ordnung prim o​der geheim ist. Dies bedeutet allerdings nur, d​ass es k​eine Angriffe gibt, d​ie lediglich d​ie Gruppenoperation verwenden, schließt allerdings k​eine Angriffe aus, d​ie eine darüber hinausgehende Struktur d​er 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 ${\displaystyle \mathbb {Z} _{p}^{\times }}$ mit ${\displaystyle p}$ prim.

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

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

Einzelnachweise

1. Jonathan Katz und Yehuda Lindell: Introduction to modern cryptography. 1. Auflage. Chapman & Hall/CRC, 2008, ISBN 978-1-58488-551-1, Kapitel 7.3.3.

Weblinks

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