{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,8]],"date-time":"2026-06-08T16:04:40Z","timestamp":1780934680854,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":44,"publisher":"ACM","license":[{"start":{"date-parts":[[2013,6,1]],"date-time":"2013-06-01T00:00:00Z","timestamp":1370044800000},"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":[[2013,6]]},"DOI":"10.1145\/2488608.2488681","type":"proceedings-article","created":{"date-parts":[[2013,5,28]],"date-time":"2013-05-28T16:35:41Z","timestamp":1369758941000},"page":"585-594","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":50,"title":["On the concrete efficiency of probabilistically-checkable proofs"],"prefix":"10.1145","author":[{"given":"Eli","family":"Ben-Sasson","sequence":"first","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alessandro","family":"Chiesa","sequence":"additional","affiliation":[{"name":"MIT, Cambridge, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel","family":"Genkin","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eran","family":"Tromer","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2013,6]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"ICALP '10","author":"Applebaum B.","unstructured":"B. Applebaum , Y. Ishai , and E. Kushilevitz . From secrecy to soundness: Efficient verification via secure computation . ICALP '10 . B. Applebaum, Y. Ishai, and E. Kushilevitz. From secrecy to soundness: Efficient verification via secure computation. ICALP '10."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103428"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/070709244"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422481"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007361"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2005.27"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704445445"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/050646445"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780631"},{"key":"e_1_3_2_1_12_1","volume-title":"Algebraic Coding Theory","author":"Berlekamp E. R.","year":"1968","unstructured":"E. R. Berlekamp . Algebraic Coding Theory . 1968 . E. R. Berlekamp. Algebraic Coding Theory. 1968."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090263"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488623"},{"key":"e_1_3_2_1_15_1","volume-title":"CRYPTO '12","author":"Bitansky N.","unstructured":"N. Bitansky and A. Chiesa . Succinct arguments from multi-prover interactive proofs and their efficiency benefits . CRYPTO '12 . N. Bitansky and A. Chiesa. Succinct arguments from multi-prover interactive proofs and their efficiency benefits. CRYPTO '12."},{"key":"e_1_3_2_1_16_1","volume-title":"ITCS '12","author":"Boneh D.","unstructured":"D. Boneh , G. Segev , and B. Waters . Targeted malleability . ITCS '12 . D. Boneh, G. Segev, and B. Waters. Targeted malleability. ITCS '12."},{"key":"e_1_3_2_1_17_1","volume-title":"ICS '10","author":"Chiesa A.","unstructured":"A. Chiesa and E. Tromer . Proof-carrying data and hearsay arguments from signature cards . ICS '10 . A. Chiesa and E. Tromer. Proof-carrying data and hearsay arguments from signature cards. ICS '10."},{"key":"e_1_3_2_1_18_1","volume-title":"Proof-carrying data: Secure computation on untrusted platforms. The Next Wave: The NSA's review of emerging technologies","author":"Chiesa A.","year":"2012","unstructured":"A. Chiesa and E. Tromer . Proof-carrying data: Secure computation on untrusted platforms. The Next Wave: The NSA's review of emerging technologies , 2012 . A. Chiesa and E. Tromer. Proof-carrying data: Secure computation on untrusted platforms. The Next Wave: The NSA's review of emerging technologies, 2012."},{"key":"e_1_3_2_1_19_1","volume-title":"CRYPTO '10","author":"Chung K.-M.","unstructured":"K.-M. Chung , Y. Kalai , and S. Vadhan . Improved delegation of computation using fully homomorphic encryption . CRYPTO '10 . K.-M. Chung, Y. Kalai, and S. Vadhan. Improved delegation of computation using fully homomorphic encryption. CRYPTO '10."},{"key":"e_1_3_2_1_20_1","volume-title":"TCC '12","author":"Damg\u00e5rd I.","unstructured":"I. Damg\u00e5rd , S. Faust , and C. Hazay . Secure two-party computation with low communication . TCC '12 . I. Damg\u00e5rd, S. Faust, and C. Hazay. Secure two-party computation with low communication. TCC '12."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69407-6_21"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236457.1236459"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/226643.226652"},{"key":"e_1_3_2_1_24_1","volume-title":"CRYPTO '10","author":"Gennaro R.","unstructured":"R. Gennaro , C. Gentry , and B. Parno . Non-interactive verifiable computing: outsourcing computation to untrusted workers . CRYPTO '10 . R. Gennaro, C. Gentry, and B. Parno. Non-interactive verifiable computing: outsourcing computation to untrusted workers. CRYPTO '10."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1162349.1162351"},{"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","volume-title":"Delegation of computation without rejection problem from designated verifier CS-proofs. ePrint","author":"Goldwasser S.","year":"2011","unstructured":"S. Goldwasser , H. Lin , and A. Rubinstein . Delegation of computation without rejection problem from designated verifier CS-proofs. ePrint , 2011 . S. Goldwasser, H. Lin, and A. Rubinstein. Delegation of computation without rejection problem from designated verifier CS-proofs. ePrint, 2011."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00001606"},{"key":"e_1_3_2_1_29_1","volume-title":"Handbook of Coding Theory","author":"Huffman W. C.","year":"1998","unstructured":"W. C. Huffman and R. A. Brualdi . Handbook of Coding Theory . Elsevier Science Inc ., New York, NY, USA, 1998 . W. C. Huffman and R. A. Brualdi. Handbook of Coding Theory. Elsevier Science Inc., New York, NY, USA, 1998."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2007.10"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129782"},{"key":"e_1_3_2_1_32_1","volume-title":"Finite Fields","author":"Lidl R.","year":"1997","unstructured":"R. Lidl and H. Niederreiter . Finite Fields . Cambridge University Press , 2 nd edition, 1997 . R. Lidl and H. Niederreiter. Finite Fields. Cambridge University Press, 2nd edition, 1997.","edition":"2"},{"key":"e_1_3_2_1_33_1","unstructured":"R. J. Lipton. Galactic algorithms. http:\/\/rjlipton.wordpress.com\/2010\/10\/23\/galactic-algorithms\/ 2010.  R. J. Lipton. Galactic algorithms. http:\/\/rjlipton.wordpress.com\/2010\/10\/23\/galactic-algorithms\/ 2010."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.10"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2012.14"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795284959"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1515\/JMC.2008.016"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10472-009-9169-y"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1754399.1754402"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195132"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258641"},{"key":"e_1_3_2_1_43_1","volume-title":"Security '12","author":"Setty S.","unstructured":"S. Setty , V. Vu , N. Panpalia , B. Braun , A. J. Blumberg , and M. Walfish . Taking proof-based verified computation a few steps closer to practicality . Security '12 . S. Setty, V. Vu, N. Panpalia, B. Braun, A. J. Blumberg, and M. Walfish. Taking proof-based verified computation a few steps closer to practicality. Security '12."},{"key":"e_1_3_2_1_44_1","volume-title":"MIT","author":"Spielman D.","year":"1995","unstructured":"D. Spielman . Computationally Efficient Error-Correcting Codes and Holographic Proofs. PhD thesis , MIT , Mathamatics Department , May 1995 . D. Spielman. Computationally Efficient Error-Correcting Codes and Holographic Proofs. PhD thesis, MIT, Mathamatics Department, May 1995."},{"key":"e_1_3_2_1_45_1","volume-title":"TCC '08","author":"Valiant P.","unstructured":"P. Valiant . Incrementally verifiable computation or proofs of knowledge imply time\/space efficiency . TCC '08 . P. Valiant. Incrementally verifiable computation or proofs of knowledge imply time\/space efficiency. TCC '08."}],"event":{"name":"STOC'13: Symposium on Theory of Computing","location":"Palo Alto California USA","acronym":"STOC'13","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the forty-fifth annual ACM symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2488608.2488681","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2488608.2488681","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:39:20Z","timestamp":1750235960000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2488608.2488681"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,6]]},"references-count":44,"alternative-id":["10.1145\/2488608.2488681","10.1145\/2488608"],"URL":"https:\/\/doi.org\/10.1145\/2488608.2488681","relation":{},"subject":[],"published":{"date-parts":[[2013,6]]},"assertion":[{"value":"2013-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}