**SNARGs for Bounded Depth Computations from Sub-Exponential LWE**

*Yael Tauman Kalai and Rachel Zhang*

**Abstract: **We construct a succinct non-interactive publicly-verifiable delegation scheme for any log-space uniform circuit under the sub-exponential $\mathsf{LWE}$ assumption, a standard assumption that is believed to be post-quantum secure. For a circuit of size $S$ and depth $D$, the prover runs in time poly$(S)$, and the verifier runs in time $(D + n) \cdot S^{o(1)}$, where $n$ is the input size. We obtain this result by slightly modifying the $\mathsf{GKR}$ protocol and proving that the Fiat-Shamir heuristic is sound when applied to this modified protocol. We build on the recent works of Canetti et al. (STOC 2019) and Peikert and Shiehian (Crypto 2020), which prove the soundness of the Fiat-Shamir heuristic when applied to a specific (non-succinct) zero-knowledge protocol.
As a corollary, by the work of Choudhuri et al. (STOC 2019), this implies that the complexity class $\mathsf{PPAD}$ is hard (on average) under the sub-exponential $\mathsf{LWE}$ assumption, assuming that $\mathsf{\#SAT}$ with $o(\log n \cdot \log\log n)$ variables is hard (on average).

**Category / Keywords: **cryptographic protocols / delegation schemes, non-interactive, Fiat-Shamir, sum-check, GKR, PPAD

**Date: **received 9 Jul 2020, last revised 11 Jul 2020

**Contact author: **yael at microsoft com

**Available format(s): **PDF | BibTeX Citation

**Version: **20200712:125111 (All versions of this report)

**Short URL: **ia.cr/2020/860

[ Cryptology ePrint archive ]