{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:15:52Z","timestamp":1750220152834,"version":"3.41.0"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2022,10,27]],"date-time":"2022-10-27T00:00:00Z","timestamp":1666828800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["SATC-1704788, RI-1703846, DGE-1650441"],"award-info":[{"award-number":["SATC-1704788, RI-1703846, DGE-1650441"]}]},{"DOI":"10.13039\/100000181","name":"AFOSR","doi-asserted-by":"crossref","award":["FA9550-18-1-0267"],"award-info":[{"award-number":["FA9550-18-1-0267"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000185","name":"DARPA","doi-asserted-by":"crossref","award":["HR00110C0086"],"award-info":[{"award-number":["HR00110C0086"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Alon Young Faculty","award":["1774\/20"],"award-info":[{"award-number":["1774\/20"]}]},{"DOI":"10.13039\/100011038","name":"Office of the Director of National Intelligence","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100011038","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100011039","name":"Intelligence Advanced Research Projects Activity","doi-asserted-by":"crossref","award":["2019-19-020700006"],"award-info":[{"award-number":["2019-19-020700006"]}],"id":[{"id":"10.13039\/100011039","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2022,10,31]]},"abstract":"<jats:p>We introduce the notion of a<jats:italic>Succinct Parallelizable Argument of Knowledge<\/jats:italic>(SPARK). This is an argument of knowledge with the following three efficiency properties for computing and proving a (non-deterministic, polynomial time) parallel RAM computation that can be computed in parallel time<jats:italic>T<\/jats:italic>with at most<jats:italic>p<\/jats:italic>processors:<jats:list list-type=\"simple\"><jats:list-item><jats:label>\u2014<\/jats:label><jats:p>The prover\u2019s (parallel) running time is<jats:inline-formula content-type=\"math\/tex\"><jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( T + \\mathrm{poly}\\hspace{-2.0pt}\\log (T \\cdot p) \\)<\/jats:tex-math><\/jats:inline-formula>. (In other words, the prover\u2019s running time is essentially<jats:italic>T<\/jats:italic>for large computation times!)<\/jats:p><\/jats:list-item><jats:list-item><jats:label>\u2014<\/jats:label><jats:p>The prover uses at most<jats:inline-formula content-type=\"math\/tex\"><jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( p \\cdot \\mathrm{poly}\\hspace{-2.0pt}\\log (T \\cdot p) \\)<\/jats:tex-math><\/jats:inline-formula>processors.<\/jats:p><\/jats:list-item><jats:list-item><jats:label>\u2014<\/jats:label><jats:p>The communication and verifier complexity are both<jats:inline-formula content-type=\"math\/tex\"><jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( \\mathrm{poly}\\hspace{-2.0pt}\\log (T \\cdot p) \\)<\/jats:tex-math><\/jats:inline-formula>.<\/jats:p><\/jats:list-item><\/jats:list>The combination of all three is desirable, as it gives a way to leverage a moderate increase in parallelism in favor of near-optimal running time. We emphasize that even a factor two overhead in the prover\u2019s parallel running time is not allowed.<\/jats:p><jats:p\/><jats:p>Our main contribution is a generic construction of SPARKs from any succinct argument of knowledge where the prover\u2019s parallel running time is<jats:inline-formula content-type=\"math\/tex\"><jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( T \\cdot \\mathrm{poly}\\hspace{-2.0pt}\\log (T \\cdot p) \\)<\/jats:tex-math><\/jats:inline-formula>when using<jats:italic>p<\/jats:italic>processors, assuming collision-resistant hash functions. When suitably instantiating our construction, we achieve a four-round SPARK for<jats:italic>any<\/jats:italic>parallel RAM computation assuming only collision resistance. Additionally assuming the existence of a succinct<jats:italic>non-interactive<\/jats:italic>argument of knowledge (SNARK), we construct a non-interactive SPARK that also preserves the space complexity of the underlying computation up to<jats:inline-formula content-type=\"math\/tex\"><jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( \\mathrm{poly}\\hspace{-2.0pt}\\log (T\\cdot p) \\)<\/jats:tex-math><\/jats:inline-formula>factors.<\/jats:p><jats:p>We also show the following applications of non-interactive SPARKs. First, they immediately imply delegation protocols with near optimal prover (parallel) running time. This, in turn, gives a way to construct verifiable delay functions (VDFs) from any sequential function. When the sequential function is also memory-hard, this yields the first construction of a memory-hard VDF.<\/jats:p>","DOI":"10.1145\/3549523","type":"journal-article","created":{"date-parts":[[2022,8,10]],"date-time":"2022-08-10T12:20:09Z","timestamp":1660134009000},"page":"1-88","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["SPARKs: Succinct Parallelizable Arguments of Knowledge"],"prefix":"10.1145","volume":"69","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3469-6002","authenticated-orcid":false,"given":"Naomi","family":"Ephraim","sequence":"first","affiliation":[{"name":"Cornell Tech, New York, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6307-204X","authenticated-orcid":false,"given":"Cody","family":"Freitag","sequence":"additional","affiliation":[{"name":"Cornell Tech, New York, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1647-2112","authenticated-orcid":false,"given":"Ilan","family":"Komargodski","sequence":"additional","affiliation":[{"name":"Hebrew University and NTT Research, Jerusalem, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7440-5690","authenticated-orcid":false,"given":"Rafael","family":"Pass","sequence":"additional","affiliation":[{"name":"Cornell Tech, New York, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,10,27]]},"reference":[{"key":"e_1_3_3_2_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/978-3-319-56617-7_1","volume-title":"EUROCRYPT","author":"Alwen Jo\u00ebl","year":"2017","unstructured":"Jo\u00ebl Alwen, Jeremiah Blocki, and Krzysztof Pietrzak. 2017. Depth-robust graphs and their cumulative memory complexity. In EUROCRYPT(Lecture Notes in Computer Science, Vol. 10212). 3\u201332."},{"key":"e_1_3_3_3_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/978-3-319-78375-8_4","volume-title":"EUROCRYPT","author":"Alwen Jo\u00ebl","year":"2018","unstructured":"Jo\u00ebl Alwen, Jeremiah Blocki, and Krzysztof Pietrzak. 2018. Sustained space complexity. In EUROCRYPT(Lecture Notes in Computer Science, Vol. 10821). Springer, 99\u2013130."},{"key":"e_1_3_3_4_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"358","DOI":"10.1007\/978-3-662-49896-5_13","volume-title":"EUROCRYPT","author":"Alwen Jo\u00ebl","year":"2016","unstructured":"Jo\u00ebl Alwen, Binyi Chen, Chethan Kamath, Vladimir Kolmogorov, Krzysztof Pietrzak, and Stefano Tessaro. 2016. On the complexity of scrypt and proofs of space in the parallel random oracle model. In EUROCRYPT(Lecture Notes in Computer Science, Vol. 9666). Springer, 358\u2013387."},{"key":"e_1_3_3_5_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/978-3-319-56617-7_2","volume-title":"EUROCRYPT","author":"Alwen Jo\u00ebl","year":"2017","unstructured":"Jo\u00ebl Alwen, Binyi Chen, Krzysztof Pietrzak, Leonid Reyzin, and Stefano Tessaro. 2017. Scrypt is maximally memory-hard. In EUROCRYPT(Lecture Notes in Computer Science, Vol. 10212). 33\u201362."},{"key":"e_1_3_3_6_2","doi-asserted-by":"crossref","first-page":"595","DOI":"10.1145\/2746539.2746622","volume-title":"STOC","author":"Alwen Jo\u00ebl","year":"2015","unstructured":"Jo\u00ebl Alwen and Vladimir Serbinenko. 2015. High parallel complexity graphs and memory-hard functions. In STOC. ACM, 595\u2013603."},{"key":"e_1_3_3_7_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1007\/978-3-319-70500-2_17","volume-title":"TCC","author":"Alwen Jo\u00ebl","year":"2017","unstructured":"Jo\u00ebl Alwen and Bj\u00f6rn Tackmann. 2017. Moderately hard functions: Definition, instantiations, and applications. In TCC(Lecture Notes in Computer Science, Vol. 10677). Springer, 493\u2013526."},{"key":"e_1_3_3_8_2","first-page":"106","volume-title":"FOCS","author":"Barak Boaz","year":"2001","unstructured":"Boaz Barak. 2001. How to go beyond the black-box simulation barrier. In FOCS. IEEE Computer Society, 106\u2013115."},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/070709244"},{"key":"e_1_3_3_10_2","series-title":"Lecture Notes in Computer Science","first-page":"390","volume-title":"CRYPTO","author":"Bellare Mihir","year":"1992","unstructured":"Mihir Bellare and Oded Goldreich. 1992. On defining proofs of knowledge. In CRYPTO(Lecture Notes in Computer Science, Vol. 740). Springer, 390\u2013420."},{"key":"e_1_3_3_11_2","series-title":"LIPIcs","first-page":"40:1\u201340:15","volume-title":"ICALP","author":"Ben-Sasson Eli","year":"2017","unstructured":"Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Michael Riabzev, and Nicholas Spooner. 2017. Interactive oracle proofs with constant rate and query complexity. In ICALP(LIPIcs, Vol. 80). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 40:1\u201340:15."},{"key":"e_1_3_3_12_2","first-page":"585","volume-title":"STOC","author":"Ben-Sasson Eli","year":"2013","unstructured":"Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, and Eran Tromer. 2013. On the concrete efficiency of probabilistically-checkable proofs. In STOC. ACM, 585\u2013594."},{"key":"e_1_3_3_13_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1007\/978-3-642-40084-1_6","volume-title":"CRYPTO","author":"Ben-Sasson Eli","year":"2013","unstructured":"Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer, and Madars Virza. 2013. SNARKs for C: Verifying program executions succinctly and in zero knowledge. In CRYPTO(Lecture Notes in Computer Science, Vol. 8043). Springer, 90\u2013108."},{"key":"e_1_3_3_14_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1007\/978-3-662-53644-5_2","volume-title":"TCC","author":"Ben-Sasson Eli","year":"2016","unstructured":"Eli Ben-Sasson, Alessandro Chiesa, and Nicholas Spooner. 2016. Interactive oracle proofs. In TCC(Lecture Notes in Computer Science, Vol. 9986). 31\u201360."},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1137\/050646445"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-016-9241-9"},{"key":"e_1_3_3_17_2","first-page":"111","volume-title":"STOC","author":"Bitansky Nir","year":"2013","unstructured":"Nir Bitansky, Ran Canetti, Alessandro Chiesa, and Eran Tromer. 2013. Recursive composition and bootstrapping for SNARKS and proof-carrying data. In STOC. ACM, 111\u2013120."},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1137\/140975048"},{"key":"e_1_3_3_19_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1007\/978-3-642-32009-5_16","volume-title":"CRYPTO","author":"Bitansky Nir","year":"2012","unstructured":"Nir Bitansky and Alessandro Chiesa. 2012. Succinct arguments from multi-prover interactive proofs and their efficiency benefits. In CRYPTO(Lecture Notes in Computer Science, Vol. 7417). Springer, 255\u2013272."},{"key":"e_1_3_3_20_2","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1145\/2840728.2840745","volume-title":"ITCS","author":"Bitansky Nir","year":"2016","unstructured":"Nir Bitansky, Shafi Goldwasser, Abhishek Jain, Omer Paneth, Vinod Vaikuntanathan, and Brent Waters. 2016. Time-lock puzzles from randomized encodings. In ITCS. ACM, 345\u2013356."},{"key":"e_1_3_3_21_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"757","DOI":"10.1007\/978-3-319-96884-1_25","volume-title":"CRYPTO","author":"Boneh Dan","year":"2018","unstructured":"Dan Boneh, Joseph Bonneau, Benedikt B\u00fcnz, and Ben Fisch. 2018. Verifiable delay functions. In CRYPTO(Lecture Notes in Computer Science, Vol. 10991). Springer, 757\u2013788."},{"key":"e_1_3_3_22_2","first-page":"712","article-title":"A survey of two verifiable delay functions","volume":"2018","author":"Boneh Dan","year":"2018","unstructured":"Dan Boneh, Benedikt B\u00fcnz, and Ben Fisch. 2018. A survey of two verifiable delay functions. IACR Cryptol. ePrint Arch. 2018 (2018), 712.","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"e_1_3_3_23_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1007\/978-3-662-48800-3_10","volume-title":"ASIACRYPT","author":"Boyle Elette","year":"2015","unstructured":"Elette Boyle and Rafael Pass. 2015. Limits of extractability assumptions with distributional auxiliary input. In ASIACRYPT(Lecture Notes in Computer Science, Vol. 9453). Springer, 236\u2013261."},{"key":"e_1_3_3_24_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/978-3-642-36362-7_5","volume-title":"Public Key Cryptography","author":"Catalano Dario","year":"2013","unstructured":"Dario Catalano and Dario Fiore. 2013. Vector commitments and their applications. In Public Key Cryptography(Lecture Notes in Computer Science, Vol. 7778). Springer, 55\u201372."},{"key":"e_1_3_3_25_2","first-page":"50","volume-title":"FOCS","author":"Chung Kai-Min","year":"2013","unstructured":"Kai-Min Chung, Huijia Lin, and Rafael Pass. 2013. Constant-round concurrent zero knowledge from P-Certificates. In FOCS. IEEE Computer Society, 50\u201359."},{"key":"e_1_3_3_26_2","first-page":"253","volume-title":"S&P","author":"Costello Craig","year":"2015","unstructured":"Craig Costello, C\u00e9dric Fournet, Jon Howell, Markulf Kohlweiss, Benjamin Kreuter, Michael Naehrig, Bryan Parno, and Samee Zahur. 2015. Geppetto: Versatile verifiable computation. In S&P. IEEE Computer Society, 253\u2013270."},{"key":"e_1_3_3_27_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/978-3-030-26954-8_1","volume-title":"CRYPTO","author":"D\u00f6ttling Nico","year":"2019","unstructured":"Nico D\u00f6ttling, Sanjam Garg, Yuval Ishai, Giulio Malavolta, Tamer Mour, and Rafail Ostrovsky. 2019. Trapdoor hash functions and their applications. In CRYPTO(Lecture Notes in Computer Science, Vol. 11694). Springer, 3\u201332."},{"key":"e_1_3_3_28_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/978-3-030-57990-6_4","volume-title":"SCN","author":"D\u00f6ttling Nico","year":"2020","unstructured":"Nico D\u00f6ttling, Sanjam Garg, Giulio Malavolta, and Prashant Nalini Vasudevan. 2020. Tight verifiable delay functions. In SCN(Lecture Notes in Computer Science, Vol. 12238). Springer, 65\u201384."},{"key":"e_1_3_3_29_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/978-3-030-03807-6_2","volume-title":"TCC","author":"Dryja Thaddeus","year":"2018","unstructured":"Thaddeus Dryja, Quanquan C. Liu, and Sunoo Park. 2018. Static-memory-hard functions, and modeling the cost of space vs. time. In TCC(Lecture Notes in Computer Science, Vol. 11239). Springer, 33\u201366."},{"key":"e_1_3_3_30_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"426","DOI":"10.1007\/978-3-540-45146-4_25","volume-title":"CRYPTO","author":"Dwork Cynthia","year":"2003","unstructured":"Cynthia Dwork, Andrew V. Goldberg, and Moni Naor. 2003. On memory-bound functions for fighting spam. In CRYPTO(Lecture Notes in Computer Science, Vol. 2729). Springer, 426\u2013444."},{"key":"e_1_3_3_31_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/11535218_3","volume-title":"CRYPTO","author":"Dwork Cynthia","year":"2005","unstructured":"Cynthia Dwork, Moni Naor, and Hoeteck Wee. 2005. Pebbling and proofs of work. In CRYPTO(Lecture Notes in Computer Science, Vol. 3621). Springer, 37\u201354."},{"key":"e_1_3_3_32_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"585","DOI":"10.1007\/978-3-662-48000-7_29","volume-title":"CRYPTO","author":"Dziembowski Stefan","year":"2015","unstructured":"Stefan Dziembowski, Sebastian Faust, Vladimir Kolmogorov, and Krzysztof Pietrzak. 2015. Proofs of space. In CRYPTO(Lecture Notes in Computer Science, Vol. 9216). Springer, 585\u2013605."},{"key":"e_1_3_3_33_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/978-3-030-45727-3_5","volume-title":"EUROCRYPT","author":"Ephraim Naomi","year":"2020","unstructured":"Naomi Ephraim, Cody Freitag, Ilan Komargodski, and Rafael Pass. 2020. Continuous verifiable delay functions. In EUROCRYPT(Lecture Notes in Computer Science, Vol. 12107). Springer, 125\u2013154."},{"key":"e_1_3_3_34_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"707","DOI":"10.1007\/978-3-030-45721-1_25","volume-title":"EUROCRYPT","author":"Ephraim Naomi","year":"2020","unstructured":"Naomi Ephraim, Cody Freitag, Ilan Komargodski, and Rafael Pass. 2020. SPARKs: Succinct parallelizable arguments of knowledge. In EUROCRYPT(Lecture Notes in Computer Science, Vol. 12105). Springer, 707\u2013737."},{"key":"e_1_3_3_35_2","series-title":"Lecture Notes in Computer Science","first-page":"186","volume-title":"CRYPTO","author":"Fiat Amos","year":"1986","unstructured":"Amos Fiat and Adi Shamir. 1986. How to prove yourself: Practical solutions to identification and signature problems. In CRYPTO(Lecture Notes in Computer Science, Vol. 263). Springer, 186\u2013194."},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/2699436"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1137\/0218012"},{"key":"e_1_3_3_38_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1007\/978-3-540-78967-3_22","volume-title":"EUROCRYPT","author":"Groth Jens","year":"2008","unstructured":"Jens Groth and Yuval Ishai. 2008. Sub-linear zero-knowledge argument for correctness of a shuffle. In EUROCRYPT(Lecture Notes in Computer Science, Vol. 4965). Springer, 379\u2013396."},{"key":"e_1_3_3_39_2","first-page":"124","volume-title":"FOCS","author":"Holmgren Justin","year":"2018","unstructured":"Justin Holmgren and Ron Rothblum. 2018. Delegating computations with (almost) minimal time and space overhead. In FOCS. IEEE Computer Society, 124\u2013135."},{"key":"e_1_3_3_40_2","first-page":"91","volume-title":"TCC","author":"Kalai Yael Tauman","year":"2016","unstructured":"Yael Tauman Kalai and Omer Paneth. 2016. Delegating RAM computations. In TCC. 91\u2013118."},{"key":"e_1_3_3_41_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"536","DOI":"10.1007\/978-3-540-70583-3_44","volume-title":"ICALP","author":"Kalai Yael Tauman","year":"2008","unstructured":"Yael Tauman Kalai and Ran Raz. 2008. Interactive PCP. In ICALP(Lecture Notes in Computer Science, Vol. 5126). Springer, 536\u2013547."},{"key":"e_1_3_3_42_2","first-page":"723","volume-title":"STOC","author":"Kilian Joe","year":"1992","unstructured":"Joe Kilian. 1992. A note on efficient zero-knowledge proofs and arguments (extended abstract). In STOC. ACM, 723\u2013732."},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-002-0143-7"},{"key":"e_1_3_3_44_2","series-title":"Lecture Notes in Computer Science","first-page":"218","volume-title":"CRYPTO","author":"Merkle Ralph C.","year":"1989","unstructured":"Ralph C. Merkle. 1989. A certified digital signature. In CRYPTO(Lecture Notes in Computer Science, Vol. 435). Springer, 218\u2013238."},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795284959"},{"key":"e_1_3_3_46_2","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1145\/1132516.1132561","volume-title":"STOC","author":"Micali Silvio","year":"2006","unstructured":"Silvio Micali and Rafael Pass. 2006. Local zero knowledge. In STOC. ACM, 306\u2013315."},{"key":"e_1_3_3_47_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/3-540-44647-8_3","volume-title":"CRYPTO","author":"Naor Dalit","year":"2001","unstructured":"Dalit Naor, Moni Naor, and Jeffery Lotspiech. 2001. Revocation and tracing schemes for stateless receivers. In CRYPTO(Lecture Notes in Computer Science, Vol. 2139). Springer, 41\u201362."},{"key":"e_1_3_3_48_2","unstructured":"Omer Paneth. 2019. Alternative VDF Constructions. Retrieved from: https:\/\/dci.mit.edu\/video-gallery\/2019\/5\/29\/alternate-vdf-constructions-by-omer-paneth-of-mit-vdf-day-2019."},{"key":"e_1_3_3_49_2","first-page":"238","volume-title":"IEEE Symposium on Security and Privacy","author":"Parno Bryan","year":"2013","unstructured":"Bryan Parno, Jon Howell, Craig Gentry, and Mariana Raykova. 2013. Pinocchio: Nearly practical verifiable computation. In IEEE Symposium on Security and Privacy. IEEE Computer Society, 238\u2013252."},{"key":"e_1_3_3_50_2","doi-asserted-by":"publisher","DOI":"10.1137\/060661880"},{"key":"e_1_3_3_51_2","volume-title":"BSDCan","author":"Percival Colin","year":"2009","unstructured":"Colin Percival. 2009. Stronger key derivation via sequential memory-hard functions. In BSDCan."},{"key":"e_1_3_3_52_2","series-title":"LIPIcs","first-page":"60:1\u201360:15","volume-title":"ITCS","author":"Pietrzak Krzysztof","year":"2019","unstructured":"Krzysztof Pietrzak. 2019. Simple verifiable delay functions. In ITCS(LIPIcs, Vol. 124). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 60:1\u201360:15."},{"key":"e_1_3_3_53_2","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1145\/2897518.2897652","volume-title":"STOC","author":"Reingold Omer","year":"2016","unstructured":"Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum. 2016. Constant-round interactive proofs for delegating computation. In STOC. ACM, 49\u201362."},{"key":"e_1_3_3_54_2","unstructured":"Ronald L. Rivest Adi Shamir and David A. Wagner. 1996. Time-lock Puzzles and Timed-release Crypto. Manuscript.https:\/\/people.csail.mit.edu\/rivest\/pubs\/RSW96.pdf."},{"key":"e_1_3_3_55_2","first-page":"846","volume-title":"FOCS","author":"Ron-Zewi Noga","year":"2020","unstructured":"Noga Ron-Zewi and Ron D. Rothblum. 2020. Local proofs approaching the witness length [extended abstract]. In FOCS. IEEE, 846\u2013857."},{"key":"e_1_3_3_56_2","series-title":"Lecture Notes in Computer Science","first-page":"1","volume-title":"TCC","author":"Valiant Paul","year":"2008","unstructured":"Paul Valiant. 2008. Incrementally verifiable computation or proofs of knowledge imply time\/space efficiency. In TCC(Lecture Notes in Computer Science, Vol. 4948). Springer, 1\u201318."},{"key":"e_1_3_3_57_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1007\/978-3-030-17659-4_13","volume-title":"EUROCRYPT","author":"Wesolowski Benjamin","year":"2019","unstructured":"Benjamin Wesolowski. 2019. Efficient verifiable delay functions. In EUROCRYPT(Lecture Notes in Computer Science, Vol. 11478). Springer, 379\u2013407."},{"key":"e_1_3_3_58_2","first-page":"675","volume-title":"USENIX Security Symposium","author":"Wu Howard","year":"2018","unstructured":"Howard Wu, Wenting Zheng, Alessandro Chiesa, Raluca Ada Popa, and Ion Stoica. 2018. DIZK: A distributed zero knowledge proof system. In USENIX Security Symposium. USENIX Association, 675\u2013692."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3549523","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3549523","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3549523","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:00:11Z","timestamp":1750186811000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3549523"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,27]]},"references-count":57,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,10,31]]}},"alternative-id":["10.1145\/3549523"],"URL":"https:\/\/doi.org\/10.1145\/3549523","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2022,10,27]]},"assertion":[{"value":"2020-06-15","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-05-25","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-10-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}