A Strong Separation for Adversarially Robust L_0 Estimation for Linear Sketches
summary
Gives the first adaptive attack against linear sketches for turnstile L_0 estimation, showing any sketch that achieves a constant-factor gap must use Ω(n^{1/3}) rows and can be broken with about ~O(r^8) queries. Constructs a preprocessing that turns A into a sparse-plus-dense A′, uses interactive fingerprinting codes to recover sparse columns, and designs moment-matching distributions (Fourier/polynomial analysis) to make dense parts indistinguishable, yielding the adaptive query attack that succeeds with constant probability.
AI-written summary · about
chapters (13)
- 0:00Introduction
- 1:36Streaming model and distinct elements
- 3:47Adversarial robustness in streaming
- 5:36Insertion-deletion streams and linear sketches
- 8:03Hardt-Woodruff attack on linear sketches
- 9:10Main result and adversarial attack on L0 estimation
- 11:05L0 norm problem formulation
- 14:21Attack strategy and sketch preprocessing
- 17:39Significant coordinates in the sketch
- 21:13Sparse and dense matrix separation
- 24:40Attacking dense part with moment-matching
- 28:00Summary and future directions
- 29:49Q&A
related talks
44mHow Robust are Linear Sketches to Adaptive Inputs?
50mRobustness of Sketches to Adaptive nputs
01h 03mAdversarially Robust Streaming Algorithms
01h 24mAdversarial Examples
01h 09mNew Developments in Multilinear Maps: Zeroizing Attacks, Defenses, and Post-Zeroizing Obfuscation
01h 06mOn the Assumptions Used for Obfuscation
01h 04mUsing Lattices for Cryptanalysis
47mA Blackbox Reduction for Adaptive Adversaries using Differential Privacy