One Attack to Rule Them All: Tight Quadratic Bounds for Adaptive Queries on Cardinality Sketches
Abstract
Cardinality sketches are compact data structures for representing sets or vectors. These sketches are space-efficient, typically requiring only logarithmic storage in the input size, and enable approximation of cardinality (or the number of nonzero entries). A crucial property in applications is \emph{composability} of the sketching map, meaning that the sketch of a union of sets can be computed from individual sketches. Existing designs provide strong statistical guarantees, ensuring that a randomly sampled sketching map is accurate with high probability for a number of queries that is exponential in the sketch size $k$. However, these guarantees degrade to quadratic in $k$ when queries are adaptive, meaning they depend on previous responses.
Prior works on statistical queries (Steinke and Ullman, 2015) and specific MinHash cardinality sketches (Ahmadian and Cohen, 2024) established that this is tight in that they can be compromised using $\tilde{O}(k^2)$ adaptive queries. In this work, we develop a unified attack framework that applies to broad classes of cardinality sketches. We show that any union-composable sketching map can be compromised with $\tilde{O}(k^4)$ adaptive queries. Moreover, this improves to a tight bound of $\tilde{O}(k^2)$ for monotone composable maps (special cases include MinHash, statistical queries, Boolean linear maps), for any linear map over the reals $\mathbb{R}$ and finite fields $\mathbb{F}_p$, and for any linear map over the integers $\mathbb{Z}$ but when the estimator may only use the nonzero structure of the sketch (as in Cormode et al., 2003). Our work is the first to apply to general composable maps and establishes and builds on fundamental properties of these structures. Specifically for linear sketches, we are the first to establish tight quadratic bounds, to any subclass, and our bounds strengthen weaker polynomial bounds recently established by Gribelyuk et al. (2024).
Prior works on statistical queries (Steinke and Ullman, 2015) and specific MinHash cardinality sketches (Ahmadian and Cohen, 2024) established that this is tight in that they can be compromised using $\tilde{O}(k^2)$ adaptive queries. In this work, we develop a unified attack framework that applies to broad classes of cardinality sketches. We show that any union-composable sketching map can be compromised with $\tilde{O}(k^4)$ adaptive queries. Moreover, this improves to a tight bound of $\tilde{O}(k^2)$ for monotone composable maps (special cases include MinHash, statistical queries, Boolean linear maps), for any linear map over the reals $\mathbb{R}$ and finite fields $\mathbb{F}_p$, and for any linear map over the integers $\mathbb{Z}$ but when the estimator may only use the nonzero structure of the sketch (as in Cormode et al., 2003). Our work is the first to apply to general composable maps and establishes and builds on fundamental properties of these structures. Specifically for linear sketches, we are the first to establish tight quadratic bounds, to any subclass, and our bounds strengthen weaker polynomial bounds recently established by Gribelyuk et al. (2024).
Research Areas
