{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,21]],"date-time":"2025-12-21T01:36:49Z","timestamp":1766281009487,"version":"3.41.0"},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662536438"},{"type":"electronic","value":"9783662536445"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-662-53644-5_4","type":"book-chapter","created":{"date-parts":[[2016,10,20]],"date-time":"2016-10-20T03:24:08Z","timestamp":1476933848000},"page":"91-118","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":27,"title":["Delegating RAM Computations"],"prefix":"10.1007","author":[{"given":"Yael","family":"Kalai","sequence":"first","affiliation":[]},{"given":"Omer","family":"Paneth","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,10,21]]},"reference":[{"key":"4_CR1","unstructured":"Ananth, P., Chen, Y.-C., Chung, K.-M., Lin, H., Lin, W.-K.: Delegating RAM computations with adaptive soundness and privacy. IACR Cryptology ePrint Archive, 2015:1082 (2015)"},{"key":"4_CR2","unstructured":"Bitansky, N., Canetti, R., Chiesa, A., Goldwasser, S., Lin, H., Rubinstein, A., Tromer, E.: The hunting of the SNARK. IACR Cryptology ePrint Archive, 2014:580 (2014)"},{"key":"4_CR3","doi-asserted-by":"crossref","unstructured":"Bitansky, N., Canetti, R., Chiesa, A., Tromer, E.: Recursive composition and bootstrapping for snarks and proof-carrying data. In: STOC, pp. 111\u2013120 (2013)","DOI":"10.1145\/2488608.2488623"},{"key":"4_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/978-3-642-36594-2_18","volume-title":"Theory of Cryptography","author":"N Bitansky","year":"2013","unstructured":"Bitansky, N., Chiesa, A., Ishai, Y., Paneth, O., Ostrovsky, R.: Succinct non-interactive arguments via linear interactive proofs. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 315\u2013333. Springer, Heidelberg (2013). doi: 10.1007\/978-3-642-36594-2_18"},{"key":"4_CR5","doi-asserted-by":"crossref","unstructured":"Blum, M., Evans, W.S., Gemmell, P., Kannan, S., Naor, M.: Checking the correctness of memories. In: 32nd Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, 1\u20134 October 1991, pp. 90\u201399 (1991)","DOI":"10.1109\/SFCS.1991.185352"},{"key":"4_CR6","unstructured":"Bitansky, N., Garg, S., Lin, H., Pass, R., Telang, S.: Succinct randomized encodings and their applications. In: Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14\u201317, 2015, pp. 439\u2013448 (2015)"},{"key":"4_CR7","first-page":"77","volume":"23","author":"Z Brakerski","year":"2016","unstructured":"Brakerski, Z., Holmgren, J., Kalai, Y.T.: Non-interactive RAM and batch NP delegation from any PIR. Electron. Colloquium Comput. Complex. (ECCC) 23, 77 (2016)","journal-title":"Electron. Colloquium Comput. Complex. (ECCC)"},{"key":"4_CR8","unstructured":"Chen, Y.-C., Chow, S.S.M., Chung, K.-M., Lai, R.W.F., Lin, W.-K., Zhou, H.-S.: Computation-trace indistinguishability obfuscation and its applications. IACR Cryptology ePrint Archive,2015:406 (2015)"},{"key":"4_CR9","unstructured":"Canetti, R., Chen, Y., Holmgren, J., Raykova, M.: Succinct adaptive garbled ram. Cryptology ePrint Archive, Report 2015\/1074 (2015). http:\/\/eprint.iacr.org\/"},{"key":"4_CR10","doi-asserted-by":"crossref","unstructured":"Canetti, R., Holmgren, J.: Fully succinct garbled RAM. IACR Cryptology ePrint Archive, 2015:388 (2015)","DOI":"10.1145\/2840728.2840765"},{"key":"4_CR11","unstructured":"Canetti, R., Holmgren, J., Jain, A., Vaikuntanathan, V.: Succinct garbling and indistinguishability obfuscation for RAM programs. In: Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14\u201317, 2015, pp. 429\u2013437 (2015)"},{"key":"4_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/978-3-642-22792-9_9","volume-title":"Advances in Cryptology \u2013 CRYPTO 2011","author":"K-M Chung","year":"2011","unstructured":"Chung, K.-M., Kalai, Y.T., Liu, F.-H., Raz, R.: Memory delegation. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 151\u2013168. Springer, Heidelberg (2011). doi: 10.1007\/978-3-642-22792-9_9"},{"key":"4_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1007\/978-3-642-28914-9_4","volume-title":"Theory of Cryptography","author":"I Damg\u00e5rd","year":"2012","unstructured":"Damg\u00e5rd, I., Faust, S., Hazay, C.: Secure two-party computation with low communication. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 54\u201374. Springer, Heidelberg (2012). doi: 10.1007\/978-3-642-28914-9_4"},{"key":"4_CR14","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"},{"key":"4_CR15","first-page":"24","volume":"22","author":"O Goldreich","year":"2015","unstructured":"Goldreich, O., Gur, T., Rothblum, R.: Proofs of proximity for context-free languages and read-once branching programs. Electron. Colloquium Comput. Complex. (ECCC) 22, 24 (2015)","journal-title":"Electron. Colloquium Comput. Complex. (ECCC)"},{"key":"4_CR16","unstructured":"Gentry, C., Halevi, S., Raykova, M., Wichs, D.: Outsourcing private RAM computation. In: 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18\u201321, 2014, pp. 404\u2013413 (2014)"},{"key":"4_CR17","unstructured":"Gur, T., Rothblum, R.D.: Non-interactive proofs of proximity. In: Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS 2015, Rehovot, Israel, January 11\u201313, 2015, pp. 133\u2013142 (2015)"},{"key":"4_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/978-3-642-17373-8_19","volume-title":"Advances in Cryptology - ASIACRYPT 2010","author":"J Groth","year":"2010","unstructured":"Groth, J.: Short pairing-based non-interactive zero-knowledge arguments. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 321\u2013340. Springer, Heidelberg (2010). doi: 10.1007\/978-3-642-17373-8_19"},{"key":"4_CR19","unstructured":"Gorbunov, S., Vaikuntanathan, V., Wichs, D.: Leveled fully homomorphic signatures from standard lattices. In: Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14\u201317, 2015, pp. 469\u2013477 (2015)"},{"key":"4_CR20","doi-asserted-by":"crossref","unstructured":"Kilian, J.: A note on efficient zero-knowledge proofs and arguments. In: Proceedings of the 24th Annual ACM Symposium on Theory of Computing, pp. 723\u2013732 (1992)","DOI":"10.1145\/129712.129782"},{"key":"4_CR21","unstructured":"Kalai, Y.T., Paneth, O.: Delegating RAM computations. IACR Cryptology ePrint Archive, 2015:957 (2015)"},{"key":"4_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1007\/978-3-662-48000-7_21","volume-title":"Advances in Cryptology \u2013 CRYPTO 2015","author":"YT Kalai","year":"2015","unstructured":"Kalai, Y.T., Rothblum, R.D.: Arguments of proximity (extended abstract). In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 422\u2013442. Springer, Heidelberg (2015). doi: 10.1007\/978-3-662-48000-7_21"},{"key":"4_CR23","unstructured":"Kalai, Y.T., Raz, R., Rothblum, R.D.: How to delegate computations: the power of no-signaling proofs. In: Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pp. 485\u2013494 (2014)"},{"key":"4_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/978-3-642-28914-9_10","volume-title":"Theory of Cryptography","author":"H Lipmaa","year":"2012","unstructured":"Lipmaa, H.: Progression-free sets and sublinear pairing-based non-interactive zero-knowledge arguments. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 169\u2013189. Springer, Heidelberg (2012). doi: 10.1007\/978-3-642-28914-9_10"},{"key":"4_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/3-540-48184-2_32","volume-title":"Advances in Cryptology \u2014 CRYPTO 87","author":"RC Merkle","year":"1988","unstructured":"Merkle, R.C.: A digital signature based on a conventional encryption function. In: Pomerance, C. (ed.) CRYPTO 1987. LNCS, vol. 293, pp. 369\u2013378. Springer, Heidelberg (1988). doi: 10.1007\/3-540-48184-2_32"},{"key":"4_CR26","doi-asserted-by":"crossref","unstructured":"Micali, S.: CS proofs (extended abstracts). In\u2019: 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 20\u201322 November 1994, pp. 436\u2013453 (1994)","DOI":"10.1109\/SFCS.1994.365746"},{"issue":"2","key":"4_CR27","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1145\/322123.322138","volume":"26","author":"N Pippenger","year":"1979","unstructured":"Pippenger, N., Fischer, M.J.: Relations among complexity measures. J. ACM 26(2), 361\u2013381 (1979)","journal-title":"J. ACM"},{"key":"4_CR28","unstructured":"Paneth, O., Rothblum, G.N.: Publicly verifiable non-interactive arguments for delegating computation. Cryptology ePrint Archive, Report 2014\/981 (2014). http:\/\/eprint.iacr.org\/"},{"key":"4_CR29","unstructured":"Rothblum, G.N., Vadhan, S.P., Wigderson, A.: Interactive proofs of proximity: delegating computation in sublinear time. In: Symposium on Theory of Computing Conference, STOC 2013, Palo Alto, CA, USA, June 1\u20134, 2013, pp. 793\u2013802 (2013)"}],"container-title":["Lecture Notes in Computer Science","Theory of Cryptography"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-53644-5_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,11]],"date-time":"2025-06-11T18:03:30Z","timestamp":1749665010000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-53644-5_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662536438","9783662536445"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-53644-5_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"21 October 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"TCC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Theory of Cryptography Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Beijing","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2016","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 November 2016","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 November 2016","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tcc2016","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}