DDH + UOWHF ⇒ CCA-secure PKE (Cramer–Shoup)

Fully-black-box reduction · standard model · CS98 · security loss: additive: the CCA advantage is at most twice the sum of the DDH and target-collision advantages, plus O(Q/q) for Q decryption queries

Statement

Let $\mathbb{G}$ be a group of prime order $q$ in which DDH holds, and let $\mathsf{H}$ be a universal one-way hash function family mapping ${\mathbb{G}}^3$ into ${\mathbb{Z}}_q$. The Cramer–Shoup cryptosystem below is IND-CCA2-secure — CS98.

\begin{algorithm}
\algname{Algorithm}
\caption{Cramer–Shoup}
\begin{algorithmic}
\State $\KeyGen$: $g_1, g_2 \getsr \GG$; $x_1, x_2, y_1, y_2, z \getsr \ZZ_q$; $k \getsr \calK$
\State $\pk := (g_1, g_2, c = g_1^{x_1} g_2^{x_2}, d = g_1^{y_1} g_2^{y_2}, h = g_1^{z}, k)$; $\sk := (x_1, x_2, y_1, y_2, z)$
\State $\Enc(\pk, m)$: $r \getsr \ZZ_q$; $u_1 := g_1^r$; $u_2 := g_2^r$; $e := h^r m$; $\alpha := \hash_k(u_1, u_2, e)$; $v := c^r d^{r\alpha}$
\Return $(u_1, u_2, e, v)$
\State $\Dec(\sk, (u_1, u_2, e, v))$: $\alpha := \hash_k(u_1, u_2, e)$
\If{$u_1^{x_1 + y_1 \alpha} u_2^{x_2 + y_2 \alpha} \ne v$}
\Return $\bot$
\EndIf
\Return $e / u_1^{z}$
\end{algorithmic}
\end{algorithm}

Sketch

Given $(g_1,g_2,u_1,u_2)$, the reduction samples $x_1,x_2,y_1,y_2,z_1,z_2\stackrel{\$}{\leftarrow }{\mathbb{Z}}_q$, publishes $h:=g_1^{z_1}{g}_2^{z_2}$, which is distributed as in $\mathsf{KeyGen}$, and decrypts by $e/(u_1^{z_1}{u}_2^{z_2})$, which agrees with $\mathsf{Dec}$ whenever ${\log }_{g_1}{u}_1={\log }_{g_2}{u}_2$. It builds the challenge from $u_1,u_2$ and these exponents. On a DDH tuple this is the real game. On a random tuple, $u_1^{z_1}{u}_2^{z_2}$ is uniform given the public key, so the hidden bit is information-theoretically hidden, provided every decryption query with ${\log }_{g_1}{u}_1^{\prime }\ne {\log }_{g_2}{u}_2^{\prime }$ is rejected; each such query passes the check with probability $O(1/q)$ unless it carries the challenge’s hash value on a different input, which is a target collision — CS98.

Notes

• Efficiency: a ciphertext is four group elements, twice ElGamal’s; encryption costs about five exponentiations and decryption about three — CS98.
• Without $g_2$, $u_2$ and the $(c,d,v)$ components the scheme is ElGamal — ElGamal85 — which is IND-CPA-secure under DDH — TY98 — and malleable — standard.
• The proof generalizes to universal hash proof systems, which give IND-CCA2 encryption from quadratic residuosity and from decisional composite residuosity — CS02.