New techniques for obfuscating conjunctions

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

A conjunction is a function (Formula presented) where S⊆[n] and each li is xi or -xi. 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 |S| ≥ 0.226n. 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 |S| ≥ n-nδ 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.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology – EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
EditorsYuval Ishai, Vincent Rijmen
PublisherSpringer Verlag
Pages636-666
Number of pages31
ISBN (Print)9783030176587
DOIs
StatePublished - Jan 1 2019
Event38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2019 - Darmstadt, Germany
Duration: May 19 2019May 23 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11478 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2019
CountryGermany
CityDarmstadt
Period5/19/195/23/19

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'New techniques for obfuscating conjunctions'. Together they form a unique fingerprint.

Cite this