SUNNYVALE, Calif.--(BUSINESS WIRE)--NTT Research, Inc., a division of NTT (TYO:9432), today announced that a paper co-authored by Cryptography & Information Security (CIS) Lab Director Brent Waters has won an IEEE Symposium on Foundations of Computer Science (FOCS) Test of Time Award. The paper, titled “Candidate Indistinguishability Obfuscation and Functional Encryption for all circuits,” was delivered at FOCS 2013. The paper’s co-authors were Sanjam Garg, Craig Gentry, Shai Helevi, Mariana Raykova and Amit Sahai. Since 2019, FOCS has given Test-of-Time awards to papers that were delivered 10, 20 and 30 years earlier. This year’s winning papers will be recognized at FOCS 2023, scheduled to be held November 6-9 in Santa Cruz, CA. In addition, two papers co-authored by scientists from the CIS Lab and the NTT Social Informatics Laboratories (SIL) will be presented at this year’s conference.
The FOCS 2013 paper co-authored by Waters, who recently won a third Test-of-Time Award for a paper presented at Crypto 2008, pioneered the first candidate of a cryptographically based obfuscation scheme. Theoretical cryptographers previously had focused on virtual black-box obfuscation. But results were restricted, and it proved impossible to achieve for general functionality. In this paper, Waters, who is also Professor of Computer Science at the University of Texas at Austin, and his co-authors showed the potential to achieve obfuscation using mathematical tools and working with the indistinguishability definition.
“This paper demonstrated for the first time a plausible method for a new class of software obfuscation that provides strong cryptographic guarantees,” CIS Lab Senior Scientist Mark Zhandry said. “The development of such cryptographic obfuscation was a goldmine and has had a profound effect on the field of theoretical cryptography. Cryptographic obfuscation was shown to solve numerous long-standing open problems in cryptography and became the go-to tool for developing novel applications.”
In indistinguishability obfuscation (iO), an obfuscator takes a program (aka, circuit) and transforms it into a new one that performs the same functionality as the old but hides its implementation. The scheme proposed in this paper was based on the use of multilinear maps. The paper also showed how to apply iO to functional encryption, a cryptographic primitive that had evolved from Waters’ pioneering work with Amit Sahai on attribute-based encryption (ABE). The paper’s basic contribution, however, involved obfuscation.
“The FOCS 2013 paper changed the landscape of theoretical cryptography,” CIS Lab Senior Scientist Abhishek Jain said. “It gave the first strong evidence that program obfuscation – long thought to be an impossible goal – could be realized securely. This had two profound effects on the research community. First, a change in belief about the existence of obfuscation became a powerful catalyst that motivated cryptographers to revisit the foundations of program obfuscation and realize it from well-founded assumptions. After nearly a decade, this effort finally culminated in a recent breakthrough work.”
The paper also changed how theoretical cryptographers approach their work. “When faced with a challenging security problem, a now ubiquitous first line of attack is to ask: ‘Can I solve this using program obfuscation?’” Jain said. “Increasing evidence over the last decade has shown that the answer is rarely no.”
CIS Lab Senior Scientist Elette Boyle underscored the paper’s innovation. “Before this result, the idea of cryptographic program obfuscation was basically considered a dead end, fraught with impossibilities,” Boyle said. “This paper opened a whole new world, with beautiful new ideas showing not only that this object may be possible, but also just how useful and important it can be.”
Boyle added that it was clear from the start that the paper would have a tremendous impact. Indeed, according to this article, in the six months after it was posted, “more papers have appeared on the ePrint archive with ‘obfuscation’ in the title than in the previous 17 years.”
FOCS covers the span of theoretical computation, not only cryptography. As a result, a FOCS Test-of-Time Award indicates that a broader community agrees that a paper was a theoretical breakthrough with enduring value. This year, FOCS also accepted these two NTT-affiliated papers on post-quantum cryptography and ABE:
- “A New Approach to Post-Quantum Non-Malleability,” Xiao Liang (NTT Research); Omkant Pandey (Stony Brook University); Takashi Yamakawa (NTT SIL)
- “ABE for Circuits with poly-sized Keys from LWE,” Valerio Cini (AIT, Austria); Hoeteck Wee (NTT Research)
Xiao Liang is currently a post-doctoral fellow at NTT Research. Takashi Yamakawa, a Distinguished Researcher at NTT SIL, focuses on constructions of post-quantum and quantum cryptographic protocols and their security. In addition to working on ABE, NTT Senior Scientist Hoeteck Wee also addresses obfuscation, selective computation and cryptographic challenges posed by Big Data and the internet. Along with iO, the topics addressed in these papers are part of the CIS Lab’s core agenda of pushing the frontiers of cryptography.
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. © 2023 NIPPON TELEGRAPH AND TELEPHONE CORPORATION
