Mihir Bellare (Theory Seminar Sp13)

bellare.jpg"Semantic Security for the Wiretap Channel"
Mihir Bellare
Monday, May 20, 2013, 2:00 pm
EBU3B, Room 4140

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.

Joint work with Stefano Tessaro (MIT) and Alexander Vardy (UCSD).