Cryptology ePrint Archive: Report 2012/053
Beating Shannon requires BOTH efficient adversaries AND non-zero advantage
Abstract: In this note we formally show a "folklore" (but, to the best of our knowledge, not 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. Despite being "folklore", we were unable to find a clean and simple proof of this result, despite asking several experts in the field. We hope that cryptography instructors will find this note useful when justifying the transition from information-theoretic to computational cryptography.
We note that our proof cleanly handles *probabilistic* encryption, as well as a small *decryption error*.
Category / Keywords: foundations / one-time pad, Shannon bound
Publication Info: this note is meant to be used in "introduction to cryptography" classes
Date: received 5 Feb 2012, last revised 5 Feb 2012
Contact author: dodis at cs nyu edu
Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation
Version: 20120206:155655 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]