A Stronger Soft-Covering Lemma that assures Semantic Security in Wiretap Channels
Friday, November 6, 2015 - 1:00pm to Saturday, November 7, 2015 - 1:55pm
Packard 202
Paul Cuff (Princeton University)
Abstract / Description: 

In 1975, Wyner published two very different papers that are unexpectedly connected. One introduced the wiretap channel, showing that information-theoretic secrecy is possible without a secret key by taking advantage of channel noise. This is the foundation for much of physical-layer security. The other paper introduced a notion of common information relevant to generating random variables at different terminals. In that work he introduced a soft-covering tool for proving achievability. Coincidently, soft covering has now become the tool of choice for proving strong secrecy in wiretap channels, although Wyner didn't appear to make any connection between the two results.

We present a sharpening of the soft-covering tool by showing that the soft-covering phenomenon happens with doubly-exponential certainty with respect to a randomly generated codebook. Through the union bound, this enables security proofs in settings where many security constraints must be satisfied simultaneously. The "type II" wiretap channel is a great example of this, where the eavesdropper can actively influence his observations but security must hold in all cases. We demonstrate the effectiveness of this tool by deriving the secrecy capacity of wiretap channels of type II with a noisy main channel---previously an open problem. Additionally, this stronger soft covering allows information-theoretic security proofs to be easily upgraded to semantic security, which is the gold standard in cryptography.


Paul Cuff received the B.S. degree in electrical engineering from Brigham Young University, Provo, UT, in 2004 and the M.S. and Ph. D. degrees in electrical engineering from Stanford University in 2006 and 2009. His Ph.D. research advisor was Thomas Cover. Since 2009 he has been an Assistant Professor of Electrical Engineering at Princeton University.

Over the years Dr. Cuff has interacted with industry in both the technology and the financial sectors, spending summers at Google, Microsoft Research, and elsewhere, and giving talks at a number of hedge funds. In 2005, while in graduate school, he co-founded a tech startup called Adaptive Hearing Solutions with Bernard Widrow centered around signal processing technology. This venture began with the winning of the Stanford business plan competition.

As a graduate student, Dr. Cuff was awarded the ISIT 2008 Student Paper Award for his work titled "Communication Requirements for Generating Correlated Random Variables." This work has led to fruitful and unexpected avenues of research in secure source coding. As faculty, he received the NSF Career Award in 2014 and the AFOSR Young Investigator Program Award in 2015.