Non-invertibility of RSA for two users

In chapter 8 (page 288) of the "Handbook of Applied Cryptography," the authors describe an attack against RSA with small exponent. Let there be 3 parties with independent RSA public keys $(e_1,n_1)$, $(e_2,n_2)$, and $(e_3,n_3)$, with $e_1=e_2=e_3=3$. With very high probability, the moduli are coprime; otherwise, it would be possible to factor them.

Consider a forth party, who wishes to secretly send a single message $m$ to the 3 parties above. He computes $c_i = m^3 \pmod{n_i}$, and sends $c_i$'s on the channel. The adversary, who eavesdrops the ciphertexts, can simply apply the Chinese Remainder Theorem to recover $m$. (See the above chapter for exact computations.)

My question is: Assume that there are only two recipients, instead of three. Given $c_1$ and $c_2$, is it possible to prove (under the RSA assumption) that the adversary cannot recover $m$ (except with negligible probability)?

More formally, let $G$ be an RSA public-key generator, and $A$ be a PPT adversary. Is it possible to prove, under the RSA assumption, that the success probability of $A$ is negligible in the experiment below?

1. $(e_1,n_1) \leftarrow G(1^k)$ and $(e_2,n_2) \leftarrow G(1^k)$
2. $m \leftarrow_R \{1,\ldots,\min\{n_1,n_2\}\}$
3. $c_1 \leftarrow m^{e_1} \pmod{n_1}$ and $c_2 \leftarrow m^{e_2} \pmod{n_2}$
4. $m' \leftarrow A(e_1,n_1,e_2,n_2,c_1,c_2)$
5. IF $m'=m$ OUTPUT "$A$ succeeded"; ELSE OUTPUT "$A$ failed".

PS: One can assume any technical condition to make the proof work; say $e_1=e_2$.

• What is the motivation for this question? The 3-party CRT attack only applies to unpadded RSA (aka "textbook RSA"). Fortunately, no one uses unpadded RSA (textbook RSA) any more, as unpadded RSA is known to be completely insecure. Even if this attack is not possible in the situation you outlined, unpadded RSA is still a terrible idea. P.S. You might be more likely to get a good answer on Crypto.SE. – D.W. Jun 6 '13 at 5:32
• @D.W.: Actually, I'm designing a protocol which uses something different than RSA, where padding does not easily apply, but the construct is rather similar to the "RSA for two users" problem described here. I think if I get a good answer for this question, I can use the ideas in my real-world problem. Besides, this question is theoretically appealing, as it has a counterpart when the textbook RSA (a one-way permutation) is replaced with a semantically-secure encryption (see cseweb.ucsd.edu/users/mihir/papers/musu.html). – M.S. Dousti Jun 6 '13 at 6:55
• @D.W.: Finally, thanks for the advice. I believe Crypto.SE is less theoretically inclined than CSTheory, and I'm less likely to get a proof there. But I'll try cross-posting there if I don't get an answer here. – M.S. Dousti Jun 6 '13 at 6:58
• @D.W., theoretical cryptography is part of TCS and completely on-topic here. Please don't try to move the on-topic cryptography questions from here to another site. – Kaveh Jun 7 '13 at 16:46

What you're asking for has been called "correlated product" security for a trapdoor function. See this paper by Rosen and Segev, which lays out the definition. Your question fixes $k$ from their Definition 3.2 to $2$; as you (and their paper) note, we know that the RSA trapdoor function with exponent $e\leq k$ is not correlated-product secure.
• Thanks for the answer. I checked the papers, and I suspect that the parameters do not work for the case of RSA (unfortunately). More specifically, Rosen–Segev Theorem 3.3 states that $k < \frac{n-\omega(\log n)}{n-\ell}$, where $\ell$ is the lossiness. On the other hand, Kiltz–O'Neill–Smith Proposition 5.2 states that (two-prime) RSA achieves $cn/2$ bit of lossiness, where $c < 1/4$ to prevent Coppersmith's attack. (Note that $n/2$ is the length of modulus. The paper itself uses $k$ instead of $n/2$, but that would mix terminology with Rosen–Segev's paper.) – M.S. Dousti Jul 7 '13 at 21:26
• (Cont'd) Since we have to achieve $k$-correlation security for $k=2$, we need $\frac{n-\omega(\log n)}{n-cn/2} > 2$. But this means $c \in C \subseteq (1,2)$, which contradicts the assumption that $c < 1$ (and more precisely, $c < 1/4$). – M.S. Dousti Jul 7 '13 at 21:32