Professor of Computer Science, UCLA
The Mathematics Behind Program Obfuscation
In the video below, Amit Sahai discusses the Mathematics Behind Program Obfuscation.
Presented at the NTT Research Upgrade 2021 Summit on September 21, 2021.
Program obfuscation is an important problem in cryptography. By obfuscating a program, its legitimate owner prevents an attacker from extracting knowledge from the program (in the extreme case reverse-engineering it entirely), decomposing the program, or changing the program’s behaviour.
A cryptographic primitive called Indistinguishability Obfuscation (IO) formalizes the concept: programs are represented as logical (binary) circuits, and it is required that two circuits of the same size and implementing the same function, once obfuscated, are computationally indistinguishable. This should be achieved by a probabilistic polynomial-time algorithm, and the growth in the size of a program under obfuscation should also be polynomially bounded. An enormous range of applications will follow if and when IO is shown to be achievable in practice, and consequently it is a very active and rapidly developing research area.
At Upgrade 2021, Professor Amit Sahai (UCLA) reported on joint work in this field with his student Aayush Jain and Huijia Lin (University of Washington). Previous approaches to IO have been based on the prevailing paradigm of lattices with small error, and so have required the usual assumptions of lattice-based cryptography, notably the hardness of the Learning With Errors problem (LWE).
Sahai’s team instead investigated an approach using random linear codes with sparse error, in which the role of LWE is played by the Learning from Parity with Noise problem (LPN), which is also believed to be hard and whose study goes back to 1950. Sahai’s team showed that LPN plus the further assumptions of the existence of a certain class of pseudo-random generators and the Decision Linear assumption (DLIN) gives IO without lattices. Of these, only DLIN is known to be strong enough to allow public-key encryption.
Sahai gave a survey of the technical aspects of their work, with emphasis on LPN. The striking difference between LPN and LWE is that in the former the frequency of errors in the noisy input is restricted, but not their size, while in LWE the size of every error must be small by some measure. There is a lot of latitude in the choice of the frequency of errors, and this aids in the proof of security.
Professor Sahai concluded by expanding on the lattice-free approach as a way to better understand the mathematical requirements of IO, by sketching directions of future work and stating some open questions, chiefly to do with whether the assumptions made in this work can be weakened further.
Professor, Computer Science | UCLA
Amit Sahai is a Professor of Computer Science at UCLA. He serves as an editor of J. Cryptology (Springer-Nature). His research interests are in security and cryptography, and theoretical computer science more broadly. He is the co-inventor of Attribute-Based Encryption, Functional Encryption, and Indistinguishability Obfuscation. He has published more than 150 original technical research papers at venues such as the ACM Symposium on Theory of Computing (STOC), CRYPTO, and the Journal of the ACM. Professor Sahai is the recipient of numerous honors; he was named an Alfred P. Sloan Foundation Research Fellow in 2002, received an Okawa Research Grant Award in 2007, a Xerox Foundation Faculty Award in 2010, a Google Faculty Research Award in 2010, a 2012 Pazy Memorial Award, a 2016 ACM CCS Test of Time Award, a 2019 AWS Machine Learning Research Award, a 2020 IACR Test of Time Award (Eurocrypt), and a STOC 2021 Best Paper Award. Most recently, Professor Sahai was named a Simons Investigator 2021.