In 2018, Aayush Jain, a graduate student from the University of California, Los Angeles, traveled to Japan to lecture on a powerful cryptographic tool he and his colleagues were developing. As he detailed the team’s approach to indistinguishable obfuscation (iO for short), an audience member raised a hand, puzzled.
“But I thought iO doesn’t exist?” he said.
At the time, such skepticism was widespread. Obfuscation of indistinguishability, if it could be constructed, could hide not only collections of data but the inner workings of a computer program itself, creating a sort of cryptographic master tool from which almost all others cryptographic protocols could be built. It’s “a crypto primitive to rule them all,” said Boaz Barak of Harvard University. But for many computer scientists, that very power has made iO too good to be true.
Computer scientists came up with candidate versions of iO starting in 2013. But the intense excitement these builds generated gradually died down, as other researchers figured out how to break their security. As the attacks piled up, “you could see a lot of negative waves,” said Yuval Ishai of Technion in Haifa, Israel. The researchers wondered, he said, “Who is going to win: the makers or the breakers?”
“There were people who were the fanatics, and they believed in [iO] and continued to work on it, ”said Shafi Goldwasser, director of the Simons Institute for the Theory of Computing at the University of California, Berkeley. But over the years, she says, “there were fewer and fewer of these people.”
Now, Jain – along with Huijia Lin from the University of Washington and Amit Sahai, Jain’s adviser at UCLA – has planted a flag for the manufacturers. In one paper Posted on August 18, the three researchers show for the first time how to create an indistinguishable masking using only “standard” security assumptions.
All cryptographic protocols are based on assumptions – some, like the famous RSA algorithm, depend on the widely held belief that standard computers will never be able to quickly factorize the product of two large prime numbers. A cryptographic protocol is only as secure as its assumptions, and iO’s previous attempts rested on untested and ultimately shaky foundations. The new protocol, on the other hand, depends on safety assumptions that have been widely used and studied in the past.
“Unless there are any truly surprising developments, these assumptions will be maintained,” Ishai said.
While the protocol is far from ready for deployment in real world applications, from a theoretical standpoint, it provides an instant way to create a range of cryptographic tools that were previously out of reach. For example, it allows for the creation of “deniable” encryption, in which you can plausibly convince an attacker that you sent a totally different message than the one you actually sent, and “working” encryption, where you can give chosen users different levels of access to perform calculations from your data.
The new result should definitely silence OI skeptics, Ishai said. “From now on, there will be no more doubts as to the existence of an indistinguishable masking”, he declared. “It seems like a happy ending.”
The jewel in the crown
For decades, computer scientists have questioned whether there is a secure and comprehensive way to hide computer programs, allowing people to use them without discovering their internal secrets. Obfuscating the program would activate a host of useful applications: for example, you could use an obscured program to delegate particular tasks within your bank or email accounts to other people, without worrying that someone could use the program in a way for which it was not intended. or read your account passwords (unless the program was designed to display them).
But so far all attempts to construct practical obfuscators have failed. “The ones that are released in real life are ridiculously broken,… usually within hours of being released into the wild,” Sahai said. At best, they offer attackers a retarder, he said.
In 2001, bad news also arrived on the theoretical front: the strongest form of obfuscation is impossible. Called black box obfuscation, it requires attackers to learn absolutely nothing about the program except what they can observe while using the program and seeing what it produces. Some programs, Barak, Sahai and five other researchers shown, reveal their secrets so resolutely that they are impossible to completely obscure.