Publications

A monotone policy batch \( \mathsf{NP} \) language \( \mathcal{L}_{\mathcal{R}, P} \) is parameterized by a monotone policy \( P \colon \{0,1\}^k \to \{0,1\} \) and an \( \mathsf{NP} \) relation \( \mathcal{R} \). A statement \( (x_1, \ldots, x_k) \) is a yes instance if there exists \( w_1, \ldots, w_k \) where \( P(\mathcal{R}(x_1, w_1), \ldots, \mathcal{R}(x_k, w_k)) = 1 \). For example, we might say that an instance \( (x_1, \ldots, x_k) \) is a yes instance if a majority of the statements are true. A monotone policy batch argument (BARG) for \( \mathsf{NP} \) allows a prover to prove that \( (x_1, \ldots, x_k) \in \mathcal{L}_{\mathcal{R}, P} \) with a proof of size \( \mathsf{poly}(\lambda, |\mathcal{R}|, \log k) \), where \( \lambda \) is the security parameter, \( |\mathcal{R}| \) is the size of the Boolean circuit that computes \( \mathcal{R} \), and \( k \) is the number of instances. Recently, Brakerski, Brodsky, Kalai, Lombardi, and Paneth (CRYPTO 2023) gave the first monotone policy BARG for \( \mathsf{NP} \) from the learning with errors (LWE) assumption.

In this work, we describe a generic approach for constructing monotone policy BARGs from any BARG for \( \mathsf{NP} \) together with an additively homomorphic encryption scheme. This yields the first constructions of monotone policy BARGs from the \( k \)-Lin assumption in prime-order pairing groups as well as the (subexponential) DDH assumption in pairing-free groups. Central to our construction is a notion of a zero-fixing hash function, which is a relaxed version of a predicate-extractable hash function from the work of Brakerski et al. Our relaxation enables a direct realization of zero-fixing hash functions from BARGs for \( \mathsf{NP} \) and additively homomorphic encryption, whereas the previous notion relied on leveled homomorphic encryption, and by extension, the LWE assumption.