Are there public key schemes that have perfect secrecy? The perfect secrecy notion is defined for symmetric key encryption. If P is a message and C the corresponding ciphertext then the cipher has perfect secrecy if pr(P|C)=pr(P). This equivalently means in terms of entropy that the conditional entropy H(P|C)=H(P). Originally as defined in Shannon's paper the encryption system is not classified as block or stream cipher. In practice it has to be one of the two and the message length is a priori fixed to a maximum. Hence for a public key scheme with the message length fixed perfect secrecy is still meaningful when probability distribution of the maximum length message is considered. In general H(P|C)< H(P). Since all public key schemes are secured in computational sense H(P|C)=0 which means an infinitely powerful adversary can always break the encryption. Can a perfectly secure public key scheme be defined? If there is one which scheme is it?


marked as duplicate by kelalaka, Squeamish Ossifrage, AleksanderRas, Maarten Bodewes Sep 15 at 19:51

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ I agree that there is some overlap of my question with previously asked question. But the question differs substantially. I am asking whether there is perfectly secure public key scheme. As I pointed out the RSA satisfies H(P|C)=0 since it is in principle computationally breakable hence RSA cannot be perfectly secure. But is it not possible for a randomised public key encryption to be perfectly secure? $\endgroup$ – Viren Sule Sep 16 at 16:40
  • $\begingroup$ If the message length is finite, then for the OTP encryption c=p+k a compuationally unbounded adversary can try all possible key pads and recognise the message with probability 1. In this way even the symmetric key OTP with finite length doesnt have perfect secrecy. In public key the relation between public and private key is breakable by brute force since both have finite length and a fixed mathematical relation. So what is the meaning of perfect secrecy for finite messages and keys? $\endgroup$ – Viren Sule Sep 17 at 0:12

Browse other questions tagged or ask your own question.