2018/10/30 by Borgs, Christian, Chayes, Jennifer, Smith, Adam +1
#Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Statistics Theory (math.ST)
paper · doi:10.48550/arxiv.1810.12518
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.