Cryptology ePrint Archive: Report 2020/980

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

Ruta Jawale and Yael Tauman Kalai and 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}$.

Category / Keywords: cryptographic protocols / delegation schemes, non-interactive, Fiat-Shamir, sum-check, GKR, PPAD, lossy, correlation intractability

Date: received 13 Aug 2020, last revised 18 Aug 2020

Contact author: jawale2 at illinois edu,yael@microsoft com,dakshita@illinois edu,rachelyz44@gmail com

Available format(s): PDF | BibTeX Citation

Version: 20200819:035531 (All versions of this report)

Short URL: ia.cr/2020/980