AMC STOC Conference Honors Paper on Using Indistinguishability Obfuscation by Waters and Amit Sahai News Highlights:

• STOC Test-of-Time Award recognizes papers published 10, 20 and 30 years earlier for long-term impact.
• Paper on Indistinguishability Obfuscation “changed the landscape of cryptography.”
• CIS Lab Scientists presenting four papers at STOC 2024.

NTT Research, Inc., a division of NTT (TYO:9432), today announced that a paper coauthored by Cryptography & Information Security (CIS) Lab Director and Distinguished Scientist Brent Waters has won an Association of Computing Machinery (ACM) Symposium on Theory of Computing (STOC) Test-of-Time Award. The paper, titled “How to Use Indistinguishability Obfuscation: Deniable Encryption, and More,” was delivered at STOC 2014. Waters co-authored the paper with UCLA Professor of Computer Science Amit Sahai. This is the fifth Test-of-Time Award that Waters has received, and his second from ACM. Since 2020, STOC has honored papers that were published 10, 20 and 30 years earlier, paying particular attention to their long-term impact. This year’s award recipients are being recognized at STOC 2024 in Vancouver, British Columbia, June 24–28, 2024. In addition, CIS Lab scientists are presenting four papers at this highly ranked conference on theory.

The backdrop for the STOC 2014 paper is an earlier one presented at the IEEE Symposium on Foundations of Computer Science (FOCS) 2013, in which Waters et al. proposed the first candidate of a cryptographically based obfuscation scheme. That paper, which also won a Test-of-Time Award, showed the potential to achieve obfuscation using mathematical tools and indistinguishability obfuscation (iO), defined in terms of a transformed program that continues to perform a functionality, while hiding its implementation. The FOCS 2013 paper showed that iO was feasible, but it was the STOC 2014 paper, according to Waters, “that opened the utility and applications.” The awards committee of the ACM Special Interest Group on Algorithms and Computation Theory (SIG ACT), which sponsors STOC, came to a similar conclusion.

“The [STOC 2014] Sahai-Waters paper changed the landscape of cryptography by developing ingenious new techniques for leveraging indistinguishability obfuscation towards powerful cryptographic primitives,” the SIG ACT committee stated in its notification of award. “Sahai and Waters demonstrated the surprising power of iO to serve as a substitute for ideal (but unrealizable) flavors of obfuscation in many cryptographic applications. This includes not only standard public-key encryption schemes, but also first-of-their-kind constructions of more advanced cryptographic primitives.”

In the STOC 2014 paper, Waters and Sahai introduced a technique for applying iO called “punctured programs” and used it to settle a longstanding open problem of realizing deniable encryption. It also suggested that iO become a “central hub” for cryptography. The steady stream of papers that followed proved both the utility of iO and the community’s interest in attempting to move it from potentiality into the realm of well-grounded assumptions, which was finally achieved in 2020. In addition to the Test-of-Time Awards for the work on iO, Waters also won two others in 2020 and 2016, respectively, from the IACR and ACM for papers that he and Sahai wrote in 2005 and 2006 on attribute-based encryption (ABE). Waters’ other Test-of-Time Award came in 2023 for a paper on oblivious transfer delivered at IACR Crypto 2008.

The CIS Lab has an additional presence at STOC 2024. This year’s program committee selected the following four papers by Waters (including one on iO), CIS Lab Senior Scientist Elette Boyle and CIS Lab Scientist and Hebrew University Professor Ilan Komargodski:

• “Memory Checking Requires Logarithmic Overhead;” Boyle, Komargodski and Neekon Vafa (MIT)
• “Optimal Load-Balanced Scalable Distributed Agreement;” Yuval Gelles (Hebrew University) and Komargodski
• “A New Approach for Non-Interactive Zero-Knowledge from Learning with Errors;” Waters
• “Adaptively-Sound Succinct Arguments for NP from Indistinguishability Obfuscation,” Waters and David J. Wu (University of Texas at Austin)

STOC 2024 is part of a five-day “TheoryFest,” which features STOC papers, poster sessions, invited talks, workshops, tutorials and social events. Avi Wigderson, a professor at the Princeton University Institute for Advanced Study’s School of Mathematics, is presenting the Turing Award lecture. Founded in 2019 as part of NTT Research Inc., the CIS Lab has assembled a team of world-class cryptographers, whose work has made landmark contributions through participation in leading international conferences and collaboration with academic and industry counterparts.

About NTT Research

NTT Research opened its offices in July 2019 as a new Silicon Valley startup to conduct basic research and advance technologies that promote positive change for humankind. Currently, three labs are housed at NTT Research facilities in Sunnyvale: the Physics and Informatics (PHI) Lab, the Cryptography and Information Security (CIS) Lab, and the Medical and Health Informatics (MEI) Lab. The organization aims to upgrade reality in three areas: 1) quantum information, neuroscience and photonics; 2) cryptographic and information security; and 3) medical and health informatics. NTT Research is part of NTT, a global technology and business solutions provider with an annual R&D budget of $3.6 billion.

NTT and the NTT logo are registered trademarks or trademarks of NIPPON TELEGRAPH AND TELEPHONE CORPORATION and/or its affiliates. All other referenced product names are trademarks of their respective owners. © 2024 NIPPON TELEGRAPH AND TELEPHONE CORPORATION

View source version on businesswire.com: https://www.businesswire.com/news/home/20240627795985/en/

@NttResearch is proud to share that our CIS Lab Director Dr. Brent Waters was awarded his 5th Test-of-Time Award at @TheOfficialACM's #STOC24 for a coauthored paper on Indistinguishability Obfuscation that changed the landscape of cryptography.