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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Major revision. FOCS 2017
Contact author(s)
wichs @ ccs neu edu
History
2017-08-16: last of 2 revisions
2017-03-26: received
See all versions
Short URL
https://ia.cr/2017/276
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/276,
      author = {Daniel Wichs and Giorgos Zirdelis},
      title = {Obfuscating Compute-and-Compare 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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.