DDH ⇒ PKE

Fully-black-box reduction · standard model · ElGamal85, TY98 · security loss: tight: one oracle call, advantage-preserving

Statement

DDH implies CPA-secure PKE: the ElGamal scheme over $(\mathbb{G},g,p)\leftarrow \mathsf{GrGen}(1^{\lambda })$ has $\mathsf{sk}=x\stackrel{\$}{\leftarrow }[p]$ and $\mathsf{pk}=y=g^x$, encrypts $m\in \mathbb{G}$ as $(g^r,m\cdot y^r)$ for $r\stackrel{\$}{\leftarrow }[p]$, and decrypts $(c_1,c_2)$ as $c_2\cdot c_1^{-x}$. The scheme is from ElGamal85; it is semantically secure iff DDH is hard for $\mathsf{GrGen}$ — TY98.

Sketch

On DDH challenge $(X,Y,Z)$ the reduction sets $\mathsf{pk}=X$ and answers the challenge query with $(Y,m_b\cdot Z)$: for $Z=g^{xy}$ this is a correctly distributed encryption of $m_b$, and for uniform $Z$ the ciphertext is uniform and independent of $b$.

\begin{algorithm}
\algname{Algorithm}
\caption{$\KeyGen(1^\secpar)$}
\begin{algorithmic}
\State $(\GG, g, p) \gets \GrGen(1^\secpar)$
\State $x \getsr [p]$; $y \gets g^x$
\Return $(\sk, \pk) \gets ((\GG, g, p, x), (\GG, g, p, y))$
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\algname{Algorithm}
\caption{$\Enc(\pk, m)$}
\begin{algorithmic}
\State $r \getsr [p]$
\Comment{$m \in \GG$}
\Return $c \gets (g^r, m \cdot y^r)$
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\algname{Algorithm}
\caption{$\Dec(\sk, (c_1, c_2))$}
\begin{algorithmic}
\Return $m \gets c_2 \cdot c_1^{-x}$
\end{algorithmic}
\end{algorithm}

Notes

• ElGamal85 predates the DDH assumption; the DDH-based CPA proof is later — TY98.
• Efficiency: a ciphertext is two group elements for a one-element message; encryption costs two exponentiations and decryption one — standard.