PaperlayerView exact revision on arXiv

Source-linked AI summary

RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response

Úlfar Erlingsson, Vasyl Pihur, Aleksandra Korolova

arXiv:1407.6981v2cs.CR

TL;DR

RAPPOR addresses the need to collect useful, up-to-date client statistics without exposing individual users or creating linkable reports. It combines local randomized response, Bloom filters, memoization, and a decoding framework to estimate population statistics. The paper reports strong privacy protection across repeated reporting while supporting practical, high-utility analysis, subject to limitations from repeated participation and correlated values.

  • Problem

    Service operators need current client statistics for software improvement and security, but direct collection can compromise users’ privacy and externalities such as linkable identifiers can increase privacy risks.

  • Method

    RAPPOR applies randomized response locally to Bloom-filter encodings, memoizes permanent noisy values, adds instantaneous randomization, and decodes aggregate reports statistically.

  • Results

    RAPPOR provides strong differential-privacy protection for repeated reports while collecting statistics on client-side strings and supporting high-utility aggregate decoding.

  • Takeaways & Limitations

    RAPPOR enables service operators to crowdsource population statistics while limiting what can be learned about individual clients and avoiding trusted third parties.

  • Takeaways & Limitations

    Operators can weaken the nominal longitudinal guarantee through repeated participation, while correlated successive values make memoization guarantees progressively weaker.

Abstract

from arXiv · show

Randomized Aggregatable Privacy-Preserving Ordinal Response, or RAPPOR, is a technology for crowdsourcing statistics from end-user client software, anonymously, with strong privacy guarantees. In short, RAPPORs allow the forest of client data to be studied, without permitting the possibility of looking at individual trees. By applying randomized response in a novel manner, RAPPOR provides the mechanisms for such collection as well as for efficient, high-utility analysis of the collected data. In particular, RAPPOR permits statistics to be collected on the population of client-side strings with strong privacy guarantees for each client, and without linkability of their reports. This paper describes and motivates RAPPOR, details its differential-privacy and utility guarantees, discusses its practical deployment and properties in the face of different attack models, and, finally, gives results of its application to both synthetic and real-world data.

1 Introduction

RAPPOR addresses the tension between collecting useful client statistics and protecting users’ privacy. It combines randomized response, Bloom filters, memoization, and local processing to support repeated collection without linkable reports.

  • Traditional randomized response preserves privacy for one-time collection, but its guarantee degrades when the same respondent is surveyed repeatedly.Repeated observations can make an underlying answer increasingly evident, motivating mechanisms designed for longitudinal collection.
  • RAPPOR collects statistics about client-side strings while providing strong per-client differential-privacy protection, even when clients report the same value repeatedly.The mechanism is designed for categories, frequencies, histograms, and other set statistics without requiring a trusted third party.
  • RAPPOR protects repeated reports by applying randomized response twice with memoization, separating a permanent noisy value from later instantaneous reports.The permanent response is reused over time, while instantaneous responses add further randomization and reduce linkability.
  • Applying randomized response to Bloom filters lets RAPPOR collect statistics about arbitrary sets of strings while adding uncertainty because multiple values can map to the same bits.Bloom-filter redundancy also supports learning across cohorts, although cohort size creates a collision-versus-signal trade-off.
  • RAPPOR’s decoding framework combines hypothesis testing, least-squares solving, and LASSO regression to obtain high-utility population statistics.The paper presents this framework as a novel approach to analyzing the collected reports.
  • RAPPOR targets a service-operator dilemma: direct collection can compromise users, while collecting no data limits software improvements and security monitoring.Existing pragmatic controls such as deletion, scrubbing, access control, and auditing provide limited provably strong privacy guarantees.

2 The Fundamental RAPPOR Algorithm

The fundamental RAPPOR algorithm locally transforms a client value into a noisy Bloom-filter report. Permanent memoization protects longitudinal privacy, while instantaneous randomization limits linkability and adds short-term protection.

  • Bloom filters compact reports and complicate inference because one bit may correspond to multiple data items.Multiple values mapping to the same bits make learning the client’s actual value harder.
  • RAPPOR hashes a client’s value v onto a Bloom filter B of size k using h hash functions.The resulting bit pattern is the signal subsequently randomized by the client.
  • The Permanent randomized response creates a noisy bit array B′ from B, memoizes it, and reuses it for all future reports of v.The parameter f controls the longitudinal privacy guarantee.
  • The Instantaneous randomized response generates a randomized report S from B′ and sends S to the server.This extra randomization makes tracking based on B′ more difficult and provides independently tunable short-term privacy.
  • Figure 1 illustrates the pipeline with v = “68”, k = 256, h = 4, p = 0.5, q = 0.75, and f = 0.5.In the example, 145 of 256 reported bits are set, and two of four Bloom-filter bits survive into B′ and the final report.
  • RAPPOR Modifications: RAPPOR can omit stages for simpler settings: one-time collection can skip instantaneous randomization, and small fixed string sets can replace Bloom filters with deterministic bit mappings.Combining both changes yields Basic One-time RAPPOR.

