Please use this identifier to cite or link to this item:
Main Title: P2KMV: A Privacy-preserving Counting Sketch for Efficient and Accurate Set Intersection Cardinality Estimations
Author(s): Sparka, Hagen
Tschorsch, Florian
Scheuermann, Björn
Type: Preprint
Language Code: en
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.
Issue Date: 1-May-2018
Date Available: 8-Apr-2019
DDC Class: 004 Datenverarbeitung; Informatik
Subject(s): privacy
counting sketch
user statistics
data minimization
Series: Cryptology ePrint Archive
Series Number: 2018/234
Appears in Collections:FG Distributed Security Infrastructures (DSI) » Publications

Files in This Item:
File Description SizeFormat 
sparka_etal_2018.pdf945.35 kBAdobe PDFThumbnail

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.