Building a RAPPOR with the Unknown: Privacy-Preserving Learning of Associations and Data Dictionaries
Authors: Giulia Fanti (U.C. Berkeley), Vasyl Pihur (Google), Úlfar Erlingsson (Google)
Volume: 2016
Issue: 3
Pages: 41–61
DOI: https://doi.org/10.1515/popets-2016-0015
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.
Keywords: privacy-preserving analytics, differential privacy
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 license.
