Order-Invariant Cardinality Estimators Are Differentially Private
Main Conference Track
Authors: Charlie Dickens, Justin Thaler, Daniel Ting

We consider privacy in the context of streaming algorithms for cardinality estimation.    We show that a large class of algorithms all satisfy $\epsilon$-differential privacy,     so long as (a) the algorithm is combined with a simple     down-sampling procedure, and (b) the input stream cardinality      is $\Omega(k/\epsilon)$. Here, $k$ is a certain parameter of the sketch    that is always at most the sketch size in bits, but is typically much smaller.    We also show that, even with no modification, algorithms in our    class satisfy $(\epsilon, \delta)$-differential privacy,    where $\delta$ falls exponentially with the stream cardinality.     Our analysis applies to essentially all popular cardinality estimation    algorithms, and substantially generalizes and tightens privacy bounds from earlier works.     Our approach is faster and exhibits a better utility-space    tradeoff than prior art.