Beating Shannon Requires BOTH Efficient Adversaries and Non-Zero Advantage
In this paper, the authors formally show a well-known (but not well documented) fact that in order to beat the famous Shannon lower bound on key length for one-time-secure encryption, one must simultaneously restrict the attacker to be efficient, and also allow the attacker to break the system with some non-zero (i.e., negligible) probability. Their proof handles probabilistic encryption, as well as a small decryption error. Let (Enc; Dec) be any encryption scheme with key space K and message space M. In general, they use capital letters for random variables, and lower case letters for specific values; e.g., M;C; S denote appropriately defined random messages, cipher-texts and keys, while m; c; s denote some specific value of those.
Provided by: International Association for Cryptologic Research Topic: Security Date Added: Feb 2012 Format: PDF