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

  1. Ninghui Li
  2. Kunal Talwar
  3. Somesh Jha
  4. Abhradeep Thakurta
  5. Vitaly Feldman
  6. Tianhao Wang
  7. Jonathan Ullman
  8. Philip S. Yu

In Computer Science Applications

  1. Ninghui Li
  2. Tianhao Wang
  3. Vitaly Feldman
  4. Kunal Talwar
  5. Somesh Jha
  6. Dan Boneh
  7. Aleksandra Korolova
  8. Divesh Srivastava

In Statistics and Probability

  1. Ninghui Li
  2. Somesh Jha
  3. Tianhao Wang
  4. Kunal Talwar
  5. Graham Cormode
  6. Abhradeep Thakurta
  7. Divesh Srivastava
  8. Xiaokui Xiao

In Privacy & Security

  1. Ninghui Li
  2. Somesh Jha
  3. Tianhao Wang
  4. Kunal Talwar
  5. Vitaly Feldman
  6. Abhradeep Thakurta
  7. Jonathan Ullman
  8. Aleksandra Korolova

In Information Theory

  1. Ninghui Li
  2. Tianhao Wang
  3. Somesh Jha
  4. Xiaokui Xiao
  5. Y. Yang
  6. Henry Corrigan-Gibbs
  7. Dan Boneh
  8. Aleksandra Korolova

Citations in the corpus