# Is there a way to provide proof of batch RSA security?

Suppose we have two encrypted messages with two different public key issued from the one server. There is a client who wants to send these to messages to the server.

In the middle there is an adversary, who eavesdrops all the communications, so he already got the two encryption keys and the two encrypted messages.

According to batch RSA, the adversary can recover the encrypted messages without the need to use the private key to decrypt the messages. Can anyone explain how can we prove that batch RSA is secure in such a scenario?

-

The attack Henrick refers to is called Håstad's broadcast attack. See for instance here. Interestingly, this attack also applies when using weak (linear) padding. Using random padding and larger public exponents in RSA ($e=2^{16}+1$ as it is common) renders these attacks useless in practice. –  DrLecter Oct 25 '13 at 10:53