The IEEE Symposium on Foundations of Computer Science (FOCS) 2023 conference recently honored a 2013 paper co-authored by Cryptography & Information Security (CIS) Lab Director Brent Waters with a Test-of-Time Award. Co-authors of the FOCS 2013 paper were Sanjam Garg, Craig Gentry, Shai Helevi, Mariana Raykova and Amit Sahai. Waters has received three previous Test-of-Time Awards. One from the ACM Special Interest Group on Security, Audit and Control (SIGSAC) for a paper presented at CCS 2016 and two from the International Association for Cryptologic Research (IACR) for papers presented at Eurocrypt 2005 (co-authored with Amit Sahai) and Crypto 2008. The FOCS 2013 paper pioneered the first candidate of a cryptographically based obfuscation scheme.
A FOCS committee every year reviews papers that were delivered 10, 20 and 30 years earlier. In its announcement, it said this 2013 work, titled “Candidate Indistinguishability Obfuscation and Functional Encryption for all circuits,” was a “remarkable” paper that “amazingly” accomplished two things: It showed that a type of cryptographic software obfuscation called “indistinguishability obfuscation” (iO) was both achievable and useful. Previous works had shown that cryptographic program obfuscation was impossible to achieve and had introduced iO as a weaker notion. This paper was the first to give a candidate solution, with evidence that it satisfies iO. “Moreover,” the committee stated, “it was the first to give a significant application of iO: it showed that iO can solve the central open problem in functional encryption.”
A cryptographic primitive that had evolved from Waters’ Eurocrypt 2005 paper with Sahai on attribute-based encryption, functional encryption is a system in which a key associated with a function f will learn f(x), where x is the encrypted data. With the application of iO to functional encryption, the FOCS 2013 paper started to reveal iO’s utility. “But it was a later paper, ‘How to Use Indistinguishability Obfuscation: Deniable Encryption and More,’ by Amit Sahai and myself in STOC 2014 that really opened up the applications,” Waters said.
An article in Quanta Magazine, published in January 2014, by mathematician and journalist Erica Klarreich titled, “Perfecting the Art of Sensible Nonsense,” described the powerful appeal of program obfuscation. Klarreich also quantified the paper’s open-the-floodgates impact: “In the six months since the original paper was posted, more papers have appeared on the ePrint archive with ‘obfuscation’ in the title than in the previous 17 years.”
In 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 proposal in the FOCS 2013 paper was based on the use of multilinear maps. “This obfuscation scheme is unbreakable, the team showed, provided that a certain newfangled problem about lattices is as hard to solve as the team thinks it is,” Klarreich wrote. “Time will tell if this assumption is warranted, but the scheme has already resisted several attempts to crack it.”
Solutions now under consideration use a different approach because multilinear maps were later shown to have some cryptographic weakness, according to Waters. This paper was nonetheless a watershed. “[It] led to a flurry of work trying to both show the power of building cryptography from iO and methods for securely building iO,” Waters said. The FOCS committee noted its catalytic impact: “Since publication, a long sequence of follow-up works has shown that iO can be used to achieve a variety of objectives in cryptography for which no other approach was known.”
The paper also led to an eventual grounding of iO. “[It] motivated cryptographers to revisit the foundations of program obfuscation and realize it from well-founded assumptions,” CIS Lab Senior Scientist Abhishek Jain said. “After nearly a decade, this work finally culminated in a recent breakthrough work.” For more from CIS Lab colleagues and additional background on FOCS, please read this related NTT Research press release.
Among the potential applications mentioned in the original FOCS 2013 paper were restricted use software, secure patching of software and protection of intellectual property. “I think all of these could be consequential if obfuscation were used in practice,” Waters said. “The biggest barrier is getting practical obfuscation schemes with cryptographic security guarantees.”
