Cryptology ePrint Archive: Report 2012/022
Polynomial-Time, Semantically-Secure Encryption Achieving the Secrecy Capacity
Mihir Bellare and Stefano Tessaro
Abstract: In the wiretap channel setting, one aims to get
information-theoretic privacy of communicated data based only on the
assumption that the channel from sender to adversary is noisier than the one
from sender to receiver. The secrecy capacity is the optimal (highest
possible) rate of a secure scheme, and the existence of schemes achieving it
has been shown. For thirty years the ultimate and unreached goal has been to
achieve this optimal rate with a scheme that is polynomial-time. (This means
both encryption and decryption are proven polynomial time algorithms.) This
paper finally delivers such a scheme. In fact it does more. Our scheme not
only meets the classical notion of security from the wiretap literature,
called MIS-R (mutual information security for random messages) but achieves
the strictly stronger notion of semantic security, thus delivering more in
terms of security without loss of rate.
Category / Keywords: Information-theoretic security, entropy, extractors
Date: received 15 Jan 2012, last revised 20 Jan 2012
Contact author: mihir at eng ucsd edu
Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation
Version: 20120120:183708 (All versions of this report)
Short URL: ia.cr/2012/022
[ Cryptology ePrint archive ]