Paper 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.

Metadata
Available format(s)
PDF PS
Publication info
Published elsewhere. Unknown where it was published
Keywords
Information-theoretic securityentropyextractors
Contact author(s)
mihir @ eng ucsd edu
History
2012-01-20: revised
2012-01-18: received
See all versions
Short URL
https://ia.cr/2012/022
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/022,
      author = {Mihir Bellare and Stefano Tessaro},
      title = {Polynomial-Time, Semantically-Secure Encryption Achieving the Secrecy Capacity},
      howpublished = {Cryptology ePrint Archive, Paper 2012/022},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/022}},
      url = {https://eprint.iacr.org/2012/022}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.