Randomized Response

The canonical form answers a sensitive yes/no question. A respondent tells the truth with probability p and lies (gives the opposite answer) with probability 1-p. The data curator, knowing p, can later debias the aggregated results to estimate the true population proportion. This provides plausible deniability for every individual response.

• Example: Surveying for a stigmatized behavior. With p=0.75, a 'yes' answer could be true, or a lie from someone who actually did not engage in the behavior.

For questions with k possible categorical answers, the mechanism generalizes. The respondent reports their true answer with probability p. With the remaining probability (1-p), they select uniformly at random from the other (k-1) categories. The perturbation probability is often structured as a k x k probability matrix.

• Utility-Privacy Trade-off: A higher p preserves more data utility but provides weaker privacy. The optimal design balances the probability of truth-telling against random guessing.

Randomized response satisfies ε-local differential privacy (LDP), where ε = ln( p / ( (1-p)/(k-1) ) ) for the k-ary variant. This provides a rigorous, quantifiable privacy guarantee:

• Client-Side Privacy: Perturbation happens on the user's device before any data leaves.
• Untrusted Curator: The server receiving the noisy data learns nothing definitive about any individual.
• Post-Processing Immunity: Any analysis on the perturbed data inherits the LDP guarantee.

In Federated Learning, randomized response can be applied to discrete model updates or metadata. For example, clients can report:

• Which of a set of predefined training labels was most common locally.
• A binary indicator for whether a local metric exceeded a threshold.
• A quantized element of a model update, perturbed before aggregation. This provides a lightweight, communication-efficient alternative to adding continuous noise (e.g., Gaussian) to full gradient vectors, suitable for extremely resource-constrained edge devices.

Proposed by Stanley Warner in 1965, this is the original randomized response design for a sensitive binary attribute A. The respondent uses a randomizing device (e.g., a spinner):

• With probability p: Answer the question 'Do you have attribute A?'
• With probability 1-p: Answer the opposite question 'Do you NOT have attribute A?' The unbiased estimator for the true proportion π_A is: π̂_A = [λ - (1-p)] / (2p - 1), where λ is the observed 'yes' proportion in the perturbed data.

While simple and elegant, randomized response has key limitations in modern ML contexts:

• High Variance for Strong Privacy: Small ε (strong privacy) requires p close to a random guess, injecting significant noise that harms utility.
• Discrete Data Focus: Naturally suited for categorical or binary data; less efficient for continuous, high-dimensional vectors like neural network gradients.
• Composition Overhead: Repeated queries consume privacy budget rapidly unless careful amplification by subsampling or shuffling is employed. It is often used as a building block within more complex LDP protocols for histograms, heavy hitters, or mean estimation.

Randomized response serves as a simple, practical local differential privacy (LDP) mechanism for client devices in federated learning. Before sending an update (e.g., a gradient or a binary label), a device flips its true value with a known probability p. This provides a formal, client-side privacy guarantee without requiring trust in a central server. The server can then compute unbiased aggregate statistics from the perturbed reports, enabling privacy-preserving model training.

A core application is estimating the distribution of sensitive attributes across a population without collecting raw data. For example, to estimate the proportion of users with a certain medical condition:

• Each user answers a sensitive question ("Do you have condition X?") using a randomized response protocol.
• The analyst collects the noisy, privatized answers.
• Using knowledge of the randomization probability p, the analyst can debias the aggregate count and calculate an accurate estimate of the true frequency, all while providing LDP to each user.

Companies use randomized response variants to collect usage statistics and diagnostic telemetry from end-user applications while respecting privacy. For instance, to learn if a feature is rarely used:

• The client software locally decides to report the true binary value ("used/not used") with probability p or report a random coin flip with probability 1-p.
• This allows the server to estimate global metrics like adoption rates or error frequencies without being able to confidently learn any individual user's behavior, complying with stringent data protection regulations.

While simple, randomized response is a fundamental primitive upon which more sophisticated local DP algorithms are built. It is often used as a subroutine in mechanisms for:

• Histogram estimation: Encoding data into a binary vector and randomizing each bit.
• Heavy hitter identification: Finding frequently occurring items in a dataset.
• Mean/Sum estimation: For bounded numerical values, techniques like the Randomized Response for Numeric Data (RAPPOR) build upon its principles. Its simplicity allows for rigorous privacy proofs and easy deployment on edge devices.

