Decision Diffie-Hellman (DDH)

The Decision Diffie-Hellman (DDH) assumption is a

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 $O({\sqrt {n}})$ time and space for groups of order $n$. (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

• There are many