Paper 2023/1967

Monotone Policy BARGs from BARGs and Additively Homomorphic Encryption

Abstract

A monotone policy batch $\mathsf{NP}$ language ${\mathcal{L}}_{\mathcal{R},P}$ is parameterized by a monotone policy $P:\{0,1{\}}^k\to \{0,1\}$ and an $\mathsf{NP}$ relation $\mathcal{R}$. A statement $(x_1,\dots ,x_k)$ is a YES instance if there exists $w_1,\dots ,w_k$ where $P(\mathcal{R}(x_1,w_1),\dots ,\mathcal{R}(x_k,w_k))=1$. For example, we might say that an instance $(x_1,\dots ,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,\dots ,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 $$ from the learning with errors (LWE) assumption. In this work, we describe a generic approach for constructing monotone policy BARGs from any BARG for $$ together with an additively homomorphic encryption scheme. This yields the first constructions of monotone policy BARGs from the $$-$$ 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 $$ and additively homomorphic encryption, whereas the previous notion relied on leveled homomorphic encryption, and by extension, the LWE assumption. As an application, we also show how to combine a monotone policy BARG with a puncturable signature scheme to obtain a monotone policy aggregate signature scheme. Our work yields the first (statically-secure) monotone policy aggregate signatures that supports general monotone Boolean circuits from standard pairing-based assumptions. Previously, this was only known from LWE.