Polynomial-Time, Semantically-Secure Encryption Achieving the Secrecy Capacity
This work solves a fundamental problem in information-theoretic cryptography by enabling efficient, optimally secure communication for scenarios where channels to adversaries are noisier, marking a significant advance after thirty years of research.
The paper tackles the long-standing problem of achieving the secrecy capacity in wiretap channels with polynomial-time encryption and decryption, and presents a scheme that not only meets this goal but also provides semantic security, a stronger notion than the classical MIS-R security, without sacrificing rate.
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 receiver is noisier than the one from sender to adversary. 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.