{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:57:19Z","timestamp":1781078239811,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":58,"publisher":"ACM","license":[{"start":{"date-parts":[[2016,6,19]],"date-time":"2016-06-19T00:00:00Z","timestamp":1466294400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2016,6,19]]},"DOI":"10.1145\/2897518.2897652","type":"proceedings-article","created":{"date-parts":[[2016,6,10]],"date-time":"2016-06-10T13:04:07Z","timestamp":1465563847000},"page":"49-62","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":113,"title":["Constant-round interactive proofs for delegating computation"],"prefix":"10.1145","author":[{"given":"Omer","family":"Reingold","sequence":"first","affiliation":[{"name":"Samsung Research, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Guy N.","family":"Rothblum","sequence":"additional","affiliation":[{"name":"Samsung Research, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ron D.","family":"Rothblum","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2016,6,19]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/1880918.1880936"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090263"},{"key":"e_1_3_2_1_3_1","volume-title":"Recursive composition and bootstrapping for snarks and proof-carrying data. IACR Cryptology ePrint Archive","author":"Bitansky Nir","year":"2012","unstructured":"{BCCT12b} Nir Bitansky , Ran Canetti , Alessandro Chiesa , and Eran Tromer . Recursive composition and bootstrapping for snarks and proof-carrying data. IACR Cryptology ePrint Archive , 2012 :95, 2012. {BCCT12b} Nir Bitansky, Ran Canetti, Alessandro Chiesa, and Eran Tromer. Recursive composition and bootstrapping for snarks and proof-carrying data. IACR Cryptology ePrint Archive, 2012:95, 2012."},{"key":"e_1_3_2_1_5_1","first-page":"333","volume-title":"TCC","author":"Nir Bitansky BCI","year":"2013","unstructured":"{ BCI + 13} Nir Bitansky , Alessandro Chiesa , Yuval Ishai , Rafail Ostrovsky , and Omer Paneth . Succinct non-interactive arguments via linear interactive proofs . In TCC , pages 315\u2013 333 , 2013 . {BCI + 13} Nir Bitansky, Alessandro Chiesa, Yuval Ishai, Rafail Ostrovsky, and Omer Paneth. Succinct non-interactive arguments via linear interactive proofs. In TCC, pages 315\u2013333, 2013."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103428"},{"key":"e_1_3_2_1_7_1","first-page":"56","volume-title":"8th Annual International Cryptology Conference","author":"Michael Ben-Or BGG","year":"1988","unstructured":"{ BGG + 88} Michael Ben-Or , Oded Goldreich , Shafi Goldwasser , Johan H\u02da astad, Joe Kilian , Silvio Micali , and Phillip Rogaway . Everything provable is provable in zero-knowledge. In Advances in Cryptology - CRYPTO \u201988 , 8th Annual International Cryptology Conference , Santa Barbara, California, USA , August 21-25, 1988 , Proceedings, pages 37\u2013 56 , 1988. {BGG + 88} Michael Ben-Or, Oded Goldreich, Shafi Goldwasser, Johan H\u02da astad, Joe Kilian, Silvio Micali, and Phillip Rogaway. Everything provable is provable in zero-knowledge. In Advances in Cryptology - CRYPTO \u201988, 8th Annual International Cryptology Conference, Santa Barbara, California, USA, August 21-25, 1988, Proceedings, pages 37\u201356, 1988."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746574"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90028-1"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258635"},{"key":"e_1_3_2_1_12_1","first-page":"1995","article-title":"Probabilistically checkable debate systems and nonapproximability of pspace-hard functions","author":"Condon Anne","year":"1995","unstructured":"{CFLS95} Anne Condon , Joan Feigenbaum , Carsten Lund , and Peter W. Shor . Probabilistically checkable debate systems and nonapproximability of pspace-hard functions . Chicago J. Theor. Comput. Sci. , 1995 , 1995 . {CFLS95} Anne Condon, Joan Feigenbaum, Carsten Lund, and Peter W. Shor. Probabilistically checkable debate systems and nonapproximability of pspace-hard functions. Chicago J. Theor. Comput. Sci., 1995, 1995.","journal-title":"Chicago J. Theor. Comput. Sci."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746621"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14623-7_26"},{"key":"e_1_3_2_1_15_1","first-page":"74","volume-title":"TCC","author":"Ivan Damg\u02da","year":"2012","unstructured":"{DFH12} Ivan Damg\u02da ard, Sebastian Faust , and Carmit Hazay . Secure two-party computation with low communication . In TCC , pages 54\u2013 74 , 2012 . {DFH12} Ivan Damg\u02da ard, Sebastian Faust, and Carmit Hazay. Secure two-party computation with low communication. In TCC, pages 54\u201374, 2012."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236457.1236459"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705446962"},{"key":"e_1_3_2_1_18_1","first-page":"529","volume-title":"APPROX 2011, and 15th International Workshop, RANDOM 2011, Princeton, NJ, USA, August 17-19, 2011. Proceedings","author":"Drucker Andrew","year":"2011","unstructured":"{Dru11} Andrew Drucker . Efficient probabilistically checkable debates. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 14th International Workshop , APPROX 2011, and 15th International Workshop, RANDOM 2011, Princeton, NJ, USA, August 17-19, 2011. Proceedings , pages 519\u2013 529 , 2011 . {Dru11} Andrew Drucker. Efficient probabilistically checkable debates. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 14th International Workshop, APPROX 2011, and 15th International Workshop, RANDOM 2011, Princeton, NJ, USA, August 17-19, 2011. Proceedings, pages 519\u2013529, 2011."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/130927115"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2003.09.005"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258644"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/1881412.1881445"},{"key":"e_1_3_2_1_23_1","volume-title":"Quadratic span programs and succinct NIZKs without PCPs. IACR Cryptology ePrint Archive","author":"Gennaro Rosario","year":"2012","unstructured":"{GGPR12} Rosario Gennaro , Craig Gentry , Bryan Parno , and Mariana Raykova . Quadratic span programs and succinct NIZKs without PCPs. IACR Cryptology ePrint Archive , 2012 :215, 2012. {GGPR12} Rosario Gennaro, Craig Gentry, Bryan Parno, and Mariana Raykova. Quadratic span programs and succinct NIZKs without PCPs. IACR Cryptology ePrint Archive, 2012:215, 2012."},{"key":"e_1_3_2_1_24_1","first-page":"677","volume-title":"42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I","author":"Goldreich Oded","year":"2015","unstructured":"{GGR15} Oded Goldreich , Tom Gur , and Ron D. Rothblum . Proofs of proximity for context-free languages and read-once branching programs - (extended abstract). In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I , pages 666\u2013 677 , 2015 . {GGR15} Oded Goldreich, Tom Gur, and Ron D. Rothblum. Proofs of proximity for context-free languages and read-once branching programs - (extended abstract). In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, pages 666\u2013677, 2015."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(98)00116-1"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374396"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2699436"},{"key":"e_1_3_2_1_28_1","volume-title":"Delegation of computation without rejection problem from designated verifier cs-proofs. IACR Cryptology ePrint Archive","author":"Goldwasser Shafi","year":"2011","unstructured":"{GLR11} Shafi Goldwasser , Huijia Lin , and Aviad Rubinstein . Delegation of computation without rejection problem from designated verifier cs-proofs. IACR Cryptology ePrint Archive , 2011 :456, 2011. {GLR11} Shafi Goldwasser, Huijia Lin, and Aviad Rubinstein. Delegation of computation without rejection problem from designated verifier cs-proofs. IACR Cryptology ePrint Archive, 2011:456, 2011."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218012"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804106"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"crossref","unstructured":"{Gol11} Oded Goldreich. Bravely moderately: A common theme in four recent works. In Oded Goldreich editor Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation - In Collaboration with Lidor Avigad Mihir Bellare Zvika Brakerski Shafi Goldwasser Shai Halevi Tali Kaufman Leonid Levin Noam Nisan Dana Ron Madhu Sudan Luca Trevisan Salil Vadhan Avi Wigderson David Zuckerman volume 6650 of Lecture Notes in Computer Science pages 373\u2013389. Springer 2011.   {Gol11} Oded Goldreich. Bravely moderately: A common theme in four recent works. In Oded Goldreich editor Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation - In Collaboration with Lidor Avigad Mihir Bellare Zvika Brakerski Shafi Goldwasser Shai Halevi Tali Kaufman Leonid Levin Noam Nisan Dana Ron Madhu Sudan Luca Trevisan Salil Vadhan Avi Wigderson David Zuckerman volume 6650 of Lecture Notes in Computer Science pages 373\u2013389. Springer 2011.","DOI":"10.1007\/978-3-642-22670-0_26"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2688073.2688079"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17373-8_19"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1162349.1162351"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-002-0169-0"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993651"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793244708"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/060668092"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250794"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129782"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746614"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70583-3_44"},{"key":"e_1_3_2_1_43_1","volume-title":"Constant-round interactive proofs for nc 1. Unpublished observation","author":"Kalai Yael","year":"2009","unstructured":"{KR09} Yael Kalai and Guy N. Rothblum . Constant-round interactive proofs for nc 1. Unpublished observation , 2009 . {KR09} Yael Kalai and Guy N. Rothblum. Constant-round interactive proofs for nc 1. Unpublished observation, 2009."},{"key":"e_1_3_2_1_44_1","volume-title":"USA","author":"Kalai Yael Tauman","year":"2015","unstructured":"{KR15} Yael Tauman Kalai and Ron D. Rothblum . Arguments of proximity - {extended abstract}. In Advances in Cryptology - CRYPTO 2015 - 35th Annual Cryptology Conference, Santa Barbara, CA , USA , August 16-20, 2015 , Proceedings, Part II, pages 422\u2013442 , 2015. {KR15} Yael Tauman Kalai and Ron D. Rothblum. Arguments of proximity - {extended abstract}. In Advances in Cryptology - CRYPTO 2015 - 35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2015, Proceedings, Part II, pages 422\u2013442, 2015."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488679"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591809"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146605"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28914-9_10"},{"key":"e_1_3_2_1_49_1","first-page":"453","volume-title":"FOCS","author":"Micali Silvio","year":"1994","unstructured":"{Mic94} Silvio Micali . CS proofs (extended abstracts) . In FOCS , pages 436\u2013 453 , 1994 . {Mic94} Silvio Micali. CS proofs (extended abstracts). In FOCS, pages 436\u2013453, 1994."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00196774"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305237"},{"key":"e_1_3_2_1_52_1","volume-title":"Publicly verifiable non-interactive arguments for delegating computation. IACR Cryptology ePrint Archive","author":"Paneth Omer","year":"2014","unstructured":"{PR14} Omer Paneth and Guy N. Rothblum . Publicly verifiable non-interactive arguments for delegating computation. IACR Cryptology ePrint Archive , 2014 :981, 2014. {PR14} Omer Paneth and Guy N. Rothblum. Publicly verifiable non-interactive arguments for delegating computation. IACR Cryptology ePrint Archive, 2014:981, 2014."},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28914-9_24"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195132"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391289.1391291"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796583"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488709"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146609"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.5555\/22101.22108"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/2641562"}],"event":{"name":"STOC '16: Symposium on Theory of Computing","location":"Cambridge MA USA","acronym":"STOC '16","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the forty-eighth annual ACM symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2897518.2897652","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2897518.2897652","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:55:58Z","timestamp":1750222558000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2897518.2897652"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,19]]},"references-count":58,"alternative-id":["10.1145\/2897518.2897652","10.1145\/2897518"],"URL":"https:\/\/doi.org\/10.1145\/2897518.2897652","relation":{},"subject":[],"published":{"date-parts":[[2016,6,19]]},"assertion":[{"value":"2016-06-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}