{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,24]],"date-time":"2026-04-24T10:03:30Z","timestamp":1777025010968,"version":"3.51.4"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319687100","type":"print"},{"value":"9783319687117","type":"electronic"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-68711-7_4","type":"book-chapter","created":{"date-parts":[[2017,10,4]],"date-time":"2017-10-04T08:23:40Z","timestamp":1507105420000},"page":"53-73","source":"Crossref","is-referenced-by-count":9,"title":["Efficient Rational Proofs for Space Bounded Computations"],"prefix":"10.1007","author":[{"given":"Matteo","family":"Campanelli","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rosario","family":"Gennaro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,10,4]]},"reference":[{"issue":"11","key":"4_CR1","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1145\/581571.581573","volume":"45","author":"DP Anderson","year":"2002","unstructured":"Anderson, D.P., Cobb, J., Korpela, E., Lebofsky, M., Werthimer, D.: SETI@ home: an experiment in public-resource computing. Commun. ACM 45(11), 56\u201361 (2002)","journal-title":"Commun. ACM"},{"issue":"2","key":"4_CR2","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/s00145-009-9040-7","volume":"23","author":"Y Aumann","year":"2010","unstructured":"Aumann, Y., Lindell, Y.: Security against covert adversaries: efficient protocols for realistic adversaries. J. Cryptology 23(2), 281\u2013343 (2010)","journal-title":"J. Cryptology"},{"key":"4_CR3","doi-asserted-by":"crossref","unstructured":"Azar, P.D., Micali, S.: Rational proofs. In: Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing, pp. 1017\u20131028. ACM (2012)","DOI":"10.1145\/2213977.2214069"},{"key":"4_CR4","doi-asserted-by":"crossref","unstructured":"Azar, P.D., Micali, S.: Super-efficient rational proofs. In: Proceedings of the Fourteenth ACM Conference on Electronic Commerce, pp. 29\u201330. ACM (2013)","DOI":"10.1145\/2492002.2482561"},{"key":"4_CR5","doi-asserted-by":"crossref","unstructured":"Babai, L.: Trading group theory for randomness. In: Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, pp. 421\u2013429. ACM (1985)","DOI":"10.1145\/22145.22192"},{"key":"4_CR6","doi-asserted-by":"crossref","unstructured":"Belenkiy, M., Chase, M., Christopher Erway, C., Jannotti, J., K\u00fcp\u00e7\u00fc, A., Lysyanskaya, A.: Incentivizing outsourced computation. In: Proceedings of the ACM SIGCOMM 2008 Workshop on Economics of Networked Systems, NetEcon 2008, Seattle, WA, USA, 22 August 2008, pp. 85\u201390 (2008)","DOI":"10.1145\/1403027.1403046"},{"issue":"6","key":"4_CR7","doi-asserted-by":"crossref","first-page":"1084","DOI":"10.1137\/0220068","volume":"20","author":"M Blum","year":"1991","unstructured":"Blum, M., De Santis, A., Micali, S., Persiano, G.: Noninteractive zero-knowledge. SIAM J. Comput. 20(6), 1084\u20131118 (1991)","journal-title":"SIAM J. Comput."},{"key":"4_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1007\/978-3-319-25594-1_15","volume-title":"Decision and Game Theory for Security","author":"M Campanelli","year":"2015","unstructured":"Campanelli, M., Gennaro, R.: Sequentially composable rational proofs. In: Khouzani, M.H.R., Panaousis, E., Theodorakopoulos, G. (eds.) GameSec 2015. LNCS, vol. 9406, pp. 270\u2013288. Springer, Cham (2015). doi: 10.1007\/978-3-319-25594-1_15"},{"key":"4_CR9","doi-asserted-by":"crossref","unstructured":"Chen, J., McCauley, S., Singh, S.: Rational proofs with multiple provers. In: Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, pp. 237\u2013248. ACM (2016)","DOI":"10.1145\/2840728.2840744"},{"issue":"2","key":"4_CR10","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1016\/S0890-5401(02)00013-5","volume":"180","author":"S Agostino De","year":"2003","unstructured":"De Agostino, S., Silvestri, R.: Bounded size dictionary compression: SC $$_k$$ -completeness and NC algorithms. Inf. Comput. 180(2), 101\u2013112 (2003)","journal-title":"Inf. Comput."},{"issue":"6","key":"4_CR11","doi-asserted-by":"crossref","first-page":"851","DOI":"10.1145\/1039488.1039489","volume":"51","author":"C Dwork","year":"2004","unstructured":"Dwork, C., Naor, M., Sahai, A.: Concurrent zero-knowledge. J. ACM 51(6), 851\u2013898 (2004)","journal-title":"J. ACM"},{"key":"4_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1007\/978-3-642-14623-7_25","volume-title":"Advances in Cryptology \u2013 CRYPTO 2010","author":"R Gennaro","year":"2010","unstructured":"Gennaro, R., Gentry, C., Parno, B.: Non-interactive verifiable computing: outsourcing computation to untrusted workers. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 465\u2013482. Springer, Heidelberg (2010). doi: 10.1007\/978-3-642-14623-7_25"},{"key":"4_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"626","DOI":"10.1007\/978-3-642-38348-9_37","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2013","author":"R Gennaro","year":"2013","unstructured":"Gennaro, R., Gentry, C., Parno, B., Raykova, M.: Quadratic span programs and succinct NIZKs without PCPs. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 626\u2013645. Springer, Heidelberg (2013). doi: 10.1007\/978-3-642-38348-9_37"},{"issue":"1","key":"4_CR14","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1137\/0218012","volume":"18","author":"S Goldwasser","year":"1989","unstructured":"Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM J. Comput. 18(1), 186\u2013208 (1989)","journal-title":"SIAM J. Comput."},{"key":"4_CR15","doi-asserted-by":"crossref","unstructured":"Guo, S., Hub\u00e1\u010dek, P., Rosen, A., Vald, M.: Rational arguments: single round delegation with sublinear verification. In: Proceedings of the 5th Conference on Innovations in Theoretical Computer Science, pp. 523\u2013540. ACM (2014)","DOI":"10.1145\/2554797.2554845"},{"key":"4_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/978-3-662-49099-0_12","volume-title":"Theory of Cryptography","author":"S Guo","year":"2016","unstructured":"Guo, S., Hub\u00e1\u010dek, P., Rosen, A., Vald, M.: Rational sumchecks. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016. LNCS, vol. 9563, pp. 319\u2013351. Springer, Heidelberg (2016). doi: 10.1007\/978-3-662-49099-0_12"},{"key":"4_CR17","unstructured":"Halpern, J.Y., Pass, R.: I don\u2019t want to think about it now: Decision theory with costly computation. arXiv preprint arXiv:1106.2657 (2011)"},{"issue":"3","key":"4_CR18","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1145\/1159892.1159901","volume":"2","author":"DS Johnson","year":"2006","unstructured":"Johnson, D.S.: The np-completeness column: the many limits on approximation. ACM Trans. Algorithms (TALG) 2(3), 473\u2013489 (2006)","journal-title":"ACM Trans. Algorithms (TALG)"},{"key":"4_CR19","doi-asserted-by":"crossref","unstructured":"Kalai, Y.T., Raz, R., Rothblum, R.D.: How to delegate computations: the power of no-signaling proofs. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pp. 485\u2013494. ACM (2014)","DOI":"10.1145\/2591796.2591809"},{"key":"4_CR20","doi-asserted-by":"crossref","unstructured":"Karp, R.M., Upfal, E., Wigderson, A.: Constructing a perfect matching is in random nc. In: Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, pp. 22\u201332. ACM (1985)","DOI":"10.1145\/22145.22148"},{"key":"4_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1007\/11786986_21","volume-title":"Automata, Languages and Programming","author":"S Khot","year":"2006","unstructured":"Khot, S., Ponnuswami, A.K.: Better inapproximability results for maxclique, chromatic number and min-3lin-deletion. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4051, pp. 226\u2013237. Springer, Heidelberg (2006). doi: 10.1007\/11786986_21"},{"key":"4_CR22","unstructured":"Larson, S.M., Snow, C.D., Shirts, M., Pande, V.S.: Folding@ home and genome@ home: Using distributed computing to tackle previously intractable problems in computational biology. arXiv preprint arXiv:0901.0866 (2009)"},{"key":"4_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"594","DOI":"10.1007\/978-3-642-14165-2_50","volume-title":"Automata, Languages and Programming","author":"K Makarychev","year":"2010","unstructured":"Makarychev, K., Manokaran, R., Sviridenko, M.: Maximum quadratic assignment problem: reduction from maximum label cover and LP-based approximation algorithm. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol. 6198, pp. 594\u2013604. Springer, Heidelberg (2010). doi: 10.1007\/978-3-642-14165-2_50"},{"issue":"4","key":"4_CR24","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1007\/BF01305237","volume":"12","author":"N Nisan","year":"1992","unstructured":"Nisan, N.: Pseudorandom generators for space-bounded computation. Combinatorica 12(4), 449\u2013461 (1992)","journal-title":"Combinatorica"},{"key":"4_CR25","unstructured":"Papakonstantinou, P.A.: Constructions, lower bounds, and new directions in Cryptography and Computational Complexity. Ph.D. Thesis, University of Toronto (2010)"},{"key":"4_CR26","doi-asserted-by":"crossref","unstructured":"Reingold, O., Rothblum, R., Rothblum, G.: Constant-round interactive proofs for delegating computation. In: Proceedings of the Forty-Eighth Annual ACM on Symposium on Theory of Computing. ACM (2016). (page to appear)","DOI":"10.1145\/2897518.2897652"},{"issue":"2","key":"4_CR27","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1145\/2641562","volume":"58","author":"M Walfish","year":"2015","unstructured":"Walfish, M., Blumberg, A.J.: Verifying computations without reexecuting them. Commun. ACM 58(2), 74\u201384 (2015)","journal-title":"Commun. ACM"}],"container-title":["Lecture Notes in Computer Science","Decision and Game Theory for Security"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-68711-7_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,3]],"date-time":"2022-08-03T22:39:02Z","timestamp":1659566342000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-68711-7_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319687100","9783319687117"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-68711-7_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017]]}}}