3 Differential Privacy of RAPPOR

RAPPOR combines permanent and instantaneous randomized response to provide differential privacy for one-time and repeated collections. The paper proves privacy bounds for both stages and notes that longitudinal bounds depend on assumptions about what attackers learn.

  • RAPPOR adopts differential privacy to provide rigorous protection against attackers with potentially extensive prior knowledge.
  • Permanent randomized response protects the randomized Bloom-filter representation, while instantaneous randomized response limits longitudinal tracking of its use.
  • Theorem 1 establishes that permanent randomized response satisfies ϵ∞-differential privacy.
  • For one-time collection, the attacker must infer the permanent randomized value from a single doubly randomized report, yielding stronger protection than assuming that value is known.
  • The instantaneous response mechanism has bit probabilities determined by whether the underlying Bloom-filter bit is set, with both probabilities mixing randomized and true responses through f.
  • Computing the privacy bound for the nth collection requires assumptions about how effectively the attacker can learn the permanent randomized value; the bound approaches but remains below ϵ∞.

4 High-utility Decoding of Reports

RAPPOR decodes noisy, Bloom-filter-based reports with a multistage statistical pipeline and cohort redundancy. Utility depends on parameter choices and imposes sample-size and frequency limits, especially for the unmodified algorithm.

  • Decoding compensates for Bloom-filter information loss and privacy noise using hypothesis testing, least squares, and LASSO regression.
  • Clients are permanently assigned to m cohorts with different h-hash-function Bloom filters, balancing collision reduction against reduced per-cohort signal.
  • LASSO selects candidate strings from a sparse Bloom-filter design matrix, after which least squares estimates counts, standard errors, and p-values.
  • Two hash functions provide the clearest utility preference, whereas Bloom-filter size k and cohort count m show no definitive optimal direction.
  • 10,000 strings are reliably detectable in a sample of ten billion, while 1,000 are detectable in a sample of one hundred million.
  • The theoretical detection bound applies only to Basic One-time RAPPOR and is achievable under a uniform frequency distribution; high-frequency strings reduce tail detectability.
  • For ln(3)-differential privacy, detecting frequencies of 1%, 0.1%, and 0.01% requires one million, one hundred million, and ten billion samples, respectively.

5 Experiments and Evaluation

The evaluation uses simulated and real-world collections to test distribution learning, string discovery, Windows-process recovery, and Chrome-homepage analysis under RAPPOR. Results show that utility improves with sufficient reports and identifies frequent strings while protecting the long tail.

  • Simulated collections: With 10,000 reports, the estimated Normal distribution is too noisy; the bell curve emerges at 100,000 reports and improves at one million.The simulation uses mean 50, standard deviation 10, q = 0.75, p = 0.5, and ϵ = ln(3).
  • Simulated collections: 47 strings were estimated to have nonzero counts, including only 2 false positives after Bonferroni correction.The analysis used one million reports generated from an exponentially decaying string population.
  • Simulated collections: All common strings above approximately 1% frequency were detected, while the long tail remained protected by the privacy mechanism.Figure 5 displays true frequencies vertically and detected strings in dark red.
  • Real-world collections: 10 Windows processes were identified with frequencies ranging from 2.5% to 4.5% using a 5% False Discovery Rate.The estimated frequency of BADAP-PLE.COM was 2.6%; the other nine detections were common Windows tasks.
  • Real-world collections: 31 unexpected homepage domains were discovered, and although fewer than 0.5% of 8,616 candidate URLs were significant, they accounted for about 85% of total probability mass.The Chrome collection used approximately 14 million daily respondents and targeted domains exceeding 0.1% frequency.

6 Attack Models and Limitations

RAPPOR’s attack analysis covers single-report, windowed, unlimited-collection, and targeted-user adversaries, while highlighting limits from repeated participation, correlations, and changing values.

  • Attack Models: Three attacker models range from one report per user to unlimited collection, with windowed access bounded by longitudinal privacy guarantee ϵ∞.The unlimited attacker can learn the Permanent randomized response with certainty but cannot improve beyond ϵ∞.
  • Limitations: Operators can exceed the nominal ϵ∞ protection by soliciting repeated participation, including through multiple accounts or devices.Running collections per account with a shared Permanent randomized response can mitigate this issue to some extent.
  • Attack Models: Targeting users individually can be counter-productive because some clients permanently randomize all positions corresponding to set Bloom-filter bits to zero.These clients contribute no useful information, while all users retain plausible deniability proportional to the fraction providing no information.
  • Attack Models: For relatively rare strings, Bloom-filter bits provide weak evidence: most clients whose two target bits are set reported a different value.At frequencies below 10%, even both set bits make non-reporting more likely than reporting.
  • Limitations: RAPPOR is not a panacea and should be deployed cautiously with application-appropriate parameters as part of a broader privacy-protection strategy.The paper specifically recommends limited data retention and other pragmatic processes.
  • Limitations: Privacy can degrade when clients contribute correlated properties, reports are collected too broadly, cohorts facilitate tracking, or Bloom filters contain too many bits.Careful collection design is required, and rapidly changing correlated values require additional measures such as budgeting ϵ∞ over time.

