NTT Research, Inc., a division of NTT (TYO:9432), along with UCLA and the University of Washington, today announced that a paper co-authored by cryptographers affiliated with their respective institutions has solved a two-decade-old problem involving indistinguishability obfuscation, the notion of making a computer program “unintelligible” while preserving its functionality. The academic paper, posted on public academic platforms, the Electronic Colloquium on Computational Complexity, the IACR ePrint server and Arxiv, 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 research intern at the NTT Research Cryptography and 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.
Titled “Indistinguishability Obfuscation from Well-Founded Assumptions,” the paper resolves a long-standing problem of designing provably secure methods for obfuscating programs based on well-founded cryptographic assumptions. Program obfuscation aims to compile a program to make it unintelligible in order to hide the logic and knowledge in the original program. Methods for program obfuscation have been long sought-after in many domains, and many heuristic attempts have been made in the past. However, the mathematical foundation of program obfuscation has lagged behind. First mathematically formalized in 2001, the problem defines a notion of program obfuscation called indistinguishability obfuscation (iO). Since then, the question of constructing iO with provable security guarantees from well-studied hardness assumptions has intrigued but eluded cryptographers for nearly 20 years. Despite extensive efforts, all previously known iO schemes required tailored and often difficult-to-understand assumptions. As a result, clarity about the state of iO security has suffered.
In this work, the authors construct iO from four well-founded assumptions that are sub-exponentially hard — they are puzzles that are computationally expensive to solve, taking at least some sub-exponential time. The assumptions are Symmetric external Diffie-Hellman (SXDH) on pairing groups, Learning with Errors (LWE), Learning Parity with Noise (LPN) over large fields, and the existence of a Boolean Pseudo-Random Generator (PRG) that is very simple to compute (i.e., by constant depth circuits). 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. Further, these assumptions have been used in many previous works for realizing a variety of cryptographic goals that have nothing to do with iO.
“Up until now, cryptographers could be suspicious about whether iO really worked or existed, but these results are convincing,” said CIS Lab Director and NTT Fellow Tatsuaki Okamoto. “And because iO implies many strong cryptographic functionalities that are considered hard to realize without iO, what this means is that our cryptographic world is now richer and more powerful.”
According to the authors, their key innovation is a simple way to leverage two of the assumptions — LPN over fields and simple Boolean PRG — to build a structured-seed (s)PRG. Here, structured seed means that the “seed” of the PRG consists of a public and private part that are correlated in a clever and non-trivial way. The most important feature of their structured-seed PRGs is that they are extremely simple to compute, involving only computing low-degree polynomials on the seed, and in fact, only quadratic polynomials on the private part of the seed. Once the structured-seed PRGs are constructed, the work draws extensively upon previous research to achieve the ultimate goal of iO.
“This work was the result of an amazing collaboration spanning over more than two years of effort,” all three collaborators said.
“The process has been an enlightening one for all of us. The result is deeply satisfying; however, the journey has been equally exciting. Over the past few years, this has led us to explore some really fundamental and beautiful questions in hardness amplification, leakage-resilient cryptographic proof techniques and algorithmic questions related to the sum-of-squares hierarchy and the hardness present in average-case constant degree polynomial systems over the reals. We also interacted with and learned from some of the most amazing people in theoretical computer science,” Jain said.
“I am excited that iO can now be based on well-founded assumptions. The next step is further pushing the envelope and constructing iO from weaker assumptions. At the same time, we shall try to improve the efficiency of the solutions, which, at the moment, are very far from being practical. These are ambitious goals that will need the joint effort from the entire cryptography community. I look forward to working with these questions and being part of the effort,” Lin said.
“Nobel laureate Steven Weinberg wrote that in scientific research, if one has the choice between working in an area where ‘the principles are well known,’ or in an area that ‘seems like a mess,’ his advice was ‘to go for the messes — that’s where the action is.’ In my opinion, this advice is particularly pertinent to theoretical research, but perhaps seldom followed by theoreticians. For years, the mathematical foundations of indistinguishability obfuscation were quite frankly a mess. But this line of work shows that with years of perseverance, diligence and humility, such messes eventually can be tamed,” Sahai said.
NTT Research has established a close working relationship with UCLA and the CEF, among other academic and research institutions. In February 2020, NTT Research announced that its CIS Lab had reached a five-year joint research agreement with UCLA to cover advanced secure cryptosystems, secure protocols, new sources of hardness and mathematical foundations of cryptography. The CIS Lab actively recruits Ph.D. candidates who are excellent in the theoretical areas of cryptography for its internship program. This year’s students come from Carnegie Mellon University, Cornell, MIT, Princeton, Rutgers, Stanford and UCLA.
About NTT Research
NTT Research opened its Palo Alto 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: 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, neuro-science 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.
About the Center for Encrypted Functionalities
The Center for Encrypted Functionalities tackles the deep and far-reaching problem of general-purpose program obfuscation. The Center’s primary mission is to transform program obfuscation from an art to a rigorous mathematical discipline. In addition to its direct research program, the Center organizes retreats and workshops to bring together researchers to carry out the Center’s mission. The Center also engages in high-impact outreach efforts, such as the development of free Massive Open Online Courses (MOOCs). The Center for Encrypted Functionalities was established through an NSF Secure and Trustworthy Cyberspace FRONTIER Award.
About the UCLA Samueli School of Engineering
UCLA Samueli is a tightly knit community of 190 full-time faculty members, more than 6,000 undergraduate and graduate students, as well as 40,000 active alumni. Known as the birthplace of the internet, UCLA Samueli is also where countless other fields took some of their first steps – from artificial intelligence to reverse osmosis, from mobile communications to human prosthetics. UCLA Samueli is consistently ranked in the Top 10 among U.S. public engineering schools. The school’s online master’s program is ranked No.1 by U.S. News & World Report.
About the Paul G. Allen School of Computer Science & Engineering
Consistently ranked among the top computer science programs in the nation, the Paul G. Allen School of Computer Science & Engineering educates tomorrow’s innovators and engages in research that advances core and emerging areas of the field. We also participate in a broad range of multi-disciplinary initiatives that demonstrate the transformative power of computing, and we are nationally recognized for our success in promoting diversity. We are located in the spectacular Paul G. Allen Center for Computer Science & Engineering and Bill & Melinda Gates Center for Computer Science & Engineering at the heart of the University of Washington campus in Seattle.
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. © 2020 NIPPON TELEGRAPH AND TELEPHONE CORPORATION
View source version on businesswire.com: https://www.businesswire.com/news/home/20200930005259/en/