{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T22:40:31Z","timestamp":1760136031154,"version":"build-2065373602"},"publisher-location":"Cham","reference-count":53,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031159848"},{"type":"electronic","value":"9783031159855"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-15985-5_6","type":"book-chapter","created":{"date-parts":[[2022,10,10]],"date-time":"2022-10-10T20:02:37Z","timestamp":1665432157000},"page":"152-181","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Snapshot-Oblivious RAMs: Sub-logarithmic Efficiency for\u00a0Short Transcripts"],"prefix":"10.1007","author":[{"given":"Yang","family":"Du","sequence":"first","affiliation":[]},{"given":"Daniel","family":"Genkin","sequence":"additional","affiliation":[]},{"given":"Paul","family":"Grubbs","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,10,11]]},"reference":[{"key":"6_CR1","doi-asserted-by":"crossref","unstructured":"Verizon Data Breach Incident Report (2021). https:\/\/www.verizon.com\/business\/resources\/reports\/2021-data-breach-investigations-report.pdfx","DOI":"10.1016\/S1361-3723(21)00061-0"},{"key":"6_CR2","doi-asserted-by":"crossref","unstructured":"Abraham, I., Fletcher, C.W., Nayak, K., Pinkas, B., Ren, L.: Asymptotically tight bounds for composing ORAM with PIR. In: IACR PKC (2017)","DOI":"10.1007\/978-3-662-54365-8_5"},{"key":"6_CR3","doi-asserted-by":"crossref","unstructured":"Amjad, G., Kamara, S., Moataz, T.: Breach-resistant structured encryption. In: Proceedings on Privacy Enhancing Technologies (2019)","DOI":"10.2478\/popets-2019-0014"},{"key":"6_CR4","doi-asserted-by":"crossref","unstructured":"Asharov, G., Komargodski, I., Lin, W.K., Nayak, K., Peserico, E., Shi, E.: Optorama: optimal oblivious RAM. In: IACR EUROCRYPT (2020)","DOI":"10.1007\/978-3-030-45724-2_14"},{"key":"6_CR5","doi-asserted-by":"crossref","unstructured":"Asharov, G., Komargodski, I., Lin, W.K., Shi, E.: Oblivious RAM with worst-case logarithmic overhead. In: IACR CRYPTO (2021)","DOI":"10.1007\/978-3-030-84259-8_21"},{"key":"6_CR6","doi-asserted-by":"crossref","unstructured":"Boyle, E., Naor, M.: Is there an oblivious RAM lower bound? In: ITCS (2016)","DOI":"10.1145\/2840728.2840761"},{"key":"6_CR7","unstructured":"Cash, D.: A survey of Oblivious RAMs (2012). https:\/\/cseweb.ucsd.edu\/~cdcash\/oram-slides.pdf"},{"key":"6_CR8","doi-asserted-by":"crossref","unstructured":"Cash, D., Drucker, A., Hoover, A.: A lower bound for one-round oblivious RAM. In: IACR TCC (2020)","DOI":"10.1007\/978-3-030-64375-1_16"},{"key":"6_CR9","doi-asserted-by":"crossref","unstructured":"Cash, D., Grubbs, P., Perry, J., Ristenpart, T.: Leakage-abuse attacks against searchable encryption. In: ACM CCS (2015)","DOI":"10.1145\/2810103.2813700"},{"key":"6_CR10","doi-asserted-by":"crossref","unstructured":"Chan, T.H.H., Guo, Y., Lin, W.K., Shi, E.: Oblivious hashing revisited, and applications to asymptotically efficient ORAM and OPRAM. In: IACR ASIACRYPT (2017)","DOI":"10.1007\/978-3-319-70694-8_23"},{"key":"6_CR11","doi-asserted-by":"crossref","unstructured":"Chase, M., Kamara, S.: Structured encryption and controlled disclosure. In: IACR ASIACRYPT (2010)","DOI":"10.1007\/978-3-642-17373-8_33"},{"key":"6_CR12","doi-asserted-by":"crossref","unstructured":"Chung, K.M., Liu, Z., Pass, R.: Statistically-secure ORAM with $$\\tilde{O}(\\log ^2 n)$$ overhead. In: IACR ASIACRYPT (2014)","DOI":"10.1007\/978-3-662-45608-8_4"},{"issue":"5","key":"6_CR13","doi-asserted-by":"publisher","first-page":"895","DOI":"10.3233\/JCS-2011-0426","volume":"19","author":"R Curtmola","year":"2011","unstructured":"Curtmola, R., Garay, J., Kamara, S., Ostrovsky, R.: Searchable symmetric encryption: improved definitions and efficient constructions. J. Comput. Secur. 19(5), 895\u2013934 (2011)","journal-title":"J. Comput. Secur."},{"key":"6_CR14","doi-asserted-by":"crossref","unstructured":"Dautrich, Jr., J.L., Ravishankar, C.V.: Compromising privacy in precise query protocols. In: EDBT (2013)","DOI":"10.1145\/2452376.2452397"},{"key":"6_CR15","unstructured":"Demertzis, I., Papadopoulos, D., Papamanthou, C., Shintre, S.: SEAL: Attack mitigation for encrypted databases via adjustable leakage. In: Usenix Security (2020)"},{"key":"6_CR16","doi-asserted-by":"crossref","unstructured":"Devadas, S., Dijk, M.v., Fletcher, C.W., Ren, L., Shi, E., Wichs, D.: Onion ORAM: a constant bandwidth blowup oblivious RAM. In: IACR TCC (2016)","DOI":"10.1007\/978-3-662-49099-0_6"},{"key":"6_CR17","doi-asserted-by":"crossref","unstructured":"Gentry, C., Goldman, K.A., Halevi, S., Julta, C., Raykova, M., Wichs, D.: Optimizing ORAM and using it efficiently for secure computation. In: PETS (2013)","DOI":"10.1007\/978-3-642-39077-7_1"},{"key":"6_CR18","doi-asserted-by":"crossref","unstructured":"George, M., Kamara, S., Moataz, T.: Structured encryption and dynamic leakage suppression. In: IACR EUROCRYPT (2021)","DOI":"10.1007\/978-3-030-77883-5_13"},{"issue":"3","key":"6_CR19","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1145\/233551.233553","volume":"43","author":"O Goldreich","year":"1996","unstructured":"Goldreich, O., Ostrovsky, R.: Software protection and simulation on oblivious RAMs. J. ACM 43(3), 431\u2013473 (1996)","journal-title":"J. ACM"},{"key":"6_CR20","doi-asserted-by":"crossref","unstructured":"Goodrich, M.T., Mitzenmacher, M.: Privacy-preserving access of outsourced data via oblivious RAM simulation. In: ICALP (2011)","DOI":"10.1137\/1.9781611973099.14"},{"key":"6_CR21","unstructured":"Grubbs, P., Khandelwal, A., Lacharit\u00e9, M.S., Brown, L., Li, L., Agarwal, R., Ristenpart, T.: Pancake: frequency smoothing for encrypted data stores. In: Usenix Security (2020)"},{"key":"6_CR22","doi-asserted-by":"crossref","unstructured":"Grubbs, P., McPherson, R., Naveed, M., Ristenpart, T., Shmatikov, V.: Breaking web applications built on top of encrypted data. In: ACM CCS (2016)","DOI":"10.1145\/2976749.2978351"},{"key":"6_CR23","doi-asserted-by":"crossref","unstructured":"Grubbs, P., Ristenpart, T., Shmatikov, V.: Why your encrypted database is not secure. In: HotOS (2017)","DOI":"10.1145\/3102980.3103007"},{"key":"6_CR24","doi-asserted-by":"crossref","unstructured":"Grubbs, P., Sekniqi, K., Bindschaedler, V., Naveed, M., Ristenpart, T.: Leakage-abuse attacks against order-revealing encryption. In: IEEE S &P (2017)","DOI":"10.1109\/SP.2017.44"},{"key":"6_CR25","doi-asserted-by":"crossref","unstructured":"Hamlin, A., Varia, M.: Two-server distributed ORAM with sublinear computation and constant rounds. In: IACR PKC (2021)","DOI":"10.1007\/978-3-030-75248-4_18"},{"key":"6_CR26","doi-asserted-by":"crossref","unstructured":"Heath, D., Kolesnikov, V.: A 2.1 KHz zero-knowledge processor with BubbleRAM. In: ACM CCS (2020)","DOI":"10.1145\/3372297.3417283"},{"key":"6_CR27","doi-asserted-by":"crossref","unstructured":"Heath, D., Kolesnikov, V.: PrORAM: fast $${O}(\\log n)$$ private coin ZK ORAM. Cryptology ePrint Archive (2021). https:\/\/eprint.iacr.org\/2021\/587","DOI":"10.1007\/978-3-030-92068-5_17"},{"key":"6_CR28","unstructured":"Islam, M.S., Kuzu, M., Kantarcioglu, M.: Access pattern disclosure on searchable encryption: Ramification, attack and mitigation. In: NDSS (2012)"},{"key":"6_CR29","doi-asserted-by":"crossref","unstructured":"Jacob, R., Larsen, K.G., Nielsen, J.B.: Lower bounds for oblivious data structures. In: ACM SODA (2019)","DOI":"10.1137\/1.9781611975482.149"},{"key":"6_CR30","doi-asserted-by":"crossref","unstructured":"Jafargholi, Z., Larsen, K.G., Simkin, M.: Optimal oblivious priority queues. In: ACM SODA (2021)","DOI":"10.1137\/1.9781611976465.141"},{"key":"6_CR31","doi-asserted-by":"crossref","unstructured":"Kamara, S., Moataz, T., Ohrimenko, O.: Structured encryption and leakage suppression. In: IACR CRYPTO (2018)","DOI":"10.1007\/978-3-319-96884-1_12"},{"key":"6_CR32","doi-asserted-by":"crossref","unstructured":"Kellaris, G., Kollios, G., Nissim, K., O\u2019Neill, A.: Generic attacks on secure outsourced databases. In: ACM CCS (2016)","DOI":"10.1145\/2976749.2978386"},{"key":"6_CR33","doi-asserted-by":"crossref","unstructured":"Komargodski, I., Lin, W.K.: A logarithmic lower bound for oblivious RAM (for all parameters). In: IACR CRYPTO (2021)","DOI":"10.1007\/978-3-030-84259-8_20"},{"key":"6_CR34","doi-asserted-by":"crossref","unstructured":"Kornaropoulos, E.M., Papamanthou, C., Tamassia, R.: Data recovery on encrypted databases with k-nearest neighbor query leakage. In: IEEE S &P (2019)","DOI":"10.1109\/SP.2019.00015"},{"key":"6_CR35","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Lu, S., Ostrovsky, R.: On the (in) security of hash-based oblivious RAM and a new balancing scheme. In: ACM SODA (2012)","DOI":"10.1137\/1.9781611973099.13"},{"key":"6_CR36","doi-asserted-by":"crossref","unstructured":"Lacharit\u00e9, M.S., Minaud, B., Paterson, K.G.: Improved reconstruction attacks on encrypted data using range query leakage. In: IEEE S &P (2018)","DOI":"10.1109\/SP.2018.00002"},{"key":"6_CR37","unstructured":"Lacharit\u00e9, M.S., Paterson, K.G.: A note on the optimality of frequency analysis vs. $$\\ell _p$$-optimization. IACR ePrint (2015). https:\/\/eprint.iacr.org\/2015\/1158"},{"key":"6_CR38","doi-asserted-by":"crossref","unstructured":"Larsen, K.G., Nielsen, J.B.: Yes, there is an oblivious RAM lower bound! In: IACR CRYPTO (2018)","DOI":"10.1007\/978-3-319-96881-0_18"},{"key":"6_CR39","doi-asserted-by":"crossref","unstructured":"Larsen, K.G., Simkin, M., Yeo, K.: Lower bounds for multi-server oblivious RAMs. In: IACR TCC (2020)","DOI":"10.1007\/978-3-030-64375-1_17"},{"key":"6_CR40","doi-asserted-by":"crossref","unstructured":"Moataz, T., Mayberry, T., Blass, E.O.: Constant communication ORAM with small blocksize. In: ACM CCS (2015)","DOI":"10.1145\/2810103.2813701"},{"key":"6_CR41","doi-asserted-by":"crossref","unstructured":"Patel, S., Persiano, G., Raykova, M., Yeo, K.: PanORAMa: oblivious RAM with logarithmic overhead. In: IEEE FOCS (2018)","DOI":"10.1109\/FOCS.2018.00087"},{"key":"6_CR42","doi-asserted-by":"crossref","unstructured":"Persiano, G., Yeo, K.: Lower bounds for differentially private RAMs. In: IACR EUROCRYPT (2019)","DOI":"10.1007\/978-3-030-17653-2_14"},{"key":"6_CR43","doi-asserted-by":"crossref","unstructured":"Pinkas, B., Reinman, T.: Oblivious RAM revisited. In: IACR CRYPTO (2010)","DOI":"10.1007\/978-3-642-14623-7_27"},{"key":"6_CR44","unstructured":"Ren, L., Fletcher, C., Kwon, A., Stefanov, E., Shi, E., Van Dijk, M., Devadas, S.: Constants count: practical improvements to oblivious RAM. In: Usenix Security (2015)"},{"key":"6_CR45","doi-asserted-by":"crossref","unstructured":"Ren, L., Fletcher, C.W., Yu, X., Van Dijk, M., Devadas, S.: Integrity verification for path oblivious-ram. In: IEEE HPEC (2013)","DOI":"10.1109\/HPEC.2013.6670339"},{"key":"6_CR46","doi-asserted-by":"crossref","unstructured":"Roche, D.S., Aviv, A., Choi, S.G.: A practical oblivious map data structure with secure deletion and history independence. In: IEEE S &P (2016)","DOI":"10.1109\/SP.2016.19"},{"key":"6_CR47","doi-asserted-by":"crossref","unstructured":"Shi, E., Chan, T.H.H., Stefanov, E., Li, M.: Oblivious RAM with $${O}(\\log ^3 {N})$$ worst-case cost. In: IACR ASIACRYPT (2011)","DOI":"10.1007\/978-3-642-25385-0_11"},{"key":"6_CR48","unstructured":"Song, D.X., Wagner, D., Perrig, A.: Practical techniques for searches on encrypted data. In: IEEE S &P (2000)"},{"key":"6_CR49","doi-asserted-by":"crossref","unstructured":"Stefanov, E., et al.: Path ORAM: an extremely simple oblivious RAM protocol. In: ACM CCS (2013)","DOI":"10.1145\/2508859.2516660"},{"key":"6_CR50","doi-asserted-by":"crossref","unstructured":"Wagh, S., Cuff, P., Mittal, P.: Differentially private oblivious RAM. In: Proceedings on Privacy Enhancing Technologies (2018)","DOI":"10.1515\/popets-2018-0032"},{"key":"6_CR51","doi-asserted-by":"crossref","unstructured":"Wang, X., Chan, H., Shi, E.: Circuit ORAM: on tightness of the goldreich-ostrovsky lower bound. In: ACM CCS (2015)","DOI":"10.1145\/2810103.2813634"},{"key":"6_CR52","doi-asserted-by":"crossref","unstructured":"Wang, X., et al.: Oblivious data structures. In: ACM CCS (2014)","DOI":"10.1145\/2660267.2660314"},{"issue":"3","key":"6_CR53","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00145-021-09392-1","volume":"34","author":"M Weiss","year":"2021","unstructured":"Weiss, M., Wichs, D.: Is there an oblivious RAM lower bound for online reads? J. Cryptology 34(3), 1\u201344 (2021). https:\/\/doi.org\/10.1007\/s00145-021-09392-1","journal-title":"J. Cryptology"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 CRYPTO 2022"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-15985-5_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T22:05:27Z","timestamp":1760133927000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-15985-5_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031159848","9783031159855"],"references-count":53,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-15985-5_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"11 October 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CRYPTO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Annual International Cryptology Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Santa Barbara, CA","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 August 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 August 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"42","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"crypto2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/crypto.iacr.org\/2022\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}