Obfuscating Compute-and-Compare Programs under LWE

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-blackbox 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 a ciphertext decrypts to 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, and to upgrade witness encryption to indistinguishability obfuscation which is secure for all “null circuits”. Furthermore, we show that our obfuscator gives new circular-security counterexamples 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.

Authors

• Daniel Wichs
• Giorgos Zirdelis

Keywords

• Encryption
• Standards
• Public key
• Integrated circuit modeling
• Target Value
• Parametrized
• Plaintext
• Multilinear
• Encryption Scheme
• Security Proof
• Waterworks
• Class Program
• Attribute-based Encryption
• Permutation
• Class Distribution
• Additional Assumptions
• Secret Key
• Standard Assumptions
• Access Patterns
• Security Parameter
• Program Length
• General Transformation
• Arbitrary Input
• Turing Machine
• Random Oracle Model
• Encoding Strategies
• Input Bits
• Output Bits
• Random Oracle
• Program Output
• Program Obfuscation