Obfuscating Conjunctions

Zvika Brakerski, Guy N. Rothblum

Published: Journal of Cryptology, 2017
Authors: Zvika Brakerski and Guy N. Rothblum

Abstract

Code obfuscation remains one of the most ambitious goals in modern cryptography, aiming to transform programs into "black boxes" that preserve functionality while hiding internal logic. While general-purpose obfuscation is known to be impossible in its strongest form, researchers have found success focusing on specific function classes. This paper presents the first secure construction for obfuscating conjunction functions—logical tests that check if input bits match a secret pattern while ignoring specified "wildcard" positions. The authors demonstrate that their construction achieves Virtual Black Box (VBB) security in the generic multilinear map model for all conjunctions and security in the standard model for conjunctions sampled from high-entropy distributions.

Introduction

The theoretical study of code obfuscation seeks to create software that is impossible to reverse-engineer. In the strictest sense, a "Virtual Black Box" (VBB) obfuscator ensures that an adversary can learn nothing from the obfuscated code that they could not learn by simply having access to the program's input-output behavior.

Prior to this work, the cryptographic community had successfully obfuscated "point functions"—simple programs that return a '1' for a single specific input (like a password) and '0' otherwise. However, point functions are limited in utility. This paper advances the field by addressing conjunctions. A conjunction (e.g., $x_1 \wedge \neg x_4 \wedge x_7$) evaluates a subset of input bits. The bits not included in the logical check are referred to as "wildcards." The primary security challenge in obfuscating conjunctions is not merely hiding the required bit values, but hiding the identity of the wildcard bits themselves. If an attacker can determine which bits are ignored, the underlying logic is compromised.

Methodology

The authors utilize Graded Encoding Schemes, a generalized framework for multilinear maps, to build their obfuscator. The construction relies on a sophisticated encoding of the secret pattern into mathematical structures that only "unlock" when the correct input is provided.

The Construction Logic

To obfuscate a conjunction over $n$ bits, the scheme generates pairs of encodings for every input position $i$:

  1. Input Encodings: For each bit position, the obfuscator provides encodings for both possible values (0 and 1).
  2. The Wildcard Mechanism: The core innovation lies in how wildcards are handled. If a bit $i$ is a wildcard, the mathematical ratio between the encodings for 0 and 1 is identical. Conversely, if a bit is required, these ratios are independent and random. This ensures that at the point of evaluation, the wildcard bits "cancel out" mathematically.
  3. Target Value: A final encoding represents the product of all required bits in their correct state.

To evaluate the program, a user selects the encodings corresponding to their input bits, computes their product using the multilinear map, and compares the result to the target value. The check passes if and only if all non-wildcard bits match the secret pattern.

Security and Results

The paper provides a dual-layered security proof to address different adversarial contexts:

  • Generic Model Security: The authors prove that the scheme is a VBB obfuscator for any conjunction when the adversary is restricted to basic algebraic operations (the Generic Multilinear Map Model). This provides strong evidence that no "algebraic" attack can break the scheme.
  • Standard Model Security: For conjunctions drawn from distributions with high entropy (where the secret pattern has significant uncertainty), the authors prove security under the Graded External DH (GXDH) and Graded Canetti (GCAN) assumptions. This demonstrates that the product of the encodings acts as an "entropy condenser," appearing random to an observer unless they possess the correct input.

Discussion and Limitations

While this work represents a major theoretical milestone, it is not without limitations. The security of the construction is inextricably linked to the security of Graded Encoding Schemes. During the period this research was published, several early candidates for these multilinear maps were found vulnerable to "zeroizing" attacks. The authors acknowledge these developments, noting that the construction's ultimate robustness depends on the continued refinement of secure multilinear map candidates.

Furthermore, while conjunctions are significantly more expressive than point functions, they remain a restricted class of programs. However, the techniques introduced here—specifically the use of symmetry to hide wildcards—have since served as foundational building blocks for obfuscating more complex classes, such as CNF formulas and beyond.

Summary updated

Abstract

We show how to securely obfuscate the class of conjunction functions (functions like \(f(x_1, \ldots , x_n) = x_1 \wedge \lnot x_4 \wedge \lnot x_6 \wedge \cdots \wedge 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 et al. (CRYPTO 2013). We show that the construction is secure when the conjunction is drawn from a distribution, under mild conditions 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.
BibTeX
@article{brakerski2017obfuscating,
  author = {Zvika Brakerski and Guy N. Rothblum},
  title = {{Obfuscating Conjunctions}},
  journal = {J. Cryptol.},
  year = {2017},
  doi = {10.1007/s00145-015-9221-5},
}
Figure