Decisional Diffie-Hellman

The Decisional Diffie-Hellman (DDH) assumption is a central assumption in cryptography, and one of the first used to construct key exchange DH76. It implies the CDH assumption: an adversary which can solve the CDH problem can also solve DDH in the same group (DDH ⇒ CDH) — folklore.

Assumption

Informally, the DDH assumption concerns a cyclic group generation algorithm $\mathsf{GrGen},$ which takes as input a security parameter $1^{\lambda }$ and outputs a succinct¹ description of a cyclic group $(\mathbb{G},g,p),$ where $\mathbb{G}$ is the group set, $g$ is a generator for the group, and $p$ is the order of the group.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\text{ddh}}_{\GrGen,\calA}(\secpar)$}
\begin{algorithmic}
\State $(\GG,g,p) \gets \GrGen(1^\secpar)$
\State $x \getsr [p]$ ; $y \getsr [p]$ ; $z \getsr [p]$
\State $X \gets g^x$ ; $Y \gets g^y$
\State $b \getsr \bits$
\State $Z_0 \gets g^{xy}$ ; $Z_1 \gets g^{z}$
\State $\hat{b} \gets \calA(1^\secpar, \GG, g, p, X, Y, Z_b)$
\Return $[\hat{b} = b]$
\end{algorithmic}
\end{algorithm}

We say that DDH is hard for a group generation algorithm $\mathsf{GrGen}$ if for all efficient $\mathcal{A},$

$${\mathbf{Adv}}_{\mathsf{GrGen},\mathcal{A}}^{\text{ddh}}(\lambda ):=\left|2\cdot \mathrm{Pr}\left[{\mathbf{G}}_{\mathsf{GrGen},\mathcal{A}}^{\text{ddh}}(\lambda )=1\right]-1\right|$$

is negligible.

Known Results

• DDH ⇒ CDH
• GGM ⇒ DDH
• DDH ⇒ PKE
• DDH implies PRFs via the Naor-Reingold construction, which maps inputs in $\{0,1{\}}^n$ to group elements using a secret exponent vector — NR97
• No fixed-construction reduction from CDH to DDH: DDH is easy in groups that admit efficient symmetric bilinear pairings (e.g., certain supersingular elliptic curves), where CDH can still be hard: given $(g^x,g^y,g^z)$, check whether $e(g^x,g^y)=e(g,g^z)$ — JN03
• No fully-black-box reduction from DDH to IBE
• In the Generic Group Model, for groups of prime order $p$, ${\mathbf{Adv}}_{\mathsf{GrGen},\mathcal{A}}^{\text{ddh}}(\lambda )\le O(\frac{q^2}{p})$, where $q$ is the number of queries that $\mathcal{A}$ issues — Sho97

Attacks

• Baby-step giant-step: a generic algorithm for the underlying discrete logarithm problem. Given $X=g^x$, it finds $x$ in $O(\sqrt{p})$ time and $O(\sqrt{p})$ space by writing $x=im+j$ (where $m=\lceil \sqrt{p}\rceil$) and matching $g^{im}=X\cdot g^{-j}$ across a hash table. Since DDH reduces to DLOG, this attack applies: any DDH distinguisher that computes $g^{xy}$ by solving DLOG runs in $O(\sqrt{p})$.
• DDH is easy in groups with efficient pairings: in groups $\mathbb{G}$ that admit an efficient bilinear pairing $e:\mathbb{G}\times \mathbb{G}\to {\mathbb{G}}_T$ (symmetric/Type-1 pairings, e.g., certain supersingular elliptic curves), DDH is trivially broken. Given $(g^x,g^y,g^z)$, check whether $e(g^x,g^y)=e(g,g^z)$; this holds iff $z=xy$. DDH is therefore not a reasonable assumption in Type-1 pairing groups — see bilinear map assumptions.
• Pohlig-Hellman: if the group order $p$ is smooth (factors into small primes), discrete log (and hence DDH) is easy via the Chinese Remainder Theorem on the prime-order subgroups. This is why DDH is only assumed in prime-order groups or carefully chosen subgroups.

Variations

In the above definition, we implicitly allow $\mathsf{GrGen}$ to choose a random generator $g$ for the group $\mathbb{G}$. However, BMZ19 has explored technical differences between this model and one where $g$ is selected deterministically.

Sub-exponential DDH