The application of randomized response involves a direct and quantifiable privacy-utility trade-off. The randomization probability p determines the privacy budget (ε). A p closer to 0.5 (a coin flip) offers stronger privacy (lower ε) but introduces more noise, reducing the accuracy (utility) of the aggregate estimate. System designers must calibrate p based on:

• The required formal privacy guarantee (ε).
• The number of participants (larger populations tolerate more noise).
• The desired statistical precision for the downstream task.

In production federated learning systems like Google's DP-FedAvg, randomized response (or other LDP mechanisms) is often combined with secure aggregation (SecAgg). This provides a defense-in-depth privacy strategy:

1. Client-side LDP: Each device perturbs its local update using randomized response, providing privacy even if the server is malicious.
2. Secure Aggregation: The noised updates are encrypted and summed by the server such that only the aggregate is revealed, hiding individual contributions even from the server. This combination strengthens the overall system against a wider range of adversarial threats.

Local differential privacy is the formal privacy model where randomized response is most commonly applied. In LDP, each data owner perturbs their own data locally using a randomized algorithm before sending it to an untrusted data curator. This provides a strong, client-side guarantee: even the curator cannot reliably infer the true value of an individual's data. Key characteristics include:

• Stronger threat model than central DP, as it assumes no trusted central server.
• Client-level protection is inherent, making it a natural fit for federated learning on user devices.
• Formalized by ε-LDP, where the parameter ε controls the privacy-utility trade-off, directly analogous to the probability parameters in randomized response.

The Laplace mechanism is a cornerstone algorithm for achieving pure ε-differential privacy in the central model. It works by adding noise drawn from a Laplace distribution to the true output of a numeric query. The scale of the noise is calibrated to the query's L1 sensitivity—the maximum change in the query's output when any single individual's data is added or removed. While randomized response is designed for categorical (yes/no) data, the Laplace mechanism handles continuous-valued queries. Both are pure DP mechanisms (using only ε, not δ) that provide privacy through carefully calibrated random noise.

Privacy amplification by sampling is a powerful technique where applying a differentially private mechanism to a random subset of a population provides a stronger privacy guarantee than if it were applied to the full population. This is highly relevant when randomized response or other LDP mechanisms are applied only to a randomly selected cohort of clients in a federated learning round. The act of random subsampling before applying the privacy mechanism effectively reduces the privacy cost (ε). This allows system designers to achieve a target privacy guarantee with less local noise, improving the final model's utility.

Secure aggregation is a cryptographic protocol used in federated learning that allows a server to compute the sum of client model updates without being able to inspect any individual client's contribution. While randomized response provides statistical privacy by obscuring individual data with noise, secure aggregation provides cryptographic privacy by ensuring the raw data is never revealed in plaintext. These techniques are often combined: clients can apply randomized response (or DP noise) locally, then use secure aggregation to mask their noised updates during transmission. This provides a defense-in-depth privacy strategy, protecting against both a curious server and potential network eavesdroppers.

Epsilon (ε) is the paramount parameter in differential privacy, quantitatively defining the privacy budget. It bounds the log-likelihood ratio of any output occurring with or without any single individual's data. In randomized response, the probabilities of telling the truth (p) and lying (1-p) directly determine the mechanism's ε value. A smaller ε signifies a stronger privacy guarantee but requires more aggressive randomization (noise), reducing data utility. Managing the consumption of ε across multiple queries or training rounds—known as privacy accounting—is critical. Randomized response provides a simple, interpretable way to achieve a specific ε guarantee for a single binary response.

Global sensitivity is a mathematical measure of how much a single individual's data can change the output of a function. It is the cornerstone for calibrating noise in mechanisms like Laplace or Gaussian. For a function f, its L1 sensitivity is the maximum absolute change |f(D) - f(D')| for any two neighboring datasets D and D'. In randomized response, the function is the individual's true binary answer, and its sensitivity is 1 (the answer can flip from 0 to 1). This fixed, bounded sensitivity is what makes randomized response a practical and analyzable mechanism, as the required noise scale does not depend on the size or specific values in the overall dataset.