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$.
Non-invertibility of RSA for two users
cr.crypto security