{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,11]],"date-time":"2026-06-11T09:13:46Z","timestamp":1781169226177,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":70,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"DARPA","award":["HR001120C0023 and HR001120C0024"],"award-info":[{"award-number":["HR001120C0023 and HR001120C0024"]}]},{"name":"Paul E. Gray (1954) UROP Fund"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451055","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"708-721","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":49,"title":["SNARGs for bounded depth computations and PPAD hardness from sub-exponential LWE"],"prefix":"10.1145","author":[{"given":"Ruta","family":"Jawale","sequence":"first","affiliation":[{"name":"University of Illinois at Urbana-Champaign, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yael Tauman","family":"Kalai","sequence":"additional","affiliation":[{"name":"Microsoft Research, USA \/ Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dakshita","family":"Khurana","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rachel","family":"Zhang","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"On algorithms for Nash equilibria. Unpublished manuscript","author":"Abbot Tim","year":"2004","unstructured":"Tim Abbot, Daniel Kane, and Paul Valiant. 2004. On algorithms for Nash equilibria. Unpublished manuscript, 2004. https:\/\/web.mit.edu\/tabbott\/Public\/final.pdf"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53644-5_1"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188924"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Boaz Barak. 2001. How to Go Beyond the Black-Box Simulation Barrier. In FOCS. Pages 106\u2013115.","DOI":"10.1109\/SFCS.2001.959885"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-36033-7_20"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/168588.168596"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53644-5_2"},{"key":"e_1_3_2_1_8_1","volume-title":"The Hunting of the SNARK. IACR Cryptology ePrint Archive","author":"Bitansky Nir","year":"2014","unstructured":"Nir Bitansky, Ran Canetti, Alessandro Chiesa, Shafi Goldwasser, Huijia Lin, Aviad Rubinstein, and Eran Tromer. 2014. The Hunting of the SNARK. IACR Cryptology ePrint Archive, 2014, 2014. Pages 580. http:\/\/eprint.iacr.org\/2014\/580"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488623"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","unstructured":"Nir Bitansky Alessandro Chiesa Yuval Ishai Rafail Ostrovsky and Omer Paneth. 2013. Succinct Non-interactive Arguments via Linear Interactive Proofs. In TCC. Pages 315\u2013333. https:\/\/doi.org\/10.1007\/978-3-642-36594-2_18 10.1007\/978-3-642-36594-2_18","DOI":"10.1007\/978-3-642-36594-2_18"},{"key":"e_1_3_2_1_11_1","volume-title":"Succinct Randomized Encodings and their Applications. IACR Cryptology ePrint Archive","author":"Bitansky Nir","year":"2015","unstructured":"Nir Bitansky, Sanjam Garg, Huijia Lin, Rafael Pass, and Sidharth Telang. 2015. Succinct Randomized Encodings and their Applications. IACR Cryptology ePrint Archive, 2015, 2015. Pages 356."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2020.6"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188870"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.94"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-36033-7_16"},{"key":"e_1_3_2_1_16_1","volume-title":"Factoring and Pairings are not Necessary for iO: Circular-Secure LWE Suffices. IACR Cryptol. ePrint Arch","author":"Brakerski Zvika","year":"2020","unstructured":"Zvika Brakerski, Nico D\u00f6ttling, Sanjam Garg, and Giulio Malavolta. 2020. Factoring and Pairings are not Necessary for iO: Circular-Secure LWE Suffices. IACR Cryptol. ePrint Arch., 2020. https:\/\/eprint.iacr.org\/2020\/1024"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055497"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-45388-6_4"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-56877-1_26"},{"key":"e_1_3_2_1_20_1","volume-title":"Minimum Disclosure Proofs of Knowledge. J. Comput. Syst. Sci., 37, 2","author":"Brassard Gilles","year":"1988","unstructured":"Gilles Brassard, David Chaum, and Claude Cr\u00e9peau. 1988. Minimum Disclosure Proofs of Knowledge. J. Comput. Syst. Sci., 37, 2, 1988. Pages 156\u2013189."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316380"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-78381-9_4"},{"key":"e_1_3_2_1_23_1","volume-title":"The random oracle methodology, revisited. J. ACM, 51, 4","author":"Canetti Ran","year":"2004","unstructured":"Ran Canetti, Oded Goldreich, and Shai Halevi. 2004. The random oracle methodology, revisited. J. ACM, 51, 4, 2004. Pages 557\u2013594."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Ran Canetti and Justin Holmgren. 2016. Fully Succinct Garbled RAM. In ITCS. ACM. Pages 169\u2013178.","DOI":"10.1145\/2840728.2840765"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Ran Canetti Justin Holmgren Abhishek Jain and Vinod Vaikuntanathan. 2015. Succinct Garbling and Indistinguishability Obfuscation for RAM Programs. In STOC. ACM. Pages 429\u2013437.","DOI":"10.1145\/2746539.2746621"},{"key":"e_1_3_2_1_26_1","first-page":"592","volume-title":"Mathematics of Compuation","author":"David","year":"1981","unstructured":"David G. Cantor and Hans Zassenhaus. 1981. A new algorithm for factoring polynomials over finite fields. Mathematics of Compuation, 1981. Pages 587\u2013592."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516512.1516516"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Yu-Chi Chen Sherman S. M. Chow Kai-Min Chung Russell W. F. Lai Wei-Kai Lin and Hong-Sheng Zhou. 2016. Cryptography for Parallel RAM from Indistinguishability Obfuscation. In ITCS. ACM. Pages 179\u2013190.","DOI":"10.1145\/2840728.2840769"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316400"},{"key":"e_1_3_2_1_30_1","volume-title":"Rothblum","author":"Choudhuri Arka Rai","year":"2019","unstructured":"Arka Rai Choudhuri, Pavel Hub\u00e1cek, Chethan Kamath, Krzysztof Pietrzak, Alon Rosen, and Guy N. Rothblum. 2019. PPAD-Hardness via Iterated Squaring Modulo a Composite. IACR Cryptol. ePrint Arch., 2019, 2019. Pages 667. https:\/\/eprint.iacr.org\/2019\/667"},{"key":"e_1_3_2_1_31_1","first-page":"456","volume-title":"Proceedings of CRYPTO\u00ef\u00bf\u015391","author":"Ivan","year":"1992","unstructured":"Ivan Damg\\r ard. 1992. Towards Practical Public Key Systems Secure Against Chosen Ciphertext Attacks. In Proceedings of CRYPTO\u00ef\u00bf\u015391. Pages 445\u2013456."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28914-9_4"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/070699652"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-26954-8_1"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-45727-3_5"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"crossref","unstructured":"Amos Fiat and Adi Shamir. 1986. How to Prove Yourself: Practical Solutions to Identification and Signature Problems. In CRYPTO. Pages 186\u2013194.","DOI":"10.1007\/3-540-47721-7_12"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53008-5_20"},{"key":"e_1_3_2_1_38_1","volume-title":"Indistinguishability Obfuscation from Circular Security. IACR Cryptol. ePrint Arch","author":"Gay Romain","year":"2020","unstructured":"Romain Gay and Rafael Pass. 2020. Indistinguishability Obfuscation from Circular Security. IACR Cryptol. ePrint Arch., 2020. https:\/\/eprint.iacr.org\/2020\/1010"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38348-9_37"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"crossref","unstructured":"Shafi Goldwasser and Yael Tauman Kalai. 2003. On the (In)security of the Fiat-Shamir Paradigm. In FOCS. Pages 102\u2013.","DOI":"10.1109\/SFCS.2003.1238185"},{"key":"e_1_3_2_1_41_1","first-page":"4","article-title":"2015","volume":"62","author":"Goldwasser Shafi","year":"2015","unstructured":"Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum. 2015. Delegating Computation: Interactive Proofs for Muggles. J. ACM, 62, 4, 2015. Pages 27.","journal-title":"Delegating Computation: Interactive Proofs for Muggles. J. ACM"},{"key":"e_1_3_2_1_42_1","series-title":"Lecture Notes in Computer Science. 6477","volume-title":"ASIACRYPT","author":"Groth Jens","unstructured":"Jens Groth. 2010. Short Pairing-Based Non-interactive Zero-Knowledge Arguments. In ASIACRYPT. Lecture Notes in Computer Science. 6477, Springer. Pages 321\u2013340."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30057-8_37"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00085"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.88"},{"key":"e_1_3_2_1_47_1","volume-title":"Dakshita Khurana, and Rachel Zhang.","author":"Jawale Ruta","year":"2020","unstructured":"Ruta Jawale, Yael Tauman Kalai, Dakshita Khurana, and Rachel Zhang. 2020. SNARGs for Bounded Depth Computations and PPAD Hardness from Sub-Exponential LWE. IACR Cryptol. ePrint Arch., 2020. https:\/\/eprint.iacr.org\/2020\/980.pdf"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53644-5_4"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316411"},{"key":"e_1_3_2_1_50_1","unstructured":"Yael Tauman Kalai Omer Paneth and Lisa Yang. 2020. PPAD-Hardness and Delegation with Unambiguous Proofs. CRYPTO."},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488679"},{"key":"e_1_3_2_1_52_1","volume-title":"Rothblum","author":"Kalai Yael Tauman","year":"2014","unstructured":"Yael Tauman Kalai, Ran Raz, and Ron D. Rothblum. 2014. How to delegate computations: the power of no-signaling proofs. In STOC. ACM. Pages 485\u2013494."},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-63715-0_8"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129782"},{"key":"e_1_3_2_1_55_1","volume-title":"Allison Bishop Lewko, and Brent Waters","author":"Koppula Venkata","year":"2015","unstructured":"Venkata Koppula, Allison Bishop Lewko, and Brent Waters. 2015. Indistinguishability Obfuscation for Turing Machines with Unbounded Memory. In STOC. ACM. Pages 419\u2013428."},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"crossref","unstructured":"Helger Lipmaa. 2012. Progression-Free Sets and Sublinear Pairing-Based Non-Interactive Zero-Knowledge Arguments. In TCC. Pages 169\u2013189.","DOI":"10.1007\/978-3-642-28914-9_10"},{"key":"e_1_3_2_1_58_1","volume-title":"Algebraic Methods for Interactive Proof Systems. J. ACM, 39, 4","author":"Lund Carsten","year":"1992","unstructured":"Carsten Lund, Lance Fortnow, Howard J. Karloff, and Noam Nisan. 1992. Algebraic Methods for Interactive Proof Systems. J. ACM, 39, 4, 1992. Pages 859\u2013868."},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365746"},{"key":"e_1_3_2_1_60_1","series-title":"SIAM J. Comput., 30, 4","volume-title":"Computationally Sound Proofs.","author":"Micali Silvio","year":"2000","unstructured":"Silvio Micali. 2000. Computationally Sound Proofs.. SIAM J. Comput., 30, 4, 2000. Pages 1253\u20131298."},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45146-4_6"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-70503-3_9"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80063-7"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28914-9_24"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-26948-7_4"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374406"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2019.60"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-68339-9_33"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897652"},{"key":"e_1_3_2_1_70_1","doi-asserted-by":"crossref","unstructured":"Adi Shamir. 1992. IP = PSPACE. J. ACM 39 4 1992. Pages 869\u2013877.","DOI":"10.1145\/146585.146609"},{"key":"e_1_3_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2018.00060"},{"key":"e_1_3_2_1_72_1","volume-title":"Candidate Obfuscation via Oblivious LWE Sampling. IACR Cryptol. ePrint Arch","author":"Wee Hoeteck","year":"2020","unstructured":"Hoeteck Wee and Daniel Wichs. 2020. Candidate Obfuscation via Oblivious LWE Sampling. IACR Cryptol. ePrint Arch., 2020. https:\/\/eprint.iacr.org\/2020\/1042"}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","location":"Virtual Italy","acronym":"STOC '21","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451055","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451055","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451055","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:44Z","timestamp":1750197704000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451055"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":70,"alternative-id":["10.1145\/3406325.3451055","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451055","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}