SNARGs for bounded depth computations and PPAD hardness from sub-exponential LWE

We construct a succinct non-interactive publicly-verifiable delegation scheme for any log-space 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: a lossy correlation-intractable hash function family . 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. Additionally, by relying on the result of Choudhuri et al. (STOC 2019), we establish (sub-exponential) average-case hardness of PPAD, assuming the sub-exponential hardness of LWE.

Authors

• Ruta Jawale
• Yael Tauman Kalai
• Dakshita Khurana
• Rachel Yun Zhang

Keywords

• Fiat-Shamir heuristic
• PPAD hardness
• cryptographic protocols
• delegation of computation