Paper 2013/471

Obfuscating Conjunctions

Zvika Brakerski and Guy N. Rothblum

Abstract

We show how to securely obfuscate the class of conjunction functions (functions like $f(x_1, \ldots, x_n) = x_1 \land \lnot x_4 \land \lnot x_6 \land \cdots \land x_{n-2}$). Given any function in the class, we produce an obfuscated program which preserves the input-output functionality of the given function, but reveals nothing else. Our construction is based on multilinear maps, and can be instantiated using the recent candidates proposed by Garg, Gentry and Halevi (EUROCRYPT 2013) and by Coron, Lepoint and Tibouchi (CRYPTO 2013). We show that the construction is secure when the conjunction is drawn from a distribution, under mild assumptions on the distribution. Security follows from multilinear entropic variants of the Diffie-Hellman assumption. We conjecture that our construction is secure for any conjunction, regardless of the distribution from which it is drawn. We offer supporting evidence for this conjecture, proving that our obfuscator is secure for any conjunction against generic adversaries.

Note: Fixed acknowledgement (technical content unchanged).

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A major revision of an IACR publication in CRYPTO 2013
Keywords
Obfuscationmultilinear maps
Contact author(s)
zvika brakerski @ weizmann ac il
History
2013-08-11: revised
2013-08-03: received
See all versions
Short URL
https://ia.cr/2013/471
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/471,
      author = {Zvika Brakerski and Guy N.  Rothblum},
      title = {Obfuscating Conjunctions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2013/471},
      year = {2013},
      url = {https://eprint.iacr.org/2013/471}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.