{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,11]],"date-time":"2026-01-11T08:26:57Z","timestamp":1768120017567,"version":"3.49.0"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2023,11,13]],"date-time":"2023-11-13T00:00:00Z","timestamp":1699833600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Hong Kong Research Grant Council","award":["16201819, 16205420, 16205422"],"award-info":[{"award-number":["16201819, 16205420, 16205422"]}]},{"name":"Alibaba Innovative Research Program"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,11,13]]},"abstract":"<jats:p>We study the problem of random sampling in the secure multi-party computation (MPC) model. In MPC, taking a sample securely must have a cost \u03a9(n) irrespective to the sample size s. This is in stark contrast with the plaintext setting, where a sample can be taken in O(s) time trivially. Thus, the goal of approximate query processing (AQP) with sublinear costs seems unachievable under MPC. To get around this inherent barrier, in this paper we take a two-stage approach: In the offline stage, we generate a batch of n\/s samples with (n) total cost, which can then be consumed to answer queries as they arrive online. Such an approach allows us to achieve an \u00d5(s) amortized cost per query, similar to the plaintext setting. Based on our secure batch sampling algorithms, we build MASQUE, an MPC-AQP system that achieves sublinear online query costs by running an MPC protocol to evaluate the queries on pre-generated samples. MASQUE achieves the strong security guarantee of the MPC model, i.e., nothing is revealed beyond the query result, which itself can be further protected by (amplified) differential privacy<\/jats:p>","DOI":"10.1145\/3617339","type":"journal-article","created":{"date-parts":[[2023,11,13]],"date-time":"2023-11-13T22:28:39Z","timestamp":1699914519000},"page":"1-27","source":"Crossref","is-referenced-by-count":2,"title":["Secure Sampling for Approximate Multi-party Query Processing"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4167-8670","authenticated-orcid":false,"given":"Qiyao","family":"Luo","sequence":"first","affiliation":[{"name":"Hong Kong University of Science and Technology, Hong Kong SAR, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7856-2527","authenticated-orcid":false,"given":"Yilei","family":"Wang","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2178-3716","authenticated-orcid":false,"given":"Ke","family":"Yi","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology, Hong Kong SAR, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-1582-3316","authenticated-orcid":false,"given":"Sheng","family":"Wang","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-0770-5775","authenticated-orcid":false,"given":"Feifei","family":"Li","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hangzhou, China"}]}],"member":"320","published-online":{"date-parts":[[2023,11,13]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465351.2465355"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing. 1--9.","author":"Ajtai M.","unstructured":"M. Ajtai, J. Koml\u00f3s, and E. Szemer\u00e9di. 1983. An \u0398(n $\u0142og$ n) Sorting Network. In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing. 1--9."},{"key":"e_1_2_1_3_1","volume-title":"Bucket Oblivious Sort: An Extremely Simple Oblivious Sort. In 3rd Symposium on Simplicity in Algorithms, SOSA","author":"Asharov Gilad","year":"2020","unstructured":"Gilad Asharov, T.-H. Hubert Chan, Kartik Nayak, Rafael Pass, Ling Ren, and Elaine Shi. 2020. Bucket Oblivious Sort: An Extremely Simple Oblivious Sort. In 3rd Symposium on Simplicity in Algorithms, SOSA 2020, Martin Farach-Colton and Inge Li G\u00f8rtz (Eds.). 8--14."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3548606.3560691"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 32nd International Conference on Neural Information Processing Systems. 6280--6290","author":"Balle Borja","year":"2018","unstructured":"Borja Balle, Gilles Barthe, and Marco Gaboardi. 2018. Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences. In Proceedings of the 32nd International Conference on Neural Information Processing Systems. 6280--6290."},{"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","first-page":"12","article-title":"SAQE","volume":"13","author":"Bater Johes","year":"2020","unstructured":"Johes Bater, Yongjoo Park, Xi He, Xiao Wang, and Jennie Rogers. 2020. SAQE: Practical Privacy-Preserving Approximate Query Processing for Data Federations. Proc. VLDB Endow., Vol. 13, 12 (jul 2020), 2691--2705.","journal-title":"Practical Privacy-Preserving Approximate Query Processing for Data Federations. Proc. VLDB Endow."},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Donald Beaver. 1992. Efficient Multiparty Protocols Using Circuit Randomization. In Advances in Cryptology -- CRYPTO '91. 420--432.","DOI":"10.1007\/3-540-46766-1_34"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62213"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/30401.315746"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008908.1008911"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3319535.3354256"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3056097"},{"key":"e_1_2_1_16_1","unstructured":"Koji Chida Koki Hamada Dai Ikarashi Ryo Kikuchi Naoto Kiribuchi and Benny Pinkas. 2019. An Efficient Secure Three-Party Sorting Protocol with an Honest Majority. Cryptology ePrint Archive Paper 2019\/695. https:\/\/eprint.iacr.org\/2019\/695 https:\/\/eprint.iacr.org\/2019\/695."},{"key":"e_1_2_1_17_1","unstructured":"Seung Geol Choi Dana Dachman-Soled S. Dov Gordon Linsheng Liu and Arkady Yerukhimovich. 2022. Secure Sampling with Sublinear Communication. Cryptology ePrint Archive Paper 2022\/660. https:\/\/eprint.iacr.org\/2022\/660 https:\/\/eprint.iacr.org\/2022\/660."},{"key":"e_1_2_1_18_1","unstructured":"Cryptography and Privacy Engineering Group at TU Darmstadt. [n. d.]. A Framework for Efficient Mixed-Protocol Secure Two-Party Computation. https:\/\/github.com\/encryptogroup\/ABY."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517844"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452813"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3517804.3524143"},{"key":"e_1_2_1_22_1","volume-title":"Foundations and Trends\u00ae in Theoretical Computer Science","volume":"9","author":"Dwork Cynthia","year":"2014","unstructured":"Cynthia Dwork and Aaron Roth. 2014. The algorithmic foundations of differential privacy. Foundations and Trends\u00ae in Theoretical Computer Science, Vol. 9, 3--4 (2014), 211--407."},{"key":"e_1_2_1_23_1","volume-title":"Statistical tables for biological, agricultural and medical research","author":"Fisher Ronald Aylmer","unstructured":"Ronald Aylmer Fisher and Frank Yates. 1953. Statistical tables for biological, agricultural and medical research. Hafner Publishing Company."},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing. 218--229","author":"Goldreich O.","unstructured":"O. Goldreich, S. Micali, and A. Wigderson. 1987. How to Play ANY Mental Game. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing. 218--229."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989493.1989555"},{"key":"e_1_2_1_26_1","volume-title":"Information Security and Cryptology -- ICISC","author":"Hamada Koki","year":"2012","unstructured":"Koki Hamada, Ryo Kikuchi, Dai Ikarashi, Koji Chida, and Katsumi Takahashi. 2013. Practically Efficient Multi-party Sorting Protocols from Comparison Sort Algorithms. In Information Security and Cryptology -- ICISC 2012. 202--216."},{"key":"e_1_2_1_27_1","volume-title":"Scape: Scalable Collaborative Analytics System on Private Database with Malicious Security. In 2022 IEEE 38th International Conference on Data Engineering (ICDE). 1740--1753","author":"Han Feng","year":"2022","unstructured":"Feng Han, Lan Zhang, Hanwen Feng, Weiran Liu, and Xiangyang Li. 2022. Scape: Scalable Collaborative Analytics System on Private Database with Malicious Security. In 2022 IEEE 38th International Conference on Data Engineering (ICDE). 1740--1753."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3187009.3177733"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882940"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3372297.3417872"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735479.2735485"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40084-1_4"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2976749.2978381"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342274"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407814"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322232"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915235"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2877362"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2014.46"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3372297.3423358"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38348-9_33"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196905"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-17659-4_5"},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of the 30th Conference on USENIX Security Symposium.","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 Proceedings of the 30th Conference on USENIX Security Symposium."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/ITW.2012.6404773"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2014.2316011"},{"key":"e_1_2_1_47_1","unstructured":"Lianke Qin Rajesh Jayaram Elaine Shi Zhao Song Danyang Zhuo and Shumo Chu. 2023. Differentially Oblivious Relational Database Operators. In VLDB."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3548606.3560603"},{"key":"e_1_2_1_49_1","unstructured":"Sajin Sasy and Olga Ohrimenko. 2019. Oblivious Sampling Algorithms for Private Data Analysis."},{"key":"e_1_2_1_50_1","doi-asserted-by":"crossref","unstructured":"Yufei Tao. 2022. Algorithmic Techniques for Independent Query Sampling. In PODS.","DOI":"10.1145\/3517804.3526068"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389762"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3302424.3303982"},{"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","unstructured":"Jonathan Katz Xiao Wang Alex J. Malozemoff. [n. d.]. EMP-toolkit: Efficient MultiParty computation toolkit. https:\/\/github.com\/emp-toolkit."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.5555\/1382436.1382751"},{"key":"e_1_2_1_57_1","volume-title":"27th Annual Symposium on Foundations of Computer Science. 162--167","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. 162--167."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3617339","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3617339","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:45:53Z","timestamp":1750178753000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3617339"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,13]]},"references-count":57,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,11,13]]}},"alternative-id":["10.1145\/3617339"],"URL":"https:\/\/doi.org\/10.1145\/3617339","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,11,13]]}}}