{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T18:08:07Z","timestamp":1757614087197,"version":"3.44.0"},"reference-count":75,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2025,7]]},"abstract":"<jats:p>We present OasisDB, an oblivious and scalable RDBMS framework designed to securely manage relational data while protecting against access and volume pattern attacks. Inspired by plaintext RDBMSs, OasisDB leverages existing oblivious key value stores (KV-stores) as storage engines and securely scales them to enhance performance. Its novel multi-tier architecture allows for independent scaling of each tier while supporting multi-user environments without compromising privacy. We demonstrate OasisDB's flexibility by deploying it with two distinct oblivious KV-stores, PathORAM and Waffle, and show its capability to execute a variety of SQL queries, including point and range queries, joins, aggregations, and (limited) updates. Experimental evaluations on the Epinions dataset show that OasisDB scales linearly with the number of machines. When deployed with a plaintext KV-store, OasisDB introduces negligible overhead in its multi-tier architecture compared to a plaintext database, CockroachDB. We also compare OasisDB with ObliDB and Obliviator, two oblivious RDBMSs, highlighting its advantages with scalability and multi-user support.<\/jats:p>","DOI":"10.14778\/3749646.3749707","type":"journal-article","created":{"date-parts":[[2025,9,4]],"date-time":"2025-09-04T17:55:06Z","timestamp":1757008506000},"page":"4478-4491","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["OasisDB: An Oblivious and Scalable System for Relational Data"],"prefix":"10.14778","volume":"18","author":[{"given":"Haseeb","family":"Ahmed","sequence":"first","affiliation":[{"name":"University of Waterloo"}]},{"given":"Nachiket","family":"Rao","sequence":"additional","affiliation":[{"name":"University of Waterloo"}]},{"given":"Abdelkarim","family":"Kati","sequence":"additional","affiliation":[{"name":"University of Waterloo"}]},{"given":"Florian","family":"Kerschbaum","sequence":"additional","affiliation":[{"name":"University of Waterloo"}]},{"given":"Sujaya","family":"Maiyya","sequence":"additional","affiliation":[{"name":"University of Waterloo"}]}],"member":"320","published-online":{"date-parts":[[2025,9,4]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Haseeb Ahmed Nachiket Rao Abdelkarim Kati Florian Kerschbaum and Sujayya Maiyya. 2025. OasisDB: An Oblivious and Scalable System for Relational Data. Cryptology ePrint Archive Paper 2025\/1263. https:\/\/eprint.iacr.org\/2025\/1263"},{"key":"e_1_2_1_2_1","volume-title":"Oblivious query processing. arXiv preprint arXiv:1312.4012","author":"Arasu Arvind","year":"2013","unstructured":"Arvind Arasu and Raghav Kaushik. 2013. Oblivious query processing. arXiv preprint arXiv:1312.4012 (2013)."},{"key":"e_1_2_1_3_1","unstructured":"Baffle. 2025. https:\/\/baffle.io. Accessed: 2025-07-11."},{"key":"e_1_2_1_4_1","unstructured":"Benchbase Epinions Dataset. 2025. https:\/\/github.com\/cmu-db\/benchbase\/wiki\/epinions. Accessed: 2025-07-11."},{"key":"e_1_2_1_5_1","unstructured":"Big Data Benchmark. 2025. https:\/\/amplab.cs.berkeley.edu\/benchmark\/. Accessed: 2025-07-11."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2810103.2813649"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14722\/ndss.2020.23103"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3460120.3484786"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2810103.2813700"},{"key":"e_1_2_1_11_1","volume-title":"ConcurORAM: High-Throughput Stateless Parallel Multi-Client ORAM. In 26th Annual Network and Distributed System Security Symposium (NDSS).","author":"Chakraborti Anrin","year":"2019","unstructured":"Anrin Chakraborti and Radu Sion. 2019. ConcurORAM: High-Throughput Stateless Parallel Multi-Client ORAM. In 26th Annual Network and Distributed System Security Symposium (NDSS)."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2021.3060757"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517868"},{"key":"e_1_2_1_14_1","unstructured":"CockroachDB. 2025. https:\/\/www.cockroachlabs.com\/blog\/pebble-rocksdb-kv-store\/. Accessed: 2025-07-11."},{"key":"e_1_2_1_15_1","unstructured":"CockroachDB - KV store layer. 2025. https:\/\/www.cockroachlabs.com\/glossary\/distributed-db\/key-value-kv-layer\/. Accessed: 2025-07-11."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491245"},{"key":"e_1_2_1_17_1","volume-title":"13th USENIX Symposium on Operating Systems Design and Implementation (OSDI). 727\u2013743","author":"Crooks Natacha","year":"2018","unstructured":"Natacha Crooks, Matthew Burke, Ethan Cecchetti, Sitar Harel, Rachit Agarwal, and Lorenzo Alvisi. 2018. Obladi: Oblivious serializable transactions in the cloud. In 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI). 727\u2013743."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3477132.3483562"},{"key":"e_1_2_1_19_1","volume-title":"29th USENIX Security Symposium (USENIX Security 20)","author":"Demertzis Ioannis","year":"2020","unstructured":"Ioannis Demertzis, Dimitrios Papadopoulos, Charalampos Papamanthou, and Saurabh Shintre. 2020. SEAL: Attack Mitigation for Encrypted Databases via Adjustable Leakage. In 29th USENIX Security Symposium (USENIX Security 20). 2433\u20132450."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3167971"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732240.2732246"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/3364324.3364331"},{"key":"e_1_2_1_23_1","volume-title":"Peter Celi, and Roger G Mark.","author":"Johnson Alistair EW","year":"2016","unstructured":"Alistair EW Johnson, Tom J Pollard, Lu Shen, H Lehman Li-Wei, Mengling Feng, Mohammad Ghassemi, Benjamin Moody, Leo Anthony Szolovits, Peter Celi, and Roger G Mark. 2016. MIMIC-III, a freely accessible critical care database. In Scientific Data, 3(1)."},{"key":"e_1_2_1_24_1","volume-title":"Proceedings, Part II 20","author":"Faber Sky","year":"2015","unstructured":"Sky Faber, Stanislaw Jarecki, Hugo Krawczyk, Quan Nguyen, Marcel Rosu, and Michael Steiner. 2015. Rich queries on encrypted data: Beyond exact matches. In Computer Security-ESORICS 2015: 20th European Symposium on Research in Computer Security, Vienna, Austria, September 21\u201325, 2015, Proceedings, Part II 20. Springer, 123\u2013145."},{"key":"e_1_2_1_25_1","volume-title":"Zachary Espiritu, and Roberto Tamassia.","author":"Falzon Francesca","year":"2022","unstructured":"Francesca Falzon, Evangelia Anna Markatou, Zachary Espiritu, and Roberto Tamassia. 2022. Range search over encrypted multi-attribute data. Cryptology ePrint Archive (2022)."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28416"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/233551.233553"},{"key":"e_1_2_1_28_1","first-page":"2025","article-title":"https:\/\/www.data.gov.uk\/dataset\/34d08a53-6b96-4fb6-b043-627e2b25840d\/organogram-government-legal-department","volume":"10","author":"Government Digital Service. Organogram of staff roles & salaries of Government Legal Department","year":"2018","unstructured":"Government Digital Service. Organogram of staff roles & salaries of Government Legal Department. 2018. https:\/\/www.data.gov.uk\/dataset\/34d08a53-6b96-4fb6-b043-627e2b25840d\/organogram-government-legal-department. Accessed Mar 10, 2025.","journal-title":"Accessed Mar"},{"key":"e_1_2_1_29_1","volume-title":"29th USENIX Security Symposium. 2451\u20132468","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. 2451\u20132468."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3243734.3243864"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2019.00030"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3319535.3363210"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3626759"},{"key":"e_1_2_1_34_1","volume-title":"19th Annual Network and Distributed System Security Symposium (NDSS).","author":"Islam Mohammad Saiful","year":"2012","unstructured":"Mohammad Saiful Islam, Mehmet Kuzu, and Murat Kantarcioglu. 2012. Access pattern disclosure on searchable encryption: ramification, attack and mitigation.. In 19th Annual Network and Distributed System Security Symposium (NDSS)."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-03326-2_6"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2976749.2978386"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2019.00015"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP40001.2021.00044"},{"key":"e_1_2_1_39_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_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2018.00002"},{"key":"e_1_2_1_41_1","volume-title":"A note on the optimality of frequency analysis vs. \u2113p-optimization. Cryptology ePrint Archive","author":"Lacharit\u00e9 Marie-Sarah","year":"2015","unstructured":"Marie-Sarah Lacharit\u00e9 and Kenneth G Paterson. 2015. A note on the optimality of frequency analysis vs. \u2113p-optimization. Cryptology ePrint Archive (2015)."},{"key":"e_1_2_1_42_1","volume-title":"Frequency-smoothing encryption: preventing snapshot attacks on deterministically encrypted data. Cryptology ePrint Archive","author":"Lacharit\u00e9 Marie-Sarah","year":"2017","unstructured":"Marie-Sarah Lacharit\u00e9 and Kenneth G Paterson. 2017. Frequency-smoothing encryption: preventing snapshot attacks on deterministically encrypted data. Cryptology ePrint Archive (2017)."},{"volume-title":"Advances in Cryptology-CRYPTO 2018: 38th Annual International Cryptology Conference. 523\u2013542.","author":"Larsen Kasper Green","key":"e_1_2_1_43_1","unstructured":"Kasper Green Larsen and Jesper Buus Nielsen. 2018. Yes, there is an oblivious RAM lower bound!. In Advances in Cryptology-CRYPTO 2018: 38th Annual International Cryptology Conference. 523\u2013542."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/DSN.2017.28"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733085.2733100"},{"key":"e_1_2_1_46_1","unstructured":"Lookout. 2025. https:\/\/www.lookout.com. Accessed: 2025-07-11."},{"key":"e_1_2_1_47_1","volume-title":"QuORAM: A Quorum-Replicated Fault Tolerant ORAM Datastore. In 31st USENIX Security Symposium. 3665\u20133682","author":"Maiyya Sujaya","year":"2022","unstructured":"Sujaya Maiyya, Seif Ibrahim, Caitlin Scarberry, Divyakant Agrawal, Amr El Abbadi, Huijia Lin, Stefano Tessaro, and Victor Zakhary. 2022. QuORAM: A Quorum-Replicated Fault Tolerant ORAM Datastore. In 31st USENIX Security Symposium. 3665\u20133682."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3626760"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.56553\/popets-2023-0106"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-30215-3_2"},{"key":"e_1_2_1_51_1","volume-title":"OBLIVIATOR: Oblivious Parallel Joins and other Operators in Shared Memory Environments. Cryptology ePrint Archive","author":"Mavrogiannakis Apostolos","year":"2025","unstructured":"Apostolos Mavrogiannakis, Xian Wang, Ioannis Demertzis, Dimitrios Papadopoulos, and Minos Garofalakis. 2025. OBLIVIATOR: Oblivious Parallel Joins and other Operators in Shared Memory Environments. Cryptology ePrint Archive (2025)."},{"key":"e_1_2_1_52_1","unstructured":"Navajo Systems. 2025. https:\/\/tinyurl.com\/yc4z5nyf. Accessed: 2025-07-11."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2810103.2813651"},{"key":"e_1_2_1_54_1","volume-title":"USENIX Security Symposium. 127\u2013142","author":"Oya Simon","year":"2021","unstructured":"Simon Oya and Florian Kerschbaum. 2021. Hiding the Access Pattern is Not Enough: Exploiting Search Pattern Leakage in Searchable Encryption.. In USENIX Security Symposium. 127\u2013142."},{"key":"e_1_2_1_55_1","volume-title":"31st USENIX Security Symposium. 2407\u20132424","author":"Oya Simon","year":"2022","unstructured":"Simon Oya and Florian Kerschbaum. 2022. IHOP: Improved Statistical Query Recovery against Searchable Symmetric Encryption through Quadratic Optimization. In 31st USENIX Security Symposium. 2407\u20132424."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3319535.3354213"},{"volume-title":"Advances in Cryptology-EUROCRYPT 2019: 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques. 404\u2013434.","author":"Persiano Giuseppe","key":"e_1_2_1_57_1","unstructured":"Giuseppe Persiano and Kevin Yeo. 2019. Lower bounds for differentially private RAMs. In Advances in Cryptology-EUROCRYPT 2019: 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques. 404\u2013434."},{"key":"e_1_2_1_58_1","unstructured":"Perspecsys. 2025. https:\/\/tinyurl.com\/45ubwnef. Accessed: 2025-07-11."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/EuroSP48549.2020.00030"},{"key":"e_1_2_1_60_1","unstructured":"Redis. 2025. https:\/\/redis.io\/. Accessed: 2025-07-11."},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/3634737.3657005"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2016.20"},{"key":"e_1_2_1_63_1","unstructured":"Scalability in MySQL. 2025. https:\/\/www.mysql.com\/products\/cluster\/scalability.html. Accessed: 2025-07-11."},{"key":"e_1_2_1_64_1","volume-title":"Treebeard: A Scalable and Fault Tolerant ORAM Datastore. Cryptology ePrint Archive, Paper 2025\/1082. https:\/\/eprint.iacr.org\/2025\/1082","author":"Setayesh Amin","year":"2025","unstructured":"Amin Setayesh, Cheran Mahalingam, Emily Chen, and Sujaya Maiyya. 2025. Treebeard: A Scalable and Fault Tolerant ORAM Datastore. Cryptology ePrint Archive, Paper 2025\/1082. https:\/\/eprint.iacr.org\/2025\/1082"},{"key":"e_1_2_1_65_1","unstructured":"Skyhigh Networks. 2025. https:\/\/www.skyhighsecurity.com. Accessed: 2025-07-11."},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2013.25"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508859.2516660"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3386134"},{"key":"e_1_2_1_69_1","doi-asserted-by":"crossref","unstructured":"TiDB. 2025. https:\/\/www.pingcap.com. Accessed: 2025-07-11.","DOI":"10.1055\/s-0045-1805049"},{"key":"e_1_2_1_70_1","volume-title":"Oblivious Data Accesss. In 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI). 719\u2013734","author":"Vuppalapati Midhul","year":"2022","unstructured":"Midhul Vuppalapati, Kushal Babel, Anurag Khandelwal, and Rachit Agarwal. 2022. SHORTSTACK: Distributed, Fault-tolerant, Oblivious Data Accesss. In 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI). 719\u2013734."},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/3548606.3559345"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660267.2660314"},{"volume-title":"Accessed","year":"2025","key":"e_1_2_1_73_1","unstructured":"YugaByte: Key-value data model. 2025. https:\/\/docs.yugabyte.com\/preview\/develop\/data-modeling\/common-patterns\/keyvalue\/. Accessed Feb 28, 2025."},{"key":"e_1_2_1_74_1","volume-title":"USENIX Security Symposium","volume":"2016","author":"Zhang Yupeng","year":"2016","unstructured":"Yupeng Zhang, Jonathan Katz, and Charalampos Papamanthou. 2016. All your queries are belong to us: The power of file-injection attacks on searchable encryption.. In USENIX Security Symposium, Vol. 2016. 707\u2013720."},{"key":"e_1_2_1_75_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\u2013298."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3749646.3749707","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,5]],"date-time":"2025-09-05T02:52:14Z","timestamp":1757040734000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3749646.3749707"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7]]},"references-count":75,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2025,7]]}},"alternative-id":["10.14778\/3749646.3749707"],"URL":"https:\/\/doi.org\/10.14778\/3749646.3749707","relation":{},"ISSN":["2150-8097"],"issn-type":[{"type":"print","value":"2150-8097"}],"subject":[],"published":{"date-parts":[[2025,7]]},"assertion":[{"value":"2025-09-04","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}