Paper 2026/1932

Obfuscating Non-Evasive Programs: Making Witness Encryption Positional

Abstract

Indistinguishability obfuscation ($i\mathcal{O}$) is a powerful cryptographic tool that enables many cryptographic capabilities. Due to its expressivity, constructing $i\mathcal{O}$ is challenging, and existing constructions based on well-founded assumptions all require multiple algebraic assumptions, including an assumption on bilinear groups. If we consider post-quantum constructions, existing candidates all rely on new heuristic assumptions. Due to the challenges in realizing $i\mathcal{O}$, a parallel line of work has aimed to build obfuscation for restricted classes of functionalities, such as point functions, compute-and-compare programs, and most broadly, null circuits (i.e., circuits that always output $\bot$) from weaker assumptions. Thus far, these techniques have all been limited to supporting evasive programs (i.e., programs where it is difficult for an evaluator to find an input where the program's output is not $\bot$). In this work, we introduce a new notion called cutoff-$i\mathcal{O}$. In cutoff-$i\mathcal{O}$, we can obfuscate a circuit $C$ together with a secret cutoff $t$. Then, given an input $(w, i)$, the obfuscated program outputs $C(w, i)$ if $i > t$ and $\bot$ otherwise. Security essentially stipulates that the obfuscated program should hide the cutoff $t$. Cutoff-$i\mathcal{O}$ is an example of obfuscation for a non-evasive function class and implies notions like positional witness encryption, which was previously only known from $i\mathcal{O}$. Our main result is showing how to construct cutoff-$i\mathcal{O}$ from witness encryption and the learning with errors (LWE) assumption. Thus, our approach shows how to lift an obfuscation scheme for an evasive function class (e.g., witness encryption, and more broadly, null-$i\mathcal{O}$) to an obfuscation scheme for a non-evasive function class. By relying on the implication to positional witness encryption, we obtain (from the same set of assumptions) a collusion-resistant broadcast-and-trace scheme with public tracing and ciphertext size $N^{\varepsilon} \cdot \mathsf{poly}(\lambda)$, where $N$ is the number of users in the system and $\varepsilon > 0$ is an arbitrary constant. Previously, such an implication was only known from $i\mathcal{O}$ (or from bilinear groups for the special case where $\varepsilon = 1/2$). Our construction also extends to the registration-based setting where users can sample their own keys and there is no central key-issuing authority. Additionally, we show that cutoff-$i\mathcal{O}$ and LWE can be used to obtain a somewhere-statistically correlation-intractable hash function for efficiently enumerable relations as well as a non-interactive batch argument for $\mathsf{NP}$ (BARG) with somewhere-statistical soundness.