Anzeige
Erschienen in:
2025 | OriginalPaper | Buchkapitel
Monotone Policy BARGs from BARGs and Additively Homomorphic Encryption
verfasst von : Shafik Nassar, Brent Waters, David J. Wu
Erschienen in: Theory of Cryptography
Verlag: Springer Nature Switzerland
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by (Link öffnet in neuem Fenster)
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.
