Research map / Learning theory and algorithms / Matrix and tensor methods
Fast White-Box Adversarial Streaming Without a Random Oracle
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.
Gives a white-box adversarially robust streaming algorithm for k-sparse recovery that avoids random oracles by combining a deterministic sparse-recovery sketch with a pseudorandom FHE (GSW) based collision-resistant hash tester.
Problem
White-box adversarially robust streaming for k-sparse recovery: the adversary sees all internal randomness and parameters, and prior solutions need a random oracle (or long random strings) whose randomness counts toward space and which have large update time.
Approach
Replace the SIS random matrix / random oracle tester with a hash built from pseudorandom FHE ciphertexts of a random index: evaluating point-function circuits on L=O(log n) ciphertexts yields n pseudorandom hash columns, so the sketch is a linear combination that detects invalid (dense or colliding) outputs; a random guessed coordinate in the proof reduces collision-finding to breaking pseudorando
Key results
- Under subexponential LWE, a WAR streaming algorithm for k-sparse recovery uses O(k) bits of space, O(1) update time, and O(k^{1+c}) report time, without a random oracle.
- Under polynomial LWE the overhead is n^c in space and time (O(n^c+k) space, O(n^c) time).
- In the distributed model under polynomial Ring-LWE, each server uses O(k) bits of communication and O(n) processing time, versus O(nk) time for prior work.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace the previous subexponential SIS streaming construction with the proposed subexponential LWE construction | White-box adversarial k-sparse recovery streaming · k-sparse recovery | update time: \OO(k) -> \OO(1) | Helped |
| Use polynomially secure LWE instead of subexponential LWE | Proposed white-box adversarial streaming algorithm · k-sparse recovery | update time: \OO(1) -> \OO(n^c) | Hurt |
| Use polynomially secure Ring-LWE instead of polynomially secure LWE | Proposed white-box adversarial distributed protocol · k-sparse recovery | processing time: \OO(n^{1+c}) -> \OO(n) | Helped |
| Replace the previous subexponential SIS distributed construction with the proposed subexponential LWE protocol | White-box adversarial distributed k-sparse recovery · k-sparse recovery | processing time: \OO(nk) -> \OO(n) | Helped |
Limitations
- Strongest efficiency results require subexponential LWE hardness; polynomial LWE incurs n^c overhead.
- Assumes entries bounded by poly(n) and integer streams; the hash is only computed for exact sparse recovery.
Experimental setup
Metrics: space bits update time report time processing time
Baselines: Ajtai et al. PODS 2022 random-oracle SIS-based WAR sparse recovery
Builds on: Ajtai et al. white-box adversarial streaming GSW FHE Ring-LWE deterministic Vandermonde-based sparse recovery
Closest papers by meaning
- Improved Algorithms for White-Box Adversarial Streams (ICML 2023 · similarity 0.94)
- Adversarially Robust Dense-Sparse Tradeoffs via Heavy-Hitters (NeurIPS 2024 · similarity 0.87)
- BRUSLEATTACK: A QUERY-EFFICIENT SCORE- BASED BLACK-BOX SPARSE ADVERSARIAL ATTACK (ICLR 2024 · similarity 0.83)
- Towards Efficient Training and Evaluation of Robust Models against $l_0$ Bounded Adversarial Perturbations (ICML 2024 · similarity 0.83)
- Out of Thin Air: Exploring Data-Free Adversarial Robustness Distillation (AAAI 2024 · similarity 0.83)
- $\sigma$-zero: Gradient-based Optimization of $\ell_0$-norm Adversarial Examples (ICLR 2025 · similarity 0.82)
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.