Paper 2023/1050

SNARGs for Monotone Policy Batch NP

Abstract

We construct a succinct non-interactive argument ($$) for the class of monotone policy batch $$ languages under the Learning with Errors ($$) assumption. This class is a subclass of $$ that is associated with a monotone function~$$ and an $$ language $$, and contains instances $$ such that $$ where $$ if and only if $$. Our $$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 $$ under standard hardness assumptions for a sub-class of $$ that is not known to have a (computational) non-signaling $$ with small locality. Indeed, our approach necessarily departs from the known framework of constructing $$s dating back to [Kalai-Raz-Rothblum, STOC '13] Our construction combines existing quasi-arguments for $$ (based on batch arguments for $$) with a novel ingredient which we call a predicate-extractable hash ($$) family. This notion generalizes the notion of a somewhere extractable hash. Whereas a somewhere extractable hash allows to extract a single input coordinate, our $$ extracts a global property of the input. We view this primitive to be of independent interest, and believe that it will find other applications.