Unlocking SNARGs Beyond Non-Signaling Assumptions 🔓

Yael Tauman Kalai (Microsoft Research)
https://simons.berkeley.edu/talks/yael-tauman-kalai-microsoft-research-2023-05-02
Minimal Complexity Assumptions for Cryptography

We construct a SNARG for the class of monotone policy batch NP languages, under the LWE assumption. This class is a subclass of NP that is associated with a monotone function f and an NP language L, and contains instances (x_1,…,x_k) such that f(b_1,…,b_k)=1 where b_j=1 if and only if x_j is in L.

This is the first SNARG under standard hardness assumptions for a sub-class of NP that is not known to have a (computational) non-signaling PCP (which small locality). Indeed, our approach necessarily departs from the previous framework used to construct SNARGs from standard assumptions.

The main novel ingredient used in our SNARG construction is a predicate-extractable hash (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 PEH extracts a global property of the input. We view this primitive to be of independent interest and believe that it will find other applications.