I have the following definition of Shannon's Perfect Security.

Assuming messages and keys are drawn randomly from some distribution then:

  1. The probability of guessing plaintext m is not enhanced by knowing any ciphertexts, i.e. $P(M=m| C=c) = P(M=m)$
  2. The keys are drawn uniformly at random and are only used for one encryption.

Does this apply to asymmetric encryption as well? How does statement 2 apply when we have public keys for encryption, say RSA encryption?

If Shannon's perfect security can be generalized then does this mean that RSA is perfectly secure?

  • 1
    $\begingroup$ I can see you're in the mood, but please relax with the number of questions. Handling one or two at the time is much easier :) $\endgroup$
    – Maarten Bodewes
    Commented May 3 at 0:52
  • $\begingroup$ Perfect secrecy requires that key size > message size. This is the first problem. The second all-public key cryptosystem relies on the hardness of some mathematical problem that is not informatically proven to be secure. Getting $p$ is nearly half of the key whereas we can recover all ( get half of the OTP bits that is all you got). This prevents informational security. Besides this requirement is the opposite of the public key that one has to generate again. $\endgroup$
    – kelalaka
    Commented May 3 at 11:10

1 Answer 1


There is no perfectly secured public-key encryption scheme.

In the asymmetric world, an adversary is allowed to encrypt a message of its choice using the public key, so it can't be that "that keys are only used for one encryption".

Consider the following attacker for some encrypted message $c=E(pk,m)$, where $m\in\{0,1\}^{n}$:

  1. Sample $m_{0}\leftarrow \{0,1\}^{n}$.
  2. If $E(pk,m_{0})=c$, output $m_{0}$.
  3. Otherwise, sample $m_{1}\leftarrow \{0,1\}^{n}$ and output it.

Clearly, knowing the ciphertext does enhance the probability of guessing the plaintext (by a negligible amount, of course, as we need to both guess the message and the randomness used by $E(pk,\cdot)$), which means the scheme is not perfectly secured.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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