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

Abstract

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}$.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
delegation schemesnon-interactiveFiat-Shamirsum-checkGKRPPADlossycorrelation intractability
Contact author(s)
jawale2 @ illinois edu
yael @ microsoft com
dakshita @ illinois edu
rachelyz44 @ gmail com
History
2020-08-19: last of 2 revisions
2020-08-18: received
See all versions
Short URL
https://ia.cr/2020/980
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/980,
      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{https://eprint.iacr.org/2020/980}},
      url = {https://eprint.iacr.org/2020/980}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.