Paper 2020/1576
How to Make Private Distributed Cardinality Estimation Practical, and Get Differential Privacy for Free
Changhui Hu, Jin Li, Zheli Liu, Xiaojie Guo, Yu Wei, Xuan Guang, Grigorios Loukides, and Changyu Dong
Abstract
Secure computation is a promising privacy enhancing technology, but it is often not scalable enough for data intensive applications. On the other hand, the use of sketches has gained popularity in data mining, because sketches often give rise to highly efficient and scalable sub-linear algorithms. It is natural to ask: what if we put secure computation and sketches together? We investigated the question and the findings are interesting: we can get security, we can get scalability, and somewhat unexpectedly, we can also get differential privacy -- for free. Our study started from building a secure computation protocol based on the Flajolet-Martin (FM) sketches, for solving the Private Distributed Cardinality Estimation (PDCE) problem, which is a fundamental problem with applications ranging from crowd tracking to network monitoring. The state of art protocol for PDCE (Fenske et al. CCS'17) is computationally expensive and not scalable enough to cope with big data applications, which prompted us to design a better protocol. Our further analysis revealed that if the cardinality to be estimated is large enough, our protocol can achieve
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. Major revision. to appear in USENIX Security '21
- Keywords
- multiparty computationdifferential privacyPrivate Distributed Cardinality EstimationPrivate Set Union CardinalityFlajolet-Martin sketch
- Contact author(s)
- changyu dong @ newcastle ac uk
- History
- 2020-12-31: revised
- 2020-12-21: received
- See all versions
- Short URL
- https://ia.cr/2020/1576
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2020/1576, author = {Changhui Hu and Jin Li and Zheli Liu and Xiaojie Guo and Yu Wei and Xuan Guang and Grigorios Loukides and Changyu Dong}, title = {How to Make Private Distributed Cardinality Estimation Practical, and Get Differential Privacy for Free}, howpublished = {Cryptology {ePrint} Archive, Paper 2020/1576}, year = {2020}, url = {https://eprint.iacr.org/2020/1576} }