“Better Security Through Obfuscation”
Communications of the ACM, August 2021, Vol. 64 No. 8, Pages 13-15
By Chris Edwards
Last year, three mathematicians published a viable method for hiding the inner workings of software. The paper was a culmination of close to two decades of work by multiple teams around the world to show that concept could work. The quest now is to find a way to make indistinguishability obfuscation (iO) efficient enough to become a practical reality.
When it was first proposed, the value of iO was uncertain. Mathematicians had originally tried to find a way to implement a more intuitive form of obfuscation intended to prevent reverse engineering. If achievable, virtual black box (VBB) obfuscation would prevent a program from leaking any information other than the data it delivers from its outputs. Unfortunately, a seminal paper published in 2001 showed that it is impossible to guarantee VBB obfuscation for every possible type of program.
In the same paper, though, the authors showed that a weaker form they called iO was feasible. While iO does not promise to hide all the details of a logic circuit, as long as they are scrambled using iO, different circuits that perform the same function will leak the same information as each other; an attacker would not be able to tell which implementation is being used to provide the results they obtain.
“Our motivation in defining the notion of iO was that it escaped the impossibility result for VBB. However, we had no idea if iO could be constructed, and even if it could be constructed, would it be useful for applications,” says Boaz Barak, George McKay professor of computer science in the John A. Paulson School of Engineering and Applied Sciences at Harvard University, and co-author of the 2001 paper on VBB.
Whatever its utility, for more than a decade iO seemed to be out of reach. A major breakthrough came in 2013, when a team came up with a candidate construction and described a functional-encryption protocol that could be built on top of it. This was quickly followed by a slew of proposals for applications that could make use of iO.
About the Author:
Chris Edwards is a Surrey, U.K.-based writer who reports on electronics, IT, and synthetic biology.
The Journey Towards Program Obfuscation
Thursday, December 10th, 2020 8:30 am – 9:20 am
In this talk I [Yael Kalai] will reflect on the journey towards constructing secure program obfuscators, starting with the seminal paper of Barak et al (Crypto 2001), and culminating with the recent series of breakthrough results. This will be a personal reflection, focusing on the lessons we learned along the way.
Yael Tauman Kalai, Senior Principal Researcher (Presenter). I joined Microsoft Research New England in 2008 after being an Assistant Professor of Computer Science at Georgia Tech and a postdoc at the Weizmann Institute in Israel and Microsoft Research in Redmond. I graduated from MIT, working in cryptography under the superb supervision of Shafi Goldwasser. I was also extremely fortunate to have the guidance of Adi Shamir for my master’s degree. My main research interests are Cryptography, the Theory of Computation, and Security & Privacy.
Shafi Goldwasser is the RSA Professor of Electrical Engineering and Computer Science in MIT, a co-leader of the cryptography and information security group and a member of the complexity theory group within the Theory of Computation Group and the Computer Science and Artificial Intelligence Laboratory.
Boaz Barak (Organizer). Boaz Barak is the Gordon McKay Professor of Computer Science at Harvard University’s John A. Paulson School of Engineering and Applied Sciences. His research interests include all areas of theoretical computer science, and in particular cryptography and computational complexity. Previously, he was a principal researcher at Microsoft Research New England, and before that, an associate professor at Princeton University’s computer science department. Barak has won the ACM dissertation award, the Packard and Sloan fellowships, and was also selected for Foreign Policy Magazine’s list of 100 leading global thinkers for 2014. He serves on the editorial boards of several journals and is also a member of the Committee for the Advancement of Theoretical Computer Science and the board of trustees of the Computational Complexity Foundation. He wrote with Sanjeev Arora the textbook “Computational Complexity: A Modern Approach”.
From the Center for Encrypted Functionalities: Aayush Jain, UCLA; Huijia (Rachel) Lin, UW; Amit Sahai, UCLA.