{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,11]],"date-time":"2026-08-11T09:27:56Z","timestamp":1786440476805,"version":"build-2736575974"},"publisher-location":"Cham","reference-count":48,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032354174","type":"print"},{"value":"9783032354181","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"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":[[2026]]},"DOI":"10.1007\/978-3-032-35418-1_11","type":"book-chapter","created":{"date-parts":[[2026,8,11]],"date-time":"2026-08-11T08:31:50Z","timestamp":1786437110000},"page":"329-360","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Oblivious Priority Queue and Single-Source Shortest Path in the External Memory Setting"],"prefix":"10.1007","author":[{"given":"Arya","family":"Maheshwari","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Elaine","family":"Shi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,8,12]]},"reference":[{"key":"11_CR1","unstructured":"Meta\u2019s ORAM implementation. https:\/\/github.com\/facebook\/oram"},{"key":"11_CR2","unstructured":"Oblivious STL library. https:\/\/github.com\/obliviouslabs\/rostl"},{"key":"11_CR3","unstructured":"Technology deep dive: Building a faster ORAM layer for enclaves. https:\/\/signal.org\/blog\/building-faster-oram\/"},{"key":"11_CR4","doi-asserted-by":"crossref","unstructured":"Aggarwal, A., Vitter, Jeffrey, S.: The input\/output complexity of sorting and related problems. Commun. ACM 31(9), 1116\u20131127 (1988)","DOI":"10.1145\/48529.48535"},{"key":"11_CR5","doi-asserted-by":"crossref","unstructured":"Appan, A., Heath, D., Ren, L.: Oblivious single access machines - a new model for oblivious computation. In: ACM CCS (2024), pp. 3080\u20133094. Association for Computing Machinery, New York, NY, USA (2024)","DOI":"10.1145\/3658644.3690352"},{"key":"11_CR6","doi-asserted-by":"crossref","unstructured":"Asharov, G., Chan, T.H.H., Nayak, K., Pass, R., Ren, L., Shi, E.: Bucket oblivious sort: an extremely simple oblivious sort. In: SOSA, pp. 8\u201314 (2020)","DOI":"10.1137\/1.9781611976014.2"},{"key":"11_CR7","doi-asserted-by":"crossref","unstructured":"Asharov, G., Eiluz, E., Komargodski, I., Lin, W.K.: MegaBlocks: beaking the logarithmic i\/o-overhead barrier for oblivious RAM. In: ACM CCS (2025)","DOI":"10.1145\/3719027.3765159"},{"key":"11_CR8","doi-asserted-by":"crossref","unstructured":"Asharov, G., Komargodski, I., Lin, W.K., Nayak, K., Peserico, E., Shi, E.: OptORAMa: optimal Oblivious RAM. In: Advances in Cryptology - EUROCRYPT 2020 (2020), to appear. See also: https:\/\/eprint.iacr.org\/2018\/892","DOI":"10.1007\/978-3-030-45724-2_14"},{"key":"11_CR9","doi-asserted-by":"crossref","unstructured":"Asharov, G., Komargodski, I., Lin, W.K., Peserico, E., Shi, E.: Optimal oblivious parallel RAM. In: Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2459\u20132521 (2022)","DOI":"10.1137\/1.9781611977073.98"},{"key":"11_CR10","doi-asserted-by":"crossref","unstructured":"Blanton, M., Steele, A., Alisagari, M.: Data-oblivious graph algorithms for secure computation and outsourcing. In: ASIA CCS (2013)","DOI":"10.1145\/2484313.2484341"},{"issue":"4","key":"11_CR11","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1016\/S0022-0000(73)80033-9","volume":"7","author":"M Blum","year":"1973","unstructured":"Blum, M., Floyd, R.W., Pratt, V., Rivest, R.L., Tarjan, R.E.: Time bounds for selection. J. Comput. Syst. Sci. 7(4), 448\u2013461 (1973)","journal-title":"J. Comput. Syst. Sci."},{"key":"11_CR12","unstructured":"Boyle, E., Chung, K.M., Pass, R.: Oblivious parallel RAM. In: Theory of Cryptography Conference (TCC) (2015)"},{"key":"11_CR13","unstructured":"Buterin, V.: A maximally simple l1 privacy roadmap. https:\/\/ethereum-magicians.org\/t\/a-maximally-simple-l1-privacy-roadmap\/23459"},{"key":"11_CR14","doi-asserted-by":"crossref","unstructured":"Canetti, R.: Security and composition of multiparty cryptographic protocols. J. Cryptol. (2000)","DOI":"10.1007\/s001459910006"},{"key":"11_CR15","doi-asserted-by":"publisher","unstructured":"Chan, T.H.H., Chung, K.M., Shi, E.: On the depth of oblivious parallel RAM. In: Takagi, T., Peyrin, T. (eds.) Advances in Cryptology - ASIACRYPT 2017 - 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3\u20137, 2017, Proceedings, Part I. Lecture Notes in Computer Science, vol. 10624, pp. 567\u2013597. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-70694-8_20","DOI":"10.1007\/978-3-319-70694-8_20"},{"key":"11_CR16","doi-asserted-by":"crossref","unstructured":"Chowdhury, R.A., Ramachandran, V.: Cache-oblivious shortest paths in graphs using buffer heap. In: SPAA \u201904, pp. 245\u2013254. Association for Computing Machinery, New York, NY, USA (2004)","DOI":"10.1145\/1007912.1007949"},{"key":"11_CR17","unstructured":"Demaine, E.D.: Cache-oblivious algorithms and data structures. In: Lecture Notes from the EEF Summer School on Massive Data Sets. BRICS, University of Aarhus, Denmark (2002)"},{"key":"11_CR18","doi-asserted-by":"crossref","unstructured":"Demme, J., Martin, R., Waksman, A., Sethumadhavan, S.: Side-channel vulnerability factor: a metric for measuring information leakage. In: International Symposium on Computer Architecture (ISCA) (2012)","DOI":"10.1109\/ISCA.2012.6237010"},{"key":"11_CR19","doi-asserted-by":"crossref","unstructured":"Dijkstra, E.W.: A note on two problems in connexion with graphs. Numer. Math. 1(1), 269\u2013271 (1959)","DOI":"10.1007\/BF01386390"},{"issue":"1","key":"11_CR20","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/BF01683268","volume":"10","author":"P van Emde Boas","year":"1976","unstructured":"van Emde Boas, P., Kaas, R., Zijlstra, E.: Design and implementation of an efficient priority queue. Theory Comput. Syst. 10(1), 99\u2013127 (1976)","journal-title":"Theory Comput. Syst."},{"key":"11_CR21","doi-asserted-by":"crossref","unstructured":"Farhadi, A., Hajiaghayi, M., Larsen, K.G., Shi, E.: Lower bounds for external memory integer sorting via network coding. In: STOC (2019)","DOI":"10.1145\/3313276.3316337"},{"key":"11_CR22","doi-asserted-by":"crossref","unstructured":"Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34(3), 596 615 (1987)","DOI":"10.1145\/28869.28874"},{"key":"11_CR23","doi-asserted-by":"crossref","unstructured":"Frigo, M., Leiserson, C., Prokop, H., Ramachandran, S.: Cache-oblivious algorithms. In: FOCS\u201999, pp. 285\u2013297 (1999)","DOI":"10.1109\/SFFCS.1999.814600"},{"key":"11_CR24","doi-asserted-by":"crossref","unstructured":"Goldreich, O.: Towards a theory of software protection and simulation by oblivious RAMs. In: STOC (1987)","DOI":"10.1145\/28395.28416"},{"key":"11_CR25","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":"11_CR26","doi-asserted-by":"crossref","unstructured":"Goodrich, M.T., Mitzenmacher, M., Ohrimenko, O., Tamassia, R.: Practical oblivious storage. In: Proceedings of the Second ACM Conference on Data and Application Security and Privacy, CODASPY \u201912, pp. 13\u201324. Association for Computing Machinery, New York, NY, USA (2012)","DOI":"10.1145\/2133601.2133604"},{"key":"11_CR27","doi-asserted-by":"crossref","unstructured":"Goodrich, M.T., Mitzenmacher, M., Ohrimenko, O., Tamassia, R.: Privacy-preserving group data access via stateless oblivious ram simulation. In: SODA \u201912, pp. 157\u2013167. SIAM (2012)","DOI":"10.1137\/1.9781611973099.14"},{"key":"11_CR28","doi-asserted-by":"crossref","unstructured":"Gordon, S.D., et al.: Secure two-party computation in sublinear (amortized) time. In: CCS (2012)","DOI":"10.1145\/2382196.2382251"},{"key":"11_CR29","unstructured":"Gu, T., Wang, Y., Tinoco, A., Chen, B., Yi, K., Shi, E.: Flexway O-sort: enclave-friendly and optimal oblivious sorting. Cryptology ePrint Archive, Paper 2023\/1258 (2023)"},{"key":"11_CR30","doi-asserted-by":"crossref","unstructured":"Jacob, R., Larsen, K.G., Nielsen, J.B.: Lower bounds for oblivious data structures. In: SODA (2019)","DOI":"10.1137\/1.9781611975482.149"},{"key":"11_CR31","doi-asserted-by":"crossref","unstructured":"Jafargholi, Z., Larsen, K.G., Simkin, M.: Optimal oblivious priority queues. In: SODA\u201921, pp. 2366\u20132383. Society for Industrial and Applied Mathematics, USA (2021)","DOI":"10.1137\/1.9781611976465.141"},{"key":"11_CR32","doi-asserted-by":"crossref","unstructured":"Jiang, S., Larsen, K.G.: A faster external memory priority queue with decreasekeys. In: SODA\u201919, pp. 1331\u20131343 (2019)","DOI":"10.1137\/1.9781611975482.81"},{"key":"11_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1007\/3-540-36574-5_4","volume-title":"Algorithms for Memory Hierarchies","author":"I Katriel","year":"2003","unstructured":"Katriel, I., Meyer, U.: Elementary graph algorithms in external memory. In: Meyer, U., Sanders, P., Sibeyn, J. (eds.) Algorithms for Memory Hierarchies. LNCS, vol. 2625, pp. 62\u201384. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/3-540-36574-5_4"},{"key":"11_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1007\/978-3-030-84259-8_20","volume-title":"Advances in Cryptology \u2013 CRYPTO 2021","author":"I Komargodski","year":"2021","unstructured":"Komargodski, I., Lin, W.-K.: A logarithmic lower bound for oblivious RAM (for all parameters). In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12828, pp. 579\u2013609. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-84259-8_20"},{"key":"11_CR35","doi-asserted-by":"crossref","unstructured":"Kumar, V., Schwabe, E.: Improved algorithms and data structures for solving graph problems in external memory. In: Proceedings of SPDP \u201996: 8th IEEE Symposium on Parallel and Distributed Processing, pp. 169\u2013176 (1996)","DOI":"10.1109\/SPDP.1996.570330"},{"key":"11_CR36","doi-asserted-by":"crossref","unstructured":"Larsen, K.G., Nielsen, J.B.: Yes, there is an oblivious RAM lower bound! In: CRYPTO (2018)","DOI":"10.1007\/978-3-319-96881-0_18"},{"key":"11_CR37","doi-asserted-by":"crossref","unstructured":"Lin, W., Shi, E., Xie, T.: Can we overcome the $$n \\log n$$ barrier for oblivious sorting? In: SODA (2019)","DOI":"10.1137\/1.9781611975482.148"},{"key":"11_CR38","doi-asserted-by":"crossref","unstructured":"Liu, C., Wang, X.S., Nayak, K., Huang, Y., Shi, E.: ObliVM: a programming framework for secure computation. In: Proceedings of the 2015 IEEE Symposium on Security and Privacy, SP \u201915, pp. 359\u2013376. IEEE Computer Society, USA (2015)","DOI":"10.1109\/SP.2015.29"},{"key":"11_CR39","doi-asserted-by":"crossref","unstructured":"Mishra, P., Poddar, R., Chen, J., Chiesa, A., Popa, R.A.: Oblix: an efficient oblivious search index. In: IEEE S&P, pp. 279\u2013296 (2018)","DOI":"10.1109\/SP.2018.00045"},{"key":"11_CR40","doi-asserted-by":"publisher","unstructured":"Ostrovsky, B.: Privacy-preserving Dijkstra. In: Reyzin, L., Stebila, D. (eds.) Advances in Cryptology CRYPTO 2024: 44th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18\u201322, 2024, Proceedings, Part IX, pp. 74\u2013110. Springer-Verlag, Berlin, Heidelberg (2024). https:\/\/doi.org\/10.1007\/978-3-031-68400-5_3","DOI":"10.1007\/978-3-031-68400-5_3"},{"key":"11_CR41","doi-asserted-by":"crossref","unstructured":"Ramachandran, V., Shi, E.: Data oblivious algorithms for multicores. In: SPAA \u201921, pp. 373\u2013384. Association for Computing Machinery, New York, NY, USA (2021)","DOI":"10.1145\/3409964.3461783"},{"key":"11_CR42","unstructured":"Ren, L., et al.: Constants count: practical improvements to oblivious RAM. In: USENIX Security (2015)"},{"key":"11_CR43","doi-asserted-by":"crossref","unstructured":"Ristenpart, T., Tromer, E., Shacham, H., Savage, S.: Hey, you, get off of my cloud: exploring information leakage in third-party compute clouds. In: ACM CCS, pp. 199\u2013212. ACM, New York, NY, USA (2009)","DOI":"10.1145\/1653662.1653687"},{"key":"11_CR44","doi-asserted-by":"crossref","unstructured":"Shi, E.: Path oblivious heap: optimal and practical oblivious priority queue. In: IEEE S&P \u201920, pp. 842\u2013858 (2020)","DOI":"10.1109\/SP40000.2020.00037"},{"key":"11_CR45","doi-asserted-by":"crossref","unstructured":"Stefanov, E., Shi, E.: ObliviStore: high performance oblivious cloud storage. In: S & P (2013)","DOI":"10.1109\/SP.2013.25"},{"key":"11_CR46","unstructured":"Tinoco, A., Gao, S., Shi, E.: EnigMap: external-memory oblivious map for secure enclaves. In: USENIX Security, pp. 4033\u20134050 (2023)"},{"key":"11_CR47","unstructured":"Wang, X.S., et al.: Oblivious data structures. In: CCS \u201914. Association for Computing Machinery, New York, NY, USA (2014)"},{"key":"11_CR48","doi-asserted-by":"crossref","unstructured":"Xu, Y., Cui, W., Peinado, M.: Controlled-channel attacks: deterministic side channels for untrusted operating systems. In: IEEE S&P\u201915, pp. 640\u2013656 (2015)","DOI":"10.1109\/SP.2015.45"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 CRYPTO 2026"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-35418-1_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,11]],"date-time":"2026-08-11T08:32:21Z","timestamp":1786437141000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-35418-1_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032354174","9783032354181"],"references-count":48,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-35418-1_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"12 August 2026","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":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 August 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 August 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"46","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"crypto2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/crypto.iacr.org\/2026\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}