  Working under a model of privacy in which data remains private even from the
statistician, we study the tradeoff between privacy guarantees and the utility
of the resulting statistical estimators. We prove bounds on
information-theoretic quantities, including mutual information and
Kullback-Leibler divergence, that depend on the privacy guarantees. When
combined with standard minimax techniques, including the Le Cam, Fano, and
Assouad methods, these inequalities allow for a precise characterization of
statistical rates under local privacy constraints. We provide a treatment of
several canonical families of problems: mean estimation, parameter estimation
in fixed-design regression, multinomial probability estimation, and
nonparametric density estimation. For all of these families, we provide lower
and upper bounds that match up to constant factors, and exhibit new (optimal)
privacy-preserving mechanisms and computationally efficient estimators that
achieve the bounds.
