PKI Multiple Samples start to expose Private Keys?

Question

My understanding is that using a PKI, public/private key pair is generally secure to send message to people. That is, encrypt a message using the recipient's public key so they use their private key to decrypt the message. My question is if encrypting the same "String" and sending them to multiple people starts to increase the possibility of cracking the private keys of the recipients as the number of samples go up.

For example, lets say I have the public key for the following people:

• ALICE
• BOB
• CAROL

I would like to secretly send each of them the same string so I encrypt that string in each of their public keys. In each data-set, it is clear to attackers that the same string is encrypted and sent to these 3 people. The public key would likely be present so it is clear to which private key the sample of encrypted data belongs. The hacker would not know what string has been encrypted, just that it is the same to all recipients.

Does this pose a situation where discovering the private keys can become simpler with more samples (More strings send to the users) and/or by increasing the number of recipients? Ultimately, does this condition decrease the effective privacy of the PKI encryption/decryption method?

Answer 1

1. There's a wide gap between plaintext recovery and key recovery. Of course, what is of interest to users is the confidenitality of their plaintext, but if an attacker can merely recover a single plaintext (which might happen outside the domain of crypto if the user just leaves it on the tube on their way to work!), that doesn't mean they can recover the next one—while if they can recover the key, they now have all the power of the legitimate user.

2. Public-key encryption is necessarily randomized so that if you send the same message to three people, or even send the same message to the same person three times, I still can't tell that just by looking at the ciphertexts without breaking the crypto.

Answer 2

In short

If the scheme is at least CPA-secure, then it is safe to encrypt and send the same message to different parts as you described.

Long answer

In the CPA-security game, the attacker has the ability of encrypting a $poly(\lambda)$ messages, which may even be the same message, and then it is still hard to distinguish two ciphertexts.

Therefore, an attacker that sees many ciphertexts of a single message under a same public key cannot recover the private key, otherwise, they would be able to distinguish the challenge ciphertexts.

Your scenario is even simpler, because you are supposing that a single message is encrypted under different public keys. Thus, supposing that those keys were independently generated, the attacker is actually trying to break the CPA-security of three independent encryption schemes with only one pair of message-ciphertext to each.