{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,21]],"date-time":"2026-05-21T16:33:20Z","timestamp":1779381200475,"version":"3.53.1"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,1,24]],"date-time":"2022-01-24T00:00:00Z","timestamp":1642982400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,24]],"date-time":"2022-01-24T00:00:00Z","timestamp":1642982400000},"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":["J Cryptol"],"published-print":{"date-parts":[[2022,4]]},"DOI":"10.1007\/s00145-022-09419-1","type":"journal-article","created":{"date-parts":[[2022,1,24]],"date-time":"2022-01-24T18:14:01Z","timestamp":1643048041000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Locality-Preserving Oblivious RAM"],"prefix":"10.1007","volume":"35","author":[{"given":"Gilad","family":"Asharov","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"T.-H. Hubert","family":"Chan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kartik","family":"Nayak","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rafael","family":"Pass","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ling","family":"Ren","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Elaine","family":"Shi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,1,24]]},"reference":[{"key":"9419_CR1","doi-asserted-by":"crossref","unstructured":"G. Asharov, T.-H.H. Chan, K. Nayak, R. Pass, L. Ren, E. Shi, Bucket oblivious sort: An extremely simple oblivious sort, in 3rd Symposium on Simplicity in Algorithms, SOSA@SODA 2020 (SIAM, 2020), pp. 8\u201314","DOI":"10.1137\/1.9781611976014.2"},{"key":"9419_CR2","doi-asserted-by":"crossref","unstructured":"L. Arge, P. Ferragina, R. Grossi, J.S. Vitter, On sorting strings in external memory (extended abstract), in ACM Symposium on the Theory of Computing (STOC \u201997) (1997), pp. 540\u2013548","DOI":"10.1145\/258533.258647"},{"key":"9419_CR3","doi-asserted-by":"crossref","unstructured":"G. Asharov, I. Komargodski, W.-K. Lin, K. Nayak, E. Peserico, E. Shi, Optorama: Optimal oblivious RAM, in Advances in Cryptology\u2014EUROCRYPT 2020, Proceedings, Part II, volume 12106 of Lecture Notes in Computer Science (Springer, 2020), pp. 403\u2013432","DOI":"10.1007\/978-3-030-45724-2_14"},{"key":"9419_CR4","doi-asserted-by":"crossref","unstructured":"M.\u00a0Ajtai, J.\u00a0Koml\u00f3s, E.\u00a0Szemer\u00e9di, An $$O(N \\log N)$$ sorting network, in ACM Symposium on Theory of Computing (STOC \u201983) (1983), pp. 1\u20139","DOI":"10.1145\/800061.808726"},{"key":"9419_CR5","doi-asserted-by":"crossref","unstructured":"D. Apon, J. Katz, E. Shi, A. Thiruvengadam, Verifiable oblivious storage, in Public Key Cryptography (PKC\u201914) (2014), pp. 131\u2013148","DOI":"10.1007\/978-3-642-54631-0_8"},{"key":"9419_CR6","doi-asserted-by":"crossref","unstructured":"G. Asharov, M. Naor, G. Segev, I. Shahaf, Searchable symmetric encryption: optimal locality in linear space via two-dimensional balanced allocations, in ACM Symposium on Theory of Computing (STOC \u201916) (2016), pp. 1101\u20131114","DOI":"10.1145\/2897518.2897562"},{"key":"9419_CR7","doi-asserted-by":"crossref","unstructured":"G. Asharov, G. Segev, I. Shahaf, Tight tradeoffs in searchable symmetric encryption, in CRYPTO (1), vol. 10991 (2018), pp. 407\u2013436","DOI":"10.1007\/978-3-319-96884-1_14"},{"key":"9419_CR8","doi-asserted-by":"crossref","unstructured":"K.E. Batcher, Sorting Networks and Their Applications. AFIPS \u201968 (1968)","DOI":"10.1145\/1468075.1468121"},{"key":"9419_CR9","doi-asserted-by":"crossref","unstructured":"E. Boyle, M. Naor, Is there an oblivious RAM lower bound?, in ACM Conference on Innovations in Theoretical Computer Science (ITCS \u201916) (2016), pp. 357\u2013368","DOI":"10.1145\/2840728.2840761"},{"key":"9419_CR10","unstructured":"E. Brewer, L. Ying, L. Greenfield, R. Cypher, T. T\u2019so, Disks for data centers\u2014white paper for FAST 2016. Technical report, Google (2016)"},{"key":"9419_CR11","doi-asserted-by":"crossref","unstructured":"A. Chakraborti, A.J. Aviv, S.G. Choi, T. Mayberry, D.S. Roche, R. Sion, rORAM: Efficient Range ORAM with $$O(\\log ^2 N)$$ Locality, in Network and Distributed System Security (NDSS) (2019)","DOI":"10.14722\/ndss.2019.23320"},{"key":"9419_CR12","doi-asserted-by":"crossref","unstructured":"R. Canetti, Security and composition of multiparty cryptographic protocols. J. Cryptology, 13(1), 143\u2013202 (2000)","DOI":"10.1007\/s001459910006"},{"key":"9419_CR13","doi-asserted-by":"crossref","unstructured":"T.H.H. Chan, K.-M. Chung, B. Maggs, E. Shi, Foundations of differentially oblivious algorithms, in Symposium on Discrete Algorithms (SODA) (2019)","DOI":"10.1137\/1.9781611975482.150"},{"key":"9419_CR14","doi-asserted-by":"crossref","unstructured":"R. Curtmola, J.A. Garay, S. Kamara, R. Ostrovsky, Searchable symmetric encryption: improved definitions and efficient constructions, in ACM Conference on Computer and Communications Security (CCS \u201906) (2006), pp. 79\u201388","DOI":"10.1145\/1180405.1180417"},{"key":"9419_CR15","doi-asserted-by":"crossref","unstructured":"D. Cash, S. Jarecki, C.S. Jutla, H. Krawczyk, M.-C. Rosu, M. Steiner, Highly-scalable searchable symmetric encryption with support for boolean queries, in Advances in Cryptology\u2014CRYPTO 2013. Proceedings, Part I (2013), pp. 353\u2013373","DOI":"10.1007\/978-3-642-40041-4_20"},{"key":"9419_CR16","doi-asserted-by":"crossref","unstructured":"M. Chase, S. Kamara, Structured encryption and controlled disclosure, in Asiacrypt (Springer, 2010), pp. 577\u2013594","DOI":"10.1007\/978-3-642-17373-8_33"},{"key":"9419_CR17","doi-asserted-by":"crossref","unstructured":"K.-M. Chung, Z. Liu, R. Pass, Statistically-secure ORAM with $${{\\tilde{O}}}(\\log ^2n)$$ overhead, in Asiacrypt (2014)","DOI":"10.1007\/978-3-662-45608-8_4"},{"key":"9419_CR18","doi-asserted-by":"crossref","unstructured":"T.-H.H. Chan, K. Nayak, E. Shi, Perfectly secure oblivious parallel RAM, in Theory of Cryptography Conference (TCC) (2018)","DOI":"10.1007\/978-3-030-03810-6_23"},{"key":"9419_CR19","doi-asserted-by":"crossref","unstructured":"T.-H.H. Chan, E. Shi, Circuit OPRAM: unifying statistically and computationally secure orams and oprams, in Theory of Cryptography\u201415th International Conference, TCC 2017, volume 10678 of Lecture Notes in Computer Science (Springer, 2017), pp. 72\u2013107","DOI":"10.1007\/978-3-319-70503-3_3"},{"key":"9419_CR20","doi-asserted-by":"crossref","unstructured":"D. Cash, S. Tessaro, The locality of searchable symmetric encryption, in Advances in Cryptology\u2014EUROCRYPT 2014, vol. 8441 (2014), pp. 351\u2013368","DOI":"10.1007\/978-3-642-55220-5_20"},{"key":"9419_CR21","doi-asserted-by":"crossref","unstructured":"I. Demertzis, C. Papamanthou, Fast searchable encryption with tunable locality, in SIGMOD Conference (ACM, 2017), pp. 1053\u20131067","DOI":"10.1145\/3035918.3064057"},{"key":"9419_CR22","doi-asserted-by":"crossref","unstructured":"I. Demertzis, D. Papadopoulos, C. Papamanthou, Searchable encryption with optimal locality: Achieving sublogarithmic read efficiency, in CRYPTO (2018)","DOI":"10.1007\/978-3-319-96884-1_13"},{"key":"9419_CR23","doi-asserted-by":"crossref","unstructured":"S. Devadas, M. van Dijk, C.W. Fletcher, L. Ren, E. Shi, D. Wichs, Onion ORAM: a constant bandwidth blowup oblivious RAM, in TCC (2016)","DOI":"10.1007\/978-3-662-49099-0_6"},{"key":"9419_CR24","doi-asserted-by":"crossref","unstructured":"M.T. Goodrich, M. Mitzenmacher, Privacy-preserving access of outsourced data via oblivious RAM simulation, in ICALP (2011)","DOI":"10.1137\/1.9781611973099.14"},{"key":"9419_CR25","doi-asserted-by":"crossref","unstructured":"O. Goldreich, R. Ostrovsky, Software protection and simulation on oblivious RAMs. J. ACM (1996)","DOI":"10.1145\/233551.233553"},{"key":"9419_CR26","doi-asserted-by":"crossref","unstructured":"O.\u00a0Goldreich, Towards a theory of software protection and simulation by oblivious RAMs, in STOC (1987)","DOI":"10.1145\/28395.28416"},{"key":"9419_CR27","doi-asserted-by":"crossref","unstructured":"O. Goldreich, The Foundations of Cryptography\u2014Volume 2, Basic Applications (Cambridge University Press, 2004)","DOI":"10.1017\/CBO9780511721656"},{"key":"9419_CR28","doi-asserted-by":"crossref","unstructured":"M.T. Goodrich, Zig-zag sort: a simple deterministic data-oblivious sorting algorithm running in o(n log n) time, in STOC (2014)","DOI":"10.1145\/2591796.2591830"},{"key":"9419_CR29","doi-asserted-by":"crossref","unstructured":"G. Kellaris, G. Kollios, K. Nissim, A. O\u2019Neill, Generic attacks on secure outsourced databases, in ACM CCS (2016), pp. 1329\u20131340","DOI":"10.1145\/2976749.2978386"},{"key":"9419_CR30","unstructured":"G. Kellaris, G. Kollios, K. Nissim, A. O\u2019Neill, Accessing data while preserving privacy. CoRR, arXiv:abs\/1706.01552 (2017)"},{"key":"9419_CR31","doi-asserted-by":"crossref","unstructured":"E. Kushilevitz, S. Lu, R. Ostrovsky, On the (in)security of hash-based oblivious RAM and a new balancing scheme, in SODA (2012)","DOI":"10.1137\/1.9781611973099.13"},{"key":"9419_CR32","doi-asserted-by":"crossref","unstructured":"K. Kurosawa, Y. Ohtaki, How to update documents verifiably in searchable symmetric encryption, in International Conference on Cryptology and Network Security (Springer, 2013), pp. 309\u2013328","DOI":"10.1007\/978-3-319-02937-5_17"},{"key":"9419_CR33","doi-asserted-by":"crossref","unstructured":"S. Kamara, C. Papamanthou, Parallel and dynamic searchable symmetric encryption, in Financial Cryptography and Data Security (2013), pp. 258\u2013274","DOI":"10.1007\/978-3-642-39884-1_22"},{"key":"9419_CR34","doi-asserted-by":"crossref","unstructured":"K.G. Larsen, J.B. Nielsen, Yes, there is an oblivious RAM lower bound!, in CRYPTO (2018), pp. 523\u2013542","DOI":"10.1007\/978-3-319-96881-0_18"},{"key":"9419_CR35","doi-asserted-by":"crossref","unstructured":"S. Patel, G. Persiano, M. Raykova, K. Yeo, Panorama: Oblivious RAM with logarithmic overhead, in FOCS (2018)","DOI":"10.1109\/FOCS.2018.00087"},{"key":"9419_CR36","doi-asserted-by":"crossref","unstructured":"C. Ruemmler, J. Wilkes, An introduction to disk drive modeling, IEEE Computer, 27(3), 17\u201328 (1994)","DOI":"10.1109\/2.268881"},{"key":"9419_CR37","doi-asserted-by":"crossref","unstructured":"E. Shi, T.-H.H. Chan, E. Stefanov, M. Li, Oblivious RAM with $$O((\\log N)^3)$$ worst-case cost, in ASIACRYPT (2011)","DOI":"10.1007\/978-3-642-25385-0_11"},{"key":"9419_CR38","doi-asserted-by":"crossref","unstructured":"E. Stefanov, M. van Dijk, E. Shi, C. Fletcher, L. Ren, X. Yu, S. Devadas, Path ORAM\u2014an extremely simple oblivious ram protocol, in CCS (2013)","DOI":"10.1145\/2508859.2516660"},{"key":"9419_CR39","doi-asserted-by":"crossref","unstructured":"J.S. Vitter, External memory algorithms and data structures. ACM Comput. Surv. 33(2), 209\u2013271 (2001)","DOI":"10.1145\/384192.384193"},{"key":"9419_CR40","doi-asserted-by":"crossref","unstructured":"J.S. Vitter, Algorithms and data structures for external memory. Foundations and Trends in Theoretical Computer Science 2(4), 305\u2013474 (2006)","DOI":"10.1561\/0400000014"},{"key":"9419_CR41","doi-asserted-by":"crossref","unstructured":"P. Van\u00a0Liesdonk, S. Sedghi, J. Doumen, P. Hartel, W. Jonker, Computationally efficient searchable symmetric encryption, in Workshop on Secure Data Management (Springer, 2010), pp. 87\u2013100","DOI":"10.1007\/978-3-642-15546-8_7"},{"key":"9419_CR42","doi-asserted-by":"crossref","unstructured":"X. Wang, T.-H.H. Chan, E. Shi, Circuit ORAM: On Tightness of the Goldreich-Ostrovsky Lower Bound, in ACM Conference on Computer and Communications Security (ACM, 2015), pp. 850\u2013861","DOI":"10.1145\/2810103.2813634"},{"key":"9419_CR43","doi-asserted-by":"crossref","unstructured":"X.S. Wang, Y. Huang, T.-H.H. Chan, A. Shelat, E. Shi, SCORAM: Oblivious RAM for Secure Computation, in CCS (2014)","DOI":"10.1145\/2660267.2660365"},{"key":"9419_CR44","unstructured":"Wikipedia. Bitonic sorter. https:\/\/en.wikipedia.org\/wiki\/Bitonic_sorter#\/media\/File:BitonicSort1.svg. Online; accessed (August 2021)."},{"key":"9419_CR45","unstructured":"P. Williams, R. Sion, Usable PIR, in Network and Distributed System Security Symposium (NDSS) (2008)"},{"key":"9419_CR46","doi-asserted-by":"crossref","unstructured":"P. Williams, R. Sion, Round-optimal access privacy on outsourced storage, in ACM Conference on Computer and Communication Security (CCS) (2012)","DOI":"10.1145\/2382196.2382229"},{"key":"9419_CR47","doi-asserted-by":"crossref","unstructured":"P. Williams, R. Sion, B. Carbunar, Building castles out of mud: practical access pattern privacy and correctness on untrusted storage, in CCS (2008), pp. 139\u2013148","DOI":"10.1145\/1455770.1455790"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-022-09419-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00145-022-09419-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-022-09419-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,25]],"date-time":"2022-04-25T18:07:14Z","timestamp":1650910034000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00145-022-09419-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,24]]},"references-count":47,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["9419"],"URL":"https:\/\/doi.org\/10.1007\/s00145-022-09419-1","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,24]]},"assertion":[{"value":"20 August 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 December 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 January 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 January 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"6"}}