Decisional-Diffie-Hellman-Problem

(Weitergeleitet von Decisional Diffie Hellman)

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

Bearbeiten

Gegeben ist eine, üblicherweise multiplikativ geschriebene, endliche zyklische Gruppe   mit endlicher Ordnung   und Erzeuger  . Das bedeutet, dass es zu jedem Element   der Gruppe einen Exponenten   gibt, so dass  .

Es seien nun   Exponenten. Das Decisional-Diffie-Hellman-Problem ist nun, für ein Tripel  , bei dem   und   zufällig sind, zu erkennen, ob   oder ob   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   keinen effizienten Algorithmus, der das Problem substantiell besser löst, so sagt man, dass in dieser Gruppe die Decisional-Diffie-Hellman-Annahme gilt.

Voraussetzungen

Bearbeiten

Das Computational-Diffie-Hellman-Problem (CDH) ist das Problem, in einer solchen Gruppe zu zwei Elementen   und   das Element   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   den Exponenten   zu finden. Ist das DLog-Problem in einer Gruppe leicht lösbar, so kann durch ziehen des DLog von   und berechnen von   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

Bearbeiten

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   mit   prim.

Gilt  , so hat die Untergruppe der quadratischen Reste prime Ordnung und stellt damit einen geeigneten Kandidaten.[1]

Andererseits ist etwa in   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   prüft man, ob  . Dies ist der Fall, wenn   ist. Die Division ist zwar keine Gruppenoperation in  , aber aufgrund der besonderen Struktur der ganzen Zahlen dennoch möglich (sowohl die Gruppenelemente als auch die „Exponenten“ sind ganze Zahlen).

Einzelnachweise

Bearbeiten
  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.
Bearbeiten