Welcome to the resource topic for 2023/1967
Title:
Monotone Policy BARGs from BARGs and Additively Homomorphic Encryption
Authors: Shafik Nassar, Brent Waters, David J. Wu
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-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 standard BARGs for \mathsf{NP} and additively homomorphic encryption, whereas the previous notion relied on leveled homomorphic encryption, and by extension, the LWE assumption.
ePrint: https://eprint.iacr.org/2023/1967
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .