Skip to main content

New Techniques for Obfuscating Conjunctions

Author(s): Bartusek, James; Lepoint, Tancrède; Ma, Fermi; Zhandry, Mark

To refer to this page use:
Abstract: A conjunction is a function 𝑓(π‘₯1,…,π‘₯𝑛)=β‹€π‘–βˆˆπ‘†π‘™π‘– where π‘†βŠ†[𝑛] and each 𝑙𝑖 is π‘₯𝑖 or Β¬π‘₯𝑖 . Bishop et al. (CRYPTO 2018) recently proposed obfuscating conjunctions by embedding them in the error positions of a noisy Reed-Solomon codeword and placing the codeword in a group exponent. They prove distributional virtual black box (VBB) security in the generic group model for random conjunctions where |𝑆|β‰₯0.226𝑛 . While conjunction obfuscation is known from LWE [31, 47], 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 |𝑆|β‰₯π‘›βˆ’π‘›π›Ώ and 𝛿<1 . Assuming discrete log and 𝛿<1/2 , we satisfy a stronger notion of functionality preservation for computationally bounded adversaries while still achieving information theoretic security.
Publication Date: 2019
Citation: Bartusek, James, TancrΓ¨de Lepoint, Fermi Ma, and Mark Zhandry. "New Techniques for Obfuscating Conjunctions." In Annual International Conference on the Theory and Applications of Cryptographic Techniques (2019): pp. 636-666. doi:10.1007/978-3-030-17659-4_22
DOI: 10.1007/978-3-030-17659-4_22
ISSN: 0302-9743
EISSN: 1611-3349
Pages: 636 - 666
Type of Material: Conference Article
Journal/Proceeding Title: Annual International Conference on the Theory and Applications of Cryptographic Techniques
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.