How Fast Can We Obfuscate Using Ideal Graded Encoding Schemes

In this work, we present a new obfuscator using a Graded Encoding Scheme (GES) with a binary slot. We characterize a class of circuits taking locally keyed input (each input bit of the circuit is a keyed function over c>1 bits of a binary-variable vector X of length n, where c is called the locality), called ideal functions, such that any function of algebraic degree d (called d-function) over them, can be obfuscated with multilinearity \mu=(d+1)n/c. Next we show that obfuscation of a general circuit C can be bootstrapped by O(n)-functions (the circuit (called RE) composing a garbled circuit (GC) with a pseudorandom function (PRF)), following an approach similar to that of Zimmerman and Applebaum et al., assuming PRF (or more precisely RE) exists among d-functions with constant d. To instantiate the above scheme, we achieve the following: 1. A concrete GC of algebraic degree 3 over its random bits, which has output size no more than 20\lambda|C| and random tape length about 10\lambda|C|, where \lambda is the security parameter, |C| denotes the number of gates of the circuit C. 2. A candidate d-function construction, where we argue that d=1 suffices to stop linear distinguishing attacks and d=2 seems enough for fully secure PRF. 3. Instantiation of the GES with a simplified version of the CLT multilinear map, and various techniques that further reduce \mu of the core obfuscator cost-equivalently to dn/(2c)+1 in cases of our interest. If we replace the PRF with d-functions, then we get various heuristic obfuscation-friendly REs, and thus general obfuscators with explicit complexities. For the most optimistic choice, we have \mu=1.5n\u27/c +2.5, n\u27\approx n+\log |C|+\log \lambda, n is the number of input bits of C, and c is a selectable constant which result in a {2^c}/{c} times increase of the key size of the RE. Our general obfuscator is VBB secure assuming that our RE is secure and our simplified CLT map is a secure instantiation of our GES (defined relative to known attacks). We leave these assumptions with concrete parameter sets as open challenges. We illustrate the efficiency of our methods with some examples: 1. Our obfuscated AES (c=13, \mu=20.5) has code size