I'm looking for a proof of this theorem

  • $\begingroup$ Just think about an attack. It can be terribly costly and have negligible success probability. However, if you find such an attack that proves that the scheme is not information-theoretically secure. If you can figure out a generic attack that works for all PKE schemes you are done. $\endgroup$ – mephisto Jul 4 '18 at 9:43
  • $\begingroup$ PKE schemes are not uncoditionally (or perfectly, or theoretically, or whatever you prefer) secure accroding to Shannon's Theorem. I'm looking for a formal proof $\endgroup$ – Luigi2405 Jul 4 '18 at 9:55
  • $\begingroup$ Do you know of a formal proof of Shannon's theorem? (You can find that anywhere with 3s of research, it's probably on Wikipedia). A formal proof of this theorem will in particular be a formal proof that no PKE scheme is unconditionnally secure. $\endgroup$ – Geoffroy Couteau Jul 4 '18 at 12:09
  • $\begingroup$ @GeoffroyCouteau 3 seconds? I've found it in just 2.. when I was looking for that. I'm interested in another theorem but luckly someone has understood me $\endgroup$ – Luigi2405 Jul 4 '18 at 15:33
  • $\begingroup$ You are interested in "another theorem"? You explicitly stated that you are looking for a proof that no PKE can be unconditionally secure. Which is exactly an immediate corollary of Shannon's theorem about perfect secrecy (Cédric essentially re-proved Shannon's theorem for the specific case of public-key encryption in his (good) answer below). It seems to me that you were looking for an explanation of Shannon's theorem in the specific case of PKE, not for a formal proof of Shannon's theorem - or are we not talking about the same theorem of Shannon? Anyway, if you got your answer, it's fine :) $\endgroup$ – Geoffroy Couteau Jul 4 '18 at 15:43

I will just turn @mephisto's comment into a longer answer.

The following attack will work against any public-key encryption scheme:

  • The attacker has access to the public key and, say, a ciphertext encrypting some unknown message
  • for every possible secret key (by enumerating the key space), the attacker does the following:
    • checking whether the secret key does correspond to the known public key (for instance, by encrypting every single possible message then trying to decrypt them using this secret key)
    • when a secret key was found that passed the test of the previous step, the attacker uses it to decrypt the message

Of course this attack will take a gigantic amount of resources, but it will work against any PKE. Now this goes against the idea of perfect secrecy which says that getting a ciphertext gives no information about the plaintext, even for an adversary with unbounded resources.

Note how such attack will not work against the one-time-pad: an adversary attacking a one-time-pad only gets a ciphertext, there is no public key. If the adversary picks a random key, betting that it is the key that was used for encryption, it has no way to tell whether it was right or wrong in picking this key.

  • 1
    $\begingroup$ No, now he did your homework :-P $\endgroup$ – mephisto Jul 5 '18 at 8:18
  • $\begingroup$ Of course he did. Now go back and do yours :) $\endgroup$ – Luigi2405 Jul 5 '18 at 12:46

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.