Research map / Learning theory and algorithms / Sample complexity
Unmasking Vulnerabilities: Cardinality Sketches under Adaptive Inputs
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows cardinality sketches (HLL/MinHash) are vulnerable to adaptive inputs: a single-batch attack with O(k) queries on standard estimators (4k queries on HLL++ gives ~40% error), and a multi-batch attack with ~O(k^2) queries against any correct query-response algorithm.
Problem
Cardinality (distinct count) sketches give strong guarantees only for non-adaptive queries; when queries depend on previous responses, the sketch randomness can leak and the estimates can be manipulated. The paper asks how vulnerable these sketches are under adaptive inputs and how efficiently they
Approach
Design an attack that issues random subset queries over a fixed ground set in one batch, then post-processes the estimator's responses to score keys; keys with lowest priorities get extreme scores and form an adversarial set. For arbitrary estimators, a multi-batch adaptive attack builds a "mask" set that hides the sketch of any larger set, using about k^2 queries.
Key results
- Single-batch attack with 4k queries on HLL++ causes consistent over- or underestimation of about 40%.
- Adaptive attack against any correct query response algorithm uses about O~(k^2) queries, matching the generic upper bound.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a single-batch attack with 4k queries to select adversarial keys | HLL++ cardinality estimation · HLL++ cardinality estimation | cardinality estimation error: 40% | Hurt |
Surprising findings
- Standard estimators are vulnerable to attacks with only linear many queries in the sketch size, in a single batch.
Limitations
- Empirical evaluation limited to HLL++ with synthetic random strings.
- Adaptive attack analysis is theoretical and relies on correctness/symmetry assumptions.
Experimental setup
Datasets: synthetic random strings
Benchmarks: HLL++ estimates on synthetic ground sets
Metrics: estimate-to-actual cardinality ratio
Baselines: HLL++ standard estimator
Builds on: HyperLogLog HLL++ robustness wrapper for adaptive data analysis
Closest papers by meaning
- Breaking the Quadratic Barrier: Robust Cardinality Sketches for Adaptive Queries (ICML 2025 · similarity 0.90)
- The Cost of Compression: Tight Quadratic Black-Box Attacks on Sketches for $\ell_2$ Norm Estimation (NeurIPS 2025 · similarity 0.87)
- Bits Leaked per Query: Information-Theoretic Bounds for Adversarial Attacks on LLMs (NeurIPS 2025 · similarity 0.83)
- Closing the Gap: Achieving Better Accuracy-Robustness Tradeoffs against Query-Based Attacks (AAAI 2024 · similarity 0.83)
- Mind the Gap: Detecting Black-box Adversarial Attacks in the Making through Query Update Analysis (CVPR 2025 · similarity 0.83)
- BRUSLEATTACK: A QUERY-EFFICIENT SCORE- BASED BLACK-BOX SPARSE ADVERSARIAL ATTACK (ICLR 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.