Publications

A tuple of NP statements \( (x_1, \ldots, x_k) \) satisfies a monotone policy \( P \colon \{0,1\}^k \to \{0,1\} \) if \( P(b_1,\ldots,b_k)=1 \), where \( b_i = 1 \) if and only if \( x_i \) is in the NP language. A monotone-policy batch argument (monotone-policy BARG) for NP is a natural extension of regular batch arguments (BARGs) that allows a prover to prove that \( x_1, \ldots, x_k \) satisfy a monotone policy \( P \) with a proof of size \( \mathsf{poly}(\lambda, |\mathcal{R}|, \log k) \), where \( |\mathcal{R}| \) is the size of the Boolean circuit computing the NP relation \( \mathcal{R} \).

Previously, Brakerski, Brodsky, Kalai, Lombardi, and Paneth (CRYPTO 2023) and Nassar, Waters, and Wu (TCC 2024) showed how to construct monotone-policy BARGs from (somewhere-extractable) BARGs for NP together with a leveled homomorphic encryption scheme (Brakerski et al.) or an additively homomorphic encryption scheme over a sufficiently-large group (Nassar et al.). In this work, we improve upon both works by showing that BARGs together with additively homomorphic encryption over any group suffices (e.g., over \( \mathbb{Z}_2 \)). For instance, we can instantiate the additively homomorphic encryption with the classic Goldwasser-Micali encryption scheme based on the quadratic residuosity (QR) assumption. Then, by appealing to existing compilers, we also obtain a monotone-policy aggregate signature scheme from any somewhere extractable BARG and the QR assumption.