I'm looking for a proof of this theorem
6
-
$\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$– mephistoCommented Jul 4, 2018 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$– Luigi2405Commented Jul 4, 2018 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 CouteauCommented Jul 4, 2018 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$– Luigi2405Commented Jul 4, 2018 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 CouteauCommented Jul 4, 2018 at 15:43
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
2
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$ Of course he did. Now go back and do yours :) $\endgroup$ Commented Jul 5, 2018 at 12:46