en>Yobot: Reference before punctuation, removed stub tag using AWB (9585)

2013-11-07T13:59:35Z

Reference before punctuation, removed stub tag using AWB (9585)

New page

The '''decisional Diffie–Hellman (DDH) assumption''' is a [[computational hardness assumption]] about a certain problem involving [[discrete logarithm]]s in [[cyclic group]]s. It is used as the basis to prove the security of many [[cryptography|cryptographic]] protocols, most notably the [[ElGamal encryption|ElGamal]] and [[Cramer–Shoup cryptosystem]]s.

==Definition==

Consider a (multiplicative) [[cyclic group]] <math>G</math> of order <math>q</math>, and with [[Generating set of a group|generator]] <math>g</math>. The DDH assumption states that, given <math>g^a</math> and <math>g^b</math> for uniformly and independently chosen <math>a,b \in \mathbb{Z}_q</math>, the value <math>g^{ab}</math> "looks like" a random element in <math>G</math>.

This intuitive notion is formally stated by saying that the following two probability distributions are [[computationally indistinguishable]] (in the [[security parameter]], <math>n=\log(q)</math>):
* <math>(g^a,g^b,g^{ab})</math>, where <math>a</math> and <math>b</math> are randomly and independently chosen from <math>\mathbb{Z}_q</math>.
* <math>(g^a,g^b,g^c)</math>, where <math>a,b,c</math> are randomly and independently chosen from <math>\mathbb{Z}_q</math>.

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 logarithm|discrete log assumption]]. If it were possible to efficiently compute discrete logs in <math>G</math>, then the DDH assumption would not hold in <math>G</math>. Given <math>(g^a,g^b,z)</math>, one could efficiently decide whether <math>z=g^{ab}</math> by first taking the discrete <math>log_g</math> of <math>g^a</math>, and then comparing <math>z</math> with <math>(g^b)^a</math>.

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 <math>g^{ab}</math> from <math>(g^a,g^b)</math>, 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-reducibility|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==


{{disputed|Incorrect claims|date=July 2013}}

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

* The subgroup of <math>k</math>th residues modulo a prime <math>p</math>, where <math>(p-1)/k</math> is also a large prime (also called a [[Schnorr group]]). For the case of <math>k=2</math>, this corresponds to the group of [[quadratic residue]]s modulo a [[safe prime]].

* The cyclic group of order <math>(p-1)(q-1)/2</math> of quadratic residues modulo <math>pq</math>, where <math>p</math> and <math>q</math> are [[safe prime]]s.

* A prime-order [[elliptic curve]] <math>E</math> over the [[field (mathematics)|field]] <math>GF(p)</math>, where <math>p</math> is prime, provided <math>E</math> has large embedding degree.

* A [[Jacobian]] of a [[hyper-elliptic curve]] over the [[field (mathematics)|field]] <math>GF(p)</math> with a prime number of reduced divisors, where <math>p</math> is prime, provided the Jacobian has large embedding degree.

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

The DDH assumption does not hold on elliptic curves over <math>GF(p)</math> with small embedding degree (say, less than <math>\log^2(p)</math>), a class which includes [[supersingular elliptic curve]]s. This is because the [[Weil pairing]] or [[Tate pairing]] can be used to solve the problem directly as follows: given <math>P,aP,bP,cP</math> on such a curve, one can compute <math>e(P,cP)</math> and <math>e(aP,bP)</math>. By the bilinearity of the pairings, the two expressions are equal if and only if <math>ab=c</math> modulo the order of <math>P</math>. If the embedding degree is large (say around the size of <math>p</math>) 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.

==See also==
* [[Diffie–Hellman problem]]
* [[Diffie–Hellman key exchange]]
* [[Computational hardness assumptions]]
* [[XDH assumption]]
* [[Decisional Linear assumption]]

==References==
*{{cite journal |authorlink=Dan Boneh |first=Dan |last=Boneh |title=The Decision Diffie–Hellman Problem |journal=Proceedings of the Third Algorithmic Number Theory Symposium |series=Lecture Notes in Computer Science |volume=1423 |pages=48–63 |year=1998 |doi=10.1007/BFb0054851 }}

{{Cryptography navbox | public-key}}

{{DEFAULTSORT:Decisional Diffie-Hellman assumption}}
[[Category:Computational hardness assumptions]]
[[Category:Elliptic curve cryptography]]

Hamiltonian system - Revision history

en>Yobot: Reference before punctuation, removed stub tag using AWB (9585)