Decision Diffie-Hellman (DDH): Difference between revisions

From Cryptology City
Jump to navigation Jump to search
No edit summary
No edit summary
 
(One intermediate revision by the same user not shown)
Line 7: Line 7:
== Formal assumption ==
== Formal assumption ==
Let <math>\mathbb{G}=\{\mathbb{G}_{\lambda}\}</math> be a group ensemble. Then, we say that the [[Decision Diffie-Hellman (DDH)]] assumption holds for <math>\mathbb{G}</math> if for any efficient algorithm <math>A</math>, there is a negligible function <math>\nu</math> such that,
Let <math>\mathbb{G}=\{\mathbb{G}_{\lambda}\}</math> be a group ensemble. Then, we say that the [[Decision Diffie-Hellman (DDH)]] assumption holds for <math>\mathbb{G}</math> if for any efficient algorithm <math>A</math>, there is a negligible function <math>\nu</math> such that,
<center><math>|\Pr[A(g,g^x,g^y,g^{xy})] - \Pr[A(g,g^x,g^y,g^z)]| \le \nu(\lambda),</math></center>
<center><math>|\Pr[A(g,g^x,g^y,g^{xy}) = 1] - \Pr[A(g,g^x,g^y,g^z) = 1]| \le \nu(\lambda),</math></center>
where <math>g</math> is a random generator of the group <math>\mathbb{G}_{\lambda}</math>, <math>x,y,z</math> are all uniform on <math>|\mathbb{G}_{\lambda}|</math>.
where <math>g</math> is a random generator of the group <math>\mathbb{G}_{\lambda}</math>, <math>x,y,z</math> are all uniform on <math>|\mathbb{G}_{\lambda}|</math>.


Line 14: Line 14:
== Known attacks ==
== Known attacks ==
* A quantum computer can compute discrete logarithms (and therefore break DDH) in any group [[ccref#sho94|[Sho94]]]
* A quantum computer can compute discrete logarithms (and therefore break DDH) in any group [[ccref#sho94|[Sho94]]]
* The [https://en.wikipedia.org/wiki/Baby-step_giant-step | Baby-Step-Giant-Step algorithm] computes discrete logarithms in any group in <math>O(\sqrt{n})</math> time and space for groups of order <math>n</math>. (Which is known to be optimal for generic groups [[ccref#sho97|[Sho97]]])
* The [https://en.wikipedia.org/wiki/Baby-step_giant-step Baby-Step-Giant-Step algorithm] computes discrete logarithms in any group in <math>O(\sqrt{n})</math> time and space for groups of order <math>n</math>. (Which is known to be optimal for generic groups [[ccref#sho97|[Sho97]]])


== Relationship to other assumptions ==
== Relationship to other assumptions ==

Latest revision as of 15:19, 4 July 2024


The Decision Diffie-Hellman (DDH) assumption is a common assumption made to construct a wide variety of primitives. It is the weakest of assumption of the common Diffie-Hellman type assumptions. And being able to break Computational Diffie-Hellman (CDH) and Discrete Logarithm (DLOG) immediately break DDH.

Formal assumption

Let be a group ensemble. Then, we say that the Decision Diffie-Hellman (DDH) assumption holds for if for any efficient algorithm , there is a negligible function such that,

where is a random generator of the group , are all uniform on .

The problem of distinguishing between these two inputs is sometimes also referred to as the Decision Diffie-Hellman problem.

Known attacks

  • A quantum computer can compute discrete logarithms (and therefore break DDH) in any group [Sho94]
  • The Baby-Step-Giant-Step algorithm computes discrete logarithms in any group in time and space for groups of order . (Which is known to be optimal for generic groups [Sho97])

Relationship to other assumptions

  • If DDH is hard in a group, then CDH is also hard in that group.

Implied primitives

Other notes

Some works define the DDH problem for a fixed generator rather than a random generator. The differences between these two definitions are discussed in [BMZ19].