Welcome to the resource topic for 2020/860
Title:
SNARGs for Bounded Depth Computations from Sub-Exponential LWE
Authors: Yael Tauman Kalai, 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).
ePrint: https://eprint.iacr.org/2020/860
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .