Hoeteck Wee: Obfuscation from LWE: How Far Are We?

Abstract:
GGH15 provide a way to encode many pairs of matrices, such that we can
check whether any subset product is zero, while potentially hiding all
other information about the matrices. This immediately yields a
candidate obfuscator for log-space computation, whose security seems
related to the LWE assumption. So, how far are we from obfuscation for
circuits or NC1 from LWE? How about smaller classes of functions, like
read-once branching programs, or the constant all-reject function?

In this talk, we will present some answers to this question:

* a proof from LWE that we can use GGH15 to securely obfuscate a large
sub-class of the all-reject function (which yields new constructions
of lockable obfuscation, private constrained PRFs and mixed FE schemes
for NC1);
* an attack on the GGH15-based obfuscator for read-once branching
programs from CCS17;
* a new and simple candidate obfuscator for NC1 (and an even simpler
one for witness encryption).