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.