Context-aware Privacy Bounds for Linear Queries

• URL: http://arxiv.org/abs/2601.02855v1
• Date: Tue, 06 Jan 2026 09:34:04 GMT
• Title: Context-aware Privacy Bounds for Linear Queries
• Authors: Heng Zhao, Sara Saeidian, Tobias J. Oechtering,
• Abstract summary: We revisit the privacy analysis of the Laplace mechanism through the lens of pointwise maximal leakage.<n>We demonstrate that the distribution-agnostic definition of the DP framework often mandates excessive noise.
• Score: 18.643148110719736
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Linear queries, as the basis of broad analysis tasks, are often released through privacy mechanisms based on differential privacy (DP), the most popular framework for privacy protection. However, DP adopts a context-free definition that operates independently of the data-generating distribution. In this paper, we revisit the privacy analysis of the Laplace mechanism through the lens of pointwise maximal leakage (PML). We demonstrate that the distribution-agnostic definition of the DP framework often mandates excessive noise. To address this, we incorporate an assumption about the prior distribution by lower-bounding the probability of any single record belonging to any specific class. With this assumption, we derive a tight, context-aware leakage bound for general linear queries, and prove that our derived bound is strictly tighter than the standard DP guarantee and converges to the DP guarantee as this probability lower bound approaches zero. Numerical evaluations demonstrate that by exploiting this prior knowledge, the required noise scale can be reduced while maintaining privacy guarantees.

Related papers

• Parallel Composition for Statistical Privacy [0.0]
  A privacy mechanism is proposed that is based on subsampling and randomly partitioning the database to bound the dependency among queries.<n>These bounds show that in realistic application scenarios taking the entropy of distributions into account yields improvements of privacy and precision guarantees.
  arXiv  Detail & Related papers  (2026-02-10T10:13:44Z)
• A Tight Context-aware Privacy Bound for Histogram Publication [15.762008564991207]
  We analyze the privacy guarantees of the Laplace mechanism releasing the histogram of a dataset through the lens of pointwise maximal leakage (PML)<n>We show that when the probability of each histogram bin is bounded away from zero, stronger privacy protection can be achieved for a fixed level of noise.
  arXiv  Detail & Related papers  (2025-08-26T09:12:23Z)
• Verifiable Exponential Mechanism for Median Estimation [4.083860866484599]
  We propose the first verifiable implementation of the exponential mechanism using zk-SNARKs.<n>As a concrete application, we present the first verifiable differentially private (DP) median estimation scheme.
  arXiv  Detail & Related papers  (2025-05-22T05:31:22Z)
• Enhancing Feature-Specific Data Protection via Bayesian Coordinate Differential Privacy [55.357715095623554]
  Local Differential Privacy (LDP) offers strong privacy guarantees without requiring users to trust external parties. We propose a Bayesian framework, Bayesian Coordinate Differential Privacy (BCDP), that enables feature-specific privacy quantification.
  arXiv  Detail & Related papers  (2024-10-24T03:39:55Z)
• Convergent Differential Privacy Analysis for General Federated Learning: the $f$-DP Perspective [57.35402286842029]
  Federated learning (FL) is an efficient collaborative training paradigm with a focus on local privacy. differential privacy (DP) is a classical approach to capture and ensure the reliability of private protections.
  arXiv  Detail & Related papers  (2024-08-28T08:22:21Z)
• Noise Variance Optimization in Differential Privacy: A Game-Theoretic Approach Through Per-Instance Differential Privacy [7.264378254137811]
  Differential privacy (DP) can measure privacy loss by observing the changes in the distribution caused by the inclusion of individuals in the target dataset. DP has been prominent in safeguarding datasets in machine learning in industry giants like Apple and Google. We propose per-instance DP (pDP) as a constraint, measuring privacy loss for each data instance and optimizing noise tailored to individual instances.
  arXiv  Detail & Related papers  (2024-04-24T06:51:16Z)
• How Private are DP-SGD Implementations? [61.19794019914523]
  We show that there can be a substantial gap between the privacy analysis when using the two types of batch sampling. Our result shows that there can be a substantial gap between the privacy analysis when using the two types of batch sampling.
  arXiv  Detail & Related papers  (2024-03-26T13:02:43Z)
• Provable Privacy with Non-Private Pre-Processing [56.770023668379615]
  We propose a general framework to evaluate the additional privacy cost incurred by non-private data-dependent pre-processing algorithms. Our framework establishes upper bounds on the overall privacy guarantees by utilising two new technical notions.
  arXiv  Detail & Related papers  (2024-03-19T17:54:49Z)
• Unified Mechanism-Specific Amplification by Subsampling and Group Privacy Amplification [54.1447806347273]
  Amplification by subsampling is one of the main primitives in machine learning with differential privacy. We propose the first general framework for deriving mechanism-specific guarantees. We analyze how subsampling affects the privacy of groups of multiple users.
  arXiv  Detail & Related papers  (2024-03-07T19:36:05Z)
• On the Privacy of Selection Mechanisms with Gaussian Noise [44.577599546904736]
  We revisit the analysis of Report Noisy Max and Above Threshold with Gaussian noise. We find that it is possible to provide pure ex-ante DP bounds for Report Noisy Max and pure ex-post DP bounds for Above Threshold.
  arXiv  Detail & Related papers  (2024-02-09T02:11:25Z)
• 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)

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.