Building a RAPPOR with the Unknown: Privacy-Preserving Learning of Associations and Data Dictionaries
By Giulia C. Fanti, Vasyl Pihur, Ú. Erlingsson. 2015
318 citations recorded by the source corpus.
Abstract Techniques based on randomized response enable the collection of potentially sensitive data from clients in a privacy-preserving manner with strong local differential privacy guarantees. A recent such technology, RAPPOR [12], enables estimation of the marginal frequencies of a set of strings via privacy-preserving crowdsourcing. However, this original estimation process relies on a known dictionary of possible strings; in practice, this dictionary can be extremely large and/or unknown. In this paper, we propose a novel decoding algorithm for the RAPPOR mechanism that enables the estimation of “unknown unknowns,” i.e., strings we do not know we should be estimating. To enable learning without explicit dictionary knowledge, we develop methodology for estimating the joint distribution of multiple variables collected with RAPPOR. Our contributions are not RAPPOR-specific, and can be generalized to other local differential privacy mechanisms for learning distributions of string-valued random variables.
Subfields: Artificial Intelligence, Computer Science Applications, Statistics and Probability, Privacy & Security, Information Theory
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Ninghui Li
- Kunal Talwar
- Somesh Jha
- Abhradeep Thakurta
- Vitaly Feldman
- Tianhao Wang
- Jonathan Ullman
- Philip S. Yu
In Computer Science Applications
- Ninghui Li
- Tianhao Wang
- Vitaly Feldman
- Kunal Talwar
- Somesh Jha
- Dan Boneh
- Aleksandra Korolova
- Divesh Srivastava
In Statistics and Probability
- Ninghui Li
- Somesh Jha
- Tianhao Wang
- Kunal Talwar
- Graham Cormode
- Abhradeep Thakurta
- Divesh Srivastava
- Xiaokui Xiao
In Privacy & Security
- Ninghui Li
- Somesh Jha
- Tianhao Wang
- Kunal Talwar
- Vitaly Feldman
- Abhradeep Thakurta
- Jonathan Ullman
- Aleksandra Korolova
In Information Theory
- Ninghui Li
- Tianhao Wang
- Somesh Jha
- Xiaokui Xiao
- Y. Yang
- Henry Corrigan-Gibbs
- Dan Boneh
- Aleksandra Korolova
Citations in the corpus
- Secure Federated Submodel Learning (2019, methodology): “, in Google [46], [47], Apple [48], and Microsoft [49]), as well as lasting academic”
- Honeycrisp: large-scale differentially private aggregation without a trusted core (2019, background): “We compare three different systems: 1) a RAPPOR-style solution (LDP) that achieves differential privacy in the local setting by making use of the randomized response mechanism; 2) a hypothetical solution (GDP) that uploads the unencrypted data to the aggregator, which then releases the result using ”
- The Power of the Hybrid Model for Mean Estimation (2018, background): “However, it is well understood theoretically and empirically that utility outcomes are far worse in the LM than in the TCM [11, 16, 22, 27, 38].”
- Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity (2018, background): “…of user data into carefully constructed fragments to increase users’ privacy has been explored for specific applications, e.g., by Fanti et al. [FPE16] which fragmented users’ string values into overlapping n -grams, to bound sensitivity while enabling an aggregator to reconstruct popular user…”
- Differentially-Private "Draw and Discard" Machine Learning (2018, background): “In particular, it supplements private histogram collection of RAPPOR [16] and learning simple associations [18] by allowing estimation of arbitrary conditional expectations.”
- Collecting Telemetry Data Privately (2017, background): “In the context of telemetry collection one typically considers algorithms that exhibit differential privacy in the local model [12, 14, 7, 5, 3, 18], also called randomized response model [19], γ-amplification [13], or FRAPP [1].”
- Marginal Release Under Local Differential Privacy (2017, methodology): “While this problem has been well-studied under centralized differential privacy, there is limited prior work that applies in the local DP model for two-way marginals [16]; in this paper, we seek to give strong guarantees for arbitrary marginals.”
- Prochlo: Strong Privacy for Analytics in the Crowd (2017, background): “[30], such multidimensional analysis over long-tail distributions (of Web pages) is a poor fit for local differential privacy methods.”
- BLENDER: Enabling Local Search with a Hybrid Differential Privacy Model (2017, methodology): “The subsequent usage of this head list in the algorithm operating in the local model helps overcome one of the main challenges to utility of privacy-preserving algorithms in the local model [15].”
- Prio: Private, Robust, and Scalable Computation of Aggregate Statistics (2017, methodology): “To ameliorate these threats, major technology companies, including Apple [72] and Google [57, 58], have deployed privacy-preserving systems for the collection of user data.”
- Local, Private, Efficient Protocols for Succinct Histograms (2015, background): “In addition to the works mentioned so far on frequency estimation [21, 14, 9, 11], many papers have studied the complexity of local private protocols for specific tasks.”
- Collecting and Analyzing Multidimensional Data with Local Differential Privacy (2019, background): “A follow-up paper [19] extends RAPPOR to more complex statistics such as joint-distributions and association testing, as well as categorical attributes that contain a large number of potential values, such as a user’s home page.”
- Encode, Shuffle, Analyze Privacy Revisited: Formalizations and Empirical Evaluation (2020, background): “, about adaptivity [3], [14], sketching [1], [18], [15], [16], or succinctness of communication [15], [16], [19]).”
- PROCHLO: Strong Privacy for Analytics in the Crowd (2017, background): “[30], such multidimensional analysis over long-tail distributions (of Web pages) is a poor fit for local differential privacy methods.”
- Cardinality Estimators do not Preserve Privacy (2018, methodology): “This model is often used to develop privacy-preserving systems to gather statistics [8, 9, 21, 23].”
- Locally Differentially Private Frequent Itemset Mining (2018, methodology): “The problem of finding heavy hitters in a very large domain was exhaustively investigated [21], [27], [20], [5], [33], [6], [37], [10].”
- PrivTrie: Effective Frequent Term Discovery under Local Differential Privacy (2018, methodology): “Currently, to our knowledge the best known solution for discovering frequent new terms under LDP is an augmented version of RAPPOR [5], which is used in Google’s Chrome browser.”