  Recently, a number of approaches and techniques have been introduced for
reporting software statistics with strong privacy guarantees. These range from
abstract algorithms to comprehensive systems with varying assumptions and built
upon local differential privacy mechanisms and anonymity. Based on the
Encode-Shuffle-Analyze (ESA) framework, notable results formally clarified
large improvements in privacy guarantees without loss of utility by making
reports anonymous. However, these results either comprise of systems with
seemingly disparate mechanisms and attack models, or formal statements with
little guidance to practitioners. Addressing this, we provide a formal
treatment and offer prescriptive guidelines for privacy-preserving reporting
with anonymity. We revisit the ESA framework with a simple, abstract model of
attackers as well as assumptions covering it and other proposed systems of
anonymity. In light of new formal privacy bounds, we examine the limitations of
sketch-based encodings and ESA mechanisms such as data-dependent crowds. We
also demonstrate how the ESA notion of fragmentation (reporting data aspects in
separate, unlinkable messages) improves privacy/utility tradeoffs both in terms
of local and central differential-privacy guarantees. Finally, to help
practitioners understand the applicability and limitations of
privacy-preserving reporting, we report on a large number of empirical
experiments. We use real-world datasets with heavy-tailed or near-flat
distributions, which pose the greatest difficulty for our techniques; in
particular, we focus on data drawn from images that can be easily visualized in
a way that highlights reconstruction errors. Showing the promise of the
approach, and of independent interest, we also report on experiments using
anonymous, privacy-preserving reporting to train high-accuracy deep neural
networks on standard tasks---MNIST and CIFAR-10.
