<p>What you're asking for has been called "correlated product" security for a trapdoor function.  See <a href="http://eprint.iacr.org/2008/116.pdf" rel="nofollow">this paper by Rosen and Segev</a>, 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.</p>

<p>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 <a href="http://eprint.iacr.org/2008/116.pdf" rel="nofollow">1</a> (which says that a lossy trapdoor function is correlated-product secure) with Section 5 of this <a href="http://eprint.iacr.org/2011/559.pdf" rel="nofollow">this paper by Kiltz, O'Neill, and Smith</a> that shows the RSA function is lossy under that assumption.  I haven't checked that the parameters works out, though.</p>

CC BY-SA 3.0
2013-07-07T21:26:06.863Z
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.)
Sadeq Dousti
CC BY-SA 3.0
2013-07-07T21:32:52.690Z
(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$).
Sadeq Dousti
CC BY-SA 3.0
2013-06-07T14:30:01.833Z
2013-06-07T14:30:01.833Z
David Cash
<p>In <a href="http://cacr.uwaterloo.ca/hac/about/chap8.pdf" rel="nofollow">chapter 8</a> (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.</p>

<p>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 <a href="http://en.wikipedia.org/wiki/Chinese_remainder_theorem" rel="nofollow">Chinese Remainder Theorem</a> to recover $m$. (See the above chapter for exact computations.)</p>

<blockquote>
  <p><strong>My question is:</strong> 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)?</p>
</blockquote>

<p>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?</p>

<ol>
<li>$(e_1,n_1) \leftarrow G(1^k)$ and $(e_2,n_2) \leftarrow G(1^k)$</li>
<li>$m \leftarrow_R \{1,\ldots,\min\{n_1,n_2\}\}$</li>
<li>$c_1 \leftarrow m^{e_1} \pmod{n_1}$ and $c_2 \leftarrow m^{e_2} \pmod{n_2}$</li>
<li>$m' \leftarrow A(e_1,n_1,e_2,n_2,c_1,c_2)$</li>
<li>IF $m'=m$ OUTPUT "$A$ succeeded"; ELSE OUTPUT "$A$ failed".</li>
</ol>

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

CC BY-SA 3.0
2013-06-06T05:32:31.780Z
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](http://crypto.stackexchange.com).
D.W.
CC BY-SA 3.0
2013-06-06T06:55:40.050Z
@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 http://cseweb.ucsd.edu/users/mihir/papers/musu.html).
Sadeq Dousti
CC BY-SA 3.0
2013-06-06T06:58:23.230Z
@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.
Sadeq Dousti
CC BY-SA 3.0
2013-06-07T16:46:47.840Z
@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
<cr.crypto-security>
Non-invertibility of RSA for two users
Sadeq Dousti
# Non-invertibility of RSA for two users

(Asked by: username_0 on 2013-06-04)

In [chapter 8](http://cacr.uwaterloo.ca/hac/about/chap8.pdf) (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](http://en.wikipedia.org/wiki/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$.

**Tags:** cr.crypto-security

> **Comments:**
> **username_1**: 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](http://crypto.stackexchange.com).  
> **username_0**: @username_1: 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 http://cseweb.ucsd.edu/users/mihir/papers/musu.html).  
> **username_0**: @username_1: 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.  
> **username_2**: @username_1, 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.  

---

## 1 answers

### Answer by username_3 on 2013-06-07. Score: 4

What you're asking for has been called "correlated product" security for a trapdoor function. See [this paper by Rosen and Segev](http://eprint.iacr.org/2008/116.pdf), 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](http://eprint.iacr.org/2008/116.pdf) (which says that a lossy trapdoor function is correlated-product secure) with Section 5 of this [this paper by Kiltz, O'Neill, and Smith](http://eprint.iacr.org/2011/559.pdf) that shows the RSA function is lossy under that assumption. I haven't checked that the parameters works out, though.

> **Comments:**
> **username_0**: 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.)  
> **username_0**: (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$).  

---

