Bipartite Randomized Response Mechanism for Local Differential Privacy

With the increasing importance of data privacy, Local Differential Privacy (LDP) has recently become a strong measure of privacy for protecting each user's privacy from data analysts without relying on a trusted third party. In this paper, we consider the problem of high-utility differentially private release. Given a domain of finite integers {1,2,...,N} and a distance-defined utility function, our goal is to design a differentially private mechanism that releases an item with the global expected error as small as possible. The most common LDP mechanism for this task is the Generalized Randomized Response (GRR) mechanism that treats all candidates equally except for the true item. In this paper, we introduce Bipartite Randomized Response mechanism (BRR), which adaptively divides all candidates into two parts by utility rankings given priori item. In the local search phase, we confirm how many high-utility candidates to be assigned with high release probability as the true item, which gives the locally optimal bipartite classification of all candidates. For preserving LDP, the global search phase uniformly selects the smallest number of dynamic high-utility candidates obtained locally. In particular, we give explicit formulas on the uniform number of dynamic high-utility candidates. The global expected error of our BRR is always no larger than the GRR, and can offer a decrease with a small and asymptotically exact factor. Extensive experiments demonstrate that BRR outperforms the state-of-the-art methods across the standard metrics and datasets.