{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T10:07:07Z","timestamp":1774951627409,"version":"3.50.1"},"reference-count":61,"publisher":"Association for Computing Machinery (ACM)","issue":"5","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2025,1]]},"abstract":"<jats:p>Trusted execution environment (TEE) has provided an isolated and secure environment for building cloud-based analytic systems, but it still suffers from access pattern leakages caused by side-channel attacks. To better secure the data, computation inside TEE enclave should be made oblivious, which introduces significant overhead and severely slows down the computation. A natural way to speed up is to build the analytic system with multiple servers in the distributed setting. However, this setting raises a new security concern\u2014the volumes of the transmissions among these servers can leak sensitive information to a network adversary. Existing works have designed specialized algorithms to address this concern, but their supports for equi-join, one of the most important but nontrivial database operators, are either inefficient, limited, or under a weak security assumption.<\/jats:p>\n          <jats:p>In this paper, we present Jodes, an efficient oblivious join algorithm in the distributed setting. Jodes prevents the leakage on both the network and enclave sides, supports a general equi-join operation, and provides a high security level protection that only publicizes the input sizes and the output size. Meanwhile, it achieves both communication cost and computation cost asymptotically superior to existing algorithms. To demonstrate the practicality of Jodes, we conduct experiments in the distributed setting comprising 16 servers. Empirical results show that Jodes achieves up to a sixfold performance improvement over state-of-the-art join algorithms.<\/jats:p>","DOI":"10.14778\/3718057.3718060","type":"journal-article","created":{"date-parts":[[2025,8,27]],"date-time":"2025-08-27T18:11:49Z","timestamp":1756318309000},"page":"1291-1304","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Jodes: Efficient Oblivious Join in the Distributed Setting"],"prefix":"10.14778","volume":"18","author":[{"given":"Yilei","family":"Wang","sequence":"first","affiliation":[{"name":"Alibaba Cloud, Hangzhou, China"}]},{"given":"Xiangdong","family":"Zeng","sequence":"additional","affiliation":[{"name":"Alibaba Cloud, Hangzhou, China"}]},{"given":"Sheng","family":"Wang","sequence":"additional","affiliation":[{"name":"Alibaba Cloud, Hangzhou, China"}]},{"given":"Feifei","family":"Li","sequence":"additional","affiliation":[{"name":"Alibaba Cloud, Hangzhou, China"}]}],"member":"320","published-online":{"date-parts":[[2025,8,27]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2011.47"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808726"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3386141"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2467797"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5441\/002\/ICDT.2014.07"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976014.2"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. Association for Computing Machinery, 209\u2013222","author":"Badrinarayanan Saikrishna","year":"2022","unstructured":"Saikrishna Badrinarayanan, Sourav Das, Gayathri Garimella, Srinivasan Raghuraman, and Peter Rindal. 2022. Secret-Shared Joins with Multiplicity from Aggregation Trees. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. Association for Computing Machinery, 209\u2013222."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1468075.1468121"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/3055330.3055334"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594558"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3125644"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2020.75"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517868"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000042"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3533737.3535098"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/3364324.3364331"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1561\/3300000019"},{"key":"e_1_2_1_20_1","volume-title":"Proxygen: Facebook's C++ HTTP Libraries. https:\/\/github.com\/facebook\/proxygen\/releases\/tag\/v2022.11.14.00 Accessed: 2024-08-12.","year":"2022","unstructured":"Facebook. 2022. Proxygen: Facebook's C++ HTTP Libraries. https:\/\/github.com\/facebook\/proxygen\/releases\/tag\/v2022.11.14.00 Accessed: 2024-08-12."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/233551.233553"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591830"},{"key":"e_1_2_1_23_1","volume-title":"Algorithms and Computation, Takao Asano, Shin-ichi Nakano","author":"Goodrich Michael T.","unstructured":"Michael T. Goodrich, Nodari Sitchinava, and Qin Zhang. 2011. Sorting, Searching, and Simulation in the MapReduce Framework. In Algorithms and Computation, Takao Asano, Shin-ichi Nakano, Yoshio Okamoto, and Osamu Watanabe (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 374\u2013383."},{"key":"e_1_2_1_24_1","first-page":"370","article-title":"StealthDB: a Scalable Encrypted Database with Full SQL Query Support","volume":"2019","author":"Gribov Alexey","year":"2017","unstructured":"Alexey Gribov, Dhinakaran Vinayagamurthy, and Sergey Gorbunov. 2017. StealthDB: a Scalable Encrypted Database with Full SQL Query Support. Proceedings on Privacy Enhancing Technologies 2019 (2017), 370\u2013388. https:\/\/api.semanticscholar.org\/CorpusID:28591687","journal-title":"Proceedings on Privacy Enhancing Technologies"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00176"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3452021.3458319"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056110"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3294052.3319698"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387657"},{"key":"e_1_2_1_30_1","volume-title":"Attack and Mitigation. In 19th Annual Network and Distributed System Security Symposium, NDSS 2012","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 2012, San Diego, California, USA, February 5\u20138, 2012. The Internet Society. https:\/\/www.ndss-symposium.org\/ndss2012\/access-pattern-disclosure-searchable-encryption-ramification-attack-and-mitigation"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3034788"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407814"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/800057.808667"},{"key":"e_1_2_1_34_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_1_35_1","volume-title":"Encrypted Databases Made Secure Yet Maintainable. In 17th USENIX Symposium on Operating Systems Design and Implementation (OSDI 23)","author":"Li Mingyu","year":"2023","unstructured":"Mingyu Li, Xuyang Zhao, Le Chen, Cheng Tan, Huorong Li, Sheng Wang, Zeyu Mi, Yubin Xia, Feifei Li, and Haibo Chen. 2023. Encrypted Databases Made Secure Yet Maintainable. In 17th USENIX Symposium on Operating Systems Design and Implementation (OSDI 23). USENIX Association, Boston, MA, 117\u2013133. https:\/\/www.usenix.org\/conference\/osdi23\/presentation\/li-mingyu"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/3583140.3583158"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/3587136.3587142"},{"key":"e_1_2_1_38_1","volume-title":"20th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2023","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 2023, Boston, MA, April 17\u201319, 2023, Mahesh Balakrishnan and Manya Ghobadi (Eds.). USENIX Association, 1031\u20131056."},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security. Association for Computing Machinery, 1271\u20131287","author":"Mohassel Payman","year":"2020","unstructured":"Payman Mohassel, Peter Rindal, and Mike Rosulek. 2020. Fast Database Joins and PSI for Secret Shared Data. In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security. Association for Computing Machinery, 1271\u20131287."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP54263.2024.00153"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2810103.2813695"},{"key":"e_1_2_1_42_1","volume-title":"Oblivious Multi-Party Machine Learning on Trusted Processors (SEC'16)","author":"Ohrimenko Olga","unstructured":"Olga Ohrimenko, Felix Schuster, C\u00e9dric Fournet, Aastha Mehta, Sebastian Nowozin, Kapil Vaswani, and Manuel Costa. 2016. Oblivious Multi-Party Machine Learning on Trusted Processors (SEC'16). USENIX Association, USA, 619\u2013636."},{"key":"e_1_2_1_43_1","volume-title":"Senate: A Maliciously-Secure MPC Platform for Collaborative Analytics. In 30th USENIX Security Symposium (USENIX Security 21)","author":"Poddar Rishabh","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 30th USENIX Security Symposium (USENIX Security 21). USENIX Association, 2129\u20132146. https:\/\/www.usenix.org\/conference\/usenixsecurity21\/presentation\/poddar"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043556.2043566"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2018.00025"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/3574245.3574248"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3548606.3560603"},{"key":"e_1_2_1_48_1","unstructured":"Amazon Web Services. 2024. Amazon EMR pricing. https:\/\/aws.amazon.com\/emr\/pricing\/ Accessed: 2024-08-12."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3177872"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.14778\/3447689.3447705"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/79173.79181"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.14778\/3554821.3554826"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452808"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3517804.3524142"},{"key":"e_1_2_1_55_1","volume-title":"Jodes: Efficient Oblivious Join in the Distributed Setting. https:\/\/raw.githubusercontent.com\/Aqua-Dream\/Jodes\/main\/Jodes_full.pdf","author":"Wang Yilei","year":"2024","unstructured":"Yilei Wang, Xiangdong Zeng, Sheng Wang, and Feifei Li. 2024. Jodes: Efficient Oblivious Join in the Distributed Setting. https:\/\/raw.githubusercontent.com\/Aqua-Dream\/Jodes\/main\/Jodes_full.pdf"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2015.45"},{"key":"e_1_2_1_57_1","unstructured":"YSU-Data-Lab. 2024. TPC-H-Skew. https:\/\/github.com\/YSU-Data-Lab\/TPC-H-Skew Accessed: 2024-08-12."},{"key":"e_1_2_1_58_1","volume-title":"Proceedings of the 9th USENIX Conference on Networked Systems Design and Implementation","author":"Zaharia Matei","year":"2012","unstructured":"Matei Zaharia, Mosharaf Chowdhury, Tathagata Das, Ankur Dave, Justin Ma, Murphy McCauley, Michael J. Franklin, Scott Shenker, and Ion Stoica. 2012. Resilient Distributed Datasets: A Fault-Tolerant Abstraction for in-Memory Cluster Computing. In Proceedings of the 9th USENIX Conference on Networked Systems Design and Implementation (San Jose, CA) (NSDI'12). USENIX Association, USA, 2."},{"key":"e_1_2_1_59_1","volume-title":"Proceedings of the 14th USENIX Conference on Networked Systems Design and Implementation","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 Proceedings of the 14th USENIX Conference on Networked Systems Design and Implementation (Boston, MA, USA) (NSDI'17). USENIX Association, USA, 283\u2013298."},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476311.3476351"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/1037947.1024403"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3718057.3718060","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,27]],"date-time":"2025-08-27T18:13:39Z","timestamp":1756318419000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3718057.3718060"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1]]},"references-count":61,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2025,1]]}},"alternative-id":["10.14778\/3718057.3718060"],"URL":"https:\/\/doi.org\/10.14778\/3718057.3718060","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2025,1]]},"assertion":[{"value":"2025-08-27","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}