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

dc.contributor.authorSparka, Hagen
dc.contributor.authorTschorsch, Florian
dc.contributor.authorScheuermann, Björn
dc.date.accessioned2019-04-08T16:07:19Z
dc.date.available2019-04-08T16:07:19Z
dc.date.issued2018-05-01
dc.description.abstractIn 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.en
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/9301
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-8374
dc.language.isoenen
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subject.ddc004 Datenverarbeitung; Informatiken
dc.subject.otherprivacyen
dc.subject.othercounting sketchen
dc.subject.otherP2KMVen
dc.subject.otheruser statisticsen
dc.subject.otherdata minimizationen
dc.titleP2KMV: A Privacy-preserving Counting Sketch for Efficient and Accurate Set Intersection Cardinality Estimationsen
dc.typePreprinten
dc.type.versionsubmittedVersionen
tub.accessrights.dnbfreeen
tub.affiliationFak. 4 Elektrotechnik und Informatik::Inst. Softwaretechnik und Theoretische Informatik::FG Distributed Security Infrastructures (DSI)de
tub.affiliation.facultyFak. 4 Elektrotechnik und Informatikde
tub.affiliation.groupFG Distributed Security Infrastructures (DSI)de
tub.affiliation.instituteInst. Softwaretechnik und Theoretische Informatikde
tub.publisher.universityorinstitutionTechnische Universität Berlinen
tub.series.issuenumber2018/234en
tub.series.nameCryptology ePrint Archiveen

Files

Original bundle
Now showing 1 - 1 of 1
Loading…
Thumbnail Image
Name:
sparka_etal_2018.pdf
Size:
945.35 KB
Format:
Adobe Portable Document Format
Description:
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
5.75 KB
Format:
Item-specific license agreed upon to submission
Description:

Collections