Shannon's Theorem
- •
Definition
- •
if a Shannon Cipher is perfectly secure, then the key space must be at least as large as the message space:
- •
- •
Why it matters
- •
this is the "bad news" that motivates the rest of modern cryptography — perfect security is achievable (the One-Time Pad does it), but only at the cost of a key as long as the message, impractical for real use (sending a 1GB file would require a pre-shared 1GB key)
- •
this impracticality motivates relaxing the security requirement to Semantic Security, which only has to resist realistically efficient adversaries rather than all mathematically possible ones
- •
- •
Proof idea
- •
if , there are too few keys to map every message to a given ciphertext without collisions — so some message can never produce under any key, while another message can; this asymmetry breaks perfect security
- •
- •