Search Mailing List Archives
[theory-seminar] "Beyond the Csiszár-Körner Bound: Best-Possible Wiretap Coding via Obfuscation" ? Amit Sahai (Thu, 12-May @ 4:00pm)
jneu at stanford.edu
Sun May 8 20:57:02 PDT 2022
Beyond the Csiszár-Körner Bound: Best-Possible Wiretap Coding via Obfuscation
Amit Sahai – Professor, UCLA
Thu, 12-May / 4:00pm / Packard 101 (in person)
Please join us for coffee and snacks at 3:30pm in the Grove outside
Packard (near Bytes' outdoor seating). The talk will be streamed on
Zoom for those unable to attend in person:
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.
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 at lists.stanford.edu.
Mailing list: https://mailman.stanford.edu/mailman/listinfo/isl-colloq
This talk: http://isl.stanford.edu/talks/talks/2022q2/amit-sahai/
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the theory-seminar