Private Algorithms Can Always Be Extended

We consider the following fundamental question on \(\epsilon\)-differential privacy. Consider an arbitrary \(\epsilon\)-differentially private algorithm defined on a subset of the input space. Is it possible to extend it to an \({\epsilon }^′\)-differentially private algorithm on the whole input space for some \({\epsilon }^′\) comparable with \(\epsilon\)? In this note we answer affirmatively this question for \({\epsilon }^′=2\epsilon\). 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.