Semantic Security for the
Wiretap Channel
Mihir Bellare (UCSD)
Stefano
Tessaro (MIT)
Alexander
Vardy (UCSD)
Abstract:
The wiretap channel is a setting where one aims to provide
information-theoretic privacy of communicated data based solely on the
assumption that the channel from sender to adversary is “noisier”
than the channel from sender to receiver. It has developed in the Information
and Coding (I&C) community over the last 30 years largely divorced from
the parallel development of modern cryptography. This paper aims to bridge
the gap with a cryptographic treatment involving advances on two fronts,
namely definitions and schemes. On the first front (definitions), we explain
that the mis-r definition in current use is weak
and propose two alternatives: mis (based on mutual
information) and ss (based on the classical notion
of semantic security). We prove them equivalent, thereby connecting two
fundamentally different ways of defining privacy and providing a new, strong
and well-founded target for constructions. On the second front (schemes), we
provide the first explicit scheme with all the following characteristics: it
is proven to achieve both security (ss and mis, not just mis-r) and decodability; it has optimal rate; and both the
encryption and decryption algorithms are proven to be polynomial time.