Peter Kairouz [1] gave a talk [2] recently describing mechanisms to get around the limitations of DP described in other comments.
The Algorithmic Foundations of Differential Privacy (2014) [pdf]
11–14 of 14 posts
Re: The Algorithmic Foundations of Differential Privacy (2014) [pdf]
#12Differential privacy appears regularly on Hacker News, with either theoretical articles or projects that aim to implement it. Yet often there is a huge gap between both. For example, Apple has touted about its use of differential privacy, but researchers [1] have shown that the privacy budget is reset every day and the parameters, buried inside the code, lack a proper derivation. Similarly, Uber seems to use DP for i…
Based on my limited understanding* of differential privacy, it falls short on exactness (of aggregate values) and robustness (against malicious clients). I've lately been studying the literature on function secret sharing and I think it is a better alternative to DP.
Take this paper: https://www.henrycg.com/files/academic/pres/nsdi17prio-slide...
Prio: Private, Robust and Scalable Computation of Aggregate Statistics
Data collection and aggregation is performed by multiple servers. Every user splits up her response into multiple shares and sends one share to each server. I've understood how private sums can be computed. Let me explain it with a straw-man scheme.
Example (slide 26):
x_1 (user 1 is on Bay Bridge):- true == 1 == 15 + (-12) + (-2)
x_2 (user 2 is on Bay Bridge):- false == 1 == (-10) + 7 + 3 ...
If all users send shares of their data to the servers in this manner AND as long as at least one server doesn't reveal the identities of the people who sent it responses, the servers can exchange the sum of the shares they've received. Adding the three responses will allow the servers to infer that there are _ number of users on Bay Bridge without revealing their identities.
This system can be made robust by using Secret-shared non-interactive proofs (SNIPs). This allows servers to test if Valid(X) holds without leaking X.
The authors also bring up the literature on computing interesting aggregates using private sums: average, variance, most popular (approx.), min and max (approx.), quality of regression model R^2, least-squares regression, stochastic gradient descent.
Bottom line: I found the discussion on deployment scenarios very interesting. Data servers with jurisdictional/geographical diversity, app store-app developer collaborations for eliminating risk in telemetry data analysis, enterprises contracting with external auditors for analyzing customer data, etc.
* - I understand the randomized response and, to some extent, the RAPPOR technique (used for collecting Chrome telemetry data) but the other literature in that community goes over my head.
* * - This technique is a black box to me at the moment.
Re: The Algorithmic Foundations of Differential Privacy (2014) [pdf]
#13Some interesting concepts to consider:
K-anonymity,
ℓ-diversity,
t-closeness.
From the paper (https://www.liebertpub.com/doi/full/10.1089/bio.2014.0069) I wrote a while ago:
While the risk of re-identification (of a record or individual participant) might be virtually non-existent with synthetic data, one could predict unknown attributes of a known individual, given an ideal model of synthesis. In other words, an attacker could find unknown attributes of some individual with a certain probability by looking for the closest match in the synthetic data. This is known as attribute disclosure.
There are several methods for quantifying attribute disclosure, most notably t-closeness, which is defined as: An equivalence class is said to have t-closeness if the distance between the distribution of a sensitive attribute in this class and the distribution of the attribute in the whole table is no more than a threshold. A table is said to have t-closeness if all equivalence classes have t-closeness.
In short: the distribution of a particular sensitive value should not be further away than a distance t from the overall distribution.
Using the t-closeness metric circumvents issues associated with k-anonymity and ℓ-diversity. Briefly, k-anonymity states that a certain attribute class should be present in at least k records, which introduces ambiguity in the data set. However, if each of the k equivalence classes are the same, properties could still be resolved simply by elimination. The ℓ-diversity metric circumvents this problem by adding a further requirement: in addition to the class to being seen in k records, these records must have at least ℓ ‘well represented’ values. But if an attacker knows the real-world distribution of values, then attributes could still be disclosed with a certain probability, simply by combining different data sources
Re: The Algorithmic Foundations of Differential Privacy (2014) [pdf]
#14Differential privacy appears regularly on Hacker News, with either theoretical articles or projects that aim to implement it. Yet often there is a huge gap between both. For example, Apple has touted about its use of differential privacy, but researchers [1] have shown that the privacy budget is reset every day and the parameters, buried inside the code, lack a proper derivation. Similarly, Uber seems to use DP for i…
Apple's epsilon reset problem is real, but it's worth pointing out that they use additional heuristics based on hashing that plausibly add another layer of privacy [1]. Plausibly, not provably, but it's a bit more than just resetting epsilon. I believe Google and Microsoft use similar tweaked forms of differential privacy. In particular, note that all of these companies -- again, going off public papers -- use the "local" variant of differential privacy, which requires less trust on the user's part.
The question of "lifetime" differential privacy, for a single user across different computations and datasets, is still fairly open as far as I know.
[1] https://machinelearning.apple.com/docs/learning-with-privacy...