# CPA-security proof of “l-padded RSA” encryption scheme

The 10.9 exercise from the Katz-Lindell textbook creates a lot of confusion, let me state it here. Consider the following experiment for an algorithm $A$ and a function $l$ with $l(n) \leq 2n-2$ for all $n$:

The padded RSA experiment $PAD_{A,GenRSA,l}(n)$:

1. $(N,e,d) \leftarrow GenRSA(1^n)$.
2. Give $N$, $e$ to $A$, who outputs a string $m \in \{0,1\}^{l(n)}$.
3. Choose random $y_0 \leftarrow \mathbb{Z}^*_N$ and $r \leftarrow \{0,1\}^{||N||-l(n)-1}$, then set $y_1=[(r||m)^e \mod N]$.
4. Choose a random bit $b \leftarrow \{0,1\}$. Adversary $A$ is given $y_b$, and outputs a bit $b'$.
5. The output of the experiment is $1$ if $b'=b$, and $0$ otherwise.

The exercise asks to prove that if this $l-padded$ $RSA$ is hard relative to $GenRSA$, then this $PAD$ construction using $l$ is CPA-secure. Unfortunately my crypto teacher stated that "if $l(n) \leq 2n-2$ then this construction is conjectured secure but there is no formal proof based on standard RSA", which is precisely what the exercise is asking (if my understanding is correct). Please don't mark this question as a duplicate of this one, because it's not, note that I'm expliciting when $l(n) \leq 2n-2$ and not when $l(n)=O(\log n)$.

So, my question is: how should I procede, as the exercise task apparently contradicts the teacher's statement?

• What is your question? There is no question mark in there. All I see are statements. – mikeazo Aug 27 '15 at 17:10
• Sorry, my question is how should I procede, as the exercise task apparently contradicts the teacher's statement. – pa5h1nh0 Aug 27 '15 at 17:13
• I don't know this for a fact, but notice that the problem says "prove that if ... is hard ... then ... is CPA-secure". Could it be that your professor is saying that there is no formal proof that the if statement is true? In other words, the problem is saying, assume X, now prove Y, while your profesor is saying that we don't really know if X is true? Therefore, there is no conflict. – mikeazo Aug 27 '15 at 17:22
• Hmm, I see. Ok, so if I'll construct an adversary $A$, in this padded RSA experiment, in such a way that when it breaks the $PAD$ scheme then an adversary $A'$ will also break the $RSA$ $problem$, do you think this could be right way? – pa5h1nh0 Aug 27 '15 at 17:33
• That sounds like a reasonable way to do it. – mikeazo Aug 27 '15 at 17:34