TL;DR
This paper quantifies the exact amount of randomness required to achieve Local Differential Privacy (LDP) and introduces a "successive refinement" framework. This framework allows a single randomized data output to serve multiple analysts at different hierarchical privacy levels by utilizing shared random keys to partially de-randomize the data.
What Problem Does This Paper Address?
Local Differential Privacy (LDP) has become the gold standard for collecting user data securely in decentralized applications (used by tech giants like Apple and Google). In standard LDP, users randomize their data locally before sending it to an untrusted analyst. However, existing literature assumes that users have access to an infinite source of randomness to perform this obfuscation. In reality, generating and managing true randomness consumes computational, storage, and communication resources. This paper addresses a fundamental question: How much randomness is strictly necessary to balance privacy and utility?
Furthermore, the authors introduce a practical multi-analyst scenario called successive refinement of privacy. Imagine a census survey where a high-clearance analyst (e.g., the government) needs to perfectly reconstruct individual data points, while a low-clearance analyst (e.g., the public) should only see a highly private, aggregated distribution. Instead of storing or transmitting multiple versions of the data, the authors investigate how a single public output can be dynamically "de-randomized" based on an analyst's specific cryptographic key clearance.
Methods
The authors tackle the problem through a mix of information-theoretic proofs and novel mechanism design:
- Information-Theoretic Lower Bounds: Using Assouad's method and Fisher information, the authors derive tight minimax risk lower bounds for distribution estimation under both privacy ($\epsilon$) and randomness ($R$, measured in Shannon entropy) constraints.
- Hadamard Response Adaptation: They adapt the standard, communication-efficient Hadamard Response mechanism to operate under strict randomness constraints, proving that it achieves order-optimal utility even when randomness is limited.
- Cascading Multi-Level Mechanism: For settings with multiple analysts ($d > 1$), they reject the naive approach of sending separate randomized messages. Instead, they propose a cascading mechanism where a user applies sequential bitwise XOR operations with Bernoulli random variables. Analysts with higher clearance receive keys that allow them to roll back layers of noise, gaining higher utility.
Datasets
The paper evaluates its theoretical findings entirely through synthetic data simulations.
- The authors generate input samples using a Geometric distribution ($Geo(0.8)$) over a finite alphabet size of $k = 1000$.
- The sample size (number of users $n$) ranges from $10^5$ to $10^6$.
- No real-world datasets are used or introduced in this work.
Key Insights and Ideas
- The Critical Threshold: There is a sharp phase transition in the randomness-utility trade-off. For any given privacy level $\epsilon$, the critical threshold of randomness is $R = H_2(\frac{e^\epsilon}{e^\epsilon + 1})$ bits. If a user has more randomness than this threshold, utility remains optimal and constant. If randomness drops below it, utility degrades severely, scaling proportionally to $1/p_R^2$ (where $p_R$ is the inverse binary entropy of the available randomness).
- No Free Lunch Over Time: You cannot reuse random keys across multiple data samples over time without completely destroying privacy. To maintain $\epsilon$-differential privacy for a sequence of $T$ samples, the required randomness must scale linearly ($T$ times the single-sample requirement).
- Hierarchical Efficiency: By structuring multi-level privacy as a cascading tree of noise, the total randomness required to satisfy multiple analysts is strictly less than generating independent reports for each analyst.
Key Results
- Order-Optimal Characterization: The authors provide the first tight characterization of the privacy-utility-randomness trade-off for distribution estimation.
- Private-Recoverability ($d=2$): They prove that the Binary Hadamard mechanism is order-optimal from a randomness perspective, requiring minimal entropy while allowing perfect data recovery for the authorized analyst.
- Randomness Savings: Numerical evaluations show that when the difference between two analysts' required privacy levels ($\epsilon_1 - \epsilon_2$) is small, the proposed cascading scheme saves up to 50% of the total randomness compared to the independent baseline.
Limitations and Future Work
- Scope of Tasks: The paper focuses strictly on distribution estimation and heavy hitter estimation. How these randomness constraints affect more complex local private tasks, such as empirical risk minimization or deep learning, remains unexplored.
- Strict Hierarchy Assumption: The multi-level privacy framework assumes a clean, nested hierarchy of privacy clearances ($\epsilon_1 > \epsilon_2 > \dots > \epsilon_d$). It does not account for scenarios where different analysts require orthogonal or non-comparable privacy guarantees on different attributes of the data.
Summary updated