Abstract

A wiretap coding scheme (Wyner, Bell Syst. Tech. J. 1975) enables Alice to reliably communicate a message m to an honest Bob by sending an encoding c over a noisy channel chB, while at the same time hiding m from Eve who receives c over another noisy channel chE.

Wiretap coding is clearly impossible when chB is a degraded version of chE, in the sense that the output of chB can be simulated using only the output of chE. A classic work of Csiszár and Körner (IEEE Trans. Inf. Theory, 1978) shows that the converse does not hold. This follows from their full characterization of the channel pairs (chB, chE) that enable information-theoretic wiretap coding.

In this work, we show that in fact the converse does hold when considering computational security; that is, wiretap coding against a computationally bounded Eve is possible if and only if chB is not a degraded version of chE. Our construction assumes the existence of virtual black-box (VBB) obfuscation of specific classes of ``evasive” functions that generalize fuzzy point functions, and can be heuristically instantiated using indistinguishability obfuscation. Finally, our solution has the appealing feature of being universal in the sense that Alice’s algorithm depends only on chB and not on chE.

Joint work with Yuval Ishai, Alexis Korb, and Paul Lou.

Bio:

Amit Sahai is a Simons Investigator (2021), Fellow of the ACM (2018) and a Fellow of the IACR (2019). He is also a Fellow of the Royal Society of Arts (2021), and Advisor to the Prison Mathematics Project. He is the incumbent of the Symantec Endowed Chair in Computer Science. He received his Ph.D. in Computer Science from MIT in 2000. From 2000 to 2004, he was on the faculty at Princeton University; in 2004 he joined the UCLA Samueli School of Engineering, where he currently holds the position of Professor of Computer Science. He serves as an editor of J. Cryptology (Springer-Nature). His research interests are in security and cryptography, and theoretical computer science more broadly. He is the co-inventor of Attribute-Based Encryption, Functional Encryption, and Indistinguishability Obfuscation. He has published more than 150 original technical research papers at venues such as the ACM Symposium on Theory of Computing (STOC), CRYPTO, and the Journal of the ACM. He has given a number of invited talks at institutions such as MIT, Stanford, and Berkeley, including the 2004 Distinguished Cryptographer Lecture Series at NTT Labs, Japan. Professor Sahai is the recipient of numerous honors; he was named an Alfred P. Sloan Foundation Research Fellow in 2002, received an Okawa Research Grant Award in 2007, a Xerox Foundation Faculty Award in 2010, a Google Faculty Research Award in 2010, a 2012 Pazy Memorial Award, a 2016 ACM CCS Test of Time Award, a 2019 AWS Machine Learning Research Award, a 2020 IACR Test of Time Award (Eurocrypt), and a STOC 2021 Best Paper Award. For his contributions to the conception and development of indistinguishability obfusction, he was awarded the 2022 Held Prize by the National Academy of Sciences. For his teaching, he was given the 2016 Lockheed Martin Excellence in Teaching Award from the Samueli School of Engineering at UCLA. His research has been covered by several news agencies including the BBC World Service, Quanta Magazine, Wired, and IEEE Spectrum.

This talk is hosted by the ISL Colloquium. To receive talk announcements, subscribe to the mailing list isl-colloq@lists.stanford.edu.