By NTT Research CIS Lab
In cryptography, well-founded assumptions are generally preferable to clever or especially hard ones. This may sound counter-intuitive, but the weaker and more well-founded the assumption, the more believable the outcome.
In that light, one popular cryptographic concept, indistinguishability obfuscation (iO), found itself in trouble. According to the authors of a breakthrough paper published in August 2020, although more than 100 papers had made use of iO in a variety of applications and theory over the past twenty years, all previous iO constructions required either difficult-to-understand hardness assumptions or new computational problems that were not especially well-studied. As a result, one could wonder whether iO really worked or even existed. That was unfortunate, because the point of iO, being able to render a computer program “unintelligible” (to hide the logic and knowledge of the original program) while preserving its functionality, is a compelling capability sought-after in many domains.
What the authors of this paper achieved, however, was a dramatic turnaround. They accomplished this feat by constructing iO from four well-founded, “sub-exponentially hard” assumptions, i.e. assumptions that are computationally expensive to solve. The result is that for the first time, iO is based on the hardness of computational problems with a long history of study, rooted in complexity, coding and number theory. These assumptions were not “tailor-made” for iO, but rather have been used in previous works for realizing a range of totally separate cryptographic goals.
The academic paper has three co-authors: Aayush Jain, a graduate student researcher in the Center for Encrypted Functionalities (CEF) at the University of California, Los Angeles (UCLA) and a recent research intern at our Cryptography & Information Security (CIS) Lab; Huijia (Rachel) Lin, associate professor in the Paul G. Allen School of Computer Science & Engineering at the University of Washington; and Amit Sahai, Symantec Chair Professor of Computer Science at the UCLA Samueli School of Engineering and director of the CEF.
In a statement, senior co-author Dr. Sahai pointed to advice from Nobel laureate (Physics) Steven Weinberg that scientific researchers should prefer areas that are messy to those where principles are well-known.
“For years, the mathematical foundations of indistinguishability obfuscation were quite frankly a mess,” said Dr. Sahai. “But this line of work shows that with years of perseverance, diligence and humility, such messes eventually can be tamed.”
At NTT Research, we are especially pleased with Aayush Jain’s role in this success. Currently a Ph.D. candidate at UCLA, where he is being advised by Dr. Sahai, Jain was previously a research fellow at Microsoft Research India. This is his sixth paper on iO, and his twentieth paper co-authored with Dr. Sahai. He well represents the excellence in theoretical cryptography that we look for in our internship program.
Dr. Lin, who is also a previous collaborator with Dr. Sahai and a long-time contributor to iO research, said she is looking forward to the next steps, namely: constructing iO from weaker assumptions and improving the efficiency and practicality of the solutions.
“These are ambitious goals that will need the joint effort from the entire cryptography community,” she said. “I look forward to working with these questions and being part of the effort.”
