Decisional-Diffie-Hellman-Problem


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 = gz. 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 ga und gb das Element gab zu finden. Ein solches Tripel (ga,gb,gab) heißt Diffie-Hellman-Tripel. Wenn in einer Gruppe DLOG leicht ist, ist auch CDH leicht. Man kann aus ga a berechnen und daraus (gb)a = gab.

Beim Decisional-Diffie-Hellman-Problem hat man ein Tripel (ga,gb,gc) gegeben und muss entscheiden, ob es sich um ein Diffie-Hellman-Tripel handelt, ob also gc = gab ist. Wenn in einer Gruppe CDH leicht ist, ist DDH auch leicht. Dann kann man aus (ga,gb) gab berechnen und mit dem gegebenen gc 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].

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Decisional Diffie Hellman — Das Decisional Diffie Hellman Problem (kurz DDH) ist eine Variante des Diffie Hellman Problems, bei dem es um die Schwierigkeit geht, aus einer vorgegebenen Zahl ihre in groben Zügen bekannte Konstruktionsweise zu erraten. Somit ist DDH ein… …   Deutsch Wikipedia

  • Diffie-Hellman problem — The Diffie Hellman problem (DHP) is the name of a specific problem in cryptography which was first proposed by Whitfield Diffie and Martin Hellman. The DHP is a problem that is assumed to be difficult to do, hence the security of many… …   Wikipedia

  • Diffie–Hellman problem — Cryptography portal The Diffie–Hellman problem (DHP) is a mathematical problem first proposed by Whitfield Diffie and Martin Hellman in the context of cryptography. The motivation for this problem is that many security systems use mathematical… …   Wikipedia

  • Decisional Diffie–Hellman assumption — The decisional Diffie–Hellman (DDH) assumption is a computational hardness assumption about a certain problem involving discrete logarithms in cyclic groups. It is used as the basis to prove the security of many cryptographic protocols, most… …   Wikipedia

  • Decisional Diffie-Hellman assumption — The decisional Diffie Hellman (DDH) assumption is a computational hardness assumption about a certain problem involving discrete logarithms in cyclic groups. It is used as the basis to prove the security of many cryptographic protocols, most… …   Wikipedia

  • Diffie-Hellman-Schlüsselaustausch — Der Diffie Hellman Schlüsselaustausch oder Diffie Hellman Merkle Schlüsselaustausch ist ein Protokoll aus dem Bereich der Kryptografie. Mit ihm erzeugen zwei Kommunikationspartner einen geheimen Schlüssel, den nur diese beiden kennen. Dieser… …   Deutsch Wikipedia

  • Computational Diffie-Hellman assumption — The computational Diffie Hellman (CDH) assumption is the assumption that a certain computational problem within a cyclic group is hard.Consider a cyclic group {mathbb G} of order q. The CDH assumption states that, given :(g,g^a,g^b) for a… …   Wikipedia

  • Computational Diffie–Hellman assumption — The computational Diffie–Hellman (CDH assumption) is the assumption that a certain computational problem within a cyclic group is hard. Consider a cyclic group G of order q. The CDH assumption states that, given for a randomly chosen… …   Wikipedia

  • Hellman — is the surname of: * Danny Hellman (born 1964), American illustrator and cartoonist nicknamed Dirty Danny * Frances Hellman, physicist at University of California, Berkeley * Jakob Hellman (born 1965), Swedish pop singer * Lillian Hellman… …   Wikipedia

  • Elliptic Curve Cryptography — Elliptische Kurve über Unter Elliptic Curve Cryptography (ECC) oder deutsch Elliptische Kurven Kryptographie versteht man asymmetrische Kryptosysteme, die Operationen auf elliptischen Kurven über endlichen Körpern v …   Deutsch Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.