An Effective and Differentially Private Protocol for Secure Distributed Cardinality Estimation
Open Access
- 26 May 2023
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 1 (1) , 1-24
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.Keywords
All Related Versions
Funding Information
- National Key R&D Program of China (2021YFB1715600)
- National Natural Science Foundation of China (U22B2019, 62272372)
- Shenzhen Basic Research Grant (JCYJ20170816100819428)
This publication has 19 references indexed in Scilit:
- An Efficient Toolkit for Computing Private Set Operations2017
- Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds2016
- Privately Computing Set-Union and Set-Intersection Cardinality via Bloom Filters2015
- An algorithm for privacy-preserving distributed user statisticsComputer Networks, 2013
- Secure Equality and Greater-Than Tests with Sublinear Online Complexity2013
- Who Invented the Delta Method?The American Statistician, 2012
- Multiparty Computation from Somewhat Homomorphic Encryption2012
- Fast and Private Computation of Cardinality of Set Intersection and Union2012
- Probability and Computing2005
- Scalable Protocols for Authenticated Group Key Exchange2003