Is it possible to make a computer program unintelligible to anyone trying to disassemble it yet still retain its functionality? It’s a key question that has been around for decades. Now, three cryptographers say they have solved the problem of Indistinguishability Obfuscation (iO).
A PDF titled: “Indistinguishability Obfuscation from Well-Founded Assumptions” is now available for download from several public servers. The three authors are 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.
CIS Lab Director and NTT Fellow Tatsuaki Okamoto said: “Up until now, cryptographers could be suspicious about whether iO really worked or existed, but these results are convincing.
“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.”
Why is this important?
Obfuscating the code in a computer program makes it harder for people to uncover the logic or data inside the program. It is a process known as security through obscurity and is designed to prevent people from reverse-engineering the code. In doing so, it also makes it harder for attackers to discover vulnerabilities in the code and how to exploit them. In short, obfuscation is about making something difficult, not impossible, to understand.
It is not a new approach. Developers have been doing this for decades. It is also a technique increasingly used by malware writers to make their code hard to understand. Just like commercial developers, they want to protect the secrets of how their code works.
The problem is that in order for programs to work effectively, they cannot be obfuscated all the time. If they were, it would be impossible for the computer to read them and make them work.
It’s the same problem as encrypting data on a hard disk. When it isn’t being accessed, it can stay encrypted and safe. But when someone wants to use the data, even when they are searching for something, the data has to be decrypted and that makes it vulnerable.
In the case of data, there are ways to keep it encrypted at all times yet still work with it. One approach is called Fully Homomorphic Encryption (FHE). The problem is that it is computationally complex making it unusable for most cases.
What are Jain, Lin and Sahai presenting?
It is important to note that in the 42-page paper, the authors are not presenting a product. Instead, they are providing a mathematical method that can be used to design provable secure methods for obfuscating programs. The method relies on four key assumptions:
- SXDH: Symmetric external Diffie-Hellman on pairing groups
- LWE: Learning with Errors
- LPN: Learning Parity with Noise over large fields
- PRG: The existence of a Boolean Pseudo-Random Generator that is very simple to compute (i.e., by constant depth circuits).
None of these assumptions are, in themselves, new. The authors write: “All four assumptions are based on computational problems with a long history of study, rooted in complexity, coding, and number theory. Further, they were introduced for building basic cryptographic primitives (such as public-key encryption), and have been used for realizing a variety of cryptographic goals that have nothing to do with iO.”
What makes this different to previous work is a key innovation. The authors describe this as: “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.”
Importantly, the structured-seed PRGs are extremely simple to compute. They use low-degree polynomials on the seed and quadratic polynomials on the private part of the seed.
Enterprise Times: What does this mean?
Obfuscating code is a serious goal for security and cryptographic teams when it comes to protecting computer programs. The problem, to date, is that all of the tools to do so are far from perfect. The way that code is executed also means that it is impossible to completely obfuscate code while protecting its functionality.
By offering a solution to the Indistinguishability Obfuscation problem, the three researchers open an opportunity to a new generation of secure computing. The question now, is how long will it take for vendors to build tools on top of this proof?