Holographic SNARGs for P and Batch-NP from (Polynomially Hard) Learning with Errors

ePrint Report: Holographic SNARGs for P and Batch-NP from (Polynomially Hard) Learning with Errors

Susumu Kiyoshima

A succinct non-interactive argument (SNARG) is called holographic if the verifier runs in time sub-linear in the input length when given oracle access to an encoding of the input. We present holographic SNARGs for P and Batch-NP under the learning with errors (LWE) assumption. Our holographic SNARG for P has a verifier that runs in time $\mathsf{poly}(\lambda, \log T, \log n)$ for $T$-time computations …

access argument batch called encoding eprint report errors hard input length linear non oracle report