{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,27]],"date-time":"2025-04-27T13:04:13Z","timestamp":1745759053697,"version":"3.40.4"},"publisher-location":"Cham","reference-count":70,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031911330","type":"print"},{"value":"9783031911347","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-91134-7_13","type":"book-chapter","created":{"date-parts":[[2025,4,26]],"date-time":"2025-04-26T11:04:35Z","timestamp":1745665475000},"page":"363-395","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Zero-Knowledge RAM: Doubly Efficient and\u00a0Black-Box"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-4096-6305","authenticated-orcid":false,"given":"Yuval","family":"Ishai","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1501-1330","authenticated-orcid":false,"given":"Rafail","family":"Ostrovsky","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-4737-0430","authenticated-orcid":false,"given":"Akash","family":"Shah","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,4,27]]},"reference":[{"key":"13_CR1","unstructured":"Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms. Addison-Wesley (1974)"},{"key":"13_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1007\/978-3-030-84259-8_4","volume-title":"Advances in Cryptology \u2013 CRYPTO 2021","author":"C Baum","year":"2021","unstructured":"Baum, C., Malozemoff, A.J., Rosen, M.B., Scholl, P.: $$\\sf Mac^{\\prime }n^{\\prime }Cheese$$: zero-knowledge proofs for\u00a0boolean and arithmetic circuits with\u00a0nested disjunctions. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12828, pp. 92\u2013122. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-84259-8_4"},{"key":"13_CR3","unstructured":"Ben-Sasson, E., Chiesa, A.: Personal Communication (2023)"},{"key":"13_CR4","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer, E.: On the concrete efficiency of probabilistically-checkable proofs. In: STOC. ACM (2013)","DOI":"10.1145\/2488608.2488681"},{"issue":"4","key":"13_CR5","doi-asserted-by":"publisher","first-page":"889","DOI":"10.1137\/S0097539705446810","volume":"36","author":"E Ben-Sasson","year":"2006","unstructured":"Ben-Sasson, E., Goldreich, O., Harsha, P., Sudan, M., Vadhan, S.: Robust PCPs of proximity, shorter PCPs, and applications to coding. SIAM J. Comput. 36(4), 889\u2013974 (2006)","journal-title":"SIAM J. Comput."},{"key":"13_CR6","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Goldreich, O., Harsha, P., Sudan, M., Vadhan, S.P.: Short PCPs verifiable in polylogarithmic time. In: 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 11\u201315 June 2005, San Jose, CA, USA, pp. 120\u2013134. IEEE Computer Society (2005)","DOI":"10.1109\/CCC.2005.27"},{"key":"13_CR7","doi-asserted-by":"crossref","unstructured":"Bitansky, N., et al.: The hunting of the SNARK. J. Cryptol. (2017)","DOI":"10.1007\/s00145-016-9241-9"},{"issue":"2","key":"13_CR8","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1016\/0022-0000(88)90005-0","volume":"37","author":"G Brassard","year":"1988","unstructured":"Brassard, G., Chaum, D., Cr\u00e9peau, C.: Minimum disclosure proofs of knowledge. J. Comput. Syst. Sci. 37(2), 156\u2013189 (1988)","journal-title":"J. Comput. Syst. Sci."},{"key":"13_CR9","doi-asserted-by":"crossref","unstructured":"B\u00fcnz, B., Chen, B.: Protostar: generic efficient accumulation\/folding for special-sound protocols. In: ASIACRYPT. Springer, Cham (2023)","DOI":"10.1007\/978-981-99-8724-5_3"},{"key":"13_CR10","doi-asserted-by":"crossref","unstructured":"Campanelli, M., Fiore, D., Han, S., Kim, J., Kolonelos, D., Hyunok, O.: Succinct zero-knowledge batch proofs for set accumulators. In: ACM CCS. ACM (2022)","DOI":"10.1145\/3548606.3560677"},{"issue":"1","key":"13_CR11","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/s001459910006","volume":"13","author":"R Canetti","year":"2000","unstructured":"Canetti, R.: Security and composition of multiparty cryptographic protocols. J. Cryptol. 13(1), 143\u2013202 (2000)","journal-title":"J. Cryptol."},{"key":"13_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/978-3-642-36362-7_5","volume-title":"Public-Key Cryptography \u2013 PKC 2013","author":"D Catalano","year":"2013","unstructured":"Catalano, D., Fiore, D.: Vector commitments and their applications. In: Kurosawa, K., Hanaoka, G. (eds.) PKC 2013. LNCS, vol. 7778, pp. 55\u201372. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-36362-7_5"},{"key":"13_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1007\/978-3-642-54242-8_21","volume-title":"Theory of Cryptography","author":"N Chandran","year":"2014","unstructured":"Chandran, N., Kanukurthi, B., Ostrovsky, R.: Locally updatable and locally decodable codes. In: Lindell, Y. (ed.) TCC 2014. LNCS, vol. 8349, pp. 489\u2013514. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-642-54242-8_21"},{"key":"13_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1007\/11426639_25","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2005","author":"M Chase","year":"2005","unstructured":"Chase, M., Healy, A., Lysyanskaya, A., Malkin, T., Reyzin, L.: Mercurial commitments with applications to zero-knowledge sets. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 422\u2013439. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11426639_25"},{"key":"13_CR15","doi-asserted-by":"crossref","unstructured":"Choudhuri, A.R., Garg, S., Goel, A., Sekar, S., Sinha, R.: Sublonk: sublinear prover plonk. In: PoPETs (2024)","DOI":"10.56553\/popets-2024-0080"},{"key":"13_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"572","DOI":"10.1007\/978-3-540-74143-5_32","volume-title":"Advances in Cryptology - CRYPTO 2007","author":"I Damg\u00e5rd","year":"2007","unstructured":"Damg\u00e5rd, I., Nielsen, J.B.: Scalable and unconditionally secure multiparty computation. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 572\u2013590. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-74143-5_32"},{"issue":"3","key":"13_CR17","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/s001459900026","volume":"10","author":"IB Damg\u00e5rd","year":"1997","unstructured":"Damg\u00e5rd, I.B., Pedersen, T.P., Pfitzmann, B.: On the existence of statistically hiding bit commitment schemes and fail-stop signatures. J. Cryptol. 10(3), 163\u2013194 (1997). https:\/\/doi.org\/10.1007\/s001459900026","journal-title":"J. Cryptol."},{"key":"13_CR18","doi-asserted-by":"crossref","unstructured":"Damg\u00e5rd, I., Pedersen, T.P., Pfitzmann, B.: Statistical secrecy and multibit commitments. IEEE Trans. Inf. Theory (1998)","DOI":"10.1109\/18.669255"},{"key":"13_CR19","doi-asserted-by":"crossref","unstructured":"Di, Z., Xia, L., Nguyen, W.D., Tyagi, N.: Muxproofs: succinct arguments for machine computation from tuple lookups. IACR Cryptol. ePrint Arch. 974 (2023)","DOI":"10.1007\/978-981-96-0935-2_8"},{"key":"13_CR20","doi-asserted-by":"crossref","unstructured":"Dutta, M., Ganesh, C., Patranabis, S., Prakash, S., Singh, N.: Batching-efficient RAM using updatable lookup arguments. In: ACM CCS. ACM (2024)","DOI":"10.1145\/3658644.3670356"},{"key":"13_CR21","unstructured":"Eagen, L., Fiore, D., Gabizon, A.: CQ: cached quotients for fast lookups. IACR Cryptol. ePrint Arch. 1763 (2022)"},{"key":"13_CR22","doi-asserted-by":"crossref","unstructured":"Franzese, N., Katz, J., Lu, S., Ostrovsky, R., Wang, X., Weng, C.: Constant-overhead zero-knowledge for ram programs. In: Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, pp. 178\u2013191 (2021)","DOI":"10.1145\/3460120.3484800"},{"key":"13_CR23","unstructured":"Friedl, K., Sudan, M.: Some improvements to total degree tests. In: ISTCS. IEEE Computer Society (1995)"},{"key":"13_CR24","unstructured":"Gabizon, A., Khovratovich, D.: flookup: fractional decomposition-based lookups in quasi-linear time independent of table size. IACR Cryptol. ePrint Arch. 1447 (2022)"},{"key":"13_CR25","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). https:\/\/doi.org\/10.1007\/978-3-642-38348-9_37"},{"key":"13_CR26","unstructured":"Goel, A., Hall-Andersen, M., Kaptchuk, G.: Dora: processor expressiveness is (nearly) free in zero-knowledge for RAM programs. In: ACM CCS. ACM (2024)"},{"key":"13_CR27","unstructured":"Goldreich, O.: The Foundations of Cryptography - Volume 1: Basic Techniques. Cambridge University Press, Cambridge (2001)"},{"key":"13_CR28","doi-asserted-by":"crossref","unstructured":"Goldreich, O.: On doubly-efficient interactive proof systems. Found. Trends Theor. Comput. Sci. (2018)","DOI":"10.1561\/9781680834253"},{"key":"13_CR29","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Ostrovsky, R.: Software protection and simulation on oblivious rams. J. ACM (1996)","DOI":"10.1145\/233551.233553"},{"key":"13_CR30","doi-asserted-by":"crossref","unstructured":"Goldwasser, S., Kalai, Y.T., Rothblum, G.N.: Delegating computation: interactive proofs for muggles. J. ACM (2015)","DOI":"10.1145\/2699436"},{"issue":"1","key":"13_CR31","doi-asserted-by":"publisher","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":"13_CR32","doi-asserted-by":"crossref","unstructured":"Gordon, S.D., et al.: Secure two-party computation in sublinear (amortized) time. In: CCS, pp. 513\u2013524. ACM (2012)","DOI":"10.1145\/2382196.2382251"},{"key":"13_CR33","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). https:\/\/doi.org\/10.1007\/978-3-642-17373-8_19"},{"key":"13_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/978-3-662-49896-5_11","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2016","author":"J Groth","year":"2016","unstructured":"Groth, J.: On the size of pairing-based non-interactive arguments. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 305\u2013326. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-49896-5_11"},{"key":"13_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1007\/3-540-51237-3_10","volume-title":"Logic at Botik \u201989","author":"Y Gurevich","year":"1989","unstructured":"Gurevich, Y., Shelah, S.: Nearly linear time. In: Meyer, A.R., Taitslin, M.A. (eds.) Logic at Botik 1989. LNCS, vol. 363, pp. 108\u2013118. Springer, Heidelberg (1989). https:\/\/doi.org\/10.1007\/3-540-51237-3_10"},{"key":"13_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/3-540-68697-5_16","volume-title":"Advances in Cryptology \u2014 CRYPTO \u201996","author":"S Halevi","year":"1996","unstructured":"Halevi, S., Micali, S.: Practical and provably-secure commitment schemes from collision-free hashing. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 201\u2013215. Springer, Heidelberg (1996). https:\/\/doi.org\/10.1007\/3-540-68697-5_16"},{"key":"13_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1007\/978-3-030-17656-3_9","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2019","author":"A Hamlin","year":"2019","unstructured":"Hamlin, A., Ostrovsky, R., Weiss, M., Wichs, D.: Private anonymous data access. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11477, pp. 244\u2013273. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-17656-3_9"},{"key":"13_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"569","DOI":"10.1007\/978-3-030-45727-3_19","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2020","author":"D Heath","year":"2020","unstructured":"Heath, D., Kolesnikov, V.: Stacked garbling for disjunctive zero-knowledge proofs. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12107, pp. 569\u2013598. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-45727-3_19"},{"key":"13_CR39","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1007\/3-540-44750-4_27","volume-title":"Advances in Cryptology \u2014 CRYPT0\u2019 95","author":"A Herzberg","year":"1995","unstructured":"Herzberg, A., Jarecki, S., Krawczyk, H., Yung, M.: Proactive secret sharing or: how to cope with perpetual leakage. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 339\u2013352. Springer, Heidelberg (1995). https:\/\/doi.org\/10.1007\/3-540-44750-4_27"},{"key":"13_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1007\/978-3-662-48000-7_8","volume-title":"Advances in Cryptology \u2013 CRYPTO 2015","author":"Z Hu","year":"2015","unstructured":"Hu, Z., Mohassel, P., Rosulek, M.: Efficient zero-knowledge proofs of non-algebraic statements with sublinear amortized cost. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 150\u2013169. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48000-7_8"},{"key":"13_CR41","doi-asserted-by":"crossref","unstructured":"Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Zero-knowledge from secure multiparty computation. In: STOC. ACM (2007)","DOI":"10.1145\/1250790.1250794"},{"key":"13_CR42","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/978-3-031-38545-2_6","volume-title":"CRYPTO 2023","author":"Y Ishai","year":"2023","unstructured":"Ishai, Y., Ostrovsky, R., Shah, A.: Succinct arguments for RAM programs via projection codes. In: Handschuh, H., Lysyanskaya, A. (eds.) CRYPTO 2023. LNCS, vol. 14082, pp. 159\u2013192. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-38545-2_6"},{"key":"13_CR43","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/978-3-642-54242-8_6","volume-title":"Theory of Cryptography","author":"Y Ishai","year":"2014","unstructured":"Ishai, Y., Weiss, M.: Probabilistically checkable proofs of proximity with zero-knowledge. In: Lindell, Y. (ed.) TCC 2014. LNCS, vol. 8349, pp. 121\u2013145. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-642-54242-8_6"},{"key":"13_CR44","doi-asserted-by":"crossref","unstructured":"Kilian, J.: A note on efficient zero-knowledge proofs and arguments. In: Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, pp. 723\u2013732 (1992)","DOI":"10.1145\/129712.129782"},{"key":"13_CR45","unstructured":"Kosba, A.E., Papadopoulos, D., Papamanthou, C., Song, D.: MIRAGE: succinct arguments for randomized algorithms with applications to universal ZK-snarks. In: USENIX Security. USENIX Association (2020)"},{"key":"13_CR46","unstructured":"Kothapalli, A., Setty, S.T.V.: Supernova: proving universal machine executions without universal circuits. IACR Cryptol. ePrint Arch. 1758 (2022)"},{"key":"13_CR47","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/978-3-031-68403-6_11","volume-title":"CRYPTO 2024","author":"A Kothapalli","year":"2024","unstructured":"Kothapalli, A., Setty, S.: Hypernova: recursive arguments for customizable constraint systems. In: Reyzin, L., Stebila, D. (eds.) CRYPTO 2024. LNCS, vol. 14929, pp. 345\u2013379. Springer, Cham (2024). https:\/\/doi.org\/10.1007\/978-3-031-68403-6_11"},{"key":"13_CR48","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/978-3-031-15985-5_13","volume-title":"CRYPTO 2022","author":"A Kothapalli","year":"2022","unstructured":"Kothapalli, A., Setty, S., Tzialla, I.: Nova: recursive zero-knowledge arguments from folding schemes. In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 2022. LNCS, vol. 13510, pp. 359\u2013388. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-15985-5_13"},{"key":"13_CR49","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1007\/978-3-642-11799-2_30","volume-title":"Theory of Cryptography","author":"B Libert","year":"2010","unstructured":"Libert, B., Yung, M.: Concise mercurial vector commitments and independent zero-knowledge sets with short proofs. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 499\u2013517. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-11799-2_30"},{"key":"13_CR50","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1007\/0-387-34805-0_21","volume-title":"Advances in Cryptology \u2014 CRYPTO\u2019 89 Proceedings","author":"RC Merkle","year":"1990","unstructured":"Merkle, R.C.: A certified digital signature. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 218\u2013238. Springer, New York (1990). https:\/\/doi.org\/10.1007\/0-387-34805-0_21"},{"key":"13_CR51","unstructured":"Micali, S.: CS proofs (extended abstracts). In: FOCS. IEEE Computer Society (1994)"},{"key":"13_CR52","unstructured":"Micali, S., Rabin, M.O., Kilian, J.: Zero-knowledge sets. In: FOCS. IEEE Computer Society (2003)"},{"key":"13_CR53","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1007\/978-3-319-56620-7_18","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2017","author":"P Mohassel","year":"2017","unstructured":"Mohassel, P., Rosulek, M., Scafuro, A.: Sublinear zero-knowledge arguments for RAM programs. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10210, pp. 501\u2013531. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-56620-7_18"},{"key":"13_CR54","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1041","DOI":"10.1007\/978-3-540-27836-8_87","volume-title":"Automata, Languages and Programming","author":"R Ostrovsky","year":"2004","unstructured":"Ostrovsky, R., Rackoff, C., Smith, A.: Efficient consistency proofs for generalized queries on a committed database. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 1041\u20131053. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-27836-8_87"},{"key":"13_CR55","doi-asserted-by":"crossref","unstructured":"Ostrovsky, R., Shoup, V.: Private information storage (extended abstract). In: ACM Symposium on the Theory of Computing, pp. 294\u2013303. ACM (1997)","DOI":"10.1145\/258533.258606"},{"key":"13_CR56","doi-asserted-by":"crossref","unstructured":"Ostrovsky, R., Yung, M.: How to withstand mobile virus attacks (extended abstract). In: PODC. ACM (1991)","DOI":"10.1145\/112600.112605"},{"key":"13_CR57","unstructured":"Ozdemir, A., Wahby, R.S., Whitehat, B., Boneh, D.: Scaling verifiable computation using efficient set accumulators. In: USENIX Security. USENIX Association (2020)"},{"key":"13_CR58","doi-asserted-by":"crossref","unstructured":"Parno, B., Howell, J., Gentry, C., Raykova, M.: Pinocchio: nearly practical verifiable computation. In: IEEE SP. IEEE Computer Society (2013)","DOI":"10.1109\/SP.2013.47"},{"key":"13_CR59","unstructured":"Posen, J., Kattis, A.A.: Caulk+: table-independent lookup arguments. IACR Cryptol. ePrint Arch. 957 (2022)"},{"issue":"2","key":"13_CR60","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1137\/S0097539793255151","volume":"25","author":"R Rubinfeld","year":"1996","unstructured":"Rubinfeld, R., Sudan, M.: Robust characterizations of polynomials with applications to program testing. SIAM J. Comput. 25(2), 252\u2013271 (1996)","journal-title":"SIAM J. Comput."},{"issue":"11","key":"13_CR61","doi-asserted-by":"publisher","first-page":"612","DOI":"10.1145\/359168.359176","volume":"22","author":"A Shamir","year":"1979","unstructured":"Shamir, A.: How to share a secret. Commun. ACM 22(11), 612\u2013613 (1979)","journal-title":"Commun. ACM"},{"key":"13_CR62","doi-asserted-by":"crossref","unstructured":"Stefanov, E., et al.: Path ORAM: an extremely simple oblivious RAM protocol. In: ACMCCS. ACM (2013)","DOI":"10.1145\/2508859.2516660"},{"key":"13_CR63","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-78524-8_1","volume-title":"Theory of Cryptography","author":"P Valiant","year":"2008","unstructured":"Valiant, P.: Incrementally verifiable computation or proofs of knowledge imply time\/space efficiency. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 1\u201318. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-78524-8_1"},{"key":"13_CR64","doi-asserted-by":"crossref","unstructured":"Wahby, R.S., Setty, S., Howald, M., Ren, Z., Blumberg, A.J., Walfish, M.: Efficient RAM and control flow in verifiable outsourced computation. In: NDSS. The Internet Society (2015)","DOI":"10.14722\/ndss.2015.23097"},{"key":"13_CR65","doi-asserted-by":"crossref","unstructured":"Yang, Y., Heath, D., Hazay, C., Kolesnikov, V., Venkitasubramaniam, M.: Batchman and robin: batched and non-batched branching for interactive ZK. In: ACM CCS. ACM (2023)","DOI":"10.1145\/3576915.3623169"},{"key":"13_CR66","doi-asserted-by":"crossref","unstructured":"Yang, Y., Heath, D., Hazay, C., Kolesnikov, V., Venkitasubramaniam, M.: Tight ZK CPU: batched ZK branching with cost proportional to evaluated instruction. In: ACM CCS. ACM (2024)","DOI":"10.1145\/3658644.3690289"},{"key":"13_CR67","doi-asserted-by":"crossref","unstructured":"Yekhanin, S.: Locally decodable codes. Found. Trends\u00ae Theor. Comput. Sci. 6(3), 139\u2013255 (2012)","DOI":"10.1561\/0400000030"},{"key":"13_CR68","unstructured":"Zapico, A., Buterin, V., Khovratovich, D., Maller, M., Nitulescu, A., Simkin, M.: Caulk: lookup arguments in sublinear time. In: ACM CCS. ACM (2022)"},{"key":"13_CR69","unstructured":"Zapico, A., Gabizon, A., Khovratovich, D., Maller, M., R\u00e0fols, C.: Baloo: nearly optimal lookup arguments. IACR Cryptol. ePrint Arch. 1565 (2022)"},{"key":"13_CR70","doi-asserted-by":"crossref","unstructured":"Zhang, Y., Genkin, D., Katz, J., Papadopoulos, D., Papamanthou, C.: vRAM: faster verifiable RAM with program-independent preprocessing. In: IEEE SP. IEEE Computer Society (2018)","DOI":"10.1109\/SP.2018.00013"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 EUROCRYPT 2025"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-91134-7_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,26]],"date-time":"2025-04-26T11:04:46Z","timestamp":1745665486000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-91134-7_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031911330","9783031911347"],"references-count":70,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-91134-7_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"27 April 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"EUROCRYPT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Annual International Conference on the Theory and Applications of Cryptographic Techniques","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Madrid","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Spain","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 May 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 May 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"44","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"eurocrypt2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/eurocrypt.iacr.org\/2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}