Paper 2012/053
Beating Shannon requires BOTH efficient adversaries AND non-zero advantage
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*.
Metadata
- Available format(s)
-
PDF
PS
- Category
- Foundations
- Publication info
- Published elsewhere. this note is meant to be used in "introduction to cryptography" classes
- Keywords
- one-time padShannon bound
- Contact author(s)
- dodis @ cs nyu edu
- History
- 2012-02-06: received
- Short URL
- https://ia.cr/2012/053
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2012/053,
author = {Yevgeniy Dodis},
title = {Beating Shannon requires {BOTH} efficient adversaries {AND} non-zero advantage},
howpublished = {Cryptology {ePrint} Archive, Paper 2012/053},
year = {2012},
url = {https://eprint.iacr.org/2012/053}
}
