# Decisional Diffie-Hellman assumption

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 notably the ElGamal and Cramer-Shoup cryptosystems.

Definition

Consider a (multiplicative) cyclic group $G$ of order $q$, and with generator $g$. The DDH assumption states that, given $g^a$ and $g^b$ for randomly-chosen $a,b in mathbb\left\{Z\right\}_q$, the value $g^\left\{ab\right\}$ "looks like" a random element in $G$.

This intuitive notion is formally stated by saying that the following two probability distributions are computationally indistinguishable (in the security parameter $q$):
* $\left(g^a,g^b,g^\left\{ab\right\}\right)$, where $a$ and $b$ are randomly and independently chosen from $mathbb\left\{Z\right\}_q$.
* $\left(g^a,g^b,g^c\right)$, where $a,b,c$ are randomly and independently chosen from $mathbb\left\{Z\right\}_q$.

Triples of the first kind are often called DDH triples or DDH tuples.

Relation to Other Assumptions

The DDH assumption is related to the discrete log assumption. If it were possible to efficiently compute discrete logs in $G$, then the DDH assumption would not hold in $G$. Given $\left(g^a,g^b,z\right)$, one could efficiently decide whether $z=g^\left\{ab\right\}$ by first taking the discrete log $a$ of $g^a$, and then comparing $z$ with $\left(g^b\right)^a$.

For this reason, DDH is considered a stronger assumption than discrete log, in the following sense: there are groups for which detecting DDH tuples is easy, but computing discrete logs is believed to be hard. Thus, requiring that the DDH assumption holds in a group is a more restricting requirement.

The DDH assumption is also related to the Computational Diffie-Hellman assumption (CDH). If it were possible to efficiently compute $g^\left\{ab\right\}$ from $\left(g^a,g^b\right)$, then one could easily distinguish the two probability distributions above. Similar to above, DDH is considered a stronger assumption than CDH.

Other Properties

The problem of detecting DDH tuples is random self-reducible, meaning, roughly, that if it is hard for even a small fraction of inputs, it is hard for almost all inputs; if it is easy for even a small fraction of inputs, it is easy for almost all inputs.

Groups For Which DDH is Assumed to Hold

When using a cryptographic protocol whose security depends on the DDH assumption, it is important that the protocol is implementing using groups where DDH is believed to hold:

* The subgroup of $k$th residues modulo a prime $p$, where $\left(p-1\right)/k$ is also a large prime (also called a Schnorr group). For the case of $k=2$, this corresponds to the group of quadratic residues modulo a safe prime.

* The cyclic group of order $\left(p-1\right)\left(q-1\right)$, where $p$ and $q$ are safe primes.

* A prime-order elliptic curve $E$ over the field $GF\left(p\right)$, where $p$ is prime, provided $E$ has large embedding degree.

* A Jacobian of a hyper-elliptic curve over the field $GF\left(p\right)$ with a prime number of reduced divisors, where $p$ is prime, provided the Jacobian has large embedding degree.

Importantly, the DDH assumption does not hold in the multiplicative group $mathbb\left\{Z\right\}^*_p$, where $p$ is prime. This is because given $g^a$ and $g^b$, one can efficiently compute the Legendre symbol of $g^\left\{ab\right\}$, giving a successful method to distinguish $g^\left\{ab\right\}$ from a random group element.

The DDH assumption does not hold on elliptic curves over $GF\left(p\right)$ with small embedding degree (say, less than $log^2\left(p\right)$), a class which includes supersingular elliptic curves. This is because the Weil pairing or Tate pairing can be used to solve the problem directly as follows: given $P,aP,bP,cP$ on such a curve, one can compute $e\left(P,cP\right)$ and $e\left(aP,bP\right)$. By the bilinearity of the pairings, the two expressions are equal if and only if $ab=c$ modulo the order of $P$. If the embedding degree is large (say around the size of $p$ then the DDH assumption will still hold because the pairing cannot be computed. Even if the embedding degree is small, there are some subgroups of the curve in which the DDH assumption is believed to hold.

ee also

* Diffie-Hellman problem
* Diffie-Hellman key exchange
* Computational hardness assumptions
* XDH Assumption
* Decisional Linear assumption

References

* Dan Boneh, The Decision Diffie-Hellman Problem, ANTS 1998, pp. 48&ndash;63 [http://crypto.stanford.edu/~dabo/abstracts/DDH.html] .

Wikimedia Foundation. 2010.

### Look at other dictionaries:

• 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

• 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

• 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

• 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

• Decisional Linear assumption — The Decisional Linear (DLIN) assumption is a mathematic assumption used in elliptic curve cryptography. In particular the DLIN assumption is often used in settings in which the Decisional Diffie Hellman assumption does not hold, as is often the… …   Wikipedia

• Computational hardness assumption — In cryptography, a major goal is to create cryptographic primitives with provable security. In some cases cryptographic protocols are found to have information theoretic security, the one time pad is a common example. In many cases, information… …   Wikipedia

• Decision Linear assumption — The Decision Linear (DLIN) assumption is a mathematical assumption used in elliptic curve cryptography. In particular, the DLIN assumption is useful in settings where the decisional Diffie–Hellman assumption does not hold (as is often the case in …   Wikipedia

• XDH assumption — The External Diffie Hellman (XDH) assumption is a mathematic assumption used in elliptic curve cryptography. The XDH assumption holds that there exist certain subgroups of elliptic curves which have useful properties for cryptography.… …   Wikipedia