  We propose and analyze a general-purpose dataset-distance-based utility
function family, Duff, for differential privacy's exponential mechanism. Given
a particular dataset and a statistic (e.g., median, mode), this function family
assigns utility to a possible output o based on the number of individuals whose
data would have to be added to or removed from the dataset in order for the
statistic to take on value o. We show that the exponential mechanism based on
Duff often offers provably higher fidelity to the statistic's true value
compared to existing differential privacy mechanisms based on smooth
sensitivity. In particular, Duff is an affirmative answer to the open question
of whether it is possible to have a noise distribution whose variance is
proportional to smooth sensitivity and whose tails decay at a
faster-than-polynomial rate. We conclude our paper with an empirical evaluation
of the practical advantages of Duff for the task of computing medians.
