{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T19:06:28Z","timestamp":1779131188562,"version":"3.51.4"},"reference-count":70,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2026,5,18]]},"abstract":"<jats:p>Processing joins in encrypted database systems presents a fundamental trade-off between privacy and efficiency. Fully oblivious algorithms can offer perfect access-pattern privacy but incur prohibitive costs by padding the execution to the worst-case output size. This limitation can be further enlarged on multi-way joins, where the worst-case output size can be exponentially large in terms of the database size. To overcome this barrier, differentially oblivious (DO) algorithms are introduced to enable instance-specific efficiency by sacrificing the perfect access-pattern privacy. While promising for two-way joins, extending this paradigm to multi-way joins has remained a significant open challenge.<\/jats:p>\n                  <jats:p>In this paper, we establish that designing efficient DO multi-way join algorithms is fundamentally equivalent to the problem of releasing join size differentially privately, but under new constraints imposed by an oblivious execution model. To solve this, we introduce relaxed-residual sensitivity, a novel sensitivity measure for counting the join size that is both differentially private and efficiently computable within an oblivious context. Based on this measure, we develop a principled DO padding mechanism that minimizes overhead while rigorously satisfying privacy. Our DO multi-way join algorithms achieve a polynomial speedup over their fully oblivious counterparts and come with a theoretical optimality guarantee for a large class of join queries. We have implemented our algorithms, and empirical evaluations confirm their substantial performance advantages, making differentially oblivious multi-way joins closer to a practical solution for secure query processing.<\/jats:p>","DOI":"10.1145\/3802039","type":"journal-article","created":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T18:19:16Z","timestamp":1779128356000},"page":"1-26","source":"Crossref","is-referenced-by-count":0,"title":["Differentially Oblivious Multi-way Join"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-8647-1416","authenticated-orcid":false,"given":"Zhiang","family":"Wu","sequence":"first","affiliation":[{"name":"University of Waterloo, Waterloo, Ontario, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0394-4125","authenticated-orcid":false,"given":"Wei","family":"Dong","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7890-665X","authenticated-orcid":false,"given":"Xiao","family":"Hu","sequence":"additional","affiliation":[{"name":"University of Waterloo, Waterloo, Ontario, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,5,18]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Amazon. https:\/\/aws.amazon.com\/redshift\/."},{"key":"e_1_2_1_2_1","unstructured":"Code. https:\/\/github.com\/z46wu\/DOJoin."},{"key":"e_1_2_1_3_1","unstructured":"Full version. https:\/\/github.com\/z46wu\/DOJoin."},{"key":"e_1_2_1_4_1","unstructured":"Google. https:\/\/cloud.google.com\/."},{"key":"e_1_2_1_5_1","unstructured":"Microsoft. https:\/\/azure.microsoft.com\/."},{"key":"e_1_2_1_6_1","unstructured":"TPC-H. https:\/\/www.tpc.org\/tpch\/."},{"key":"e_1_2_1_7_1","volume-title":"Foundations of databases","author":"Abiteboul Serge","unstructured":"Serge Abiteboul, Richard Hull, and Victor Vianu. 1995. Foundations of databases. Vol. 8. Addison-Wesley Reading."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902280"},{"key":"e_1_2_1_9_1","unstructured":"Arvind Arasu Spyros Blanas Ken Eguro Raghav Kaushik Donald Kossmann Ravishankar Ramamurthy and Ramarathnam Venkatesan. 2013. Orthogonal Security with Cipherbase. In CIDR."},{"key":"e_1_2_1_10_1","volume-title":"Oblivious query processing. ICDT","author":"Arasu Arvind","year":"2013","unstructured":"Arvind Arasu and Raghav Kaushik. 2013. Oblivious query processing. ICDT (2013)."},{"key":"e_1_2_1_11_1","volume-title":"Optorama: Optimal oblivious ram. In Eurocrypt","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 Eurocrypt. Springer, 403-432."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3576915.3623125"},{"key":"e_1_2_1_13_1","first-page":"739","article-title":"Size bounds and query plans for relational joins","author":"Atserias Albert","year":"2008","unstructured":"Albert Atserias, Martin Grohe, and D\u00e1niel Marx. 2008. Size bounds and query plans for relational joins. In FOCS. IEEE, 739-748.","journal-title":"FOCS. IEEE"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3548606.3560670"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74915-8_18"},{"key":"e_1_2_1_16_1","first-page":"752","article-title":"TrustedDB: A trusted hardware-based database with privacy and data confidentiality","volume":"26","author":"Bajaj Sumeet","year":"2013","unstructured":"Sumeet Bajaj and Radu Sion. 2013. TrustedDB: A trusted hardware-based database with privacy and data confidentiality. TKDE 26, 3 (2013), 752-765.","journal-title":"TKDE"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/3055330.3055334"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/3291264.3291274"},{"key":"e_1_2_1_19_1","unstructured":"Amos Beimel Kobbi Nissim and Mohammad Zaheri. 2019. Exploring Differential Obliviousness. In APPROX\/RANDOM."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3555984"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2023.3310038"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3652597"},{"key":"e_1_2_1_23_1","first-page":"1","article-title":"Differentially Oblivious Database Joins: Overcoming the Worst-Case Curse of Fully Oblivious Algorithms","volume":"199","author":"Chu Shumo","year":"2021","unstructured":"Shumo Chu, Danyang Zhuo, Elaine Shi, and T-H. Hubert Chan. 2021. Differentially Oblivious Database Joins: Overcoming the Worst-Case Curse of Fully Oblivious Algorithms. In ITC, Vol. 199. 19:1-19:24.","journal-title":"ITC"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517844"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452813"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Wei Dong and Ke Yi. 2022. A Nearly Instance-optimal Differentially Private Mechanism for Conjunctive Queries. In PODS.","DOI":"10.1145\/3517804.3524143"},{"key":"e_1_2_1_27_1","first-page":"265","article-title":"Calibrating noise to sensitivity in private data analysis","author":"Dwork Cynthia","year":"2006","unstructured":"Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. 2006. Calibrating noise to sensitivity in private data analysis. In TCC. 265-284.","journal-title":"TCC."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3533737.3535098"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/3364324.3364331"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/304181.304210"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3626725"},{"key":"e_1_2_1_32_1","first-page":"182","article-title":"Towards a theory of software protection and simulation by oblivious RAMs","author":"Goldreich Oded","year":"1987","unstructured":"Oded Goldreich. 1987. Towards a theory of software protection and simulation by oblivious RAMs. In STOC. 182-194.","journal-title":"STOC."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/233551.233553"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-09234-3_25"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902309"},{"key":"e_1_2_1_36_1","volume-title":"29th USENIX Security Symposium (USENIX Security . 2451-2468","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 . 2451-2468."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00176"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2025.25"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3187009.3177733"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611523"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2021.68"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342274"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407814"},{"key":"e_1_2_1_44_1","first-page":"1352","article-title":"Privacy preserving joins","author":"Li Yaping","year":"2008","unstructured":"Yaping Li and Minghua Chen. 2008. Privacy preserving joins. In ICDE. IEEE, 1352-1354.","journal-title":"ICDE. IEEE"},{"key":"e_1_2_1_45_1","first-page":"1031","volume-title":"20th USENIX Symposium on Networked Systems Design and Implementation (NSDI 23)","author":"Liagouris John","year":"2023","unstructured":"John Liagouris, Vasiliki Kalavri, Muhammad Faisal, and Mayank Varia. 2023. {SECRECY}: Secure collaborative analytics in untrusted clouds. In 20th USENIX Symposium on Networked Systems Design and Implementation (NSDI 23). 1031-1056."},{"key":"e_1_2_1_46_1","volume-title":"Proceedings of the 34th USENIX Conference on Security Symposium","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. In Proceedings of the 34th USENIX Conference on Security Symposium (Seattle, WA, USA) (SEC '25). USENIX Association, USA, Article 437, 20 pages."},{"key":"e_1_2_1_47_1","first-page":"490","article-title":"Secure computation with differentially private access patterns","author":"Mazloom Sahar","year":"2018","unstructured":"Sahar Mazloom and S Dov Gordon. 2018. Secure computation with differentially private access patterns. In CCS. 490-507.","journal-title":"CCS."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2018.00045"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3180143"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250803"},{"key":"e_1_2_1_51_1","first-page":"2129","article-title":"Senate","author":"Poddar Rishabh","year":"2021","unstructured":"Rishabh Poddar, Sukrit Kalra, Avishay Yanai, Ryan Deng, Raluca Ada Popa, and Joseph M Hellerstein. 2021. Senate: A Maliciously-Secure MPC Platform for Collaborative Analytics. In USENIX Security. 2129-2146.","journal-title":"A Maliciously-Secure MPC Platform for Collaborative Analytics. In USENIX Security."},{"key":"e_1_2_1_52_1","first-page":"85","article-title":"CryptDB: protecting confidentiality with encrypted query processing","author":"Popa Raluca Ada","year":"2011","unstructured":"Raluca Ada Popa, Catherine MS Redfield, Nickolai Zeldovich, and Hari Balakrishnan. 2011. CryptDB: protecting confidentiality with encrypted query processing. In SOSP. 85-100.","journal-title":"SOSP."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732296.2732300"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.14778\/3574245.3574267"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.14778\/3625054.3625055"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/212433.220199"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3340531.3411866"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP40000.2020.00037"},{"key":"e_1_2_1_59_1","unstructured":"Avi Silberschatz Henry F. Korth and S. Sudarshan. 2020. Database System Concepts Seventh Edition. McGraw-Hill Book Company. https:\/\/www.db-book.com\/"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3177872"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389762"},{"key":"e_1_2_1_62_1","first-page":"1969","article-title":"Secure Yannakakis: Join-Aggregate Queries over Private Data","author":"Wang Yilei","year":"2021","unstructured":"Yilei Wang and Ke Yi. 2021. Secure Yannakakis: Join-Aggregate Queries over Private Data. In SIGMOD. 1969-1981.","journal-title":"SIGMOD."},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/3517804.3524142"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/3719027.3765110"},{"key":"e_1_2_1_65_1","first-page":"82","article-title":"Algorithms for acyclic database schemes","volume":"81","author":"Yannakakis Mihalis","year":"1981","unstructured":"Mihalis Yannakakis. 1981. Algorithms for acyclic database schemes. In VLDB, Vol. 81. 82-94.","journal-title":"VLDB"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/3639266"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/3584372.3588675"},{"key":"e_1_2_1_68_1","volume-title":"H2O2RAM: a high-performance hierarchical doubly oblivious RAM","author":"Zheng Leqian","unstructured":"Leqian Zheng, Zheng Zhang, Wentao Dong, Yao Zhang, Ye Wu, and Cong Wang. 2025. H2O2RAM: a high-performance hierarchical doubly oblivious RAM. USENIX Association, USA."},{"key":"e_1_2_1_69_1","first-page":"283","article-title":"Opaque: An oblivious and encrypted distributed analytics platform","volume":"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 NSDI 17. 283-298.","journal-title":"NSDI"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-30620-4_1"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3802039","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T18:24:13Z","timestamp":1779128653000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3802039"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,18]]},"references-count":70,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,5,18]]}},"alternative-id":["10.1145\/3802039"],"URL":"https:\/\/doi.org\/10.1145\/3802039","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,18]]}}}