Bipartite Randomized Response Mechanism for Local Differential Privacy

• URL: http://arxiv.org/abs/2504.20926v1
• Date: Tue, 29 Apr 2025 16:39:50 GMT
• Title: Bipartite Randomized Response Mechanism for Local Differential Privacy
• Authors: Shun Zhang, Hai Zhu, Zhili Chen, Neal N. Xiong,
• Abstract summary: We introduce an adaptive Local Privacy (LDP) mechanism called Bipartite Randomized Response (BRR)<n>We prove that for any utility function and any privacy level, solving the problem is equivalent to confirming how many high-utility data to be treated equally as the true data on release probability.<n>Our BRR significantly outperforms the state-of-the-art LDP mechanisms of both continuous and distributed types.
• Score: 12.356030528988002
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 many cases, both data providers and data analysts hope to maximize the utility of released data. In this paper, we study the fundamental trade-off formulated as a constrained optimization problem: maximizing data utility subject to the constraint of LDP budgets. In particular, the Generalized Randomized Response (GRR) treats all discrete data equally except for the true data. For this, we introduce an adaptive LDP mechanism called Bipartite Randomized Response (BRR), which solves the above privacy-utility maximization problem from the global standpoint. We prove that for any utility function and any privacy level, solving the maximization problem is equivalent to confirming how many high-utility data to be treated equally as the true data on release probability, the outcome of which gives the optimal randomized response. Further, solving this linear program can be computationally cheap in theory. Several examples of utility functions defined by distance metrics and applications in decision trees and deep learning are presented. The results of various experiments show that our BRR significantly outperforms the state-of-the-art LDP mechanisms of both continuous and distributed types.

Related papers

• From Randomized Response to Randomized Index: Answering Subset Counting Queries with Local Differential Privacy [27.59934932590226]
  Local Differential Privacy (LDP) is the predominant privacy model for safeguarding individual data privacy.<n>We propose an alternative approach -- instead of perturbing values, we apply randomization to indexes of values.<n>Inspired by the deniability of randomized indexes, we present CRIAD for answering subset counting queries on set-value data.
  arXiv  Detail & Related papers  (2025-04-24T13:08:11Z)
• Differentially Private Random Feature Model [52.468511541184895]
  We produce a differentially private random feature model for privacy-preserving kernel machines.<n>We show that our method preserves privacy and derive a generalization error bound for the method.
  arXiv  Detail & Related papers  (2024-12-06T05:31:08Z)
• Pseudo-Probability Unlearning: Towards Efficient and Privacy-Preserving Machine Unlearning [59.29849532966454]
  We propose PseudoProbability Unlearning (PPU), a novel method that enables models to forget data to adhere to privacy-preserving manner. Our method achieves over 20% improvements in forgetting error compared to the state-of-the-art.
  arXiv  Detail & Related papers  (2024-11-04T21:27:06Z)
• AAA: an Adaptive Mechanism for Locally Differential Private Mean Estimation [42.95927712062214]
  Local differential privacy (LDP) is a strong privacy standard that has been adopted by popular software systems. We propose the advanced adaptive additive (AAA) mechanism, which is a distribution-aware approach that addresses the average utility. We provide rigorous privacy proofs, utility analyses, and extensive experiments comparing AAA with state-of-the-art mechanisms.
  arXiv  Detail & Related papers  (2024-04-02T04:22:07Z)
• Privacy Amplification for the Gaussian Mechanism via Bounded Support [64.86780616066575]
  Data-dependent privacy accounting frameworks such as per-instance differential privacy (pDP) and Fisher information loss (FIL) confer fine-grained privacy guarantees for individuals in a fixed training dataset. We propose simple modifications of the Gaussian mechanism with bounded support, showing that they amplify privacy guarantees under data-dependent accounting.
  arXiv  Detail & Related papers  (2024-03-07T21:22:07Z)
• Bounded and Unbiased Composite Differential Privacy [25.427802467876248]
  The objective of differential privacy (DP) is to protect privacy by producing an output distribution that is indistinguishable between two neighboring databases. Existing solutions attempt to address this issue by employing post-processing or truncation techniques. We propose a novel differentially private mechanism which uses a composite probability density function to generate bounded and unbiased outputs.
  arXiv  Detail & Related papers  (2023-11-04T04:43:47Z)
• On the Privacy-Robustness-Utility Trilemma in Distributed Learning [7.778461949427662]
  We present the first tight analysis of the error incurred by any algorithm ensuring robustness against a fraction of adversarial machines. Our analysis exhibits a fundamental trade-off between privacy, robustness, and utility.
  arXiv  Detail & Related papers  (2023-02-09T17:24:18Z)
• FedLAP-DP: Federated Learning by Sharing Differentially Private Loss Approximations [53.268801169075836]
  We propose FedLAP-DP, a novel privacy-preserving approach for federated learning. A formal privacy analysis demonstrates that FedLAP-DP incurs the same privacy costs as typical gradient-sharing schemes. Our approach presents a faster convergence speed compared to typical gradient-sharing methods.
  arXiv  Detail & Related papers  (2023-02-02T12:56:46Z)
• DP2-Pub: Differentially Private High-Dimensional Data Publication with Invariant Post Randomization [58.155151571362914]
  We propose a differentially private high-dimensional data publication mechanism (DP2-Pub) that runs in two phases. splitting attributes into several low-dimensional clusters with high intra-cluster cohesion and low inter-cluster coupling helps obtain a reasonable privacy budget. We also extend our DP2-Pub mechanism to the scenario with a semi-honest server which satisfies local differential privacy.
  arXiv  Detail & Related papers  (2022-08-24T17:52:43Z)
• Production of Categorical Data Verifying Differential Privacy: Conception and Applications to Machine Learning [0.0]
  Differential privacy is a formal definition that allows quantifying the privacy-utility trade-off. With the local DP (LDP) model, users can sanitize their data locally before transmitting it to the server. In all cases, we concluded that differentially private ML models achieve nearly the same utility metrics as non-private ones.
  arXiv  Detail & Related papers  (2022-04-02T12:50:14Z)
• Smoothed Differential Privacy [55.415581832037084]
  Differential privacy (DP) is a widely-accepted and widely-applied notion of privacy based on worst-case analysis. In this paper, we propose a natural extension of DP following the worst average-case idea behind the celebrated smoothed analysis. We prove that any discrete mechanism with sampling procedures is more private than what DP predicts, while many continuous mechanisms with sampling procedures are still non-private under smoothed DP.
  arXiv  Detail & Related papers  (2021-07-04T06:55:45Z)
• Graph-Homomorphic Perturbations for Private Decentralized Learning [64.26238893241322]
  Local exchange of estimates allows inference of data based on private data. perturbations chosen independently at every agent, resulting in a significant performance loss. We propose an alternative scheme, which constructs perturbations according to a particular nullspace condition, allowing them to be invisible.
  arXiv  Detail & Related papers  (2020-10-23T10:35:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.