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 \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$$\mathsf{Lin}$ assumption in primeorder pairing groups as well as the (subexponential) DDH assumption in pairingfree groups. Central to our construction is a notion of a zerofixing hash function, which is a relaxed version of a predicateextractable hash function from the work of Brakerski et al. Our relaxation enables a direct realization of zerofixing 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. 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 (staticallysecure) monotone policy aggregate signatures that supports general monotone Boolean circuits from standard pairingbased assumptions. Previously, this was only known from LWE.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 A major revision of an IACR publication in TCC 2024
 Keywords
 monotone policy batch argumentsBARGzerofixing hash function
 Contact author(s)

shafik @ cs utexas edu
bwaters @ cs utexas edu
dwu4 @ cs utexas edu  History
 20241003: last of 4 revisions
 20231229: received
 See all versions
 Short URL
 https://ia.cr/2023/1967
 License

CC BY
BibTeX
@misc{cryptoeprint:2023/1967, author = {Shafik Nassar and Brent Waters and David J. Wu}, title = {Monotone Policy {BARGs} from {BARGs} and Additively Homomorphic Encryption}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/1967}, year = {2023}, url = {https://eprint.iacr.org/2023/1967} }