Shannon Impossibility, Revisited

摘要: In this note we revisit the famous result of Shannon [Sha49] stating that any encryption scheme with perfect security against computationally unbounded attackers must have a secret key as long message. This motivated introduction modern schemes, which are secure only bounded attacker, and allow some small (negligible) advantage to such an attacker. It is well known folklore both relaxations -- limiting power attacker allowing for necessary overcome Shannon's result. To our surprise, could not find clean documented proof belief. (In fact, two proofs required, each showing one above sufficient.) Most saw either made assumptions (e.g., deterministic), or proved much more complicated statement beating bound implies existence one-way functions [IL89].)