  We derive the optimal $\epsilon$-differentially private mechanism for single
real-valued query function under a very general utility-maximization (or
cost-minimization) framework. The class of noise probability distributions in
the optimal mechanism has {\em staircase-shaped} probability density functions
which are symmetric (around the origin), monotonically decreasing and
geometrically decaying. The staircase mechanism can be viewed as a {\em
geometric mixture of uniform probability distributions}, providing a simple
algorithmic description for the mechanism. Furthermore, the staircase mechanism
naturally generalizes to discrete query output settings as well as more
abstract settings. We explicitly derive the optimal noise probability
distributions with minimum expectation of noise amplitude and power. Comparing
the optimal performances with those of the Laplacian mechanism, we show that in
the high privacy regime ($\epsilon$ is small), Laplacian mechanism is
asymptotically optimal as $\epsilon \to 0$; in the low privacy regime
($\epsilon$ is large), the minimum expectation of noise amplitude and minimum
noise power are $\Theta(\Delta e^{-\frac{\epsilon}{2}})$ and $\Theta(\Delta^2
e^{-\frac{2\epsilon}{3}})$ as $\epsilon \to +\infty$, while the expectation of
noise amplitude and power using the Laplacian mechanism are
$\frac{\Delta}{\epsilon}$ and $\frac{2\Delta^2}{\epsilon^2}$, where $\Delta$ is
the sensitivity of the query function. We conclude that the gains are more
pronounced in the low privacy regime.