7 Related Work

Related work addresses privacy-preserving aggregate learning through randomized response, dimensionality reduction, and distributed protocols. RAPPOR distinguishes itself through broader decoding, Instantaneous randomized response, and local privacy protection.

  • Privacy-Preserving Aggregation: Prior work studies how untrusted aggregators can learn heavy hitters or run learning algorithms while guaranteeing contributing-client privacy.These efforts form the broader research context for RAPPOR’s privacy-preserving aggregate statistics.
  • Randomized Response: Randomized response suits RAPPOR because client values may be categorical and local privacy must not depend on a trusted third party.The Exponential mechanism requires data-space knowledge unavailable to the client, while Laplace noise is unsuitable for categorical values.
  • Dimensionality Reduction: Bloom filters provide compact data representations that reduce client transmission costs while leveraging widely adopted technology.Related dimensionality-reduction work also seeks improved privacy while retaining utility.
  • Closest Prior Work: Compared with the most similar prior work, RAPPOR adds extensive decoding for more complex queries and a second randomization step that hinders report linking.The comparison emphasizes both statistical analysis and longitudinal unlinkability.
  • Distributed Privacy: Other approaches remove trusted aggregators through distributed trust or rely on honest-but-curious proxies and aggregators with commitments.These protocols differ from RAPPOR’s purely client-based privacy model.
  • Longitudinal Privacy: Related longitudinal-privacy work reconstructs query answers from previous answers, whereas RAPPOR uses Instantaneous randomized response within its own collection design.The paper notes a high-level resemblance between these approaches.

8 Summary

RAPPOR is presented as a practical, mathematically rigorous platform for anonymous population-statistics collection. It supports repeated client data collection with longitudinal guarantees and keeps privacy protection on the client.

  • Summary: RAPPOR is a flexible, mathematically rigorous, practical platform for anonymous crowdsourcing of population statistics on client-side data.Its purpose is privacy-preserving aggregate analysis rather than inspection of individual client records.
  • Summary: RAPPOR handles multiple collections from the same client through well-defined longitudinal differential privacy guarantees.Tunable parameters allow risk and utility to be balanced over time for different attack models.
  • Summary: RAPPOR is purely client-based, eliminating the need for a trusted third-party server and returning control over client data to users.This local privacy model is a central design characteristic of the platform.

Appendix

The appendix presents an elementary inequality observation and a proof by contradiction under nonnegative and positive variable assumptions.

  • Appendix: Observation 1 states an inequality for nonnegative a and b and positive c and d.The displayed relation compares the ratio (a+b)/(c+d) with a/c.
  • Appendix: The proof assumes without loss of generality that a≤d and derives bc>ad from the negation of the claimed inequality.This contradicts the stated assumption and establishes the observation.

Deriving Limits on Learning

The paper derives theoretical limits for Basic One-time RAPPOR, using its lossless decoding to bound what can be learned from N reports. It frames detectable signal bits as a multiple-testing problem and derives the largest support size detectable under the stated conditions.

  • Basic One-time RAPPOR establishes theoretical learning limits for a parameter configuration and N collected reports, providing an upper bound for RAPPOR modifications.The bound follows because Basic One-time RAPPOR is more efficient than the original RAPPOR.
  • Decoding estimates the number of reports in which bit i was truly set from the observed count C_i, assuming f = 0.The passages introduce the expected observed count and the resulting estimator but do not reproduce the complete definitions in text.
  • Under T_i = 0, the estimator's variance determines the uncertainty used to assess whether bit i has a nonzero true count.The variance is stated for the null case in which bit i was never truly set.
  • The detection test compares H0: T_i = 0 with H1: T_i > 0, using p = 0.5 and a standard-deviation threshold.The critical value is taken from the standard normal distribution.
  • Bonferroni correction divides the significance threshold by M, the number of tests, to control false positive findings across the k-bit array.Here M equals k, the bit-array length.
  • The largest detectable support x occurs when x bits share nearly all probability mass uniformly, giving each nonzero bit frequency 1/x and expected count N/x.The remaining M − x bits have essentially zero probability.
Loading 1407.6981v2…