License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FORC.2020.4
URN: urn:nbn:de:0030-drops-120205
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12020/
Naor, Moni ;
Vexler, Neil
Can Two Walk Together: Privacy Enhancing Methods and Preventing Tracking of Users
Abstract
We present a new concern when collecting data from individuals that arises from the attempt to mitigate privacy leakage in multiple reporting: tracking of users participating in the data collection via the mechanisms added to provide privacy. We present several definitions for untrackable mechanisms, inspired by the differential privacy framework.
Specifically, we define the trackable parameter as the log of the maximum ratio between the probability that a set of reports originated from a single user and the probability that the same set of reports originated from two users (with the same private value). We explore the implications of this new definition. We show how differentially private and untrackable mechanisms can be combined to achieve a bound for the problem of detecting when a certain user changed their private value.
Examining Google’s deployed solution for everlasting privacy, we show that RAPPOR (Erlingsson et al. ACM CCS, 2014) is trackable in our framework for the parameters presented in their paper.
We analyze a variant of randomized response for collecting statistics of single bits, Bitwise Everlasting Privacy, that achieves good accuracy and everlasting privacy, while only being reasonably untrackable, specifically grows linearly in the number of reports. For collecting statistics about data from larger domains (for histograms and heavy hitters) we present a mechanism that prevents tracking for a limited number of responses.
We also present the concept of Mechanism Chaining, using the output of one mechanism as the input of another, in the scope of Differential Privacy, and show that the chaining of an ε₁-LDP mechanism with an ε₂-LDP mechanism is ln (e^{ε₁+ε₂} + 1)/(e^ε₁ + e^ε₂)-LDP and that this bound is tight.
BibTeX - Entry
@InProceedings{naor_et_al:LIPIcs:2020:12020,
author = {Moni Naor and Neil Vexler},
title = {{Can Two Walk Together: Privacy Enhancing Methods and Preventing Tracking of Users}},
booktitle = {1st Symposium on Foundations of Responsible Computing (FORC 2020)},
pages = {4:1--4:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-142-9},
ISSN = {1868-8969},
year = {2020},
volume = {156},
editor = {Aaron Roth},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12020},
URN = {urn:nbn:de:0030-drops-120205},
doi = {10.4230/LIPIcs.FORC.2020.4},
annote = {Keywords: Differential Privacy, Surveillance}
}
|
Keywords: |
|
Differential Privacy, Surveillance |
|
Collection: |
|
1st Symposium on Foundations of Responsible Computing (FORC 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
18.05.2020 |
