International Association for Cryptologic Research

International Association
for Cryptologic Research


SNARGs for Monotone Policy Batch NP

Zvika Brakerski , Weizmann Institute of Science
Maya Farber Brodsky , Tel Aviv University
Yael Tauman Kalai , Microsoft Research, Massachusetts Institute of Technology
Alex Lombardi , Simons Institute, University of California, Berkeley
Omer Paneth , Tel Aviv University
DOI: 10.1007/978-3-031-38545-2_9 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2023
Abstract: We construct a succinct non-interactive argument ($\mathsf{SNARG}$) for the class of monotone policy batch $\mathsf{NP}$ languages, under the Learning with Errors ($\mathsf{LWE}$) assumption. This class is a subclass of $\mathsf{NP}$ that is associated with a monotone function~$f:\{0,1\}^k\rightarrow\{0,1\}$ and an $\mathsf{NP}$ language $\mathcal{L}$, and contains instances $(x_1,\ldots,x_k)$ such the $f(b_1,\ldots,b_k)=1$ where $b_j=1$ if and only if $x_j\in \mathcal{L}$. Our $\mathsf{SNARG}$s are arguments of knowledge in the non-adaptive setting, and satisfy a new notion of somewhere extractability against adaptive adversaries. This is the first $\mathsf{SNARG}$ under standard hardness assumptions for a sub-class of $\mathsf{NP}$ that is not known to have a (computational) non-signaling $\mathsf{PCP}$ with parameters compatible with the standard framework for constructing $\mathsf{SNARG}$s dating back to [Kalai-Raz-Rothblum, STOC '13]. Indeed, our approach necessarily departs from this framework. Our construction combines existing quasi-arguments for $\mathsf{NP}$ (based on batch arguments for $\mathsf{NP}$) with a new type of cryptographic encoding of the instance and a new analysis going from local to global soundness. The main novel ingredient used in our encoding is a {\em predicate-extractable hash} ($\mathsf{PEH}$) family, which is a primitive that generalizes the notion of a somewhere extractable hash. Whereas a somewhere extractable hash allows to extract a single input coordinate, our $\mathsf{PEH}$ extracts a {\em global} property of the input. We view this primitive to be of independent interest, and believe that it will find other applications.
  title={SNARGs for Monotone Policy Batch NP},
  author={Zvika Brakerski and Maya Farber Brodsky and Yael Tauman Kalai and Alex Lombardi and Omer Paneth},