In a presentation at the recent Upgrade 2020 NTT Research Summit, Dr. Amit Sahai presented a solution to a problem that’s been confounding the crypto world for years: Indistinguishability obfuscation, or a way to obfuscate computer programs such that people can use the programs but never get a glimpse into the code that makes them work.

Sahai is Director of the Center for Encrypted Functionalities at the University of California Los Angeles (UCLA). His breakthrough came from two years of work with one of his graduate students, Aayush Jain (who also served as an intern at NTT Research during part of the time he was working on the research), and Dr. Huijia (Rachel) Lin, an associate professor at the University of Washington.

The goal of indistinguishability obfuscation is to compile computer programs into unintelligible ones while preserving their functionality. Such a capability would enable the creation of programs that would let your accountant access your bank account and download transactions, but not read your password or conduct any other transactions, for example.

“It is a fascinating and powerful object that has been shown to enable a host of new cryptographic goals and beyond,” according to the paper that was the basis for Sahai’s talk, published on Nov. 20, 2020. “However, constructions of indistinguishability obfuscation have remained elusive, with all other proposals relying on heuristics or newly conjectured hardness assumptions.”

“There have been over 100 papers written that show how to use IO to achieve a number of remarkable cryptographic goals that really expand the scope of cryptography in addition to doing just remarkable, really interesting new things,” Sahai said in his NTT Research Summit talk. But all known constructions of IO required hardness assumptions designed to prove the IO was secure.

“Unfortunately, this has a tortuous history and many of the assumptions were actually broken, which led to a lot of doubt and uncertainty about the status of IO, whether it really exists or doesn’t exist,” he said.

His work “changes that state of affairs in a fundamental way.”  

The fundamental difference is that he and his team were able to build IO based on four variations of widely used cryptographic assumptions, namely:

• The Learning With Errors (LWE) assumption over Z_p
• The Learning Parity with Noise (LPN) assumption over Z_p
• The existence of a Boolean Pseudo-Random Generator (PRG) in NC⁰
• The Symmetric eXternal Diffie-Hellman (SXDH) assumption

His talk goes into depth on each of them, explaining how slight changes to the assumptions, such as adding a sparse error or tweaking a matrix, enabled the team to prove the existence of indistinguishability obfuscation.

The team’s work is making an impression in cryptography circles.

“It really is kind of the crown jewel” of cryptographic protocols, Rafael Pass of Cornell University told Quanta magazine. “Once you achieve this, we can get essentially everything.”

Yuval Ishai of the Technion, the Israel Institute of Technology, told Quanta, “Barring a really surprising development, these assumptions will stand.”

“This is a pretty amazing theoretical result, and one to be excited about. We can now do obfuscation, and we can do it using assumptions that make real-world sense,” wrote security expert Bruce Schneier on his blog.

Schneier and others correctly noted, and Sahai readily acknowledges, that his team’s work is just a beginning. Currently it would take an impractically massive amount of computing power to perform the calculations described. But such is the case with most any breakthrough in cryptography – it has to start somewhere.

For the full transcript of Amit Sahai’s presentation, click here.

Watch Amit Sahai’s full presentation below.