# Unleashing the Power of Randomization in Auditing Differentially Private ML

arXiv: https://arxiv.org/abs/2305.18447 · HTML: https://mlsanity.com/paper/2305.18447/

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 70 references that are in the map.
- First posted on arXiv 29 May 2023.

## Builds on (most cited first, 30 of 37)

- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Membership Inference Attacks against Machine Learning Models](https://mlsanity.com/paper/1610.05820/) (2016)
- [Extracting Training Data from Large Language Models](https://mlsanity.com/paper/2012.07805/) (2020)
- [Membership Inference Attacks From First Principles](https://mlsanity.com/paper/2112.03570/) (2021)
- [The Secret Sharer: Evaluating and Testing Unintended Memorization in Neural Networks](https://mlsanity.com/paper/1802.08232/) (2018)
- [Quantifying Memorization Across Neural Language Models](https://mlsanity.com/paper/2202.07646/) (2022)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [The Composition Theorem for Differential Privacy](https://mlsanity.com/paper/1311.0776/) (2013)
- [Enhanced Membership Inference Attacks against Machine Learning Models](https://mlsanity.com/paper/2111.09679/) (2021)
- [Auditing Differentially Private Machine Learning: How Private is Private SGD?](https://mlsanity.com/paper/2006.07709/) (2020)
- [Adversary Instantiation: Lower Bounds for Differentially Private Machine Learning](https://mlsanity.com/paper/2101.04535/) (2021)
- [How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy](https://mlsanity.com/paper/2303.00654/) (2023)
- [Concentrated Differential Privacy](https://mlsanity.com/paper/1603.01887/) (2016)
- [Privacy Auditing with One (1) Training Run](https://mlsanity.com/paper/2305.08846/) (2023)
- [Truth Serum: Poisoning Machine Learning Models to Reveal Their Secrets](https://mlsanity.com/paper/2204.00032/) (2022)
- [Hypothesis Testing Interpretations and Renyi Differential Privacy](https://mlsanity.com/paper/1905.09982/) (2019)
- [Fingerprinting Codes and the Price of Approximate Differential Privacy](https://mlsanity.com/paper/1311.3158/) (2013)
- [Antipodes of Label Differential Privacy: PATE and ALIBI](https://mlsanity.com/paper/2106.03408/) (2021)
- [Bounding Training Data Reconstruction in Private (Deep) Learning](https://mlsanity.com/paper/2201.12383/) (2022)
- [Bounding Training Data Reconstruction in DP-SGD](https://mlsanity.com/paper/2302.07225/) (2023)
- [Debugging Differential Privacy: A Case Study for Privacy Auditing](https://mlsanity.com/paper/2202.12219/) (2022)
- [Detecting Violations of Differential Privacy](https://mlsanity.com/paper/1805.10277/) (2018)
- [One-shot Empirical Privacy Estimation for Federated Learning](https://mlsanity.com/paper/2302.03098/) (2023)
- [Measuring Data Leakage in Machine-Learning Models with Fisher Information](https://mlsanity.com/paper/2102.11673/) (2021)
- [Bayesian Estimation of Differential Privacy](https://mlsanity.com/paper/2206.05199/) (2022)
- [Understanding the Sparse Vector Technique for Differential Privacy](https://mlsanity.com/paper/1603.01699/) (2016)
- [A General Framework for Auditing Differentially Private Machine Learning](https://mlsanity.com/paper/2210.08643/) (2022)
- [CANIFE: Crafting Canaries for Empirical Privacy Measurement in Federated Learning](https://mlsanity.com/paper/2210.02912/) (2022)

## Built on by (most cited first, 20 of 20)

- [User Inference Attacks on Large Language Models](https://mlsanity.com/paper/2310.09266/) (2023)
- [Evaluations of Machine Learning Privacy Defenses are Misleading](https://mlsanity.com/paper/2404.17399/) (2024)
- [Privacy-Preserving Instructions for Aligning Large Language Models](https://mlsanity.com/paper/2402.13659/) (2024)
- [Auditing f-Differential Privacy in One Run](https://mlsanity.com/paper/2410.22235/) (2024)
- [Label Poisoning is All You Need](https://mlsanity.com/paper/2310.18933/) (2023)
- [Fine-Tuning Large Language Models with User-Level Differential Privacy](https://mlsanity.com/paper/2407.07737/) (2024)
- [Privacy Auditing of Large Language Models](https://mlsanity.com/paper/2503.06808/) (2025)
- [Are Robust LLM Fingerprints Adversarially Robust?](https://mlsanity.com/paper/2509.26598/) (2025)
- [A Note On Interpreting Canary Exposure](https://mlsanity.com/paper/2306.00133/) (2023)
- [Auditing Differential Privacy Guarantees Using Density Estimation](https://mlsanity.com/paper/2406.04827/) (2024)
- [To Shuffle or not to Shuffle: Auditing DP-SGD with Shuffling](https://mlsanity.com/paper/2411.10614/) (2024)
- [BadGD: A unified data-centric framework to identify gradient descent vulnerabilities](https://mlsanity.com/paper/2405.15979/) (2024)
- [The Hitchhiker's Guide to Efficient, End-to-End, and Tight DP Auditing](https://mlsanity.com/paper/2506.16666/) (2025)
- [Enhancing One-run Privacy Auditing with Quantile Regression-Based Membership Inference](https://mlsanity.com/paper/2506.15349/) (2025)
- [VFLGAN-TS: Vertical Federated Learning-based Generative Adversarial Networks for Publication of Vertically Partitioned Time-Series Data](https://mlsanity.com/paper/2409.03612/) (2024)
- [MCMC for Bayesian estimation of Differential Privacy from Membership Inference Attacks](https://mlsanity.com/paper/2504.16683/) (2025)
- [Auditing of Unlearning Algorithms](https://mlsanity.com/paper/2607.05898/) (2026)
- [Privacy Failure in Split-LLM Training, The Returned Gradient Nullifies the Decoys](https://mlsanity.com/paper/2609.04382/) (2026)
- [Black-Box Auditing of Quantum Model: Lifted Differential Privacy with Quantum Canaries](https://mlsanity.com/paper/2512.14388/) (2025)
- [A Bayesian Approach to Membership Inference for Statistical Release](https://mlsanity.com/paper/2605.30203/) (2026)

## Abstract (arXiv)

We present a rigorous methodology for auditing differentially private machine learning algorithms by adding multiple carefully designed examples called canaries. We take a first principles approach based on three key components. First, we introduce Lifted Differential Privacy (LiDP) that expands the definition of differential privacy to handle randomized datasets. This gives us the freedom to design randomized canaries. Second, we audit LiDP by trying to distinguish between the model trained with K canaries versus K - 1 canaries in the dataset, leaving one canary out. By drawing the canaries i.i.d., LiDP can leverage the symmetry in the design and reuse each privately trained model to run multiple statistical tests, one for each canary. Third, we introduce novel confidence intervals that take advantage of the multiple test statistics by adapting to the empirical higher-order correlations. Together, this new recipe demonstrates significant improvements in sample complexity, both theoretically and empirically, using synthetic and real data. Further, recent advances in designing stronger canaries can be readily incorporated into the new framework.