Paper 2020/860

SNARGs for Bounded Depth Computations from Sub-Exponential LWE

Yael Tauman Kalai and Rachel Zhang


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).

Available format(s)
Cryptographic protocols
Publication info
delegation schemesnon-interactiveFiat-Shamirsum-checkGKRPPAD
Contact author(s)
yael @ microsoft com
2020-07-12: received
Short URL
Creative Commons Attribution


      author = {Yael Tauman Kalai and Rachel Zhang},
      title = {SNARGs for Bounded Depth Computations from Sub-Exponential LWE},
      howpublished = {Cryptology ePrint Archive, Paper 2020/860},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.