Advertisement
Published in:
2025 | OriginalPaper | Chapter
Monotone Policy BARGs from BARGs and Additively Homomorphic Encryption
Authors : Shafik Nassar, Brent Waters, David J. Wu
Published in: Theory of Cryptography
Publisher: Springer Nature Switzerland
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by (Link opens in a new window)
Abstract
A monotone policy batch \(\textsf{NP} \) language \(\mathcal {L}_{\mathcal {R}, P}\) is parameterized by a monotone policy \(P :\{0,1\}^k \rightarrow \{0,1\}\) and an \(\textsf{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 \(\textsf{NP} \) allows a prover to prove that \((x_1, \ldots , x_k) \in \mathcal {L}_{\mathcal {R}, P}\) with a proof of size \(\textsf{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 \(\textsf{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 \(\textsf{NP} \) together with an additively homomorphic encryption scheme. This yields the first constructions of monotone policy BARGs from the k-\(\textsf{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 \(\textsf{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 (statically-secure) monotone policy aggregate signatures that supports general monotone Boolean circuits from standard pairing-based assumptions. Previously, this was only known from LWE.
