SNARGs and PPAD Hardness from Sub-exponential LWE

We construct a succinct non-interactive publicly-verifiable delegation scheme for any logspace uniform circuit under the sub-exponential Learning With Errors (LWE) assumption. For a circuit C : {0, 1}^N -> {0, 1} of size S and depth D, the prover runs in time poly(S), the communication complexity is D * polylog(S), and the verifier runs in time (D + N) * 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 GKR protocol, assuming the sub-exponential hardness of LWE. By relying on the result of Choudhuri et al. (STOC 2019), we also establish the sub-exponential average-case hardness of PPAD, assuming the sub-exponential hardness of LWE. 

This is based on a joint work with Yael Tauman Kalai, Dakshita Khurana, and Rachel Zhang.