TY - GEN

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

AU - Jawale, Ruta

AU - Kalai, Yael Tauman

AU - Khurana, Dakshita

AU - Zhang, Rachel

N1 - Funding Information:
This material is based on work supported in part by DARPA under Contract Nos. HR001120C0023 and HR001120C0024. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the United States Government or DARPA. Rachel Zhang is supported by the Paul E. Gray (1954) UROP Fund.
Publisher Copyright:
© 2021 ACM.

PY - 2021/6/15

Y1 - 2021/6/15

N2 - 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.

AB - 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.

KW - Fiat-Shamir heuristic

KW - PPAD hardness

KW - cryptographic protocols

KW - delegation of computation

UR - http://www.scopus.com/inward/record.url?scp=85108159172&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85108159172&partnerID=8YFLogxK

U2 - 10.1145/3406325.3451055

DO - 10.1145/3406325.3451055

M3 - Conference contribution

AN - SCOPUS:85108159172

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 708

EP - 721

BT - STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing

A2 - Khuller, Samir

A2 - Williams, Virginia Vassilevska

PB - Association for Computing Machinery

T2 - 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021

Y2 - 21 June 2021 through 25 June 2021

ER -