{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T05:36:57Z","timestamp":1775281017638,"version":"3.50.1"},"reference-count":80,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,12]]},"abstract":"<jats:p>Secure collaborative analytics (SCA) enables the processing of analytical SQL queries across data from multiple owners, even when direct data sharing is not possible. While traditional SCA provides strong privacy through data-oblivious methods, the significant overhead has limited its practical use. Recent SCA variants that allow controlled leakages under differential privacy (DP) strike balance between privacy and efficiency but still face challenges like unbounded privacy loss, costly execution plan, and lossy processing.<\/jats:p>\n          <jats:p>\n            To address these challenges, we introduce SPECIAL, the first SCA system that simultaneously ensures bounded privacy loss, advanced query planning, and lossless processing. SPECIAL employs a novel\n            <jats:italic>synopsis-assisted secure processing model<\/jats:italic>\n            , where a one-time privacy cost is used to generate private synopses from owner data. These synopses enable SPECIAL to estimate compaction sizes for secure operations (e.g., filter, join) and index encrypted data without additional privacy loss. These estimates and indexes can be prepared before runtime, enabling efficient query planning and accurate cost estimations. By leveraging one-sided noise mechanisms and private upper bound techniques, SPECIAL guarantees lossless processing for complex queries (e.g., multi-join). Our comprehensive benchmarks demonstrate that SPECIAL outperforms state-of-the-art SCAs, with up to 80\u00d7 faster query times, 900\u00d7 smaller memory usage for complex queries, and up to 89\u00d7 reduced privacy loss in continual processing.\n          <\/jats:p>","DOI":"10.14778\/3717755.3717764","type":"journal-article","created":{"date-parts":[[2025,5,20]],"date-time":"2025-05-20T15:51:49Z","timestamp":1747756309000},"page":"1035-1048","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["SPECIAL: SynoPsis AssistEd Secure Collaborative AnaLytics"],"prefix":"10.14778","volume":"18","author":[{"given":"Chenghong","family":"Wang","sequence":"first","affiliation":[{"name":"Indiana University"}]},{"given":"Lina","family":"Qiu","sequence":"additional","affiliation":[{"name":"Boston University"}]},{"given":"Johes","family":"Bater","sequence":"additional","affiliation":[{"name":"Tufts University"}]},{"given":"Yukui","family":"Luo","sequence":"additional","affiliation":[{"name":"Umass Dartmouth"}]}],"member":"320","published-online":{"date-parts":[[2025,5,20]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"[n.d.]. Financial Dataset. https:\/\/relational-data.org\/dataset\/Financial. Accessed: 2024-03-30."},{"key":"e_1_2_1_2_1","volume-title":"CIDR","volume":"2005","author":"Aggarwal Gagan","year":"2005","unstructured":"Gagan Aggarwal, Mayank Bawa, Prasanna Ganesan, Hector Garcia-Molina, Krishnaram Kenthapadi, Rajeev Motwani, Utkarsh Srivastava, Dilys Thomas, and Ying Xu. 2005. Two Can Keep A Secret: A Distributed Architecture for Secure Database Services.. In CIDR, Vol. 2005. 186\u2013199."},{"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\/2976749.2978331"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976014.2"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1468075.1468121"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/3055330.3055334"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/3291264.3291274"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407854"},{"key":"e_1_2_1_10_1","unstructured":"Michael Ben-Or Shafi Goldwasser and Avi Wigderson. 2019. Completeness theorems for non-cryptographic fault-tolerant distributed computation. In Providing sound foundations for cryptography: on the work of Shafi Goldwasser and Silvio Micali. 351\u2013371."},{"key":"e_1_2_1_11_1","volume-title":"Revisiting leakage abuse attacks. Cryptology ePrint Archive","author":"Blackstone Laura","year":"2019","unstructured":"Laura Blackstone, Seny Kamara, and Tarik Moataz. 2019. Revisiting leakage abuse attacks. Cryptology ePrint Archive (2019)."},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Mike W Blasgen Morton M Astrahan Donald D Chamberlin JN Gray WF King Bruce G Lindsay Raymond A Lorie James W Mehl Thomas G Price Gianfranco R Putzolu et al. 1981. System R: An architectural overview. IBM systems journal 20 1 (1981) 41\u201362.","DOI":"10.1147\/sj.201.0041"},{"key":"e_1_2_1_13_1","volume-title":"Epsolute: E iciently erying Databases While Providing Differential Privacy.","author":"Bogatov Dmytro","year":"2021","unstructured":"Dmytro Bogatov, Georgios Kellaris, George Kollios, Kobbi Nissim, and Adam O'Neill. 2021. Epsolute: E iciently erying Databases While Providing Differential Privacy. (2021)."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53641-4_24"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2810103.2813700"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3555984"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517868"},{"key":"e_1_2_1_18_1","volume-title":"SPECIAL: Synopsis Assisted Secure Collaborative Analytics. https:\/\/arxiv.org\/abs\/2404.18388.","author":"Yukui Luo Chenghong Wang Johes Bater","year":"2024","unstructured":"Johes Bater Yukui Luo Chenghong Wang, Lina Qiu. 2024. SPECIAL: Synopsis Assisted Secure Collaborative Analytics. https:\/\/arxiv.org\/abs\/2404.18388."},{"key":"e_1_2_1_19_1","volume-title":"Differentially oblivious database joins: Overcoming the worst-case curse of fully oblivious algorithms. Cryptology ePrint Archive","author":"Chu Shumo","year":"2021","unstructured":"Shumo Chu, Danyang Zhuo, Elaine Shi, and TH Hubert Chan. 2021. Differentially oblivious database joins: Overcoming the worst-case curse of fully oblivious algorithms. Cryptology ePrint Archive (2021)."},{"key":"e_1_2_1_20_1","volume-title":"13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18)","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 18). 727\u2013743."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517844"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806787"},{"key":"e_1_2_1_23_1","first-page":"3","article-title":"The algorithmic foundations of differential privacy","volume":"9","author":"Dwork Cynthia","year":"2014","unstructured":"Cynthia Dwork, Aaron Roth, et al. 2014. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci. 9, 3-4 (2014), 211\u2013407.","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"e_1_2_1_24_1","volume-title":"Advances in Databases and Information Systems: 24th European Conference, ADBIS 2020, Lyon, France, August 25\u201327, 2020, Proceedings","volume":"12245","author":"Elmasri R","year":"2020","unstructured":"R Elmasri, SB Navathe, R Elmasri, and SB Navathe. 2020. Fundamentals of Database Systems<\/Title. In Advances in Databases and Information Systems: 24th European Conference, ADBIS 2020, Lyon, France, August 25\u201327, 2020, Proceedings, Vol. 12245. Springer Nature, 139."},{"key":"e_1_2_1_25_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_26_1","volume-title":"Foundations of cryptography","author":"Goldreich Oded","unstructured":"Oded Goldreich. 2009. Foundations of cryptography: volume 2, basic applications. Cambridge university press."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591830"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.2478\/popets-2019-0034"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3243734.3243864"},{"key":"e_1_2_1_30_1","volume-title":"Kai Zeng, Gao Cong, Yanzhao Qin, Andreas Pfadler, et al.","author":"Han Yuxing","year":"2021","unstructured":"Yuxing Han, Ziniu Wu, Peizhi Wu, Rong Zhu, Jingyi Yang, Liang Wei Tan, Kai Zeng, Gao Cong, Yanzhao Qin, Andreas Pfadler, et al. 2021. Cardinality estimation in DBMS: A comprehensive benchmark evaluation. arXiv preprint arXiv:2109.05877 (2021)."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186728.3164145"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133956.3134030"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824090"},{"key":"e_1_2_1_34_1","unstructured":"Axel Hertzschuch Claudio Hartmann Dirk Habich and Wolfgang Lehner. 2021. Simplicity Done Right for Join Ordering.. In CIDR."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/3415478.3415535"},{"key":"e_1_2_1_36_1","volume-title":"Secure multiparty sorting and applications. Cryptology ePrint Archive","author":"J\u00f6nsson Kristj\u00e4n Valur","year":"2011","unstructured":"Kristj\u00e4n Valur J\u00f6nsson, Gunnar Kreitz, and Misbah Uddin. 2011. Secure multiparty sorting and applications. Cryptology ePrint Archive (2011)."},{"key":"e_1_2_1_37_1","volume-title":"Outsourcing multi-party computation. Cryptology ePrint Archive","author":"Kamara Seny","year":"2011","unstructured":"Seny Kamara, Payman Mohassel, and Mariana Raykova. 2011. Outsourcing multi-party computation. Cryptology ePrint Archive (2011)."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2976749.2978386"},{"key":"e_1_2_1_39_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\u2013525."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989345"},{"key":"e_1_2_1_41_1","first-page":"4961","article-title":"Crypten: Secure multi-party computation meets machine learning","volume":"34","author":"Knott Brian","year":"2021","unstructured":"Brian Knott, Shobha Venkataraman, Awni Hannun, Shubho Sengupta, Mark Ibrahim, and Laurens van der Maaten. 2021. Crypten: Secure multi-party computation meets machine learning. Advances in Neural Information Processing Systems 34 (2021), 4961\u20134973.","journal-title":"Advances in Neural Information Processing Systems"},{"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.1145\/3183713.3196909"},{"key":"e_1_2_1_44_1","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\u20131056."},{"key":"e_1_2_1_45_1","unstructured":"Lovingmage. 2024. Synopsis Assisted Secure Collaborative Analytics. https:\/\/github.com\/lovingmage\/SPECIAL\/."},{"key":"e_1_2_1_46_1","volume-title":"Proceedings of the Nineteenth ACM Symp. on Theory of Computing, STOC. ACM New York, NY, USA, 218\u2013229","author":"Micali Silvio","year":"1987","unstructured":"Silvio Micali, Oded Goldreich, and Avi Wigderson. 1987. How to play any mental game. In Proceedings of the Nineteenth ACM Symp. on Theory of Computing, STOC. ACM New York, NY, USA, 218\u2013229."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2018.00045"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2017.12"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.56553\/popets-2024-0040"},{"key":"e_1_2_1_50_1","volume-title":"30th USENIX security symposium (USENIX Security 21). 127\u2013142.","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\u2013142."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3319535.3354213"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2818000.2818027"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14623-7_27"},{"key":"e_1_2_1_54_1","volume-title":"30th USENIX Security Symposium (USENIX Security 21)","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 30th USENIX Security Symposium (USENIX Security 21). 2129\u20132146."},{"key":"e_1_2_1_55_1","volume-title":"Adore: Differentially oblivious relational database operators. arXiv preprint arXiv:2212.05176","author":"Qin Lianke","year":"2022","unstructured":"Lianke Qin, Rajesh Jayaram, Elaine Shi, Zhao Song, Danyang Zhuo, and Shumo Chu. 2022. Adore: Differentially oblivious relational database operators. arXiv preprint arXiv:2212.05176 (2022)."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.14778\/3625054.3625055"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380596"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3548606.3560603"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-71045-7_4"},{"key":"e_1_2_1_60_1","volume-title":"Obfuscated access and search patterns in searchable encryption. arXiv preprint arXiv:2102.09651","author":"Shang Zhiwei","year":"2021","unstructured":"Zhiwei Shang, Simon Oya, Andreas Peter, and Florian Kerschbaum. 2021. Obfuscated access and search patterns in searchable encryption. arXiv preprint arXiv:2102.09651 (2021)."},{"key":"e_1_2_1_61_1","unstructured":"Abraham Silberschatz Henry F Korth and Shashank Sudarshan. 2011. Database system concepts. (2011)."},{"key":"e_1_2_1_62_1","unstructured":"SMCQL. [n.d.]. SMCQL: Secure Multi-party Computation Query Language. https:\/\/github.com\/smcql\/smcql\/tree\/master\/conf\/workload. Accessed: 2024-08-12."},{"key":"e_1_2_1_63_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_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP40001.2021.00098"},{"key":"e_1_2_1_65_1","volume-title":"32nd USENIX Security Symposium (USENIX Security 23)","author":"Tinoco Afonso","year":"2023","unstructured":"Afonso Tinoco, Sixiang Gao, and Elaine Shi. 2023. {EnigMap}:{External-Memory} Oblivious Map for Secure Enclaves. In 32nd USENIX Security Symposium (USENIX Security 23). 4033\u20134050."},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-57048-8_7"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/3302424.3303982"},{"key":"e_1_2_1_68_1","volume-title":"Differentially private oblivious ram. arXiv preprint arXiv:1601.03378","author":"Wagh Sameer","year":"2016","unstructured":"Sameer Wagh, Paul Cuff, and Prateek Mittal. 2016. Differentially private oblivious ram. arXiv preprint arXiv:1601.03378 (2016)."},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/3418290"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457306"},{"key":"e_1_2_1_71_1","volume-title":"IncShrink: Architecting Efficient Outsourced Databases using Incremental MPC and Differential Privacy. arXiv preprint arXiv:2203.05084","author":"Wang Chenghong","year":"2022","unstructured":"Chenghong Wang, Johes Bater, Kartik Nayak, and Ashwin Machanavajjhala. 2022. IncShrink: Architecting Efficient Outsourced Databases using Incremental MPC and Differential Privacy. arXiv preprint arXiv:2203.05084 (2022)."},{"key":"e_1_2_1_72_1","volume-title":"Private Proof-of-Stake Blockchains using Differentially-private Stake Distortion. Cryptology ePrint Archive","author":"Wang Chenghong","year":"2023","unstructured":"Chenghong Wang, David Pujo, Kartik Nayak, and Ashwin Machanavajjhala. 2023. Private Proof-of-Stake Blockchains using Differentially-private Stake Distortion. Cryptology ePrint Archive (2023)."},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660267.2660314"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452808"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1145\/2810103.2813640"},{"key":"e_1_2_1_76_1","volume-title":"27th annual symposium on foundations of computer science (Sfcs","author":"Chi-Chih Yao Andrew","year":"1986","unstructured":"Andrew Chi-Chih Yao. 1986. How to generate and exchange secrets. In 27th annual symposium on foundations of computer science (Sfcs 1986). IEEE, 162\u2013167."},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.14778\/3594512.3594529"},{"key":"e_1_2_1_78_1","volume-title":"25th USENIX Security Symposium (USENIX Security 16)","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 25th USENIX Security Symposium (USENIX Security 16). 707\u2013720."},{"key":"e_1_2_1_79_1","volume-title":"30th USENIX Security Symposium (USENIX Security 21)","author":"Zhang Zhikun","year":"2021","unstructured":"Zhikun Zhang, Tianhao Wang, Ninghui Li, Jean Honorio, Michael Backes, Shibo He, Jiming Chen, and Yang Zhang. 2021. {PrivSyn}: Differentially Private Data Synthesis. In 30th USENIX Security Symposium (USENIX Security 21). 929\u2013946."},{"key":"e_1_2_1_80_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\/3717755.3717764","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,20]],"date-time":"2025-05-20T16:15:28Z","timestamp":1747757728000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3717755.3717764"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12]]},"references-count":80,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["10.14778\/3717755.3717764"],"URL":"https:\/\/doi.org\/10.14778\/3717755.3717764","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,12]]},"assertion":[{"value":"2025-05-20","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}