{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T05:17:13Z","timestamp":1755839833489,"version":"3.40.3"},"reference-count":69,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,11]]},"abstract":"<jats:p>\n            Oblivious map (OMAP) is an important component in encrypted databases, utilized to prevent the server inferring sensitive information about client's encrypted databases based on\n            <jats:italic>access patterns.<\/jats:italic>\n            Despite its widespread usage and importance, existing OMAP solutions face practical challenges, including the need for a large number of interaction rounds between the client and server, as well as substantial communication bandwidth. For example, the SOTA protocol OMIX++ in VLDB 2024 still requires\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            ) interaction rounds and\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) communication bandwidth per access, where\n            <jats:italic>n<\/jats:italic>\n            denotes the total number of key-value pairs stored. In this work, we introduce more practical and efficient OMAP constructions. Consistent with all prior OMAPs, our constructions also adapt only the\n            <jats:italic>tree-based Oblivious RAM (ORAM)<\/jats:italic>\n            and\n            <jats:italic>oblivious data structures<\/jats:italic>\n            (ODS) to achieve OMAP for enhanced practicality. In complexity, our approach needs\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            \/log log\n            <jats:italic>n<\/jats:italic>\n            )+\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>\u03bb<\/jats:italic>\n            ) interaction rounds and\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            \/log log\n            <jats:italic>n<\/jats:italic>\n            ) +\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>\u03bb<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            ) communication bandwidth per data access where\n            <jats:italic>\u03bb<\/jats:italic>\n            is the security parameter. This new complexity results from our two main contributions. First, unlike prior works relying solely on\n            <jats:italic>search trees<\/jats:italic>\n            , we design a novel framework for OMAP that combines\n            <jats:italic>hash table<\/jats:italic>\n            with search trees. Second, we propose a more efficient tree-based ORAM named DAORAM, which is of significant independent interest. This new ORAM accelerates our constructions as it supports obliviously accessing hash tables more efficiently. We implement both our proposed constructions and prior methods to experimentally demonstrate that our constructions substantially outperform prior methods in terms of efficiency.\n          <\/jats:p>","DOI":"10.14778\/3712221.3712235","type":"journal-article","created":{"date-parts":[[2025,4,7]],"date-time":"2025-04-07T18:03:04Z","timestamp":1744048984000},"page":"688-701","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Towards Practical Oblivious Map"],"prefix":"10.14778","volume":"18","author":[{"given":"Xinle","family":"Cao","sequence":"first","affiliation":[{"name":"Zhejiang University"}]},{"given":"Weiqi","family":"Feng","sequence":"additional","affiliation":[{"name":"University of Massachusetts Amherst"}]},{"given":"Jian","family":"Liu","sequence":"additional","affiliation":[{"name":"Zhejiang University"}]},{"given":"Jinjin","family":"Zhou","sequence":"additional","affiliation":[{"name":"Ant Group"}]},{"given":"Wenjing","family":"Fang","sequence":"additional","affiliation":[{"name":"Ant Group"}]},{"given":"Lei","family":"Wang","sequence":"additional","affiliation":[{"name":"Ant Group"}]},{"given":"Quanqing","family":"Xu","sequence":"additional","affiliation":[{"name":"OceanBase, Ant Group"}]},{"given":"Chuanhui","family":"Yang","sequence":"additional","affiliation":[{"name":"OceanBase, Ant Group"}]},{"given":"Kui","family":"Ren","sequence":"additional","affiliation":[{"name":"Zhejiang University"}]}],"member":"320","published-online":{"date-parts":[[2025,4,7]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"ObliDB open-sourced repository. ([n. d.]). https:\/\/github.com\/SabaEskandarian\/ObliDB. Accessed","year":"2024","unstructured":"[n.d.]. ObliDB open-sourced repository. ([n. d.]). https:\/\/github.com\/SabaEskandarian\/ObliDB. Accessed in December 2024."},{"key":"e_1_2_1_2_1","volume-title":"An open-sourced repository for ODS+AVL. ([n. d.]). https:\/\/github.com\/obliviousram\/oblivious-avl-tree. Accessed","year":"2024","unstructured":"[n.d.]. An open-sourced repository for ODS+AVL. ([n. d.]). https:\/\/github.com\/obliviousram\/oblivious-avl-tree. Accessed in December 2024."},{"key":"e_1_2_1_3_1","volume-title":"Python package pycryptodome. ([n. d.]). https:\/\/github.com\/Legrandin\/pycryptodome. Accessed","year":"2024","unstructured":"[n.d.]. Python package pycryptodome. ([n. d.]). https:\/\/github.com\/Legrandin\/pycryptodome. Accessed in December 2024."},{"key":"e_1_2_1_4_1","volume-title":"Advances in Cryptology-EUROCRYPT 2020: 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10--14","author":"Asharov Gilad","year":"2020","unstructured":"Gilad Asharov, Ilan Komargodski, Wei-Kai Lin, Kartik Nayak, Enoch Peserico, and Elaine Shi. 2020. OptORAMa: optimal oblivious RAM. In Advances in Cryptology-EUROCRYPT 2020: 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10--14, 2020, Proceedings, Part II 30. Springer, 403--432."},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2459--2521","author":"Asharov Gilad","year":"2022","unstructured":"Gilad Asharov, Ilan Komargodski, Wei-Kai Lin, Enoch Peserico, and Elaine Shi. 2022. Optimal Oblivious Parallel RAM. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2459--2521."},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1007\/s00145-023-09447-5","article-title":"Oblivious RAM with worst-case logarithmic overhead","volume":"36","author":"Asharov Gilad","year":"2023","unstructured":"Gilad Asharov, Ilan Komargodski, Wei-Kai Lin, and Elaine Shi. 2023. Oblivious RAM with worst-case logarithmic overhead. Journal of Cryptology 36, 2 (2023), 7.","journal-title":"Journal of Cryptology"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security. 837--849","author":"Bindschaedler Vincent","year":"2015","unstructured":"Vincent Bindschaedler, Muhammad Naveed, Xiaorui Pan, XiaoFeng Wang, and Yan Huang. 2015. Practicing oblivious access on cloud storage: the gap, the fallacy, and the new way forward. In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security. 837--849."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 8th ACM SIGSAC symposium on Information, computer and communications security. 207--218","author":"Blanton Marina","year":"2013","unstructured":"Marina Blanton, Aaron Steele, and Mehrdad Alisagari. 2013. Data-oblivious graph algorithms for secure computation and outsourcing. In Proceedings of the 8th ACM SIGSAC symposium on Information, computer and communications security. 207--218."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security. 2262--2276","author":"Bogatov Dmytro","year":"2021","unstructured":"Dmytro Bogatov, Georgios Kellaris, George Kollios, Kobbi Nissim, and Adam O'Neill. 2021. \u03b5psolute: Efficiently Querying Databases While Providing Differential Privacy. In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security. 2262--2276."},{"key":"e_1_2_1_10_1","unstructured":"Xinle Cao Weiqi Feng Jian Liu Jinjin Zhou Wenjing Fang Lei Wang Quanqing Xu Chuanhui Yang and Kui Ren. 2024. Towards Practical Oblivious Map. Cryptology ePrint Archive Paper 2024\/1650. https:\/\/eprint.iacr.org\/2024\/1650"},{"key":"e_1_2_1_11_1","volume-title":"Secure and Practical Functional Dependency Discovery in Outsourced Databases. Cryptology ePrint Archive","author":"Cao Xinle","year":"2023","unstructured":"Xinle Cao, Yuhan Li, Dmytro Bogatov, Jian Liu, and Kui Ren. 2023. Secure and Practical Functional Dependency Discovery in Outsourced Databases. Cryptology ePrint Archive (2023)."},{"key":"e_1_2_1_12_1","volume-title":"Travis Mayberry, Daniel S Roche, and Radu Sion.","author":"Chakraborti Anrin","year":"2019","unstructured":"Anrin Chakraborti, Adam J Aviv, Seung Geol Choi, Travis Mayberry, Daniel S Roche, and Radu Sion. 2019. rORAM: Efficient Range ORAM with O (log2 N) Locality.. In NDSS."},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","first-page":"4324","DOI":"10.14778\/3625054.3625067","article-title":"GraphOS: Towards Oblivious Graph Processing","volume":"16","author":"Chamani Javad Ghareh","year":"2023","unstructured":"Javad Ghareh Chamani, Ioannis Demertzis, Dimitrios Papadopoulos, Charalampos Papamanthou, and Rasool Jalili. 2023. GraphOS: Towards Oblivious Graph Processing. Proc. VLDB Endow. 16 (2023), 4324--4338. https:\/\/api.semanticscholar.org\/CorpusID:265455667","journal-title":"Proc. VLDB Endow."},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2201--2220","author":"Hubert Chan TH","year":"2018","unstructured":"TH Hubert Chan, Yue Guo, Wei-Kai Lin, and Elaine Shi. 2018. Cache-oblivious and data-oblivious sorting and applications. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2201--2220."},{"key":"e_1_2_1_15_1","volume-title":"Advances in Cryptology-ASIACRYPT 2017: 23rd International Conference on the Theory and Applications of Cryptology and Information Security","author":"Hubert Chan T-H","year":"2017","unstructured":"T-H Hubert Chan, Yue Guo, Wei-Kai Lin, and Elaine Shi. 2017. Oblivious hashing revisited, and applications to asymptotically efficient ORAM and OPRAM. In Advances in Cryptology-ASIACRYPT 2017: 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3-7, 2017, Proceedings, Part I 23. Springer, 660--690."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2021.3060757"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 2022 International Conference on Management of Data. 803--817","author":"Chang Zhao","year":"2022","unstructured":"Zhao Chang, Dong Xie, Sheng Wang, and Feifei Li. 2022. Towards Practical Oblivious Join. In Proceedings of the 2022 International Conference on Management of Data. 803--817."},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security. 345--360","author":"Chen Hao","year":"2019","unstructured":"Hao Chen, Ilaria Chillotti, and Ling Ren. 2019. Onion ring ORAM: efficient constant bandwidth oblivious RAM from (leveled) TFHE. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security. 345--360."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 2017 ACM on Asia Conference on Computer and Communications Security (Abu Dhabi, United Arab Emirates) (ASIA CCS '17). Association for Computing Machinery","author":"Chen Sanchuan","year":"2017","unstructured":"Sanchuan Chen, Xiaokuan Zhang, Michael K. Reiter, and Yinqian Zhang. 2017. Detecting Privileged Side-Channel Attacks in Shielded Execution with D\u00e9j\u00e0 Vu. In Proceedings of the 2017 ACM on Asia Conference on Computer and Communications Security (Abu Dhabi, United Arab Emirates) (ASIA CCS '17). Association for Computing Machinery, New York, NY, USA, 7--18. 10.1145\/3052973.3053007"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security. 2277--2291","author":"Choi Seung Geol","year":"2021","unstructured":"Seung Geol Choi, Dana Dachman-Soled, S Dov Gordon, Linsheng Liu, and Arkady Yerukhimovich. 2021. Compressed oblivious encoding for homomorphically encrypted search. In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security. 2277--2291."},{"key":"e_1_2_1_21_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","unstructured":"Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms, Third Edition (3rd ed.). The MIT Press.","edition":"3"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles. 655--671","author":"Dauterman Emma","year":"2021","unstructured":"Emma Dauterman, Vivian Fang, Ioannis Demertzis, Natacha Crooks, and Raluca Ada Popa. 2021. Snoopy: Surpassing the scalability bottleneck of oblivious storage. In Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles. 655--671."},{"key":"e_1_2_1_23_1","volume-title":"Dimitrios Papadopoulos, and Charalampos Papamanthou.","author":"Demertzis Ioannis","year":"2019","unstructured":"Ioannis Demertzis, Javad Ghareh Chamani, Dimitrios Papadopoulos, and Charalampos Papamanthou. 2019. Dynamic searchable encryption with small client storage. Cryptology ePrint Archive (2019)."},{"key":"e_1_2_1_24_1","volume-title":"Oblidb: Oblivious query processing for secure databases. arXiv preprint arXiv:1710.00458","author":"Eskandarian Saba","year":"2017","unstructured":"Saba Eskandarian and Matei Zaharia. 2017. Oblidb: Oblivious query processing for secure databases. arXiv preprint arXiv:1710.00458 (2017)."},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","first-page":"587","DOI":"10.14778\/3574245.3574247","article-title":"Range Search over Encrypted Multi-Attribute Data","volume":"16","author":"Falzon Francesca","year":"2022","unstructured":"Francesca Falzon, Evangelia Anna Markatou, Zachary Espiritu, and Roberto Tamassia. 2022. Range Search over Encrypted Multi-Attribute Data. Proc. VLDB Endow. 16 (2022), 587--600. https:\/\/api.semanticscholar.org\/CorpusID:252545892","journal-title":"Proc. VLDB Endow."},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the Twentieth International Conference on Architectural Support for Programming Languages and Operating Systems. 103--116","author":"Fletcher Christopher W","year":"2015","unstructured":"Christopher W Fletcher, Ling Ren, Albert Kwon, Marten Van Dijk, and Srinivas Devadas. 2015. Freecursive ORAM: [Nearly] Free Recursion and Integrity Verification for Position-based Oblivious RAM. In Proceedings of the Twentieth International Conference on Architectural Support for Programming Languages and Operating Systems. 103--116."},{"key":"e_1_2_1_27_1","volume-title":"2014 IEEE 20th International Symposium on High Performance Computer Architecture (HPCA). 213--224","author":"Fletchery Christopher W.","year":"2014","unstructured":"Christopher W. Fletchery, Ling Ren, Xiangyao Yu, Marten Van Dijk, Omer Khan, and Srinivas Devadas. 2014. Suppressing the Oblivious RAM timing channel while making information leakage and program efficiency trade-offs. In 2014 IEEE 20th International Symposium on High Performance Computer Architecture (HPCA). 213--224. 10.1109\/HPCA.2014.6835932"},{"key":"e_1_2_1_28_1","volume-title":"Annual International Cryptology Conference. Springer, 563--592","author":"Garg Sanjam","year":"2016","unstructured":"Sanjam Garg, Payman Mohassel, and Charalampos Papamanthou. 2016. TWORAM: Efficient oblivious RAM in two rounds with applications to searchable encryption. In Annual International Cryptology Conference. Springer, 563--592."},{"key":"e_1_2_1_29_1","volume-title":"Privacy Enhancing Technologies: 13th International Symposium, PETS 2013, Bloomington, IN, USA, July 10-12, 2013. Proceedings 13","author":"Gentry Craig","year":"2013","unstructured":"Craig Gentry, Kenny A Goldman, Shai Halevi, Charanjit Julta, Mariana Raykova, and Daniel Wichs. 2013. Optimizing ORAM and using it efficiently for secure computation. In Privacy Enhancing Technologies: 13th International Symposium, PETS 2013, Bloomington, IN, USA, July 10-12, 2013. Proceedings 13. Springer, 1--18."},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. 1038--1055","author":"Chamani Javad Ghareh","year":"2018","unstructured":"Javad Ghareh Chamani, Dimitrios Papadopoulos, Charalampos Papamanthou, and Rasool Jalili. 2018. New constructions for forward and backward private symmetric searchable encryption. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. 1038--1055."},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1145\/233551.233553","article-title":"Software protection and simulation on oblivious RAMs","volume":"43","author":"Goldreich Oded","year":"1996","unstructured":"Oded Goldreich and Rafail Ostrovsky. 1996. Software protection and simulation on oblivious RAMs. Journal of the ACM (JACM) 43, 3 (1996), 431--473.","journal-title":"Journal of the ACM (JACM)"},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2049697.2049701","article-title":"Randomized shellsort: A simple data-oblivious sorting algorithm","volume":"58","author":"Goodrich Michael T","year":"2011","unstructured":"Michael T Goodrich. 2011. Randomized shellsort: A simple data-oblivious sorting algorithm. Journal of the ACM (JACM) 58, 6 (2011), 1--26.","journal-title":"Journal of the ACM (JACM)"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 3rd ACM Workshop on Cloud Computing Security Workshop","author":"Goodrich Michael T.","year":"2011","unstructured":"Michael T. Goodrich, Michael Mitzenmacher, Olga Ohrimenko, and Roberto Tamassia. 2011. Oblivious RAM simulation with efficient worst-case access overhead. In Proceedings of the 3rd ACM Workshop on Cloud Computing Security Workshop (Chicago, Illinois, USA) (CCSW '11). Association for Computing Machinery, New York, NY, USA, 95--100. 10.1145\/2046660.2046680"},{"key":"e_1_2_1_34_1","volume-title":"29th USENIX Security Symposium (USENIX Security 20)","author":"Grubbs Paul","year":"2020","unstructured":"Paul Grubbs, Anurag Khandelwal, Marie-Sarah Lacharit\u00e9, Lloyd Brown, Lucy Li, Rachit Agarwal, and Thomas Ristenpart. 2020. Pancake: Frequency smoothing for encrypted data stores. In 29th USENIX Security Symposium (USENIX Security 20). 2451--2468."},{"key":"e_1_2_1_35_1","volume-title":"26th USENIX Security Symposium (USENIX Security 17)","author":"Gruss Daniel","year":"2017","unstructured":"Daniel Gruss, Julian Lettner, Felix Schuster, Olya Ohrimenko, Istvan Haller, and Manuel Costa. 2017. Strong and Efficient Cache Side-Channel Protection using Hardware Transactional Memory. In 26th USENIX Security Symposium (USENIX Security 17). USENIX Association, Vancouver, BC, 217--233. https:\/\/www.usenix.org\/conference\/usenixsecurity17\/technical-sessions\/presentation\/gruss"},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","first-page":"598","DOI":"10.1109\/TCC.2018.2879104","article-title":"Efficient oblivious data structures for database services on the cloud","volume":"9","author":"Hoang Thang","year":"2018","unstructured":"Thang Hoang, Ceyhun D Ozkaptan, Gabriel Hackebeil, and Attila Altay Yavuz. 2018. Efficient oblivious data structures for database services on the cloud. IEEE Transactions on Cloud Computing 9, 2 (2018), 598--609.","journal-title":"IEEE Transactions on Cloud Computing"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCC.2018.2879104"},{"key":"e_1_2_1_38_1","doi-asserted-by":"crossref","first-page":"172","DOI":"10.2478\/popets-2019-0010","article-title":"Hardware-Supported ORAM in Effect: Practical Oblivious Search and Update on Very Large Dataset","volume":"2019","author":"Hoang Thang","year":"2018","unstructured":"Thang Hoang, Muslum Ozgur Ozmen, Yeongjin Jang, and Attila Altay Yavuz. 2018. Hardware-Supported ORAM in Effect: Practical Oblivious Search and Update on Very Large Dataset. Proceedings on Privacy Enhancing Technologies 2019 (2018), 172 -- 191. https:\/\/api.semanticscholar.org\/CorpusID:4007767","journal-title":"Proceedings on Privacy Enhancing Technologies"},{"key":"e_1_2_1_39_1","volume-title":"Theory of Cryptography Conference. Springer, 72--107","author":"Hubert Chan T-H","year":"2017","unstructured":"T-H Hubert Chan and Elaine Shi. 2017. Circuit OPRAM: Unifying statistically and computationally secure ORAMs and OPRAMs. In Theory of Cryptography Conference. Springer, 72--107."},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2439--2447","author":"Jacob Riko","year":"2019","unstructured":"Riko Jacob, Kasper Green Larsen, and Jesper Buus Nielsen. 2019. Lower bounds for oblivious data structures. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2439--2447."},{"key":"e_1_2_1_41_1","doi-asserted-by":"crossref","DOI":"10.1201\/b17668","volume-title":"Introduction to Modern Cryptography. (No Title)","author":"Katz Jonathan","year":"2014","unstructured":"Jonathan Katz and Yehuda Lindell. 2014. Introduction to Modern Cryptography. (No Title) (2014)."},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. 1329--1340","author":"Kellaris Georgios","year":"2016","unstructured":"Georgios Kellaris, George Kollios, Kobbi Nissim, and Adam O'neill. 2016. Generic attacks on secure outsourced databases. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. 1329--1340."},{"key":"e_1_2_1_43_1","volume-title":"Advances in Cryptology-ASIACRYPT 2014: 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung","author":"Keller Marcel","year":"2014","unstructured":"Marcel Keller and Peter Scholl. 2014. Efficient, oblivious data structures for MPC. In Advances in Cryptology-ASIACRYPT 2014: 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, ROC, December 7-11, 2014, Proceedings, Part II 20. Springer, 506--525."},{"key":"e_1_2_1_44_1","volume-title":"Efficient oblivious database joins. arXiv preprint arXiv:2003.09481","author":"Krastnikov Simeon","year":"2020","unstructured":"Simeon Krastnikov, Florian Kerschbaum, and Douglas Stebila. 2020. Efficient oblivious database joins. arXiv preprint arXiv:2003.09481 (2020)."},{"key":"e_1_2_1_45_1","volume-title":"Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms. SIAM, 143--156","author":"Kushilevitz Eyal","year":"2012","unstructured":"Eyal Kushilevitz, Steve Lu, and Rafail Ostrovsky. 2012. On the (in) security of hash-based oblivious RAM and a new balancing scheme. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms. SIAM, 143--156."},{"key":"e_1_2_1_46_1","volume-title":"2018 IEEE Symposium on Security and Privacy (SP). IEEE, 297--314","author":"Lacharit\u00e9 Marie-Sarah","year":"2018","unstructured":"Marie-Sarah Lacharit\u00e9, Brice Minaud, and Kenneth G Paterson. 2018. Improved reconstruction attacks on encrypted data using range query leakage. In 2018 IEEE Symposium on Security and Privacy (SP). IEEE, 297--314."},{"key":"e_1_2_1_47_1","volume-title":"Annual International Cryptology Conference. Springer, 523--542","author":"Larsen Kasper Green","year":"2018","unstructured":"Kasper Green Larsen and Jesper Buus Nielsen. 2018. Yes, there is an oblivious RAM lower bound!. In Annual International Cryptology Conference. Springer, 523--542."},{"key":"e_1_2_1_48_1","volume-title":"2018 IEEE Symposium on Security and Privacy (SP). IEEE, 279--296","author":"Mishra Pratyush","year":"2018","unstructured":"Pratyush Mishra, Rishabh Poddar, Jerry Chen, Alessandro Chiesa, and Raluca Ada Popa. 2018. Oblix: An efficient oblivious search index. In 2018 IEEE Symposium on Security and Privacy (SP). IEEE, 279--296."},{"key":"e_1_2_1_49_1","unstructured":"Muhammad Naveed. 2015. The Fallacy of Composition of Oblivious RAM and Searchable Encryption. Cryptology ePrint Archive Paper 2015\/668. https:\/\/eprint.iacr.org\/2015\/668"},{"key":"e_1_2_1_50_1","unstructured":"Rafail Ostrovsky and Victor Shoup. 1996. Private Information Storage. Cryptology ePrint Archive Paper 1996\/005. https:\/\/eprint.iacr.org\/1996\/005 https:\/\/eprint.iacr.org\/1996\/005."},{"key":"e_1_2_1_51_1","volume-title":"30th USENIX security symposium (USENIX Security 21). 127--142.","author":"Oya Simon","unstructured":"Simon Oya and Florian Kerschbaum. 2021. Hiding the access pattern is not enough: Exploiting search pattern leakage in searchable encryption. In 30th USENIX security symposium (USENIX Security 21). 127--142."},{"key":"e_1_2_1_52_1","volume-title":"2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 871--882","author":"Patel Sarvar","year":"2018","unstructured":"Sarvar Patel, Giuseppe Persiano, Mariana Raykova, and Kevin Yeo. 2018. PanORAMa: Oblivious RAM with logarithmic overhead. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 871--882."},{"key":"e_1_2_1_53_1","volume-title":"Advances in Cryptology-CRYPTO 2010: 30th Annual Cryptology Conference","author":"Pinkas Benny","year":"2010","unstructured":"Benny Pinkas and Tzachy Reinman. 2010. Oblivious RAM revisited. In Advances in Cryptology-CRYPTO 2010: 30th Annual Cryptology Conference, Santa Barbara, CA, USA, August 15-19, 2010. Proceedings 30. Springer, 502--519."},{"key":"e_1_2_1_54_1","volume-title":"Proceedings of the Second International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM '98)","author":"Raab Martin","year":"1998","unstructured":"Martin Raab and Angelika Steger. 1998. \"Balls into Bins\" - A Simple and Tight Analysis. In Proceedings of the Second International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM '98). Springer-Verlag, Berlin, Heidelberg, 159--170."},{"key":"e_1_2_1_55_1","volume-title":"24th USENIX Security Symposium (USENIX Security 15)","author":"Ren Ling","year":"2015","unstructured":"Ling Ren, Christopher Fletcher, Albert Kwon, Emil Stefanov, Elaine Shi, Marten Van Dijk, and Srinivas Devadas. 2015. Constants count: Practical improvements to oblivious {RAM}. In 24th USENIX Security Symposium (USENIX Security 15). 415--430."},{"key":"e_1_2_1_56_1","volume-title":"2016 IEEE Symposium on Security and Privacy (SP). IEEE, 178--197","author":"Roche Daniel S","year":"2016","unstructured":"Daniel S Roche, Adam Aviv, and Seung Geol Choi. 2016. A practical oblivious map data structure with secure deletion and history independence. In 2016 IEEE Symposium on Security and Privacy (SP). IEEE, 178--197."},{"key":"e_1_2_1_57_1","volume-title":"Oblivious sampling algorithms for private data analysis. Advances in Neural Information Processing Systems 32","author":"Sasy Sajin","year":"2019","unstructured":"Sajin Sasy and Olga Ohrimenko. 2019. Oblivious sampling algorithms for private data analysis. Advances in Neural Information Processing Systems 32 (2019)."},{"key":"e_1_2_1_58_1","volume-title":"2020 IEEE Symposium on Security and Privacy (SP). IEEE, 842--858","author":"Shi Elaine","year":"2020","unstructured":"Elaine Shi. 2020. Path oblivious heap: Optimal and practical oblivious priority queue. In 2020 IEEE Symposium on Security and Privacy (SP). IEEE, 842--858."},{"key":"e_1_2_1_59_1","volume-title":"Advances in Cryptology - ASIACRYPT","author":"Shi Elaine","year":"2011","unstructured":"Elaine Shi, T. H. Hubert Chan, Emil Stefanov, and Mingfei Li. 2011. Oblivious RAM with O((logN)3) Worst-Case Cost. In Advances in Cryptology - ASIACRYPT 2011, Dong Hoon Lee and Xiaoyun Wang (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 197--214."},{"key":"e_1_2_1_60_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3177872","article-title":"Path ORAM: an extremely simple oblivious RAM protocol","volume":"65","author":"Stefanov Emil","year":"2018","unstructured":"Emil Stefanov, Marten van Dijk, Elaine Shi, T-H Hubert Chan, Christopher Fletcher, Ling Ren, Xiangyao Yu, and Srinivas Devadas. 2018. Path ORAM: an extremely simple oblivious RAM protocol. Journal of the ACM (JACM) 65, 4 (2018), 1--26.","journal-title":"Journal of the ACM (JACM)"},{"key":"e_1_2_1_61_1","volume-title":"Towards practical oblivious RAM. arXiv preprint arXiv:1106.3652","author":"Stefanov Emil","year":"2011","unstructured":"Emil Stefanov, Elaine Shi, and Dawn Song. 2011. Towards practical oblivious RAM. arXiv preprint arXiv:1106.3652 (2011)."},{"key":"e_1_2_1_62_1","unstructured":"Afonso Tinoco Sixiang Gao and Elaine Shi. 2022. Enigmap : External-Memory Oblivious Map for Secure Enclaves. Cryptology ePrint Archive Paper 2022\/1083. https:\/\/eprint.iacr.org\/2022\/1083 https:\/\/eprint.iacr.org\/2022\/1083."},{"key":"e_1_2_1_63_1","volume-title":"Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security. 850--861","author":"Wang Xiao","year":"2015","unstructured":"Xiao Wang, Hubert Chan, and Elaine Shi. 2015. Circuit oram: On tightness of the goldreich-ostrovsky lower bound. In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security. 850--861."},{"key":"e_1_2_1_64_1","volume-title":"Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security. 215--226","author":"Wang Xiao Shaun","year":"2014","unstructured":"Xiao Shaun Wang, Kartik Nayak, Chang Liu, TH Hubert Chan, Elaine Shi, Emil Stefanov, and Yan Huang. 2014. Oblivious data structures. In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security. 215--226."},{"key":"e_1_2_1_65_1","volume-title":"Proceedings of the 2012 ACM conference on Computer and communications security. 293--304","author":"Williams Peter","year":"2012","unstructured":"Peter Williams and Radu Sion. 2012. Single round access privacy on outsourced storage. In Proceedings of the 2012 ACM conference on Computer and communications security. 293--304."},{"key":"e_1_2_1_66_1","unstructured":"Zhiqiang Wu and Rui Li. 2023. OBI: a multi-path oblivious RAM for forward-and-backward-secure searchable encryption.. In NDSS."},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.14778\/3611540.3611560"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.14778\/3554821.3554830"},{"key":"e_1_2_1_69_1","volume-title":"14th USENIX Symposium on Networked Systems Design and Implementation (NSDI 17)","author":"Zheng Wenting","year":"2017","unstructured":"Wenting Zheng, Ankur Dave, Jethro G Beekman, Raluca Ada Popa, Joseph E Gonzalez, and Ion Stoica. 2017. Opaque: An oblivious and encrypted distributed analytics platform. In 14th USENIX Symposium on Networked Systems Design and Implementation (NSDI 17). 283--298."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3712221.3712235","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,7]],"date-time":"2025-04-07T18:56:07Z","timestamp":1744052167000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3712221.3712235"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11]]},"references-count":69,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,11]]}},"alternative-id":["10.14778\/3712221.3712235"],"URL":"https:\/\/doi.org\/10.14778\/3712221.3712235","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,11]]},"assertion":[{"value":"2025-04-07","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}