I would be very grateful for any help. I cant figure out why (probabilistic) public key encryption schemes can never provide perfect secrecy? Any Ideas?

Excerpt: In contrast to the private-key setting, perfectly-secret public-key encryption does not exist. (We stress that this holds regardless of how long the keys are and how short the message is.) In fact, given pk and a ciphertext c computed via c ← Enc_pk(m), it is possible for an unbounded adversary to determine the message m with probability 1.

(See comments for why this is not a duplicate.)

  • $\begingroup$ What makes you think they can't? Just because we don't know of one that does, does not mean that one does not exist. I am not aware of any proof stating that a public key cipher cannot provide perfect secrecy. Are you? $\endgroup$
    – mikeazo
    May 14 '15 at 2:35
  • $\begingroup$ @James I'm not sure what part of the linked question you're confused by. Do you get why a computationally unbounded adversary can find a private key corresponding to any public key (and thus decrypt a message encrypted with said public key)? If so, do you get why that implies that $\Pr(M=m\mid C=c)$ cannot generally be equal to $\Pr(M=m)$? The core concept of perfect security is that there is no information in the ciphertext alone; if a computationally unbounded adversary can decrypt the ciphertext without the private key, there must be information there. $\endgroup$
    – cpast
    May 14 '15 at 3:23
  • $\begingroup$ @cpast If I understand you correctly, you are saying that the adversary can exhaustively search the private key space to find the private key that decrypts the ciphertext and thus Public key cannot be perfectly secure. But if we follow that logic, wouldn't a similar argument conclude that One time pads aren't perfectly secure because an adversary with a given ciphertext c search the key space and eventually find the desired key k that decrypts it, and thus make it not perfectly secure? Thank you in advance for any clarification! $\endgroup$
    – Gordon
    May 14 '15 at 3:42
  • $\begingroup$ @James Ah. No, and the difference is this: An OTP adversary knows nothing about the secret key. A public-key adversary does know something: they know the public key that the private key corresponds to. The KeyGen algorithm in the accepted answer there isn't used to enumerate all private keys; it's used to enumerate all keypairs. The attacker doesn't directly look for the private key; what they're looking for is a keypair with the same public key as the victim, and the associated private key (which the attacker knows, having generated the keypair) will decrypt the message. $\endgroup$
    – cpast
    May 14 '15 at 4:06
  • $\begingroup$ I'm currently writing up an alternate way, which revolves around encrypting all possible messages. $\endgroup$
    – cpast
    May 14 '15 at 4:08

The threshold for a perfectly secure system is that a computationally unbounded adversary cannot conclude anything about the plaintext from the ciphertext. With a public-key system, the attacker can try to encrypt messages with the real public key; this is not possible with one-time pads. What the attacker can do, quite simply, is to try all one-bit messages, then all two-bit messages, then all three-bit messages, etc., looking for a matching ciphertext.

Now, a public-key encryption algorithm may involve some randomness. The way to handle this is to try all possible outputs of the random number generator. You can make an algorithm $\textsf{Check(c,k,m,r)}$, where $c$ is the known ciphertext, $k$ the known public key, $m$ the guessed message, and $r$ is a string of bits. This runs the public-key algorithm with key $k$ on message $m$. Where the algorithm needs a random bit, it takes the first unused bit of $r$ (so it starts with the first bit, then the second, etc.), so the algorithm becomes deterministic. If all the bits of $r$ have been used and it needs another random bit, or if the encryption completes and the generated ciphertext does not match $c$, it returns False; if the encryption completes and the ciphertext matches $c$, it returns True. You can then run $\textsf{Check}$ with 1-bit $m$ and 1-bit $r$, then 1-bit $m$ and 2-bit $r$, then 2-bit $m$ and 1-bit $r$, then 3 and 1, then 2 and 2, then 1 and 3, etc. (i.e. the sum of the lengths of $m$ and $r$ is two, then three, then four, etc.) This will terminate with $\textsf{Check}$ returning True; when it does, you know what $m$ is.

  • $\begingroup$ This only works if an honestly generated public key has probability greater than half of being such that different messages cannot result in the same ciphertext. $\;$ $\endgroup$
    – user991
    May 14 '15 at 5:01
  • $\begingroup$ @RickyDemer No two valid messages can ever have the same ciphertext in any sound encryption system; any ciphertext that can be the result of two different messages can never be the result of a valid encryption. It is impossible to decrypt if they do. $\endgroup$
    – cpast
    May 14 '15 at 5:48
  • $\begingroup$ James did not say that he wants the definition of soundness you're apparently referring to. $\hspace{.82 in}$ Such a PKE scheme cannot be sender-deniable. $\;$ $\endgroup$
    – user991
    May 14 '15 at 6:33
  • $\begingroup$ @RickyDemer: I don't really see any way to have sender-deniable public key encryption against a computationally unbounded adversary; in particular, the adversary can always recover the private key by enumerating the keyspace, and then decrypt the message. With overwhelming probability, the plaintext they get is what was originally encrypted, or at least what the intended recipient would have received. $\endgroup$ May 19 '15 at 16:27
  • $\begingroup$ @IlmariKaronen : $\;\;\;$ That's because there is none. $\:$ However, what do you propose should be checked during the enumeration of the keyspace? $\;\;\;\;\;\;\;\;$ $\endgroup$
    – user991
    May 19 '15 at 18:42

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