Adaptively Sound Zero-Knowledge SNARKs for UP

We study succinct non-interactive arguments (SNARGs) and succinct non-interactive arguments of knowledge (SNARKs) for the class \(\textsf{UP}\) in the reusable designated verifier model. \(\textsf{UP}\) is an expressive subclass of \(\textsf{NP}\) consisting of all \(\textsf{NP}\) languages where each instance has at most one witness; a designated verifier SNARG (dvSNARG) is one where verification of the SNARG proof requires a private verification key; and such a dvSNARG is reusable if soundness holds even against a malicious prover with oracle access to the (private) verification algorithm. Our main results are as follows. Applying (3) to our SNARG for \(\textsf{UP}\) from evasive LWE (1), we obtain a reusably and adaptively sound designated-verifier zero-knowledge SNARK for \(\textsf{UP}\) from subexponential LWE and evasive LWE. Moreover, applying both (2) and (3) to the Sahai-Waters SNARG, we obtain the same result from LWE, subexponentially secure one-way functions, and subexponentially secure indistinguishability obfuscation. Both constructions have succinct proofs of size \(\textsf{poly}(\lambda ).\) These are the first SNARK constructions with adaptive soundness (even in the designated-verifier setting) for a non-trivial subset of \(\textsf{NP}\) from (subexponentially) falsifiable assumptions.