39 citations · 308 across the 129 of their papers we have counts for
23 papers · 1 filter
Overcoming the Randomness-Utility Trade-off in Answering Differentially Private Linear Queries
Surendra Ghentiyala, Pritish Kamath, Ravi Kumar +1
We study the question of answering linear queries with differential privacy using few (expected) random bits. We provide a randomness-efficient analog of the -norm m…
Optimal partition selection with Rényi differential privacy
Charlie Harrison, Pasin Manurangsi
A common problem in private data analysis is the partition selection problem, where each user holds a set of partitions (e.g. keys in a GROUP BY operation) from a possibly unbounde…
Keeping a Secret Requires a Good Memory: Space Lower-Bounds for Private Algorithms
Alessandro Epasto, Xin Lyu, Pasin Manurangsi
We study the computational cost of differential privacy in terms of memory efficiency. While the trade-off between accuracy and differential privacy is well-understood, the inheren…
Privacy Filters are Captured by Residues: A Characterization of Free Natural Filters and the Cost of Adaptivity
Matthew Regehr, Bingshan Hu, Ethan Leeman +3
We study privacy filters, which enable privacy accounting for differentially private (DP) mechanisms with adaptively chosen privacy characteristics. We develop a general theory tha…
Nearly-Optimal Private Selection via Gaussian Mechanism
Ethan Leeman, Pasin Manurangsi
Steinke (2025) recently asked the following intriguing open question: Can we solve the differentially private selection problem with nearly-optimal error by only (adaptively) invok…
Exact zCDP Characterizations for Fundamental Differentially Private Mechanisms
Charlie Harrison, Pasin Manurangsi
Zero-concentrated differential privacy (zCDP) is a variant of differential privacy (DP) that is widely used partly thanks to its nice composition property. While a tight conversion…
VaultGemma: A Differentially Private Gemma Model
Amer Sinha, Thomas Mesnard, Ryan McKenna +18
We introduce VaultGemma 1B, a 1 billion parameter model within the Gemma family, fully trained with differential privacy. Pretrained on the identical data mixture used for the Gemm…
Private Hyperparameter Tuning with Ex-Post Guarantee
Badih Ghazi, Pritish Kamath, Alexander Knop +3
The conventional approach in differential privacy (DP) literature formulates the privacy-utility trade-off with a "privacy-first" perspective: for a predetermined level of privacy,…
Infinitely Divisible Noise for Differential Privacy: Nearly Optimal Error in the High Regime
Charlie Harrison, Pasin Manurangsi
Differential privacy (DP) can be achieved in a distributed manner, where multiple parties add independent noise such that their sum protects the overall dataset with DP. A common t…
On the Differential Privacy and Interactivity of Privacy Sandbox Reports
Badih Ghazi, Charlie Harrison, Arpana Hosabettu +8
The Privacy Sandbox initiative from Google includes APIs for enabling privacy-preserving advertising functionalities as part of the effort around limiting third-party cookies. In p…
Differential Privacy on Trust Graphs
Badih Ghazi, Ravi Kumar, Pasin Manurangsi +1
We study differential privacy (DP) in a multi-party setting where each party only trusts a (known) subset of the other parties with its data. Specifically, given a trust graph wher…
Unlearn and Burn: Adversarial Machine Unlearning Requests Destroy Model Accuracy
Yangsibo Huang, Daogao Liu, Lynn Chua +7
Machine unlearning algorithms, designed for selective removal of training data from models, have emerged as a promising approach to growing privacy concerns. In this work, we expos…
Differentially Private Ad Conversion Measurement
John Delaney, Badih Ghazi, Charlie Harrison +6
In this work, we study ad conversion measurement, a central functionality in digital advertising, where an advertiser seeks to estimate advertiser website (or mobile app) conversio…
Summary Reports Optimization in the Privacy Sandbox Attribution Reporting API
Hidayet Aksu, Badih Ghazi, Pritish Kamath +4
The Privacy Sandbox Attribution Reporting API has been recently deployed by Google Chrome to support the basic advertising functionality of attribution reporting (aka conversion me…
Differentially Private Aggregation via Imperfect Shuffling
Badih Ghazi, Ravi Kumar, Pasin Manurangsi +2
In this paper, we introduce the imperfect shuffle differential privacy model, where messages sent from users are shuffled in an almost uniform manner before being observed by a cur…
Towards Separating Computational and Statistical Differential Privacy
Badih Ghazi, Rahul Ilango, Pritish Kamath +2
Computational differential privacy (CDP) is a natural relaxation of the standard notion of (statistical) differential privacy (SDP) proposed by Beimel, Nissim, and Omri (CRYPTO 200…
Algorithms with More Granular Differential Privacy Guarantees
Badih Ghazi, Ravi Kumar, Pasin Manurangsi +1
Differential privacy is often applied with a privacy parameter that is larger than the theory suggests is ideal; various informal justifications for tolerating large privacy parame…
Differentially Private Aggregation in the Shuffle Model: Almost Central Accuracy in Almost a Single Message
Badih Ghazi, Ravi Kumar, Pasin Manurangsi +2
The shuffle model of differential privacy has attracted attention in the literature due to it being a middle ground between the well-studied central and local models. In this work,…
Google COVID-19 Vaccination Search Insights: Anonymization Process Description
Shailesh Bavadekar, Adam Boulanger, John Davis +22
This report describes the aggregation and anonymization process applied to the COVID-19 Vaccination Search Insights (published at http://goo.gle/covid19vaccinationinsights), a publ…
Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead
Badih Ghazi, Ravi Kumar, Pasin Manurangsi +1
Differential privacy (DP) is a formal notion for quantifying the privacy loss of algorithms. Algorithms in the central model of DP achieve high accuracy but make the strongest trus…
On Distributed Differential Privacy and Counting Distinct Elements
Lijie Chen, Badih Ghazi, Ravi Kumar +1
We study the setup where each of users holds an element from a discrete set, and the goal is to count the number of distinct elements across all users, under the constraint of…
Pure Differentially Private Summation from Anonymous Messages
Badih Ghazi, Noah Golowich, Ravi Kumar +3
The shuffled (aka anonymous) model has recently generated significant interest as a candidate distributed privacy framework with trust assumptions better than the central model but…
Private Aggregation from Fewer Anonymous Messages
Badih Ghazi, Pasin Manurangsi, Rasmus Pagh +1
Consider the setup where parties are each given a number and the goal is to compute the sum in a secure fashion and with as little communica…