Privacy and distortion balanced in limited-radius randomized response
Exact Privacy--Distortion Design of Support-Constrained Randomized Response
Information Theory
Summary
Data privacy tools often add noise by randomizing answers, but this can distort results unnecessarily, especially when answers have order. The authors study a way to restrict random answers to be close to the true one, reducing distortion. They find exact formulas to measure privacy risk in this setup and optimize parameters that control how much answers can differ. Their results show trade-offs between privacy protection and accuracy, and how stringent privacy demands require larger answer sets.
What this means in practice
- •For data privacy engineers: Design private data collection methods that minimize distortion by limiting randomized outputs to nearby values.
- •For mobile app developers: Implement privacy-preserving user input collection that balances data accuracy with strict privacy guarantees by tuning local randomization parameters.
Authors
Amirreza Zamani, Parastoo Sadeghi, Mikael Skoglund
Abstract
Full-support local randomizers can incur unnecessary reporting distortion on ordered alphabets. We study randomized response whose output is restricted to a radius-$t$ neighborhood of the private input. Input-dependent supports create privacy leakage at their boundaries, so ordinary likelihood-ratio calibration is no longer sufficient. Under approximate local privacy restricted to input pairs at distance at most $H$, we derive the exact hockey-stick defect of the mechanism. We then solve the joint design of the truthful probability, off-truth probability, and support radius. The fixed-radius optimum is available in closed form, while the global optimum requires only a one-dimensional integer search. We characterize both the privacy floor and its inverse, namely the smallest defect attainable under a reporting-distortion budget. We further prove that stringent approximate privacy forces the support size to scale as $Ω(H/δ)$. Deterministic evaluations illustrate the resulting tradeoff.