# Proof that padded RSA is CPA-secure

I'm referring to page 383 of J. Katz and Y. Lindell's Introduction to Modern Cryptography. The book presents a padded RSA:

• ${\bf Key Generation:}$ same as Textbook RSA (given security parameter $1^n$, generate public key ($N,e$), secret key ($N,d$), such that $N = pq, ed \equiv 1 \mod{(p-1)(q-1)}$)
• ${\bf Encryption:}$ given public key ($N,e$), and message $m$ of length $l(n) \leq 2n - 2$, choose random bit string $r$ of length $2n - l(n) - 1$, and interpret the padded message $r||m$ (where $||$ is concatenation) as an element of $(\mathbb{Z}/N\mathbb{Z})^*$. Output the ciphertext $c := (r||m)^e \mod{N}$.
• ${\bf Decryption:}$ given secret key ($N,d$), and cipertext $c$, compute $m' := c^d \mod{N}$, and ouput the $l(n)$ low-order bits of $m'$

The book claims that if $l(n) = O(\log{N})$, then the padded cryptosystem is CPA-secure. Unfortunately, it states that the full proof is beyond the scope of the book. Where can I find the full proof of the CPA-security of this version of padded RSA?

This result is proven in the following research papers:

They show that if you can predict the least significant bit (or the $O(\log \log N)$ least significant bits), then you can break RSA. See also the citations in that article for similar results.

I can give you a taste for why this might be true, by sketching how to prove a much weaker version: if you have a way to compute the least significant bit of $x$ from the RSA encryption $E(x)$, then I can break RSA.

Let me start with a warmup. Suppose you have a black box that, given a ciphertext $E(x)$, can answer the yes-or-no question is $x$ in the range $[0, N/2)$?''. Suppose your black box is perfect: it always gives the right answer. Let me show you how I can use your black box to break RSA.

Notation: Here $E(x)$ denotes the RSA encryption of message $x$, i.e., $E(x) = x^e \bmod N$. Notice that there is no padding and no randomization in my definition of $E(\cdot)$. Also note that RSA is homomorphic, so $E(2x) = 2^e E(x) \bmod N$. In other words, given $E(x)$, I can derive $E(2x)$ even without knowing $x$. I will use the notation $[a,b)$ to represent the set of integers $a,a+1,a+2,\ldots,b-1$.

Now let's solve the warmup problem. We are given $E(x)$, and we want to find $x$. Basically, we're going to use binary search.

• First, we query your black box with $E(x)$ to learn whether $x$ is in the range $[0,N/2)$ or in the range $[N/2,N)$. Suppose we learn that $x$ was in the range $[0,N/2)$.

• Next, we query your black box with $E(2x)$. This tells us whether $2x$ is in the range $[0,N/2)$ or in $[N/2,N)$, which in turn tells us whether $x$ is in the range $[0,N/4)$ or in $[N/4,N/2)$. Suppose we learn that $x$ is in the range $[N/4,N/2)$.

• Next, we query your black box with $E(4x)$. This tells us whether $4x \bmod N$ is in the range $[0,N/2)$ or in $[N/2,N)$. Note that $4x \bmod N = 4x-N$ (given what we know about the range $x$ is in). So, we know whether $4x-N$ is in the range $[0,N/2)$ or in $[N/2,N)$, which in turn tells us whether $x$ is in the range $[N/4,3N/8)$ or in $[3N/8,N/2)$.

• Keep going like this, until $x$ is completely known.

This requires $O(\lg N)$ queries to your black box. If your black box always gives the correct answer, then at the end we learn the exact value of $x$.

In other words, if you have a black box like that, then given any RSA ciphertext $E(x)$, I can derive $x$: which is a total break of RSA. (Conversely, if we assume RSA is secure, then such a black box is impossible to build.)

The warmup above might start to give you some idea of what it might look like to try to prove the stronger result.

• For instance, suppose you don't have a black box that answers the question "is $x$ in the range $[0,N/2)$?", but you do have a green box that answers the question "is the least significant bit of $x$ one?".

Well, given a green box, we can build a black box. Given $E(x)$, we query the green box on $E(2x) = 2^e E(x) \bmod N$; if it answers "yes", then $x$ is in the range $[0,N/2)$, otherwise $x$ is in the range $[N/2,N)$. So, the green box's answer to $E(2x)$ reveals how the black box should respond to the query $E(x)$.

Therefore, if you have a green box that can compute the least significant bit, you can break RSA (by constructing a black box and applying the binary search method as above). Conversely, if we think RSA is secure, then there should be no way to build a green box like this.

• As another example of a generalization, suppose your black box doesn't always give the right answer; it answers correctly with probability $1/2 + \epsilon$, and incorrectly with probability $1/2 - \epsilon$, for some $\epsilon>0$. Then we have an instance of a game of 20 questions, where we have only a noisy view of our answer. It turns out there are algorithmic ways to deal with this noise, though it does take a lot of difficult technical work. For the details, see the papers mentioned above.