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?

  • $\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 '19 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 '19 at 0:12

Browse other questions tagged or ask your own question.