Private Algorithms Can Always Be Extended
This solves a fundamental theoretical problem in differential privacy, ensuring that private algorithms can be universally extended, which is foundational for privacy-preserving data analysis.
The paper addresses whether any differentially private algorithm defined on a subset of inputs can be extended to the entire input space while maintaining privacy, and shows that it is always possible with a privacy parameter of 2ε.
We consider the following fundamental question on $ε$-differential privacy. Consider an arbitrary $ε$-differentially private algorithm defined on a subset of the input space. Is it possible to extend it to an $ε'$-differentially private algorithm on the whole input space for some $ε'$ comparable with $ε$? In this note we answer affirmatively this question for $ε'=2ε$. Our result applies to every input metric space and space of possible outputs. This result originally appeared in a recent paper by the authors [BCSZ18]. We present a self-contained version in this note, in the hopes that it will be broadly useful.