Adaptive Attacks against Linear Sketches

When Answers Reveal the Sketch

A linear sketch stores $y=Ax$ for a hidden random matrix $A\in\mathbb R^{m\times n}$ with $m\ll n$. Classical analysis often says: fix $x$ first, draw $A$, and the estimate is accurate with high probability. An interactive service reverses part of that order: a user sees answers, chooses the next query from the transcript, and may gradually learn which inputs are unusually bad for the reused sketch.

Think of repeatedly asking a scale about carefully chosen objects. One noisy answer reveals little; many correlated answers can reveal calibration quirks. Similarly, sketch outputs may leak information about row space, collisions, signs, thresholds, or failure directions. The threat is not that linearity is wrong, but that an oblivious guarantee is applied to an adaptively selected sequence.

For a simple matrix $A=[1\ \ 1]$, vector $z=(1,-1)$ is nonzero but $Az=0$. If an estimator infers size only from $Az$, it cannot distinguish $z$ from zero. A randomly chosen fixed vector is unlikely to align with a hidden null space under a suitable theorem, but a vector selected after learning $A$ can align exactly.

An adaptive query depends on earlier answers. Transcript leakage is information about hidden sketch randomness exposed through answers or metadata. Reconstruction estimates that hidden structure. A null-space attack chooses a nonzero vector nearly annihilated by the learned map. Fresh randomness limits reuse of one vulnerable state. Robustification changes the algorithm or interface—through sketch switching, private monitoring, noise, query limits, or robust aggregation—so transcript-conditioned inputs remain controlled.

Adaptive Queries and Hidden Subspaces

For a dimension-reducing matrix with rank at most $m$, the null space has dimension at least $n-m$. If a transcript exposes enough independent information about the row space, an analyst can construct $z$ orthogonal to every row and hence $Az=0$. Approximate reconstruction gives a near-null vector with $\lVert Az\rVert$ much smaller than $\lVert z\rVert$.

The key quantifiers are: \[ \text{oblivious: }\forall x\text{ fixed independently},\quad \Pr_A[\mathcal A_A(x)\text{ succeeds}]\ge1-\delta, \] versus the much stronger adaptive statement in which $x_t$ is a function of previous outputs under the same $A$. A union bound works for a fixed finite query set independent of $A$; it does not automatically apply to transcript-conditioned queries.

A generic attack argument has three obligations: show answers contain a measurable signal about hidden sketch geometry; show the adaptive strategy accumulates enough signal despite estimator noise; and show the constructed final input lies in the promised domain while causing a certified error. Boundary cases include output rounding that blocks reconstruction, a tiny query budget, refreshed independent sketches, or an estimator whose robustness theorem already covers adaptive inputs.

flowchart TD
 A[Reuse hidden linear map A] --> B[Issue permitted probe]
 B --> C[Observe answer transcript]
 C --> D[Update hypothesis about row space]
 D --> E{Enough leakage?}
 E -->|no| B
 E -->|yes| F[Construct near-null vector z]
 F --> G[Check z satisfies input promise]
 G --> H[Compare true quantity with sketch estimate]
 H --> I[Witness adaptive failure]
 A --> J{Fresh state or robust theorem?}
 J -->|yes| K[Attack argument may not apply]
 J -->|no| B
 classDef navy fill:#17365D,color:#fff,stroke:#17365D;
 classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
 classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
 classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
 class A,B,C,D navy;
 class E,F,G purple;
 class H,I crimson;
 class J,K teal;

Steering Estimates Toward Failure

The cleanest laboratory exposes $A$ directly and computes its smallest right-singular vector. This is not a black-box reconstruction attack; it isolates the final geometric step safely and makes the quantifier failure measurable. For an underdetermined full-row-rank map, SVD returns a unit vector $z$ in the null space. Then $\lVert z\rVert_2=1$ but $\lVert Az\rVert_2$ is numerical zero.

import numpy as np

def normalized_null_vector(matrix):
    matrix = np.asarray(matrix, dtype=float)
    if matrix.ndim != 2 or not np.all(np.isfinite(matrix)):
        raise ValueError("finite matrix required")
    rows, cols = matrix.shape
    if rows >= cols:
        raise ValueError("demonstration requires an underdetermined map")
    _, _, vt = np.linalg.svd(matrix, full_matrices=True)
    vector = vt[-1]
    return vector / np.linalg.norm(vector)

rng = np.random.default_rng(19)
A = rng.normal(size=(4, 9))
z = normalized_null_vector(A)
assert abs(np.linalg.norm(z) - 1.0) < 1e-12
assert np.linalg.norm(A @ z) < 1e-10

fixed = np.zeros(9)
fixed[0] = 1.0
fixed_ratio = np.linalg.norm(A @ fixed) / np.linalg.norm(fixed)
assert fixed_ratio > 0

perturbation = rng.normal(size=9)
perturbation *= 1e-4 / np.linalg.norm(perturbation)
near_null = z + perturbation
assert np.linalg.norm(A @ near_null) <= np.linalg.norm(A, 2) * np.linalg.norm(perturbation) + 1e-12

try:
    normalized_null_vector(np.eye(3))
    raise AssertionError("square map accepted")
except ValueError:
    pass

print("fixed-vector sketch ratio:", round(float(fixed_ratio), 6))
print("adaptive null residual:", format(float(np.linalg.norm(A @ z)), ".3e"))
print("near-null residual:", format(float(np.linalg.norm(A @ near_null)), ".3e"))

Attacks, Monitoring and Defensive Limits

In a teaching case, reveal a small matrix and contrast a fixed vector with a computed null vector. In a professional telemetry API, users may repeatedly filter, query, and publish sketch-derived estimates; the transcript, dashboards, error messages, and timing all belong in the threat model. In an adversarial public service, assuming secret seeds forever is not a proof: leakage, compromise, multi-tenant correlation, and chosen inputs must be considered.

Defenses include limiting adaptive queries, delaying or coarsening outputs, rotating independent sketches, maintaining multiple sketches and using robust aggregation, privately monitoring transcript-dependent risk, and falling back to exact computation. These are not interchangeable. Fresh randomness must really be independent; switching rules can themselves leak; differential privacy has a composition budget; noise may destroy utility; and aggregation requires enough independent replicas.

Invalidating evidence includes error increasing with interaction count, repeated failures concentrated on transcript-conditioned inputs, seed/state reuse across tenants, unusually small sketch-to-true norm ratios, monitor alerts near switching thresholds, correlated replica failures, or an attacker model stronger than the theorem.

flowchart TD
 A[Classify query adaptivity and exposure] --> B[Inventory reused randomness and outputs]
 B --> C[Set query leakage and failure budgets]
 C --> D[Choose rotation aggregation monitor or exact fallback]
 D --> E[Red-team transcript-conditioned inputs]
 E --> F{Adaptive accuracy passes?}
 F -->|yes| G[Deploy versioned protected states]
 F -->|no| H[Reduce exposure strengthen or reject]
 G --> I[Monitor drift replica correlation and alerts]
 I --> J{Threat model unchanged?}
 J -->|yes| I
 J -->|no| H
 classDef navy fill:#17365D,color:#fff,stroke:#17365D;
 classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
 classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
 classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
 class A,B,C navy;
 class D,E,G purple;
 class F,I teal;
 class H,J crimson;

Threat-Model an Interactive Sketch

Robustness begins with quantifier order and an information-flow diagram, not a larger nonadaptive confidence parameter.