FLDP: Flexible strategy for local differential privacy

Local differential privacy (LDP), a technique applying unbiased statistical estimations instead of real data, is often adopted in data collection. In particular, this technique is used in frequency oracles (FO) because it can protect each user's privacy and prevent leakage of sensitive information. However, the definition of LDP is so conservative that it requires all inputs to be indistinguishable after perturbation. Indeed, LDP protects each value; however, it is rarely used in practical scenarios owing to its cost in terms of accuracy. In this paper, we address the challenge of providing weakened but flexible protection where each value only needs to be indistinguishable from part of the domain after perturbation. First, we present this weakened but flexible LDP (FLDP) notion which splits the domain. We then prove the association with LDP. Second, we design a Flexible Hadamard Response (FHR) approach for the common FO issue while satisfying FLDP. The proposed approach balances communication cost, computational complexity, and estimation accuracy. Finally, experimental results using practical and synthetic datasets verify the effectiveness and efficiency of our approach.