Paper 2020/980

SNARGs for Bounded Depth Computations and PPAD Hardness from Sub-Exponential LWE

Ruta Jawale, Yael Tauman Kalai, Dakshita Khurana, and Rachel Zhang


We construct a succinct non-interactive publicly-verifiable delegation scheme for any log-space uniform circuit under the sub-exponential Learning With Errors ($\mathsf{LWE}$) assumption. For a circuit $C:\{0,1\}^N\rightarrow\{0,1\}$ of size $S$ and depth $D$, the prover runs in time $\mathsf{poly}(S)$, the communication complexity is $D \cdot \mathsf{polylog} (S)$, and the verifier runs in time $(D+N) \cdot \mathsf{polylog} (S)$. To obtain this result, we introduce a new cryptographic primitive: lossy correlation-intractable hash functions. We use this primitive to soundly instantiate the Fiat-Shamir transform for a large class of interactive proofs, including the interactive sum-check protocol and the $\mathsf{GKR}$ protocol, assuming the sub-exponential hardness of $\mathsf{LWE}$. By relying on the result of Choudhuri et al. (STOC 2019), we also establish the sub-exponential average-case hardness of $\mathsf{PPAD}$, assuming the sub-exponential hardness of $\mathsf{LWE}$.

Available format(s)
Cryptographic protocols
Publication info
delegation schemesnon-interactiveFiat-Shamirsum-checkGKRPPADlossycorrelation intractability
Contact author(s)
jawale2 @ illinois edu
yael @ microsoft com
dakshita @ illinois edu
rachelyz44 @ gmail com
2020-08-19: last of 2 revisions
2020-08-18: received
See all versions
Short URL
Creative Commons Attribution


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