Paper 2017/276

Obfuscating Compute-and-Compare Programs under LWE

Daniel Wichs and Giorgos Zirdelis

Abstract

We show how to obfuscate a large and expressive class of programs, which we call compute-and-compare programs, under the learning-with-errors (LWE) assumption. Each such program $CC[f,y]$ is parametrized by an arbitrary polynomial-time computable function $f$ along with a target value $y$ and we define $CC[f,y](x)$ to output $1$ if $f(x)=y$ and $0$ otherwise. In other words, the program performs an arbitrary computation $f$ and then compares its output against a target $y$. Our obfuscator satisfies distributional virtual-black-box security, which guarantees that the obfuscated program does not reveal any partial information about the function $f$ or the target value $y$, as long as they are chosen from some distribution where $y$ has sufficient pseudo-entropy given $f$. We also extend our result to multi-bit compute-and-compare programs $MBCC[f,y,z](x)$ which output a message $z$ if $f(x)=y$. Compute-and-compare programs are powerful enough to capture many interesting obfuscation tasks as special cases. This includes obfuscating conjunctions, and therefore we improve on the prior work of Brakerski et al. (ITCS '16) which constructed a conjunction obfuscator under a non-standard "entropic" ring-LWE assumption, while here we obfuscate a significantly broader class of programs under standard LWE. We show that our obfuscator has several interesting applications. For example, we can take any encryption scheme and publish an obfuscated plaintext equality tester that allows users to check whether an arbitrary ciphertext encrypts some target value $y$; as long as $y$ has sufficient pseudo-entropy this will not harm semantic security. We can also use our obfuscator to generically upgrade attribute-based encryption to predicate encryption with one-sided attribute-hiding security, as well as witness encryption to indistinguishability obfuscation which is secure for all null circuits. Furthermore, we show that our obfuscator gives new circular-security counter-examples for public-key bit encryption and for unbounded length key cycles. Our result uses the graph-induced multi-linear maps of Gentry, Gorbunov and Halevi (TCC '15), but only in a carefully restricted manner which is provably secure under LWE. Our technique is inspired by ideas introduced in a recent work of Goyal, Koppula and Waters (EUROCRYPT '17) in a seemingly unrelated context.