More Like this

1. Privacy-Aware Rejection Sampling

   Awan, Jordan; Rao, Vinayak (February 2023, Journal of machine learning research)

   Weller, Adrian (Ed.)

   While differential privacy (DP) offers strong theoretical privacy guarantees, implementations of DP mechanisms may be vulnerable to side-channel attacks, such as timing attacks. When sampling methods such as MCMC or rejection sampling are used to implement a privacy mechanism, the runtime can leak private information. We characterize the additional privacy cost due to the runtime of a rejection sampler in terms of both (, δ)-DP as well as f -DP. We also show that unless the acceptance probability is constant across databases, the runtime of a rejection sampler does not satisfy -DP for any . We show that there is a similar breakdown in privacy with adaptive rejection samplers. We propose three modifications to the rejection sampling algorithm, with varying assumptions, to protect against timing attacks by making the runtime independent of the data. The modification with the weakest assumptions is an approximate sampler, introducing a small increase in the privacy cost, whereas the other modifications give perfect samplers. We also use our techniques to develop an adaptive rejection sampler for log-H ̈older densities, which also has data-independent runtime. We give several examples of DP mechanisms that fit the assumptions of our methods and can thus be implemented using our samplers. 

   more » « less
2. Privacy-Aware Rejection Sampling

   Awan, Jordan; Rao, Vinayak (January 2023, Journal of machine learning research)

   Weller, Adrian (Ed.)

   Differential privacy (DP) offers strong theoretical privacy guarantees, though implementations of DP mechanisms may be vulnerable to side-channel attacks, such as timing attacks. When sampling methods such as MCMC or rejection sampling are used to implement a mechanism, the runtime can leak private information. We characterize the additional privacy cost due to the runtime of a rejection sampler in terms of both (epsilon,delta)-DP as well as f-DP. We also show that unless the acceptance probability is constant across databases, the runtime of a rejection sampler does not satisfy epsilon-DP for any epsilon. We show that there is a similar breakdown in privacy with adaptive rejection samplers. We propose three modifications to the rejection sampling algorithm, with varying assumptions, to protect against timing attacks by making the runtime independent of the data. The modification with the weakest assumptions is an approximate sampler, introducing a small increase in the privacy cost, whereas the other modifications give perfect samplers. We also use our techniques to develop an adaptive rejection sampler for log-Holder densities, which also has data-independent runtime. We give several examples of DP mechanisms that fit the assumptions of our methods and can thus be implemented using our samplers. 

   more » « less
3. Tractable MCMC for Private Learning with Pure and Gaussian Differential Privacy

   Lin, Yingyu; Ma, Yi-An; Wang, Yu-Xiang; Redberg, Rachel; Bu, Zhiqi (May 2024, ICLR 2024)

   Posterior sampling, i.e., exponential mechanism to sample from the posterior distribution, provides ε-pure differential privacy (DP) guarantees and does not suffer from potentially unbounded privacy breach introduced by (ε,δ)-approximate DP. In practice, however, one needs to apply approximate sampling methods such as Markov chain Monte Carlo (MCMC), thus re-introducing the unappealing δ-approximation error into the privacy guarantees. To bridge this gap, we propose the Approximate SAample Perturbation (abbr. ASAP) algorithm which perturbs an MCMC sample with noise proportional to its Wasserstein-infinity (W∞) distance from a reference distribution that satisfies pure DP or pure Gaussian DP (i.e., δ=0). We then leverage a Metropolis-Hastings algorithm to generate the sample and prove that the algorithm converges in W∞ distance. We show that by combining our new techniques with a localization step, we obtain the first nearly linear-time algorithm that achieves the optimal rates in the DP-ERM problem with strongly convex and smooth losses. 

   more » « less
4. Approximating Functions with Approximate Privacy for Applications in Signal Estimation and Learning

   https://doi.org/10.3390/e25050825  

   Tasnim, Naima; Mohammadi, Jafar; Sarwate, Anand D.; Imtiaz, Hafiz (May 2023, Entropy)

   Large corporations, government entities and institutions such as hospitals and census bureaus routinely collect our personal and sensitive information for providing services. A key technological challenge is designing algorithms for these services that provide useful results, while simultaneously maintaining the privacy of the individuals whose data are being shared. Differential privacy (DP) is a cryptographically motivated and mathematically rigorous approach for addressing this challenge. Under DP, a randomized algorithm provides privacy guarantees by approximating the desired functionality, leading to a privacy–utility trade-off. Strong (pure DP) privacy guarantees are often costly in terms of utility. Motivated by the need for a more efficient mechanism with better privacy–utility trade-off, we propose Gaussian FM, an improvement to the functional mechanism (FM) that offers higher utility at the expense of a weakened (approximate) DP guarantee. We analytically show that the proposed Gaussian FM algorithm can offer orders of magnitude smaller noise compared to the existing FM algorithms. We further extend our Gaussian FM algorithm to decentralized-data settings by incorporating the CAPE protocol and propose capeFM. Our method can offer the same level of utility as its centralized counterparts for a range of parameter choices. We empirically show that our proposed algorithms outperform existing state-of-the-art approaches on synthetic and real datasets. 

   more » « less
5. Privacy Loss of Noise Perturbation via Concentration Analysis of A Product Measure

   https://doi.org/10.1145/3786680  

   Liu, Shuainan; Ji, Tianxi; Fang, Zhongshuo; Wei, Lu; Li, Pan (April 2026, Proceedings of the ACM on Management of Data)

   Noise perturbation is one of the most fundamental approaches for achieving (ε,δ)-differential privacy (DP) guarantees when releasing the result of a query or function ƒ(•)∈R^Mevaluated on a sensitive datasetx. In this approach, calibrated noisen∈ R^Mis used to obscure the difference vectorf(x) 0 f(x'), wherex' is known as a neighboring dataset. A DP guarantee is obtained by studying the tail probability bound of a privacy loss random variable (PLRV), defined as the Radon-Nikodym derivative between two distributions. Whennfollows a multivariate Gaussian distribution, the PLRV is characterized as a specific univariate Gaussian. In this paper, we propose a novel scheme to generatenby leveraging the fact that the perturbation noise is typically spherically symmetric (i.e., the distribution is rotationally invariant around the origin). The new noise generation scheme allows us to investigate the privacy loss from a geometric perspective and express the resulting PLRV using a product measure, W x U; measureWis related to a radius random variable controlling the magnitude ofn, while measureUinvolves a directional random variable governing the angle betweennand the difference ƒ(x)-ƒ(x'). We derive a closed-form moment bound on the product measure to prove (ε,δ)-DP. Under the same (ε,δ)-DP guarantee, our mechanism yields a smaller expected noise magnitude than the classic Gaussian noise in high dimensions, thereby significantly improving the utility of the noisy result ƒ(x)+n. To validate this, we consider privacy-preserving convex and non-convex empirical risk minimization (ERM) problems in high dimensional space. We propose leveraging our developed noise in output perturbation, objective perturbation, and gradient perturbation to establish DP guarantees when solving ERMs. Experiments on multiple datasets show that our method achieves significant utility improvements for convex ERM models (e.g., regression and SVM) under the same privacy guarantees. For non-convex models (e.g., neural networks), it provides substantially stronger privacy guarantees under comparable utility. Code Repository: https://github.com/issleepgroup/Product-Noise-ERM 

   more » « less