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\to \{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 $$. By relying on the result of Choudhuri et al. (STOC 2019), we also establish the sub-exponential average-case hardness of $$, assuming the sub-exponential hardness of $$.