Paper 2018/234

P2KMV: A Privacy-preserving Counting Sketch for Efficient and Accurate Set Intersection Cardinality Estimations

Hagen Sparka, Florian Tschorsch, and Björn Scheuermann

Abstract

In this paper, we propose P2KMV, a novel privacy-preserving counting sketch, based on the k minimum values algorithm. With P2KMV, we offer a versatile privacy-enhanced technology for obtaining statistics, following the principle of data minimization, and aiming for the sweet spot between privacy, accuracy, and computational efficiency. As our main contribution, we develop methods to perform set operations, which facilitate cardinality estimates under strong privacy requirements. Most notably, we propose an efficient, privacy-preserving algorithm to estimate the set intersection cardinality. P2KMV provides plausible deniability for all data items contained in the sketch. We discuss the algorithm's privacy guarantees as well as the accuracy of the obtained estimates. An experimental evaluation confirms our analytical expectations and provides insights regarding parameter choices.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Preprint. MINOR revision.
Keywords
privacy
Contact author(s)
florian tschorsch @ tu-berlin de
History
2018-03-05: received
Short URL
https://ia.cr/2018/234
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/234,
      author = {Hagen Sparka and Florian Tschorsch and Björn Scheuermann},
      title = {P2KMV: A Privacy-preserving Counting Sketch for Efficient and Accurate Set Intersection Cardinality Estimations},
      howpublished = {Cryptology ePrint Archive, Paper 2018/234},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/234}},
      url = {https://eprint.iacr.org/2018/234}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.