Decision Diffie-Hellman (DDH): Difference between revisions
No edit summary |
No edit summary |
||
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 | * 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 == |
Revision as of 01:23, 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
Implied primitives
- Key Agreement (KA) due to the original work [DH76]
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].