Welcome to the resource topic for 2020/980
Title:
SNARGs for Bounded Depth Computations and PPAD Hardness from Sub-Exponential LWE
Authors: Ruta Jawale, Yael Tauman Kalai, Dakshita Khurana, 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}.
ePrint: https://eprint.iacr.org/2020/980
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 .