2
$\begingroup$

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$.

Improve this question
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Jun 6, 2013 at 5:32
  • $\begingroup$ @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). $\endgroup$
    – M.S. Dousti
    Jun 6, 2013 at 6:55
  • $\begingroup$ @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. $\endgroup$
    – M.S. Dousti
    Jun 6, 2013 at 6:58
  • $\begingroup$ @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. $\endgroup$
    – Kaveh
    Jun 7, 2013 at 16:46

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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.) $\endgroup$
    – M.S. Dousti
    Jul 7, 2013 at 21:26
  • $\begingroup$ (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$). $\endgroup$
    – M.S. Dousti
    Jul 7, 2013 at 21:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.