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

Available format(s)
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Contact author(s)
yael @ microsoft com
History
Short URL
https://ia.cr/2020/860

CC BY

BibTeX

@misc{cryptoeprint:2020/860,
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{https://eprint.iacr.org/2020/860}},
url = {https://eprint.iacr.org/2020/860}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.