From Randomized Response to Randomized Index: Answering Subset Counting Queries with Local Differential Privacy

• URL: http://arxiv.org/abs/2504.17523v1
• Date: Thu, 24 Apr 2025 13:08:11 GMT
• Title: From Randomized Response to Randomized Index: Answering Subset Counting Queries with Local Differential Privacy
• Authors: Qingqing Ye, Liantong Yu, Kai Huang, Xiaokui Xiao, Weiran Liu, Haibo Hu,
• Abstract summary: 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.
• Score: 27.59934932590226
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Local Differential Privacy (LDP) is the predominant privacy model for safeguarding individual data privacy. Existing perturbation mechanisms typically require perturbing the original values to ensure acceptable privacy, which inevitably results in value distortion and utility deterioration. In this work, we propose an alternative approach -- instead of perturbing values, we apply randomization to indexes of values while ensuring rigorous LDP guarantees. Inspired by the deniability of randomized indexes, we present CRIAD for answering subset counting queries on set-value data. By integrating a multi-dummy, multi-sample, and multi-group strategy, CRIAD serves as a fully scalable solution that offers flexibility across various privacy requirements and domain sizes, and achieves more accurate query results than any existing methods. Through comprehensive theoretical analysis and extensive experimental evaluations, we validate the effectiveness of CRIAD and demonstrate its superiority over traditional value-perturbation mechanisms.

Related papers

• Bipartite Randomized Response Mechanism for Local Differential Privacy [12.356030528988002]
  We introduce an adaptive Local Privacy (LDP) mechanism called Bipartite Randomized Response (BRR) 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. Our BRR significantly outperforms the state-of-the-art LDP mechanisms of both continuous and distributed types.
  arXiv  Detail & Related papers  (2025-04-29T16:39:50Z)
• 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)
• Mitigating LLM Hallucinations via Conformal Abstention [70.83870602967625]
  We develop a principled procedure for determining when a large language model should abstain from responding in a general domain. We leverage conformal prediction techniques to develop an abstention procedure that benefits from rigorous theoretical guarantees on the hallucination rate (error rate) Experimentally, our resulting conformal abstention method reliably bounds the hallucination rate on various closed-book, open-domain generative question answering datasets.
  arXiv  Detail & Related papers  (2024-04-04T11:32:03Z)
• TernaryVote: Differentially Private, Communication Efficient, and Byzantine Resilient Distributed Optimization on Heterogeneous Data [50.797729676285876]
  We propose TernaryVote, which combines a ternary compressor and the majority vote mechanism to realize differential privacy, gradient compression, and Byzantine resilience simultaneously. We theoretically quantify the privacy guarantee through the lens of the emerging f-differential privacy (DP) and the Byzantine resilience of the proposed algorithm.
  arXiv  Detail & Related papers  (2024-02-16T16:41:14Z)
• Likelihood Ratio Confidence Sets for Sequential Decision Making [51.66638486226482]
  We revisit the likelihood-based inference principle and propose to use likelihood ratios to construct valid confidence sequences. Our method is especially suitable for problems with well-specified likelihoods. We show how to provably choose the best sequence of estimators and shed light on connections to online convex optimization.
  arXiv  Detail & Related papers  (2023-11-08T00:10:21Z)
• 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)
• Evaluating the Impact of Local Differential Privacy on Utility Loss via Influence Functions [11.504012974208466]
  We demonstrate the ability of influence functions to offer insight into how a specific privacy parameter value will affect a model's test loss. Our proposed method allows a data curator to select the privacy parameter best aligned with their allowed privacy-utility trade-off.
  arXiv  Detail & Related papers  (2023-09-15T18:08:24Z)
• Causal Inference with Differentially Private (Clustered) Outcomes [16.166525280886578]
  Estimating causal effects from randomized experiments is only feasible if participants agree to reveal their responses. We suggest a new differential privacy mechanism, Cluster-DP, which leverages any given cluster structure. We show that, depending on an intuitive measure of cluster quality, we can improve the variance loss while maintaining our privacy guarantees.
  arXiv  Detail & Related papers  (2023-08-02T05:51:57Z)
• Regression with Label Differential Privacy [64.21020761920322]
  We derive a label DP randomization mechanism that is optimal under a given regression loss function. We prove that the optimal mechanism takes the form of a "randomized response on bins"
  arXiv  Detail & Related papers  (2022-12-12T17:41:32Z)
• Trustworthy Multimodal Regression with Mixture of Normal-inverse Gamma Distributions [91.63716984911278]
  We introduce a novel Mixture of Normal-Inverse Gamma distributions (MoNIG) algorithm, which efficiently estimates uncertainty in principle for adaptive integration of different modalities and produces a trustworthy regression result. Experimental results on both synthetic and different real-world data demonstrate the effectiveness and trustworthiness of our method on various multimodal regression tasks.
  arXiv  Detail & Related papers  (2021-11-11T14:28:12Z)
• Non-parametric Differentially Private Confidence Intervals for the Median [3.205141100055992]
  This paper proposes and evaluates several strategies to compute valid differentially private confidence intervals for the median. We also illustrate that addressing both sources of uncertainty--the error from sampling and the error from protecting the output--should be preferred over simpler approaches that incorporate the uncertainty in a sequential fashion.
  arXiv  Detail & Related papers  (2021-06-18T19:45:37Z)

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.