# Tag Info

Let $K$ be the set of all possible keys (for AES-256, this set has $2^{256}$ elements.) Let $M$ be the set of all possible messages (for AES, it has $2^{128}$ elements). Let $C$ be the set of all possible cipher texts (for AES, again $2^{128}$ elements). I was reading a proof to the statement: Perfect privacy implies that $|K|=|M|$ ...
As far as I know the statement is not correct. perfect secrecy implies $|K|\geq |M|$ (as you can see in Theorem 2.10 in Introduction to Modern Cryptography) and does not implies $|M|=|K|$ necessarily. Your mentioned proof works well for $|K|>|M|$ (and yes I believe $p$ refers to probability) . also here is Katz and Lindell proof for this theorem (this ...