You are looking at a specific version 20120206:155655 of this paper. See the latest version.

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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.