DCR ⇒ PKE

Fully-black-box reduction · standard model · Pai99 · security loss: tight: one call to the CPA adversary

Statement

DCR implies CPA-secure PKE: the Paillier cryptosystem has public key $(n,g)$ with $n=pq$ an RSA modulus and $g\in {\mathbb{Z}}_{n^2}^{\ast }$ of order a nonzero multiple of $n$ ($g=1+n$ suffices), and encrypts $m\in {\mathbb{Z}}_n$ as $c=g^m{r}^n\mathrm{mod}{n}^2$ for $r\stackrel{\$}{\leftarrow }{\mathbb{Z}}_n^{\ast }$; the scheme is semantically secure iff DCR is hard — Pai99.

Sketch

The reduction sets the challenge ciphertext to $c^{\ast }=g^{m_b}\cdot z\mathrm{mod}{n}^2$ for DCR challenge $z$: if $z$ is an $n$-th residue this is a correctly distributed encryption of $m_b$, and if $z$ is uniform in ${\mathbb{Z}}_{n^2}^{\ast }$ the ciphertext is uniform and independent of $b$.

\begin{algorithm}
\algname{Algorithm}
\caption{$\KeyGen(1^\secpar)$}
\begin{algorithmic}
\State sample distinct $\secpar$-bit primes $p, q$; $n \gets pq$; $\varphi \gets (p-1)(q-1)$
\Comment{Equal length gives $\gcd(n, \varphi) = 1$}
\Return $(\sk, \pk) \gets ((n, \varphi), n)$
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\algname{Algorithm}
\caption{$\Enc(\pk, m)$}
\begin{algorithmic}
\State $r \getsr \ZZ_n^*$
\Comment{$m \in \ZZ_n$; $g = 1+n$ has order $n$ in $\ZZ_{n^2}^*$}
\Return $c \gets (1+n)^m \cdot r^n \bmod n^2$
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\algname{Algorithm}
\caption{$\Dec(\sk, c)$}
\begin{algorithmic}
\State $u \gets c^{\varphi} \bmod n^2$
\Return $m \gets \frac{u - 1}{n} \cdot \varphi^{-1} \bmod n$
\Comment{$u = 1 + m \varphi n \bmod n^2$}
\end{algorithmic}
\end{algorithm}

Notes

• The simplification $g=1+n$ and the generalisation to modulus $n^{s+1}$ are from DJ01.
• Efficiency: a ciphertext is one element of ${\mathbb{Z}}_{n^2}^{\ast }$, twice the length of a plaintext in ${\mathbb{Z}}_n$. With $g=1+n$, $g^m\equiv 1+mn(\mathrm{mod}{n}^2)$, so encryption costs one exponentiation $r^n\mathrm{mod}{n}^2$ and decryption one exponentiation by $\phi$ — standard. Working modulo $n^{s+1}$ with plaintexts in ${\mathbb{Z}}_{n^s}$ lowers the expansion to $(s+1)/s$ — DJ01.