What is perfect (information-theoretic) security, and what does $p(m \mid c) = p(m)$ mean?

Perfect security means observing the ciphertext gives an attacker absolutely zero information about the plaintext — the ciphertext is statistically independent of the message.

* Perfect secrecy: seeing the ciphertext leaves every message as likely as before — $p(m \mid c) = p(m)$. *

The formula $p(m \mid c) = p(m)$ states: the probability of a message $m$ given ciphertext $c$ equals the prior probability of $m$ — knowing $c$ doesn't help at all.

Requirements for perfect security:

• The key must be truly random (not pseudo-random)
• The key must be at least as long as the plaintext
• The key must be used only once (one-time)

Implication: Even with unlimited computational power, an attacker cannot break the cipher. This is security against any adversary, not just computationally bounded ones.

The catch: Perfect security is impractical for most real-world applications because key distribution becomes as hard as securely sending the message itself.

Go deeper:

• Information-theoretic security (Wikipedia) — Shannon's proof that the one-time pad is unbreakable.