Paper 2018/936

New Techniques for Obfuscating Conjunctions

James Bartusek, Tancrède Lepoint, Fermi Ma, and Mark Zhandry


A conjunction is a function $f(x_1,\dots,x_n) = \bigwedge_{i \in S} l_i$ where $S \subseteq [n]$ and each $l_i$ is $x_i$ or $\neg x_i$. Bishop et al. (CRYPTO 2018) recently proposed obfuscating conjunctions by embedding them in the error positions of a noisy Reed-Solomon codeword and encoding the codeword in a group exponent. They prove distributional virtual black box (VBB) security in the generic group model for random conjunctions where $|S| \geq 0.226n$. While conjunction obfuscation was known from LWE due to Wichs and Zirdelis (FOCS 2017) and Goyal et al. (FOCS 2017), these constructions rely on substantial technical machinery. In this work, we conduct an extensive study of simple conjunction obfuscation techniques. - We abstract the Bishop et al. scheme to obtain an equivalent yet more efficient "dual'' scheme that can handle conjunctions over exponential size alphabets. This scheme admits a straightforward proof of generic group security, which we combine with a novel combinatorial argument to obtain distributional VBB security for $|S|$ of any size. - If we replace the Reed-Solomon code with a random binary linear code, we can prove security from standard LPN and avoid encoding in a group. This addresses an open problem posed by Bishop et al. to prove security of this simple approach in the standard model. - We give a new construction that achieves information theoretic distributional VBB security and weak functionality preservation for $|S| \geq n - n^\delta$ and $\delta < 1$. Assuming discrete log and $\delta < 1/2$, we satisfy a stronger notion of functionality preservation for computationally bounded adversaries while still achieving information theoretic security.

Note: Revised introduction to clarify results, fixed typos.

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in EUROCRYPT 2019
obfuscationconjunctionslearning parity with noisegeneric group
Contact author(s)
bartusek james @ gmail com
tancrede @ google com
fermima1 @ gmail com
mzhandry @ princeton edu
2019-03-05: last of 7 revisions
2018-10-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {James Bartusek and Tancrède Lepoint and Fermi Ma and Mark Zhandry},
      title = {New Techniques for Obfuscating Conjunctions},
      howpublished = {Cryptology ePrint Archive, Paper 2018/936},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.