TY - GEN
T1 - Shannon impossibility, revisited
AU - Dodis, Yevgeniy
N1 - Copyright:
Copyright 2012 Elsevier B.V., All rights reserved.
PY - 2012
Y1 - 2012
N2 - In this note we revisit the famous result of Shannon [Sha49] stating that any encryption scheme with perfect security against computationally unbounded attackers must have a secret key as long as the message. This result motivated the introduction of modern encryption schemes, which are secure only against a computationally bounded attacker, and allow some small (negligible) advantage to such an attacker. It is a well known folklore that both such relaxations - limiting the power of the attacker and allowing for some small advantage - are necessary to overcome Shannon's result. To our surprise, we could not find a clean and well documented proof of this folklore belief. (In fact, two proofs are required, each showing that only one of the two relaxations above is not sufficient.) Most proofs we saw either made some limiting assumptions (e.g., encryption is deterministic), or proved a much more complicated statement (e.g., beating Shannon's bound implies the existence of one-way functions [IL89].)
AB - In this note we revisit the famous result of Shannon [Sha49] stating that any encryption scheme with perfect security against computationally unbounded attackers must have a secret key as long as the message. This result motivated the introduction of modern encryption schemes, which are secure only against a computationally bounded attacker, and allow some small (negligible) advantage to such an attacker. It is a well known folklore that both such relaxations - limiting the power of the attacker and allowing for some small advantage - are necessary to overcome Shannon's result. To our surprise, we could not find a clean and well documented proof of this folklore belief. (In fact, two proofs are required, each showing that only one of the two relaxations above is not sufficient.) Most proofs we saw either made some limiting assumptions (e.g., encryption is deterministic), or proved a much more complicated statement (e.g., beating Shannon's bound implies the existence of one-way functions [IL89].)
UR - http://www.scopus.com/inward/record.url?scp=84865034944&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84865034944&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-32284-6_6
DO - 10.1007/978-3-642-32284-6_6
M3 - Conference contribution
AN - SCOPUS:84865034944
SN - 9783642322839
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 100
EP - 110
BT - Information Theoretic Security - 6th International Conference, ICITS 2012, Proceedings
T2 - 6th International Conference on Information Theoretic Security, ICITS 2012
Y2 - 15 August 2012 through 17 August 2012
ER -