2024/11/10 by Edith Cohen, Jelani Nelson, Cohen, Edith +7 · 3 citations
Computer Science · #Advanced Database Systems and Queries #Complexity and Algorithms in Graphs #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2411.06370
openalex publication_date 2024/11/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 composability, 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 remains robust for an exponential number of queries in terms of 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 a quadratic number of adaptive queries. In this work, we develop a universal attack framework that applies to broad classes of cardinality sketches. We show that any union-composable sketching map can be compromised with O(k4) adaptive queries and this improves to a tight bound of O(k2) for monotone maps (including MinHash, statistical queries, and Boolean linear maps). Similarly, any linear sketching map over the reals ℝ and finite fields \mathbbFp can be compromised using O(k2) adaptive queries, which is optimal and strengthens some of the recent results by~\citetGribelyukLWYZ:FOCS2024, who established a weaker polynomial bound.