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?


$(e_1,n_1) \leftarrow G(1^k)$ and $(e_2,n_2) \leftarrow G(1^k)$
$m \leftarrow_R \{1,\ldots,\min\{n_1,n_2\}\}$
$c_1 \leftarrow m^{e_1} \pmod{n_1}$ and $c_2 \leftarrow m^{e_2} \pmod{n_2}$
$m' \leftarrow A(e_1,n_1,e_2,n_2,c_1,c_2)$
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 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.

I don't know how to give a reduction to plain RSA to prove what you want, and I'd guess that it's very hard.  The best I can think of is to try to prove this under the so-called Phi-hiding assumption (see Cachin, Micali, Stadler, Eurocrypt'99, or reference below).  This may follow by combining Theorem 3.3 of 1 (which says that a lossy trapdoor function is correlated-product secure) with Section 5 of this this paper by Kiltz, O'Neill, and Smith that shows the RSA function is lossy under that assumption.  I haven't checked that the parameters works out, though.