  We study the fundamental task of estimating the median of an underlying
distribution from a finite number of samples, under pure differential privacy
constraints. We focus on distributions satisfying the minimal assumption that
they have a positive density at a small neighborhood around the median. In
particular, the distribution is allowed to output unbounded values and is not
required to have finite moments. We compute the exact, up-to-constant terms,
statistical rate of estimation for the median by providing nearly-tight upper
and lower bounds. Furthermore, we design a polynomial-time differentially
private algorithm which provably achieves the optimal performance. At a
technical level, our results leverage a Lipschitz Extension Lemma which allows
us to design and analyze differentially private algorithms solely on
appropriately defined "typical" instances of the samples.