DDH is sub-exponentially hard for $\mathsf{GrGen}$ if there is a constant $\epsilon >0$ such that for all sufficiently large $\lambda$, every adversary $\mathcal{A}$ of size at most $2^{{\lambda }^{\epsilon }}$ has ${\mathbf{Adv}}_{\mathsf{GrGen},\mathcal{A}}^{\text{ddh}}(\lambda )\le 2^{-{\lambda }^{\epsilon }}$ — standard. The weaker form that bounds only polynomial-time adversaries by advantage $2^{-{\lambda }^{\epsilon }}$ suffices for NIZK arguments for $\mathbf{NP}$, and no pairing is needed — JJ21.

DLIN

Given $(u,v,h,u^a,v^b,h^c)\in {\mathbb{G}}^6$ for $u,v,h\stackrel{\$}{\leftarrow }\mathbb{G}$ and $a,b\stackrel{\$}{\leftarrow }{\mathbb{Z}}_p$, distinguish $c=a+b$ from $c\stackrel{\$}{\leftarrow }{\mathbb{Z}}_p$ — BBS04.

k-Lin

The $k$-Linear assumption is defined on Bilinear map assumptions.

Matrix Diffie-Hellman

TODO

SXDH (Symmetric External Diffie-Hellman)

Assumes DDH is hard in both ${\mathbb{G}}_1$ and ${\mathbb{G}}_2$ of an asymmetric (Type 3) pairing; used to instantiate Groth–Sahai proofs efficiently — GS08.

Sub-exponential SXDH

SXDH is sub-exponentially hard if there is a constant $\epsilon >0$ such that for all sufficiently large $\lambda$, every adversary of size at most $2^{{\lambda }^{\epsilon }}$ has advantage at most $2^{-{\lambda }^{\epsilon }}$ against DDH in each of ${\mathbb{G}}_1$ and ${\mathbb{G}}_2$.

Participates in

Builds on Decisional Diffie-Hellman

• DBDH + DLIN ⇒ HIBE (via DLIN)
• DBDH + DLIN ⇒ IBE (via DLIN)
• Bilinear pairing + DLIN ⇒ Zaps (non-interactive) (via DLIN)
• Sub-exponential SXDH + LWE + LPN + NC0-PRG ⇒ iO (via Sub-exponential SXDH)
• DDH + Sparse Learning Parity with Noise ⇒ Somewhat homomorphic encryption (SHE)
• DDH + UOWHF ⇒ CCA-secure PKE (Cramer–Shoup)
• DDH ⇒ CDH
• DDH ⇒ Highly lossy TDF (Peikert–Waters)
• DDH ⇒ UC-secure OT (PVW)
• DDH ⇒ Non-interactive key exchange (NIKE)
• DDH ⇒ Multiplicatively homomorphic encryption
• DDH ⇒ PKE
• DDH ⇒ PRF (Naor–Reingold)
• DDH ⇒ TDH
• DLIN ⇒ PKE (Linear Encryption) (via DLIN)
• DLIN ⇒ IPPE (via DLIN)
• DLIN ⇒ NIZK (via DLIN)
• Low-noise LPN + DDH ⇒ NIZK argument for NP
• Sub-exponential DDH ⇒ DDH (via Sub-exponential DDH)
• Sub-exponential DDH ⇒ NIZK argument for NP (via Sub-exponential DDH)
• Sub-exponential DDH ⇒ PPAD hardness (via Sub-exponential DDH)
• Sub-exponential SXDH ⇒ Sub-exponential DDH (via Sub-exponential SXDH)
• Sub-exponential SXDH ⇒ SXDH (via Sub-exponential SXDH)
• SXDH (Symmetric External Diffie-Hellman) ⇒ NIZK (via SXDH (Symmetric External Diffie-Hellman))
• SXDH ⇒ DDH (via SXDH (Symmetric External Diffie-Hellman))

Produces Decisional Diffie-Hellman

• GGM ⇒ DDH
• Sub-exponential DDH ⇒ DDH
• Sub-exponential SXDH ⇒ Sub-exponential DDH (via Sub-exponential DDH)
• Sub-exponential SXDH ⇒ SXDH (via SXDH (Symmetric External Diffie-Hellman))
• SXDH ⇒ DDH

Barriers

• No fixed-construction reduction from CDH to DDH
• No fully-black-box reduction from DDH to IBE — circumvented by CDH ⇒ IBE (Döttling–Garg)

Footnotes

1. Succinct means that the tuple $(\mathbb{G},g,p)$ is at most $\mathrm{poly}(\lambda )$-bits, but $|\mathbb{G}|=p$ may be super-polynomial in $\lambda .$ ↩