Building a RAPPOR with the Unknown: Privacy-Preserving Learning of Associations and Data Dictionaries

Citations Over TimeTop 10% of 2016 papers

Abstract

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.

Related Papers

• → Calibrating Noise to Sensitivity in Private Data Analysis(2006)6,894 cited
• → Building a RAPPOR with the Unknown: Privacy-Preserving Learning of Associations and Data Dictionaries(2016)279 cited
• Perturbation based privacy preserving data mining techniques for real-world data(2008)
• → A Condensation Approach to Privacy Preserving Data Mining(2014)