  Data sketching is a critical tool for distinct counting, enabling multisets
to be represented by compact summaries that admit fast cardinality estimates.
Because sketches may be merged to summarize multiset unions, they are a basic
building block in data warehouses. Although many practical sketches for
cardinality estimation exist, none provide privacy when merging. We propose the
first practical cardinality sketches that are simultaneously mergeable,
differentially private (DP), and have low empirical errors. These introduce a
novel randomized algorithm for performing logical operations on noisy bits, a
tight privacy analysis, and provably optimal estimation. Our sketches
dramatically outperform existing theoretical solutions in simulations and on
real-world data.
