Paper 2017/276
Obfuscating ComputeandCompare Programs under LWE
Daniel Wichs and Giorgos Zirdelis
Abstract
We show how to obfuscate a large and expressive class of programs, which we call computeandcompare programs, under the learningwitherrors (LWE) assumption. Each such program $CC[f,y]$ is parametrized by an arbitrary polynomialtime 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 virtualblackbox 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 pseudoentropy given $f$. We also extend our result to multibit computeandcompare programs $MBCC[f,y,z](x)$ which output a message $z$ if $f(x)=y$. Computeandcompare 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 nonstandard "entropic" ringLWE 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 pseudoentropy this will not harm semantic security. We can also use our obfuscator to generically upgrade attributebased encryption to predicate encryption with onesided attributehiding security, as well as witness encryption to indistinguishability obfuscation which is secure for all null circuits. Furthermore, we show that our obfuscator gives new circularsecurity counterexamples for publickey bit encryption and for unbounded length key cycles. Our result uses the graphinduced multilinear 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.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Published elsewhere. MAJOR revision.FOCS 2017
 Contact author(s)
 wichs @ ccs neu edu
 History
 20170816: last of 2 revisions
 20170326: received
 See all versions
 Short URL
 https://ia.cr/2017/276
 License

CC BY
BibTeX
@misc{cryptoeprint:2017/276, author = {Daniel Wichs and Giorgos Zirdelis}, title = {Obfuscating ComputeandCompare Programs under LWE}, howpublished = {Cryptology ePrint Archive, Paper 2017/276}, year = {2017}, note = {\url{https://eprint.iacr.org/2017/276}}, url = {https://eprint.iacr.org/2017/276} }