Paper 2026/074

Noisette: Certifying Differential Privacy Mechanisms Efficiently

Abstract

Differential privacy (DP) has emerged as a rigorous framework for privacy-preserving data analysis, with widespread deployment in industry and government. Yet existing implementations typically assume that the party applying the mechanism can be trusted to sample noise correctly. This trust assumption is overly optimistic: a malicious party may deviate from the protocol to gain accuracy or avoid scrutiny, thereby undermining users’ privacy guarantees. In this paper, we introduce Noisette, a family of efficient protocols for certifying DP noise sampling across both discrete and continuous settings. We design a protocol that supports any discrete DP noise distribution through certifiable lookup table evaluation, and introduce a staircase-based optimization that greatly improves efficiency without compromising privacy or utility. We further extend this framework to continuous mechanisms, providing the first efficient protocol for certifiable continuous noise sampling with a rigorous end-to-end $(\epsilon,\delta)$-DP guarantee under standard floating-point arithmetic, closing the precision-induced privacy loss left open by prior work. We demonstrate the practicality of our protocols through concrete DP applications, including mean estimation and federated learning. Our protocols outperform the prior state-of-the-art by orders of magnitude in runtime and communication, while preserving the same accuracy as uncertified DP mechanisms. These results establish Noisette as the first efficient, scalable, and general-purpose solution for certifiable DP noise sampling, making certified privacy guarantees practical in high-stakes applications.