RSA ⇒ PKE

Standard model · ACGS88 · security loss: polynomial: a CPA adversary with advantage $\epsilon$ predicts the least-significant bit of $x$ from $(n,e,x^e\mathrm{mod}n)$ with the same advantage, and ACGS88 turn such a predictor into an RSA inverter running in time $\mathrm{poly}(\log n,1/\epsilon )$

Statement

The RSA assumption implies PKE. The scheme of RSA78, $\mathsf{Enc}(\mathsf{pk},m)=m^e\mathrm{mod}n$ and $\mathsf{Dec}(\mathsf{sk},c)=c^d\mathrm{mod}n$, is one-way under the RSA assumption but deterministic, hence not CPA-secure. Encrypting a bit $b$ as $(x^e\mathrm{mod}n,b\oplus h(x))$ for $x\stackrel{\$}{\leftarrow }{\mathbb{Z}}_n^{\ast }$ is CPA-secure under the RSA assumption when $h$ is a hard-core predicate of the RSA function; the least-significant bit is one, since predicting it from $(n,e,x^e\mathrm{mod}n)$ with non-negligible advantage yields an RSA inverter — ACGS88.

Sketch

Decryption recovers $x=y^d\mathrm{mod}n$ from $y=x^e\mathrm{mod}n$ with the trapdoor $d$. A CPA adversary distinguishing encryptions of $0$ and $1$ is a predictor for $h(x)$ given $(n,e,y)$, which the hard-core reduction turns into an RSA inverter.

Notes

• The Goldreich–Levin bit $⟨x,r⟩\mathrm{mod}2$ is hard-core for $(x,r)\mapsto (x^e\mathrm{mod}n,r)$, which gives the same bit encryption, with $r$ sent in the clear, without an RSA-specific argument — GL89; for an arbitrary trapdoor permutation this is TDP ⇒ PKE.
• Efficiency: the CPA-secure scheme spends, per plaintext bit, one exponentiation by the public exponent, which may be small, such as $e=2^{16}+1$, and a ciphertext of $\log n+1$ bits; decryption is one exponentiation by $d$ per bit, which the Chinese remainder theorem splits into two exponentiations modulo $p$ and $q$ with half-length exponents. Deterministic RSA encrypts a whole $\log n$-bit block at that cost — standard.