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

Ruta Jawale; Yael Tauman Kalai; Dakshita Khurana; Rachel Zhang

doi:10.1145/3406325.3451055

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

Ruta Jawale, Yael Tauman Kalai, Dakshita Khurana, Rachel Zhang

Siebel School of Computing and Data Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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.

Original language	English (US)
Title of host publication	STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
Editors	Samir Khuller, Virginia Vassilevska Williams
Publisher	Association for Computing Machinery
Pages	708-721
Number of pages	14
ISBN (Electronic)	9781450380539
DOIs	https://doi.org/10.1145/3406325.3451055
State	Published - Jun 15 2021
Event	53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021 - Virtual, Online, Italy Duration: Jun 21 2021 → Jun 25 2021

Publication series

Name	Proceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)	0737-8017

Conference

Conference	53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021
Country/Territory	Italy
City	Virtual, Online
Period	6/21/21 → 6/25/21

Keywords

Fiat-Shamir heuristic
PPAD hardness
cryptographic protocols
delegation of computation

ASJC Scopus subject areas

Software

Online availability

10.1145/3406325.3451055

Library availability

Discover UIUC Full Text

Cite this

Jawale, R., Kalai, Y. T., Khurana, D., & Zhang, R. (2021). SNARGs for bounded depth computations and PPAD hardness from sub-exponential LWE. In S. Khuller, & V. V. Williams (Eds.), STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (pp. 708-721). (Proceedings of the Annual ACM Symposium on Theory of Computing). Association for Computing Machinery. https://doi.org/10.1145/3406325.3451055

SNARGs for bounded depth computations and PPAD hardness from sub-exponential LWE. / Jawale, Ruta; Kalai, Yael Tauman; Khurana, Dakshita et al.
STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. ed. / Samir Khuller; Virginia Vassilevska Williams. Association for Computing Machinery, 2021. p. 708-721 (Proceedings of the Annual ACM Symposium on Theory of Computing).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Jawale, R, Kalai, YT, Khurana, D & Zhang, R 2021, SNARGs for bounded depth computations and PPAD hardness from sub-exponential LWE. in S Khuller & VV Williams (eds), STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. Proceedings of the Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, pp. 708-721, 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, Virtual, Online, Italy, 6/21/21. https://doi.org/10.1145/3406325.3451055

Jawale R, Kalai YT, Khurana D, Zhang R. SNARGs for bounded depth computations and PPAD hardness from sub-exponential LWE. In Khuller S, Williams VV, editors, STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery. 2021. p. 708-721. (Proceedings of the Annual ACM Symposium on Theory of Computing). doi: 10.1145/3406325.3451055

Jawale, Ruta ; Kalai, Yael Tauman ; Khurana, Dakshita et al. / SNARGs for bounded depth computations and PPAD hardness from sub-exponential LWE. STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. editor / Samir Khuller ; Virginia Vassilevska Williams. Association for Computing Machinery, 2021. pp. 708-721 (Proceedings of the Annual ACM Symposium on Theory of Computing).

@inproceedings{225a83b4a4e04f31ba17284f2ae5181e,

title = "SNARGs for bounded depth computations and PPAD hardness from sub-exponential LWE",

abstract = "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.",

keywords = "Fiat-Shamir heuristic, PPAD hardness, cryptographic protocols, delegation of computation",

author = "Ruta Jawale and Kalai, {Yael Tauman} and Dakshita Khurana and Rachel Zhang",

note = "Publisher Copyright: {\textcopyright} 2021 ACM.; 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021 ; Conference date: 21-06-2021 Through 25-06-2021",

year = "2021",

month = jun,

day = "15",

doi = "10.1145/3406325.3451055",

language = "English (US)",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

pages = "708--721",

editor = "Samir Khuller and Williams, {Virginia Vassilevska}",

booktitle = "STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing",

address = "United States",

}

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

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 -

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

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this