乐胖代购免代理版

{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,17]],"date-time":"2025-04-17T04:13:00Z","timestamp":1744863180246,"version":"3.40.4"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"1","funder":[{"DOI":"10.13039\/501100012166","name":"National Key R&D Program of China","doi-asserted-by":"crossref","award":["2021YFB1715600"],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["U22B2019, 62272372"],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Shenzhen Basic Research Grant","award":["JCYJ20170816100819428"]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,5,26]]},"abstract":"Counting the number of distinct elements distributed over multiple data holders is a fundamental problem with many real-world applications ranging from crowd counting to network monitoring. Although a number of space and computationally efficient sketch methods (e.g., the Flajolet-Martin sketch and the HyperLogLog sketch) for cardinality estimation have been proposed to solve the above problem, these sketch methods are insecure when considering privacy concerns related to the use of each data holder's personal dataset. Despite a recently proposed protocol that successfully implements the well-known Flajolet-Martin (FM) sketch on a secret-sharing based multiparty computation (MPC) framework for solving the problem of private distributed cardinality estimation (PDCE), we observe that this MPC-FM protocol is not differentially private. In addition, the MPC-FM protocol is computationally expensive, which limits its applications to data holders with limited computation resources. To address the above issues, in this paper we propose a novel protocol DP-DICE, which is computationally efficient and differentially private for solving the problem of PDCE. Experimental results show that our DP-DICE achieves orders of magnitude speedup and reduces the estimation error by several times in comparison with state-of-the-arts under the same security requirements.<\/jats:p>","DOI":"10.1145\/3588914","type":"journal-article","created":{"date-parts":[[2023,5,30]],"date-time":"2023-05-30T17:42:05Z","timestamp":1685468525000},"page":"1-24","source":"Crossref","is-referenced-by-count":0,"title":["An Effective and Differentially Private Protocol for Secure Distributed Cardinality Estimation"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1434-837X","authenticated-orcid":false,"given":"Pinghui","family":"Wang","sequence":"first","affiliation":[{"name":"Xi'an Jiaotong University, Xi'an, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-5081-1719","authenticated-orcid":false,"given":"Chengjin","family":"Yang","sequence":"additional","affiliation":[{"name":"Xi'an Jiaotong University, Xi'an, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-8727-4946","authenticated-orcid":false,"given":"Dongdong","family":"Xie","sequence":"additional","affiliation":[{"name":"Xi'an Jiaotong University, Xi'an, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3476-8248","authenticated-orcid":false,"given":"Junzhou","family":"Zhao","sequence":"additional","affiliation":[{"name":"Xi'an Jiaotong University, Xi'an, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2382-6289","authenticated-orcid":false,"given":"Hui","family":"Li","sequence":"additional","affiliation":[{"name":"Xidian University, Xi'an, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-3911-4260","authenticated-orcid":false,"given":"Jing","family":"Tao","sequence":"additional","affiliation":[{"name":"Xi'an Jiaotong University, Xi'an, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8826-0362","authenticated-orcid":false,"given":"Xiaohong","family":"Guan","sequence":"additional","affiliation":[{"name":"Xi'an Jiaotong University, Xi'an, China"}]}],"member":"320","published-online":{"date-parts":[[2023,5,30]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICICTA.2010.650"},{"key":"e_1_2_2_2_1","volume-title":"Assessing disease exposure risk with location histories and protecting privacy: A cryptographic approach in response to A global pandemic. CoRR, abs\/2003.14412","author":"Berke Alex","year":"2020","unstructured":"Alex Berke, Michiel A. Bakker, Praneeth Vepakomma, Ramesh Raskar, Kent Larson, and Alex 'Sandy' Pentland. Assessing disease exposure risk with location histories and protecting privacy: A cryptographic approach in response to A global pandemic. CoRR, abs\/2003.14412, 2020."},{"key":"e_1_2_2_3_1","volume-title":"Jeffrey Scott Wilhelm, Josh Bao","author":"Ulbrich Andreas","year":"2021","unstructured":"Andreas Ulbrich, Evgeny Sergeevich Skvortsov, Jeffrey Scott Wilhelm, Josh Bao, Lawrence Tsang, and Will Bradbury. Tracking audience statistics with hyperloglog. 2021."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.2478\/popets-2022-0019"},{"key":"e_1_2_2_5_1","volume-title":"Proceedings of the 13th USENIX Security Symposium, August 9--13, 2004","author":"Dingledine Roger","year":"2004","unstructured":"Roger Dingledine, Nick Mathewson, and Paul F. Syverson. Tor: The second-generation onion router. In Matt Blaze, editor, Proceedings of the 13th USENIX Security Symposium, August 9--13, 2004, San Diego, CA, USA, pages 303--320. USENIX, 2004."},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186728.3164145"},{"key":"e_1_2_2_7_1","volume-title":"Probabilistic counting algorithms for data base applications. Journal of computer and system sciences, 31(2):182--209","author":"Flajolet Philippe","year":"1985","unstructured":"Philippe Flajolet and G Nigel Martin. Probabilistic counting algorithms for data base applications. Journal of computer and system sciences, 31(2):182--209, 1985."},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2452376.2452456"},{"key":"e_1_2_2_9_1","first-page":"19561","article-title":"The flajolet-martin sketch itself preserves differential privacy: Private counting with minimal space","volume":"33","author":"Smith Adam","year":"2020","unstructured":"Adam Smith, Shuang Song, and Abhradeep Guha Thakurta. The flajolet-martin sketch itself preserves differential privacy: Private counting with minimal space. Advances in Neural Information Processing Systems, 33:19561--19572, 2020.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_2_10_1","unstructured":"Charlie Dickens Justin Thaler and Daniel Ting. (nearly) all cardinality estimators are differentially private 2022."},{"key":"e_1_2_2_11_1","volume-title":"USENIX Security","author":"Hu Changhui","year":"2021","unstructured":"Changhui Hu, Jin Li, Zheli Liu, Xiaojie Guo, Yu Wei, Xuan Guang, Grigorios Loukides, and Changyu Dong. How to make private distributed cardinality estimation practical, and get differential privacy for free. In USENIX Security, 2021."},{"key":"e_1_2_2_12_1","first-page":"137","volume-title":"Discrete Mathematics and Theoretical Computer Science","author":"Flajolet Philippe","year":"2007","unstructured":"Philippe Flajolet, \u00c9ric Fusy, Olivier Gandouet, and Fr\u00e9d\u00e9ric Meunier. Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm. In Discrete Mathematics and Theoretical Computer Science, pages 137--156. Discrete Mathematics and Theoretical Computer Science, 2007."},{"key":"e_1_2_2_13_1","volume-title":"EUROCRYPT","author":"Dwork Cynthia","year":"2006","unstructured":"Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In EUROCRYPT, 2006."},{"key":"e_1_2_2_14_1","volume-title":"Concentrated differential privacy. arXiv preprint arXiv:1603.01887","author":"Dwork Cynthia","year":"2016","unstructured":"Cynthia Dwork and Guy N Rothblum. Concentrated differential privacy. arXiv preprint arXiv:1603.01887, 2016."},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53641-4_24"},{"key":"e_1_2_2_16_1","volume-title":"ICML","author":"Kairouz Peter","year":"2021","unstructured":"Peter Kairouz, Ziyu Liu, and Thomas Steinke. The distributed discrete gaussian mechanism for federated learning with secure aggregation. In ICML, 2021."},{"key":"e_1_2_2_17_1","first-page":"15676","article-title":"The discrete gaussian for differential privacy","volume":"33","author":"Canonne Cl\u00e9ment L","year":"2020","unstructured":"Cl\u00e9ment L Canonne, Gautam Kamath, and Thomas Steinke. The discrete gaussian for differential privacy. Advances in Neural Information Processing Systems, 33:15676--15688, 2020.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_2_18_1","volume-title":"The algorithmic foundations of differential privacy. Foundations and Trends\u00ae in Theoretical Computer Science, 9(3--4):211--407","author":"Dwork Cynthia","year":"2014","unstructured":"Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Foundations and Trends\u00ae in Theoretical Computer Science, 9(3--4):211--407, 2014."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2382196.2382264"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32009-5_38"},{"key":"e_1_2_2_21_1","first-page":"6346","volume-title":"Distributed learning without distress: Privacy- preserving empirical risk minimization","author":"Jayaraman Bargav","year":"2018","unstructured":"Bargav Jayaraman, Lingxiao Wang, David Evans, and Quanquan Gu. Distributed learning without distress: Privacy- preserving empirical risk minimization. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicol\u00f2 Cesa-Bianchi, and Roman Garnett, editors, NeurIPS, pages 6346--6357, 2018."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511813603"},{"key":"e_1_2_2_23_1","volume-title":"Probability and Measure","author":"Billingsley Patrick","year":"1986","unstructured":"Patrick Billingsley. Probability and Measure. John Wiley and Sons, second edition, 1986."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1080\/00031305.2012.687494"},{"key":"e_1_2_2_25_1","volume-title":"EUROCRYPT","author":"Keller Marcel","year":"2018","unstructured":"Marcel Keller, Valerio Pastro, and Dragos Rotaru. Overdrive: Making SPDZ great again. In EUROCRYPT, 2018."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45146-4_7"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39212-2_56"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3402457"},{"key":"e_1_2_2_29_1","volume-title":"CCS","author":"Fenske Ellis","year":"2017","unstructured":"Ellis Fenske, Akshaya Mani, Aaron Johnson, and Micah Sherr. Distributed measurement with private set-union cardinality. In CCS, 2017."},{"key":"e_1_2_2_30_1","volume-title":"ESA","author":"Durand Marianne","year":"2003","unstructured":"Marianne Durand and Philippe Flajolet. Loglog counting of large cardinalities (extended abstract). In Giuseppe Di Battista and Uri Zwick, editors, ESA, 2003."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-35404-5_17"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-59870-3_15"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2013.05.011"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIFS.2017.2721360"},{"key":"e_1_2_2_35_1","volume-title":"ITCS","volume":"185","author":"Chen Lijie","year":"2021","unstructured":"Lijie Chen, Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. On distributed differential privacy and counting distinct elements. In ITCS, volume 185, 2021."},{"key":"e_1_2_2_36_1","volume-title":"Shuffle-based private set union: Faster and more secure. IACR Cryptol. ePrint Arch., page 157","author":"Jia Yanxue","year":"2022","unstructured":"Yanxue Jia, Shi-Feng Sun, Hong-Sheng Zhou, Jiajun Du, and Dawu Gu. Shuffle-based private set union: Faster and more secure. IACR Cryptol. ePrint Arch., page 157, 2022."},{"key":"e_1_2_2_37_1","volume-title":"DBSec","author":"Vikas","year":"2014","unstructured":"Vikas G. Ashok and Ravi Mukkamala. A scalable and efficient privacy preserving global itemset support approximation using bloom filters. In DBSec, 2014."},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-19962-7_24"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/PAC.2017.43"},{"key":"e_1_2_2_40_1","volume-title":"Differentially-private multi-party sketching for large-scale statistics. Cryptology ePrint Archive","author":"Choi Seung Geol","year":"2020","unstructured":"Seung Geol Choi, Dana Dachman-Soled, Mukul Kulkarni, and Arkady Yerukhimovich. Differentially-private multi-party sketching for large-scale statistics. Cryptology ePrint Archive, 2020."},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3477531"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3588914","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,16]],"date-time":"2025-04-16T16:54:28Z","timestamp":1744822468000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588914"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,26]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,5,26]]}},"alternative-id":["10.1145\/3588914"],"URL":"https:\/\/doi.org\/10.1145\/3588914","relation":{},"ISSN":["2836-6573"],"issn-type":[{"type":"electronic","value":"2836-6573"}],"subject":[],"published":{"date-parts":[[2023,5,26]]}}}