Welcome to the resource topic for 2012/053
Title:
Beating Shannon requires BOTH efficient adversaries AND non-zero advantage
Authors: Yevgeniy Dodis
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.
ePrint: https://eprint.iacr.org/2012/053
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .