Introduction
A system that is reliable on independently chosen inputs may fail under adaptive interaction, where new queries are formed after observing answers that may reveal internal parameters. In machine learning, a model can have small error on its test distribution while searches guided by its outputs find failures [44 , 54 ] . Defenses against language-model attacks can be bypassed through adaptive interaction [53 ] . The robustness of a system is studied by quantifying how many interactions are needed to find a failure, and by how much a responder can delay this process by controlling what its answers reveal.
We study this question for the fundamental task of estimating the Euclidean norm of a vector from a linear sketch . A fixed matrix A ∈ R k × n A \in\mathbb{R}^{k \times n} A ∈ R k × n compresses each input v ∈ R n v \in\mathbb{R}^n v ∈ R n to k k k linear measurements A v Av A v . A responder uses this sketch to estimate ∥ v ∥ 2 \lVert v\rVert_2 ∥ v ∥ 2 . The black-box attacker chooses inputs and sees the returned estimates, but never sees A A A or the sketches. Note that when k < n k<n k < n , inputs with different norms can have the same sketch, so errors exist. The aim of the attacker is to force failures efficiently .
The quadratic benchmark. At constant relative accuracy, classical randomized constructions, including the Johnson–Lindenstrauss transform and the AMS sketch [4 , 47 ] , support exponentially many nonadaptive queries in the sketch dimension k k k . Under adaptivity, the immediate guarantee is Ω ~ ( k ) \widetilde{\Omega}(k) Ω ( k ) , by using a fresh sketch for each query. Defenses based on differential privacy or subsampling support Ω ~ ( k 2 ) \widetilde{\Omega}(k^2) Ω ( k 2 ) queries [14 , 41 ] , by using a randomized estimator with JL or AMS sketches. These defenses draw on adaptive data analysis: limiting what each answer reveals allows repeated use of the same randomness [9 , 27 ] . The quadratic guarantee is attainable but its optimality remained open:
Question. Can a different choice of a linear sketch and responder support substantially more adaptive queries at the same sketch dimension?
Prior attacks either required polynomially more queries, targeted particular sketching matrices or estimators, restricted the responder, or established weaker failure guarantees [2 , 12 , 20 , 40 ] .
Our results: attacks
We show that the quadratic guarantee is also a limit. We design an attack algorithm that applies to any matrix with n > 40 k n > 40k n > 40 k and forces errors even from powerful unrestricted responders.
Informed responder model. The responder has unbounded computation, memory, and private randomness. It knows A A A , the attack algorithm, and the attacker’s complete execution history and current state. Before each query, it knows the input distribution. It may change its randomized rule adaptively after every query. Its only information restriction is that it observes each fresh input through the sketch. After it returns a response, the input itself and the rest of that query’s execution are revealed. Note that a stronger responder model only strengthens the attack guarantee. Definition 2.1 formalizes this model.
Norm gap task. Our attacks work even when the responder only has to distinguish ∥ v ∥ 2 ≤ L \lVert v\rVert_2 \le L ∥ v ∥ 2 ≤ L from ∥ v ∥ 2 ≥ U \lVert v\rVert_2 \ge U ∥ v ∥ 2 ≥ U , for fixed public thresholds with U / L = 1 + Θ ( α ) U/L = 1 + \Theta(\alpha) U / L = 1 + Θ ( α ) ; either binary answer is permitted between the thresholds. This task, also considered by [2 , 40 ] , is easier than norm estimation with relative error Ω ( α ) \Omega(\alpha) Ω ( α ) : thresholding a sufficiently accurate norm estimate gives a correct gap answer. Thus errors on the norm-gap task transfer to errors in norm estimation.
Theorem 1.1 (A universal attack). There is an attack algorithm and a positive absolute constant c f r a c c_{\mathrm{frac}} c frac such that, for every A ∈ R k × n A \in\mathbb{R}^{k \times n} A ∈ R k × n with n > 40 k n > 40k n > 40 k , every α ∈ ( 0 , 1 ] \alpha\in(0,1] α ∈ ( 0 , 1 ] , and every informed responder, the attack uses
O ( k + α 2 k 2 log ( 2 + α 2 k ) ) O(k + \alpha^2 k^2 \log(2 + \alpha^2 k)) O ( k + α 2 k 2 log ( 2 + α 2 k )) queries and returns, with probability at least 0.9, a round B B B of Θ ( k ) \Theta(k) Θ ( k ) consecutive queries generated independently from one announced distribution. For binary norm gap with U / L = 1 + Θ ( α ) U/L = 1 + \Theta(\alpha) U / L = 1 + Θ ( α ) , at least c f r a c ∣ B ∣ c_{\mathrm{frac}}|B| c frac ∣ B ∣ answers are incorrect; for norm estimation, at least c f r a c ∣ B ∣ c_{\mathrm{frac}}|B| c frac ∣ B ∣ estimates have relative error Ω ( α ) \Omega(\alpha) Ω ( α ) .
All queries are supported on a common set of 40 k + 1 40k + 1 40 k + 1 coordinates, which may be prescribed arbitrarily before the interaction. The attack uses O ( 1 + α 2 k log ( 2 + α 2 k ) ) O(1 + \alpha^2 k \log(2 + \alpha^2 k)) O ( 1 + α 2 k log ( 2 + α 2 k )) adaptive rounds; working memory is O ~ ( k + α 2 k 2 ) \widetilde{O}(k + \alpha^2 k^2) O ( k + α 2 k 2 ) words and arithmetic cost is O ~ ( k 2 + α 4 k 4 ) \widetilde{O}(k^2 + \alpha^4 k^4) O ( k 2 + α 4 k 4 ) .
The linear support size is optimal up to a constant factor: if A A A is such that every k k k columns are linearly independent, every input supported on a known set of at most k k k coordinates can be recovered exactly from its sketch, allowing exact norm answers that do not reveal anything about $A.
Accuracy vs. robustness The attack is more effective when higher accuracy is required. At constant accuracy, our bounds match known defenses of Ω ~ ( k 2 ) \widetilde{\Omega}(k^2) Ω ( k 2 ) up to logarithmic factors. At high accuracy α = Θ ( k − 1 / 2 ) \alpha= \Theta(k^{-1/2}) α = Θ ( k − 1/2 ) , the attack uses O ( k ) O(k) O ( k ) queries in O ( 1 ) O(1) O ( 1 ) rounds. At very high accuracy ( α < C k − 1 / 2 ) (\alpha< Ck^{-1/2}) ( α < C k − 1/2 ) , the initial distribution already forces a constant fraction of errors.
Attack structure. Each query combines a scalar signal with Gaussian noise. The signal distribution remains fixed, while the attacker changes the noise covariance between rounds. The attack keeps the noise norm concentrated, so accurate norm answers distinguish low from high signal values. Our analysis proceeds through this auxiliary signal-gap task.
The noise covariance determines how accurately the signal can be estimated from the sketch. Higher signal-estimation variance makes the two signal regimes harder to distinguish, even while the input noise norm remains concentrated. Starting from isotropic covariance, the attack seeks a universally hard query distribution1 by changing the noise covariance (see Figure 1 ).
Figure 1. The covariance attack in sketch space for queries with signal w = 1 w = 1 w = 1 (blue) and w = 1 + α w = 1 + \alpha w = 1 + α (orange). Sketches are projected on the signal column A h A_h A h and an orthogonal direction. Illustration shows 2 σ 2\sigma 2 σ ellipses of the sketch noise. The dashed line is the threshold 1 + α / 2 1 + \alpha/2 1 + α /2 . At the start the input noise is isotropic, and the sketch noise may separate the two signals (if there is overlap we are done). At the end, if the responder does not err earlier on an easy distribution, the sketch noise is stretched along A h A_h A h and the two signals overlap.
Each round also checks accuracy. If its empirical signal-gap loss exceeds the validation threshold, the attack returns the round and its query distribution. Otherwise, correlations between the answers and the sampled noise guide a covariance update. The analysis bounds the number of rounds that can pass validation, forcing an observed round with many errors. The returned distribution need not be universally hard, since the responder can err on an easier distribution. But if the responder maintains sufficiently small error whenever a smaller constant error is achievable, the returned distribution is universally hard.
Sufficient-statistic responders. For each fixed distribution, a scalar sufficient statistic contains all the information about the signal available in the sketch. A sufficient-statistic responder is restricted so that, conditional on the disclosed history, its mean binary answer depends on the current sketch only through this statistic (formalized in § 5 ). The class includes the Bayesoptimal signal-gap predictor, as well as predictors computed from the statistic followed by output noise, rounding, or clipping. It provides an idealized model of repeatedly fitting a predictor to the current query distribution while keeping the compressive map fixed. In this interpretation, accurate predictions supply feedback that guides the attacker’s search for a hard noise distribution, even as the predictor is adapted to each new distribution. Section A.2 develops the learning interpretation and its implications for output defenses. We obtain a more efficient attack for informed responders with this additional restriction.
Theorem 1.2 (Attack on sufficient-statistic responders; informal). There is an attack algorithm such that, for every A ∈ R k × n A \in\mathbb{R}^{k \times n} A ∈ R k × n with n > 40 k n > 40k n > 40 k , every α ∈ ( 0 , 1 ] \alpha\in(0,1] α ∈ ( 0 , 1 ] , and every sufficient-statistic norm responder, with probability at least 0.9 0.9 0.9 the attack returns a round of Ω ( k ) \Omega(k) Ω ( k ) consecutive queries, generated independently from one distribution, for which at least a constant fraction of norm estimates have relative error Ω ( α ) \Omega(\alpha) Ω ( α ) . The attack uses O ( k + α 2 k 2 ) O(k+\alpha^2 k^2) O ( k + α 2 k 2 ) queries, O ( log ( 2 + α 2 k ) ) O(\log(2+\alpha^2 k)) O ( log ( 2 + α 2 k )) adaptive rounds, O ( k log ( 2 + α 2 k ) ) O(k\log(2+\alpha^2 k)) O ( k log ( 2 + α 2 k )) words of working memory, and O ~ ( k 2 + α 2 k 3 ) \widetilde{O}(k^2+\alpha^2 k^3) O ( k 2 + α 2 k 3 ) arithmetic operations. All queries use any prescribed set of 40 k + 1 40k+1 40 k + 1 coordinates. On the same success event, if the threshold is reached before a round is rejected, the final query distribution is universally hard for norm tasks.
Analyzing attack progress. We establish the existence of a comparator covariance whose signal-estimation variance makes the query distribution universally hard. The key property exploited by both attacks is that accurate answers force a component of the mean signed noise—the expected product of the generated noise vector and the binary answer—along the hidden signal-estimation direction; we extend the correlation bound of Ahmadian et al. [2 ] to general covariances. For sufficient-statistic responders, the mean signed noise is aligned with the hidden direction, allowing direct multiplicative growth of the signal-estimation variance. For general responders, the challenge is that other components of the mean signed noise can obscure the useful direction. We extract measurements that separate the current covariance from the hard comparator and use them in matrix multiplicative-weights updates, with progress measured by a relative-entropy potential.
Lower bound for informed responders
Our attacks use O ~ ( k + α 2 k 2 ) \widetilde{O}(k+\alpha^2 k^2) O ( k + α 2 k 2 ) queries but known defenses [14 , 41 ] guarantee only Ω ~ ( α 4 k 2 ) \widetilde{\Omega}(\alpha^4 k^2) Ω ( α 4 k 2 ) adaptive queries, leaving a gap for higher accuracy. The distinction is that the known defenses use responders without knowledge of the query distributions. We show that for a broad family of signal–noise query distributions, a Gaussian JL sketch can withstand Ω ( α 2 k 2 ) \Omega(\alpha^2 k^2) Ω ( α 2 k 2 ) adaptive queries when paired with a responder that is provided with the noise mean and covariance.
Theorem 1.3 (Matching lower bound; informal). Fix a target error fraction δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) . For a sufficiently large constant C C C and C / k ≤ α ≤ 1 C/\sqrt{k} \le\alpha\le1 C / k ≤ α ≤ 1 , consider attacks using the signal–noise query family specified in Section D, with sufficiently concentrated noise energy. For either norm task, any such attack that forces, with probability at least 0.9, a δ \delta δ fraction of errors in an observed interval of Ω ( k ) \Omega(k) Ω ( k ) consecutive queries against every sketching matrix and every informed responder requires Ω ( α 2 k 2 ) \Omega(\alpha^2 k^2) Ω ( α 2 k 2 ) queries. The constants may depend on δ \delta δ .
Subject to the family’s moment and concentration conditions, the noise law is arbitrary and may depend on the signal; the distribution may change after every answer. The lower bound is witnessed by a Gaussian JL matrix sampled once and kept fixed, together with a responder that beyond the matrix, current sketch, and task parameters, uses only the signal direction and noise mean and covariance.
Taking δ \delta δ to be the constant error fraction guaranteed by our attacks, this establishes optimal query complexity for the sufficient-statistic attack within this family and accuracy regime. The general attack is optimal up to its logarithmic factor.
The responder adds noise to a distribution-informed linear estimator. For the analysis, we use KL divergence to bound what its answers reveal about the hidden Gaussian matrix, showing that finding a query law with large signal-estimation variance requires Ω ( α 2 k 2 ) \Omega(\alpha^2 k^2) Ω ( α 2 k 2 ) queries. Section D gives the precise statement and proof.
Comparison with prior work
Table 1 summarizes a comparison of our results with directly related prior work. A broader related work discussion is included in Section A.
Table 1. Comparison at constant accuracy and success probability. Sketch dimension k k k . Rounds are of attack adaptivity. Support is the size of a common coordinate set. Arithmetic-operation counts assume unit-cost sampling.
The problem was first formalized by Hardt and Woodruff [40 ] . They gave polynomial-query attacks for arbitrary sketching matrices A A A , using O ~ ( k ) \widetilde{O}(k) O ( k ) adaptive rounds and common query support of size O ( k ) O(k) O ( k ) at constant relative accuracy. Their responder uses a randomized estimator that may change between rounds, but remains fixed throughout each round. Their attack returns a distribution on which that estimator has a constant error rate. Our attack forces errors from a much stronger informed responder that additionally knows each query distribution and may change its rule after every query.
Ahmadian, Cohen, and Stemmer [2 ] (ACS) obtained a O ~ ( k 2 ) \widetilde{O}(k^2) O ( k 2 ) -query attack against arbitrary A A A (with n = Ω ~ ( k 2 ) n = \widetilde{\Omega}(k^2) n = Ω ( k 2 ) ) and informed responders. It samples all queries i.i.d. from one distribution in a single nonadaptive round. The attack guarantees that either the responder makes errors on a constant fraction of queries, or the attack constructs an input on which the estimator optimal for the query distribution fails (but the latter need not be an error by the actual responder). They left open the existence of a quadratic-query attack with a constant error rate and with support reduced from O ~ ( k 2 ) \widetilde{O}(k^2) O ( k 2 ) to O ~ ( k ) \widetilde{O}(k) O ( k ) coordinates. As observed by [2 ] , at constant accuracy, Ω ~ ( k ) \widetilde{\Omega}(k) Ω ( k ) adaptive rounds are necessary to force errors against arbitrary sketches and responders using polynomially many queries.2
Organization. § 2 defines the interaction model and attack objective. § 3 presents the general attack. § 4 previews the analysis. § 5 gives the more efficient attack for sufficient-statistic responders. § 6 concludes. Section A places our work in a broader context of related works. The full analyses appear in Sections B and C; the lower bound in Section D; subsequent appendices give supporting proofs and details.
Interaction model and attack objectives
Fix a matrix A ∈ R k × n A \in\mathbb{R}^{k \times n} A ∈ R k × n and a publicly specified task with response space Y \mathcal{Y} Y . The task determines which answers are correct for each input.
The interaction is between an attacker and a responder . In query i i i , the attacker chooses an input v i ∈ R n v_i \in\mathbb{R}^n v i ∈ R n , the responder receives the sketch A v i Av_i A v i and returns an answer a i ∈ Y a_i \in\mathcal{Y} a i ∈ Y that the attacker observes.
The attacker never observes A A A or the sketches; it observes only its own execution and the returned answers from the responder. Its objective is to cause the responder to return incorrect answers.
The informed responder model
Our attacks are analyzed against an informed responder , which has unbounded computation, memory, and randomness. It knows A A A and the attacker’s algorithm and its parameters, and the complete execution history. The only information temporarily withheld from the responder at the beginning of query i i i is the fresh randomness that the attacker uses to sample its current input v i v_i v i . This information is shared with the responder, but only after the answer a i a_i a i is determined.
Let T r i \mathrm{Tr}_i Tr i denote the complete execution of both parties through the completion of query i i i , including their random choices, inputs, and responses. This transcript is available to the responder. Our attack queries follow a particular structure:
Definition 2.1 (Adaptive interaction query). Query i i i proceeds as follows.
The attacker announces a Borel distribution D i \mathcal{D}_i D i on R n \mathbb{R}^n R n , chosen measurably from its own execution transcript so far and fresh randomness. It discloses D i \mathcal{D}_i D i and the execution history of this query.
Using A A A , T r i − 1 \mathrm{Tr}_{i-1} Tr i − 1 , and the newly disclosed information, the responder privately selects a measurable map ψ i : R k → Y \psi_i: \mathbb{R}^k \to\mathcal{Y} ψ i : R k → Y , possibly at random.
The attacker draws v i ∼ D i v_i \sim\mathcal{D}_i v i ∼ D i using fresh randomness. The responder receives the sketch y i = A v i y_i = Av_i y i = A v i and returns an answer a i = ψ i ( y i ) a_i = \psi_i(y_i) a i = ψ i ( y i ) , which the attacker observes. After the answer, the attacker discloses the remainder of its execution for this query.
The attacker may stop and return an output based on its information and fresh randomness.
Attack structure and objective
Our attacks proceed in rounds , each containing Ω ( k ) \Omega(k) Ω ( k ) queries. At the start of each round, the attacker fixes a query distribution and the number of queries, then draws the queries independently from that distribution. Thus, conditional on these choices and the preceding history, the queries in a round are i.i.d. The responder may still change its rule after every query. We use i i i for the global query index, t t t for the round index, and j j j for the query index within a round.
The attack’s goal is to return a round, together with its query distribution, in which a constant fraction of the answers were incorrect for the task. We seek this guarantee with constant probability using few queries and rounds.
Norm tasks
Norm estimation. The responder returns an estimate r ^ i ∈ Y = [ 0 , ∞ ) \hat{r}_i \in\mathcal{Y} = [0,\infty) r ^ i ∈ Y = [ 0 , ∞ ) of ∥ v i ∥ 2 \lVert v_i\rVert_2 ∥ v i ∥ 2 . For an accuracy parameter α > 0 \alpha> 0 α > 0 and a fixed absolute constant c e r r > 0 c_{\mathrm{err}} > 0 c err > 0 , the loss is
e i = 1 ∣ r ^ i − ∥ v i ∥ 2 ∣ > c e r r α ∥ v i ∥ 2 . (1) e_i = \mathbf{1}_{\lvert\hat{r}_i-\lVert v_i\rVert_2\rvert>c_{\mathrm{err}}\alpha\lVert v_i\rVert_2}. \tag*{(1)} e i = 1 ∣ r ^ i − ∥ v i ∥ 2 ∣ > c err α ∥ v i ∥ 2 . (1)
Thus an answer is correct when its relative error is at most c e r r α c_{\mathrm{err}}\alpha c err α .
Binary norm gap. Fix public thresholds 0 < L < U 0 < L < U 0 < L < U . The responder returns an answer in Y = { − 1 , + 1 } \mathcal{Y} = \{-1,+1\} Y = { − 1 , + 1 } : the correct answer is − 1 -1 − 1 when ∥ v ∥ 2 ≤ L \lVert v\rVert_2 \le L ∥ v ∥ 2 ≤ L and + 1 +1 + 1 when ∥ v ∥ 2 ≥ U \lVert v\rVert_2 \ge U ∥ v ∥ 2 ≥ U , with either answer permitted between the thresholds. The loss is
e n g ( b , v ) : = 1 b = + 1 , ∥ v ∥ 2 ≤ L + 1 b = − 1 , ∥ v ∥ 2 ≥ U . (2) e_{\mathrm{ng}}(b,v) := \mathbf{1}_{b=+1,\ \lVert v\rVert_2\le L}+\mathbf{1}_{b=-1,\ \lVert v\rVert_2\ge U}. \tag*{(2)} e ng ( b , v ) := 1 b = + 1 , ∥ v ∥ 2 ≤ L + 1 b = − 1 , ∥ v ∥ 2 ≥ U . (2)
Our thresholds satisfy U / L = 1 + Θ ( α ) U/L = 1+\Theta(\alpha) U / L = 1 + Θ ( α ) . When gap responses are derived from norm estimates by thresholding at ( L 2 + U 2 ) / 2 \sqrt{(L^2+U^2)/2} ( L 2 + U 2 ) /2 , every incorrect gap answer therefore certifies Ω ( α ) \Omega(\alpha) Ω ( α ) relative error in the norm estimate on the same input.
Definition 2.2 (Realized loss and empirical accuracy). For a fixed task, let e i ∈ [ 0 , 1 ] e_i \in[0,1] e i ∈ [ 0 , 1 ] denote the realized loss on query i i i , a measurable function of its input and response. For δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , the responder is δ \delta δ -accurate on a round with query index set B B B if
1 ∣ B ∣ ∑ i ∈ B e i ≤ δ . \frac{1}{\lvert B\rvert}\sum_{i\in B}e_i \le\delta. ∣ B ∣ 1 i ∈ B ∑ e i ≤ δ . For both norm tasks, the loss is binary, so empirical accuracy means that at most a δ \delta δ fraction of the answers in the round are incorrect.
The covariance attack
This section presents the general attack, given in Algorithm 1. § 4 previews its analysis; the full proof is in Section B. The interaction follows the disclosure protocol of Definition 2.1 . The algorithm uses up to T max T_{\max} T m a x rounds with r r r queries each. In each round, the attacker draws queries from a fixed signal–noise distribution and converts the norm-task responses into signal-gap answers b j ∈ [ − 1 , 1 ] b_j \in[-1,1] b j ∈ [ − 1 , 1 ] . It accumulates the signed noise S t S_t S t and the loss sum E t E_t E t , using a fixed validation level δ 0 \delta_0 δ 0 . If E t > r δ 0 / 2 E_t > r\delta_0/2 E t > r δ 0 /2 , it returns the round; otherwise it uses S t S_t S t to update the noise covariance, which is initially isotropic. The following subsections specify the query law, response conversion, and covariance update. The updates are parametrized by the cap λ \lambda λ .
The parameters have the following scales:
λ = Θ ( α 2 ) , r = Θ ( k ) , \lambda= \Theta(\alpha^2), \qquad r = \Theta(k), λ = Θ ( α 2 ) , r = Θ ( k ) ,
T max = Θ ( 1 + α 2 k log ( 2 + α 2 k ) ) . T_{\max} = \Theta(1+\alpha^2 k\log(2+\alpha^2 k)). T m a x = Θ ( 1 + α 2 k log ( 2 + α 2 k )) .
Accuracy regimes. Fix absolute constants C min ≥ 1 C_{\min} \ge1 C m i n ≥ 1 and sufficiently small α 0 ∈ ( 0 , 1 ] \alpha_0 \in(0,1] α 0 ∈ ( 0 , 1 ] . First replace α \alpha α by min { α , α 0 } \min\{\alpha,\alpha_0\} min { α , α 0 } ; this changes only absolute constants in the guarantees. If the resulting parameter is below C min / k C_{\min}/\sqrt{k} C m i n / k , both attacks return their first isotropic round of Θ ( k ) \Theta(k) Θ ( k ) queries (Corollary F.3 ). The pseudocode and covariance-update analysis below concern the remaining regime $\alpha \in [C_{\min}/\sqrt{k},\alpha_0]`.
Query distribution
Fix any prescribed set S S S of m + 1 ≤ n m+1\le n m + 1 ≤ n coordinates, where m = 40 k m=40k m = 40 k . Choose the signal coordinate h h h uniformly from S S S and let M = S ∖ { h } M=S\setminus\{h\} M = S ∖ { h } carry the noise. Both h h h and M M M remain fixed throughout the attack. Query entries are 0 0 0 outside S S S , so we may discard the unused columns of A A A and, for the analysis, relabel the coordinates as n = m + 1 n=m+1 n = m + 1 and M = [ n ] ∖ { h } M=[n]\setminus\{h\} M = [ n ] ∖ { h } . Section B.2 justifies this initialization.
We also fix a noise multiplier c > 0 c>0 c > 0 (a universal constant) and a signal law W W W supported near 1 1 1 , specified in Definition 3.1. For any Σ ⪰ 0 \Sigma\succeq0 Σ ⪰ 0 with tr Σ = 1 \operatorname{tr}\Sigma=1 tr Σ = 1 , define the query law D Σ D_\Sigma D Σ by
w ∼ W , u ∼ N ( 0 , Σ ) , v = w e h + c ι M u , (3) w\sim W,\qquad u\sim N(0,\Sigma),\qquad v= w e_h+c\iota_Mu, \tag*{(3)} w ∼ W , u ∼ N ( 0 , Σ ) , v = w e h + c ι M u , (3)
where w w w and u u u are independent and ι M : R m → R n \iota_M:\mathbb{R}^m\to\mathbb{R}^n ι M : R m → R n embeds a vector on the coordinates M M M . Writing A h = A ∙ h A_h=A_{\bullet h} A h = A ∙ h and A M = A ∙ M A_M=A_{\bullet M} A M = A ∙ M , the sketch takes the form
y = A v = w A h + c A M u . (4) y=Av=wA_h+cA_Mu. \tag*{(4)} y = A v = w A h + c A M u . (4)
After initialization, the attack changes only the covariance of the query distribution. In round t t t it announces D Σ t D_{\Sigma_t} D Σ t and uses fresh, independent draws of ( w , u ) (w,u) ( w , u ) for every query in that round.
The signal-gap task
The auxiliary task is to distinguish w ≤ 1 w\le1 w ≤ 1 from w ≥ 1 + α w\ge1+\alpha w ≥ 1 + α . A response b ∈ [ − 1 , 1 ] b\in[-1,1] b ∈ [ − 1 , 1 ] incurs loss
L ( b , w ) = 1 + b 2 1 w ≤ 1 + 1 − b 2 1 w ≥ 1 + α . (5) \mathcal{L}(b,w)=\frac{1+b}{2}\mathbf{1}_{w\le1}+\frac{1-b}{2}\mathbf{1}_{w\ge1+\alpha}. \tag*{(5)} L ( b , w ) = 2 1 + b 1 w ≤ 1 + 2 1 − b 1 w ≥ 1 + α . (5)
The answers − 1 -1 − 1 and + 1 +1 + 1 correspond to the low and high regimes; intermediate values hedge between them. The gap 1 < w < 1 + α 1<w<1+\alpha 1 < w < 1 + α is unlabeled and incurs no loss. The use of Y = [ − 1 , 1 ] \mathcal{Y}=[-1,1] Y = [ − 1 , 1 ] facilitates averaging of randomized and changing discrete response rules.
Definition 3.1 (Signal distribution). Put ℓ = 10 α / c \ell=10\alpha/c ℓ = 10 α / c . The signal law W = W α , c W=W_{\alpha,c} W = W α , c is sampled as
w = 1 − ℓ + U 1 + U 2 , w=1-\ell+U_1+U_2, w = 1 − ℓ + U 1 + U 2 , U 1 ∼ Unif [ 0 , ℓ ] , U 2 ∼ Unif [ 0 , ℓ + α ] , U_1\sim\operatorname{Unif}[0,\ell],\qquad U_2\sim\operatorname{Unif}[0,\ell+\alpha], U 1 ∼ Unif [ 0 , ℓ ] , U 2 ∼ Unif [ 0 , ℓ + α ] , with U 1 , U 2 U_1,U_2 U 1 , U 2 independent.
Its density is trapezoidal: the two ramps occupy the labeled regimes, and the plateau occupies the unlabeled gap. Section E gives the density and explains its role in extracting correlation from accurate answers. We take c > 0 c>0 c > 0 to be a small absolute constant and 0 < α ≤ c / 20 0<\alpha\le c/20 0 < α ≤ c /20 , so the signal support stays at or above 1 / 2 1/2 1/2 .
From norm answers to signal-gap answers
The norm and the signal relate as follows:
∥ v ∥ 2 2 = w 2 + c 2 ∥ u ∥ 2 2 = w 2 + c 2 + c 2 ( ∥ u ∥ 2 2 − 1 ) . (6) \lVert v\rVert_2^2=w^2+c^2\lVert u\rVert_2^2=w^2+c^2+c^2\left(\lVert u\rVert_2^2-1\right). \tag*{(6)} ∥ v ∥ 2 2 = w 2 + c 2 ∥ u ∥ 2 2 = w 2 + c 2 + c 2 ( ∥ u ∥ 2 2 − 1 ) . (6)
Since E ∥ u ∥ 2 2 = tr Σ = 1 \mathbb{E}\lVert u\rVert_2^2=\operatorname{tr}\Sigma=1 E ∥ u ∥ 2 2 = tr Σ = 1 , concentration of the noise norm makes the squared query norm close to w 2 + c 2 w^2+c^2 w 2 + c 2 . We call a trace-one covariance norm-admissible at budget ρ \rho ρ when tr ( Σ 2 ) ≤ ρ \operatorname{tr}(\Sigma^2)\le\rho tr ( Σ 2 ) ≤ ρ .
For fixed c c c , we use a sufficiently small constant multiple of α 2 / c 4 \alpha^2/c^4 α 2 / c 4 as the admissibility budget. For binary norm-gap queries, fix the public thresholds
L = 1 + c 2 + α / 2 , U = 1 + c 2 + 3 α / 2 (7) L = \sqrt{1+c^2+\alpha/2}, \qquad U = \sqrt{1+c^2+3\alpha/2} \tag*{(7)} L = 1 + c 2 + α /2 , U = 1 + c 2 + 3 α /2 (7)
and use the returned bit as the signal-gap response. These thresholds have U / L = 1 + Θ ( α ) U/L = 1+\Theta(\alpha) U / L = 1 + Θ ( α ) . For norm estimates r ^ \hat{r} r ^ , use
b : = { + 1 , r ^ 2 ≥ 1 + c 2 + α , − 1 , otherwise , (8) b := \begin{cases}
+1, & \hat{r}^2 \ge1+c^2+\alpha,\\
-1, & \text{otherwise},
\end{cases} \tag*{(8)} b := { + 1 , − 1 , r ^ 2 ≥ 1 + c 2 + α , otherwise , (8)
In either case, the signal-gap loss is at most the error indicator for the chosen norm task plus the indicator of c 2 ∥ u ∥ 2 2 − 1 > α / 2 c^2\lVert u\rVert_2^2-1 > \alpha/2 c 2 ∥ u ∥ 2 2 − 1 > α /2 . Section B.6 proves this pointwise reduction and bounds the concentration-failure probability. Consequently, a round with large signal-gap loss also has many norm-task errors, except for these rare concentration failures. The attacker computes the signal-gap loss from its own w w w and the returned or thresholded answer.
Covariance constraints
For a cap parameter λ ∈ ( 1 / m , 1 / 2 ] \lambda\in(1/m,1/2] λ ∈ ( 1/ m , 1/2 ] , the attack keeps the covariance in
K λ : = { Σ : tr Σ = 1 , 1 − λ m − 1 I m ⪯ Σ } . (9) \mathcal{K}_{\lambda} := \left\{ \Sigma: \operatorname{tr}\Sigma= 1,\quad\frac{1-\lambda}{m-1}I_m \preceq\Sigma\right\}. \tag*{(9)} K λ := { Σ : tr Σ = 1 , m − 1 1 − λ I m ⪯ Σ } . (9)
The initial covariance Σ 0 = I m / m \Sigma_0 = I_m/m Σ 0 = I m / m belongs to K λ \mathcal{K}_{\lambda} K λ . The eigenvalue floor ensures invertibility and, together with tr Σ = 1 \operatorname{tr}\Sigma= 1 tr Σ = 1 , implies the cap
λ max ( Σ ) ≤ 1 − ( m − 1 ) 1 − λ m − 1 = λ . \lambda_{\max}(\Sigma) \le1-(m-1)\frac{1-\lambda}{m-1} = \lambda. λ m a x ( Σ ) ≤ 1 − ( m − 1 ) m − 1 1 − λ = λ .
The same constraints give
tr ( Σ 2 ) ≤ λ 2 + ( 1 − λ ) 2 m − 1 ≤ λ 2 + 1 m − 1 . (10) \operatorname{tr}(\Sigma^2) \le\lambda^2+\frac{(1-\lambda)^2}{m-1} \le\lambda^2+\frac{1}{m-1}. \tag*{(10)} tr ( Σ 2 ) ≤ λ 2 + m − 1 ( 1 − λ ) 2 ≤ λ 2 + m − 1 1 . (10)
This follows since concentrating all eigenvalue mass above the floor in one eigenvalue maximizes the sum of squares, giving one eigenvalue λ \lambda λ and the remaining m − 1 m-1 m − 1 eigenvalues equal to ( 1 − λ ) / ( m − 1 ) (1-\lambda)/(m-1) ( 1 − λ ) / ( m − 1 ) . Thus every Σ ∈ K λ \Sigma\in\mathcal{K}_{\lambda} Σ ∈ K λ is norm-admissible with budget ρ = λ 2 + 1 / ( m − 1 ) \rho= \lambda^2+1/(m-1) ρ = λ 2 + 1/ ( m − 1 ) . The parameter choices make this budget small enough for the norm reduction (Section B.1).
Covariance update
Let ( S t , E t ) = Round ( Σ t , r ) (S_t,E_t) = \operatorname{Round}(\Sigma_t,r) ( S t , E t ) = Round ( Σ t , r ) and R t = Σ t 1 / 2 R_t = \Sigma_t^{1/2} R t = Σ t 1/2 . If the round passes validation, the attacker forms
q ^ t = S t ∥ S t ∥ 2 , \hat{q}_t = \frac{S_t}{\lVert S_t\rVert_2}, q ^ t = ∥ S t ∥ 2 S t ,
a t = R t − T q ^ t , Z t = q 0 a t a t T , (11) a_t = R_t^{-\mathsf{T}}\hat{q}_t,\qquad Z_t = q_0 a_t a_t^{\mathsf{T}}, \tag*{(11)} a t = R t − T q ^ t , Z t = q 0 a t a t T , (11)
where q 0 = 1 − λ m − 1 q_0 = \frac{1-\lambda}{m-1} q 0 = m − 1 1 − λ .
If S t = 0 S_t=0 S t = 0 , choose any unit vector for q ^ t \hat{q}_t q ^ t . For positive definite trace-one matrices, define the relative entropy
D ( P ∥ Q ) = tr ( P ( log P − log Q ) ) . (12) D(P\mathbin{\|}Q) = \operatorname{tr}(P(\log P-\log Q)). \tag*{(12)} D ( P ∥ Q ) = tr ( P ( log P − log Q )) . (12)
Algorithm 1: Covariance attack
Input: norm task; cap λ \lambda λ ; round size r r r ; validation level δ 0 = 1 / 20 \delta_0 = 1/20 δ 0 = 1/20 ; round budget T max T_{\max} T m a x
Output: a rejected round and its covariance, or ⊥ \perp ⊥
Σ 0 ← I m / m \Sigma_0 \gets I_m/m Σ 0 ← I m / m ; q 0 ← ( 1 − λ ) / ( m − 1 ) q_0 \gets(1-\lambda)/(m-1) q 0 ← ( 1 − λ ) / ( m − 1 )
for t = 0 , … , T max − 1 t = 0,\ldots,T_{\max}-1 t = 0 , … , T m a x − 1 do
( S t , E t ) ← Round ( Σ t , r ) (S_t,E_t) \gets\operatorname{Round}(\Sigma_t,r) ( S t , E t ) ← Round ( Σ t , r )
if E t > r δ 0 / 2 E_t > r\delta_0/2 E t > r δ 0 /2 then // check round accuracy
return round t t t and Σ t \Sigma_t Σ t
q ^ t ← S t / ∥ S t ∥ 2 \widehat{q}_t \gets S_t/\lVert S_t\rVert_2 q t ← S t / ∥ S t ∥ 2 (any unit vector if S t = 0 S_t = 0 S t = 0 )
Form Z t Z_t Z t using (11) // rank-one measurement
Update Σ t + 1 \Sigma_{t+1} Σ t + 1 by (13)–(14) with η = 1 / 2 \eta= 1/2 η = 1/2
return ⊥ \perp ⊥
Procedure Round ( Σ , r ) \operatorname{Round}(\Sigma,r) Round ( Σ , r ) :
Announce D Σ D_\Sigma D Σ (§ 3.1 ) and round size r r r
R ← Σ 1 / 2 R \gets\Sigma^{1/2} R ← Σ 1/2 ; S ← 0 S \gets0 S ← 0 ; E ← 0 E \gets0 E ← 0
for j = 1 , … , r j = 1,\ldots,r j = 1 , … , r do // queries
Draw w j ∼ W α , c w_j \sim W_{\alpha,c} w j ∼ W α , c , z j ∼ N ( 0 , I m ) z_j \sim\mathcal{N}(0,I_m) z j ∼ N ( 0 , I m )
Query v j = w j e h + c ι M R z j v_j = w_j e_h + c\,\iota_M Rz_j v j = w j e h + c ι M R z j // v j ∼ D Σ v_j \sim D_\Sigma v j ∼ D Σ (§ 3.1 )
Obtain b j b_j b j // signal-gap answer b j b_j b j from norm task response (§ 3.3 )
S ← S + b j z j S \gets S + b_jz_j S ← S + b j z j // accumulate signed noise
E ← E + L ( b j , w j ) E \gets E + L(b_j,w_j) E ← E + L ( b j , w j ) // accumulate signal-gap loss (5)
return ( S , E ) (S,E) ( S , E )
We use a matrix multiplicative-weights update [5 , 59 ] with step size η = 1 / 2 \eta= 1/2 η = 1/2 , followed by a relative-entropy projection:
Σ ^ t + 1 = exp ( log Σ t + η Z t ) tr exp ( log Σ t + η Z t ) (13) \widehat{\Sigma}_{t+1} =
\frac{\exp(\log\Sigma_t + \eta Z_t)}
{\operatorname{tr}\exp(\log\Sigma_t + \eta Z_t)} \tag*{(13)} Σ t + 1 = tr exp ( log Σ t + η Z t ) exp ( log Σ t + η Z t ) (13)
Σ t + 1 = argmin Σ ′ ∈ K λ D ( Σ ′ ∥ Σ ^ t + 1 ) . (14) \Sigma_{t+1} = \underset{\Sigma' \in\mathcal{K}_\lambda}{\operatorname{argmin}}\,
D(\Sigma' \mathbin{\|} \widehat{\Sigma}_{t+1}). \tag*{(14)} Σ t + 1 = Σ ′ ∈ K λ argmin D ( Σ ′ ∥ Σ t + 1 ) . (14)
The exponential step (13) increases weight according to Z t Z_t Z t . The projection (14) ensures that the covariance remains in K λ \mathcal{K}_\lambda K λ . The projection is computed by rescaling the eigenvalues of Σ ^ t + 1 \widehat{\Sigma}_{t+1} Σ t + 1 and clipping them from below at q 0 q_0 q 0 , with the scale chosen so that they sum to one (Section G.1).
Analysis preview
We show that, with high constant probability, some round must fail validation before the round budget is exhausted.
We first express the signal-estimation variance in terms of the query covariance Σ \Sigma Σ . We then show that successful initialization guarantees the existence of a hard comparator covariance Σ ⋆ \Sigma_\star Σ ⋆ . We measure progress by the relative entropy D ( Σ ⋆ ∥ Σ t ) D(\Sigma_\star\mathbin{\|}\Sigma_t) D ( Σ ⋆ ∥ Σ t ) between this comparator and the current covariance. Accurate rounds produce sufficiently many potential-decreasing updates. Its bounded initial value and nonnegativity, together with a concentration argument, bound the number of rounds that can pass validation.
The scalar channel
Recall that the sketch has the form y = w A h + c A M u y = wA_h + cA_Mu y = w A h + c A M u , where u ∼ N ( 0 , Σ ) u \sim\mathcal{N}(0,\Sigma) u ∼ N ( 0 , Σ ) is independent of w w w . Put
K Σ = A M Σ A M T . (15) K_\Sigma= A_M\Sigma A_M^{\mathsf{T}}. \tag*{(15)} K Σ = A M Σ A M T . (15)
Suppose A h ∈ im ( K Σ ) ∖ { 0 } A_h \in\operatorname{im}(K_\Sigma) \setminus\{0\} A h ∈ im ( K Σ ) ∖ { 0 } . Define the normalized signal-estimation variance and the scalar statistic by
V ( Σ ) = ( A h T K Σ † A h ) − 1 , T Σ ( y ) = V ( Σ ) A h T K Σ † y , (16) \mathcal{V}(\Sigma) = (A_h^{\mathsf{T}} K_\Sigma^{\dagger} A_h)^{-1},
\qquad
T_\Sigma(y) = \mathcal{V}(\Sigma) A_h^{\mathsf{T}} K_\Sigma^{\dagger} y, \tag*{(16)} V ( Σ ) = ( A h T K Σ † A h ) − 1 , T Σ ( y ) = V ( Σ ) A h T K Σ † y , (16)
where † \dagger † denotes the Moore–Penrose pseudoinverse. The statistic is sufficient for w w w : conditional on T Σ ( y ) T_\Sigma(y) T Σ ( y ) , the remaining sketch contains no additional information about the signal. Moreover,
T Σ ( y ) = w + X , X ∼ N ( 0 , c 2 V ( Σ ) ) , (17) T_\Sigma(y) = w + X,\qquad X \sim N(0,c^2\mathcal{V}(\Sigma)), \tag*{(17)} T Σ ( y ) = w + X , X ∼ N ( 0 , c 2 V ( Σ )) , (17)
with X X X independent of w w w . Thus c 2 V ( Σ ) c^2\mathcal{V}(\Sigma) c 2 V ( Σ ) is the actual signal-estimation variance, and a larger value makes the two signal regimes harder to distinguish. In particular, if c 2 V ( Σ ) ≥ α 2 c^2\mathcal{V}(\Sigma) \ge\alpha^2 c 2 V ( Σ ) ≥ α 2 , every responder incurs a constant expected signal-gap loss (Lemma F.2 ) and the distribution is universally hard for the signal-gap task.
If A h = 0 A_h = 0 A h = 0 , then the sketch is independent of w w w and V ( Σ ) = + ∞ \mathcal{V}(\Sigma) = +\infty V ( Σ ) = + ∞ . If A h ∉ im ( K Σ ) A_h \notin\operatorname{im}(K_\Sigma) A h ∈ / im ( K Σ ) , then the sketch contains a noiseless signal component and V ( Σ ) = 0 \mathcal{V}(\Sigma) = 0 V ( Σ ) = 0 .
Successful initialization
With high constant probability, random-coordinate initialization (§ 3.1 ) gives either A h = 0 A_h = 0 A h = 0 , in which case the sketch carries no signal information and the isotropic query distribution is already hard for the signal-gap task, or A h ∈ im ( A M ) ∖ { 0 } A_h \in\operatorname{im}(A_M) \setminus\{0\} A h ∈ im ( A M ) ∖ { 0 } and V ( I m / m ) ≥ 1 / ( 40 k ) \mathcal{V}(I_m/m) \ge1/(40k) V ( I m / m ) ≥ 1/ ( 40 k ) (Corollary B.2).
Existence of a hard comparator
We measure progress relative to a fixed comparator covariance Σ ⋆ ∈ K λ \Sigma_\star\in\mathcal{K}_\lambda Σ ⋆ ∈ K λ , constructed in the analysis using the hidden matrix A A A . It has eigenvalue λ \lambda λ along a suitable hidden direction and eigenvalue q 0 q_0 q 0 in every orthogonal direction. This covariance spike amplifies the isotropic variance by m λ = Θ ( α 2 k ) m\lambda= \Theta(\alpha^2 k) mλ = Θ ( α 2 k ) :
V ( Σ ⋆ ) = m λ V ( I m / m ) . \mathcal{V}(\Sigma_\star) = m\lambda\mathcal{V}(I_m/m). V ( Σ ⋆ ) = mλ V ( I m / m ) .
Together with the initialization bound, a sufficiently large constant in λ = Θ ( α 2 ) \lambda= \Theta(\alpha^2) λ = Θ ( α 2 ) makes c 2 V ( Σ ⋆ ) c^2\mathcal{V}(\Sigma_\star) c 2 V ( Σ ⋆ ) a sufficiently large multiple of α 2 \alpha^2 α 2 , so the comparator is universally hard for the signal-gap task. It is also norm-admissible because it belongs to K λ \mathcal{K}_\lambda K λ (Equation (10) and Section B.1).
Accuracy forces correlation
An accurate response must correlate with the signal-estimation error T Σ ( y ) − w T_\Sigma(y) - w T Σ ( y ) − w . The following lemma extends the isotropic gain bound of [2 Lemma 4.9] to general covariances; its proof appears in Section E. Write L Σ ( ψ ) = E [ L ( ψ ( y ) , w ) ] L_\Sigma(\psi) = \mathbb{E}[L(\psi(y),w)] L Σ ( ψ ) = E [ L ( ψ ( y ) , w )] for the expected signal-gap loss under D Σ D_\Sigma D Σ .
Lemma 4.1 (General-covariance gain lemma). Let α > 0 \alpha> 0 α > 0 , 0 < c ≤ 1 0 < c \le1 0 < c ≤ 1 , δ 0 = 1 / 20 \delta_0 = 1/20 δ 0 = 1/20 , and c g = 1 / 22 c_g = 1/22 c g = 1/22 . For the query law D Σ D_\Sigma D Σ with signal law W α , c W_{\alpha,c} W α , c , let Σ ⪰ 0 \Sigma\succeq0 Σ ⪰ 0 satisfy tr Σ = 1 \operatorname{tr}\Sigma= 1 tr Σ = 1 and 0 < V ( Σ ) < ∞ 0 < \mathcal{V}(\Sigma) < \infty 0 < V ( Σ ) < ∞ . Every measurable response rule ψ : R k → [ − 1 , 1 ] \psi: \mathbb{R}^k \to[-1,1] ψ : R k → [ − 1 , 1 ] with L Σ ( ψ ) ≤ δ 0 L_\Sigma(\psi) \le\delta_0 L Σ ( ψ ) ≤ δ 0 satisfies
E [ ψ ( y ) ( T Σ ( y ) − w ) ] ≥ c V ( Σ ) g , (18) \mathbb{E}[\psi(y)(T_\Sigma(y)-w)] \ge c\mathcal{V}(\Sigma)g, \tag*{(18)} E [ ψ ( y ) ( T Σ ( y ) − w )] ≥ c V ( Σ ) g , (18) g : = c g c 2 α . g := c_g \frac{c^2}{\alpha}. g := c g α c 2 .
Since the estimation error is a linear function of the generated Gaussian noise, the gain bound guarantees a useful component of the mean signed noise along the hidden signal-estimation direction. The attacker accumulates this correlation through S t = ∑ j b j z j S_t = \sum_j b_j z_j S t = ∑ j b j z j .
If the conditional expected losses are small on average over the round, the useful component accumulates linearly with the number of queries, while concentration controls the sampling fluctuations. This remains true when the responder changes its rule after every query: we analyze each contribution conditional on the preceding history. Other components of the mean signed noise may also accumulate, so S t S_t S t need not approximate the hidden direction. The next step shows that it nevertheless yields a separating measurement.
Correlation yields separating measurements
The rank-one measurement Z t Z_t Z t computed in (11) always satisfies
0 ⪯ Z t ⪯ I m , ⟨ Σ t , Z t ⟩ = q 0 , 0 \preceq Z_t \preceq I_m,\qquad\langle\Sigma_t,Z_t\rangle= q_0, 0 ⪯ Z t ⪯ I m , ⟨ Σ t , Z t ⟩ = q 0 ,
where ⟨ P , Q ⟩ = tr ( P Q ) \langle P,Q\rangle= \operatorname{tr}(PQ) ⟨ P , Q ⟩ = tr ( P Q ) . We show that, conditional on the history before the round, with probability bounded below by an absolute constant, either validation rejects the round or
⟨ Σ ⋆ , Z t ⟩ ≥ κ q 0 \langle\Sigma_\star,Z_t\rangle\ge\kappa q_0 ⟨ Σ ⋆ , Z t ⟩ ≥ κ q 0
for a sufficiently large absolute constant κ \kappa κ . Since Z t = q 0 a t a t T Z_t = q_0 a_t a_t^\mathsf{T} Z t = q 0 a t a t T , this means that the comparator assigns at least κ \kappa κ times as much noise variance as the current covariance along the direction a t a_t a t .
On a high-probability validation event, passing the test implies small average conditional loss, so the correlation guarantee from the preceding subsection applies. A geometric bound converts the useful component of the accumulated mean signed noise into separation from the comparator, even when other components are large. With r = Θ ( k ) r = \Theta(k) r = Θ ( k ) queries, martingale bounds ensure that sampling fluctuations preserve this separation with constant probability. Thus the observed sum S t S_t S t supplies the measurement needed for the covariance update (Section B.4).
Entropy bounds the number of rounds
The potential D ( Σ ⋆ ∥ Σ t ) D(\Sigma_\star\Vert\Sigma_t) D ( Σ ⋆ ∥ Σ t ) is nonnegative and initially at most λ log ( m λ ) \lambda\log(m\lambda) λ log ( mλ ) . After an accepted round, a separating measurement makes the covariance update decrease this potential by a sufficiently large constant multiple of q 0 q_0 q 0 . Any other update can increase it by at most a smaller constant multiple of q 0 q_0 q 0 .
The preceding separation guarantee, together with a concentration bound, implies that with high constant probability, if all rounds passed validation, a constant fraction of their measurements would be separating. The constants ensure that their decreases outweigh the possible increases from the remaining updates, giving a total decrease of Ω ( T q 0 ) \Omega(Tq_0) Ω ( T q 0 ) over T T T rounds. Since the potential cannot become negative, this rules out more than
O ( 1 + λ q 0 log ( m λ ) ) = O ( 1 + α 2 k log ( 2 + α 2 k ) ) O\left(1+\frac{\lambda}{q_0}\log(m\lambda)\right) = O\left(1+\alpha^2 k\log(2+\alpha^2 k)\right) O ( 1 + q 0 λ log ( mλ ) ) = O ( 1 + α 2 k log ( 2 + α 2 k ) )
accepted rounds. Thus some round must fail validation within the stated round budget (Section B.5).
Note that this argument requires cumulative progress in relative entropy. The signal-estimation variance may still decrease on individual updates, and the attack need not reach the comparator.
Sufficient-statistic attack
We define the sufficient-statistic responder class using T Σ T_{\Sigma} T Σ from § 4.1 . As in the general analysis, consider a successful initialization with A h ∈ im ( A M ) ∖ { 0 } A_h \in\operatorname{im}(A_M) \setminus\{0\} A h ∈ im ( A M ) ∖ { 0 } and a positive definite covariance. In the zero-signal case, the isotropic query distribution is already hard for the signal-gap task, without any restriction on the responder.
Let H j − 1 \mathcal{H}_{j-1} H j − 1 denote the disclosed information before query j j j of round t t t , including the current query law but excluding the responder’s private execution. The averaged response rule is
ψ ‾ t , j ( y ) = E [ ψ t , j ( y ) ∣ H j − 1 ] , \overline{\psi}_{t,j}(y) = \mathbb{E}[\psi_{t,j}(y) \mid\mathcal{H}_{j-1}], ψ t , j ( y ) = E [ ψ t , j ( y ) ∣ H j − 1 ] ,
where the expectation averages over private responder state and randomization. The conditioning is formalized in Section B.3.2.
Definition 5.1 (Sufficient-statistic responder). The responder is sufficient-statistic if, in every round t t t and query j j j ,
ψ ‾ t , j ( y ) = φ t , j ( T Σ t ( y ) ) \overline{\psi}_{t,j}(y) = \varphi_{t,j}\left(T_{\Sigma_t}(y)\right) ψ t , j ( y ) = φ t , j ( T Σ t ( y ) ) for an H j − 1 \mathcal{H}_{j-1} H j − 1 -measurable function φ t , j : R → [ − 1 , 1 ] \varphi_{t,j} : \mathbb{R} \to[-1,1] φ t , j : R → [ − 1 , 1 ] , almost surely under the current sketch law. The responder may change its randomized rule after every query; only the dependence of its conditional mean on the current sketch is restricted.
For norm estimation, this condition applies to the thresholded answer in (8) . For the binary norm-gap task, it applies to the returned bit.
The class includes the Bayes-optimal signal-gap predictor (Proposition F.1 ) and any responder that computes its answer from T Σ T_{\Sigma} T Σ and fresh randomness.
The attack
The attack, described in Algorithm 2, uses the same query family and signal-gap validation test as Algorithm 1, starting at Σ 0 = I m / m \Sigma_0 = I_m/m Σ 0 = I m / m . For α ∈ [ C min / k , α 0 ] \alpha\in[C_{\min}/\sqrt{k},\alpha_0] α ∈ [ C m i n / k , α 0 ] , the attack uses an eigenvalue stopping threshold ρ ˉ \bar{\rho} ρ ˉ . It uses at most T max T_{\max} T m a x covariance-update rounds, followed by one final validation round when the top eigenvalue reaches or exceeds this threshold. The parameters have scales
ρ ˉ = Θ ( α 2 ) , T max = O ( log ( 2 + α 2 k ) ) , \bar{\rho} = \Theta(\alpha^2), \qquad T_{\max} = O\left(\log(2+\alpha^2 k)\right), ρ ˉ = Θ ( α 2 ) , T m a x = O ( log ( 2 + α 2 k ) ) ,
r t = Θ ( k + α 2 k 2 ϑ t ) ( 0 ≤ t < T max ) , r f i n = Θ ( k ) , r_t = \Theta\left(k+\alpha^2 k^2\vartheta^t\right)\quad(0 \le t < T_{\max}), \qquad r_{\mathrm{fin}} = \Theta(k), r t = Θ ( k + α 2 k 2 ϑ t ) ( 0 ≤ t < T m a x ) , r fin = Θ ( k ) ,
where ϑ ∈ ( 0 , 1 ) \vartheta\in(0,1) ϑ ∈ ( 0 , 1 ) is a fixed absolute constant. The first round uses Θ ( k + α 2 k 2 ) \Theta(k+\alpha^2 k^2) Θ ( k + α 2 k 2 ) queries; the geometrically decreasing term allows smaller later rounds, while every round retains Ω ( k ) \Omega(k) Ω ( k ) queries. The total query budget is
∑ t = 0 T max − 1 r t + r f i n = O ( k + α 2 k 2 ) . \sum_{t=0}^{T_{\max}-1} r_t + r_{\mathrm{fin}} = O(k+\alpha^2 k^2). t = 0 ∑ T m a x − 1 r t + r fin = O ( k + α 2 k 2 ) .
The precise schedule is given in (65) , with its norm-task specialization in Section C.1.
The rounds are as in Algorithm 1, with ( S t , E t ) = Round ( Σ t , r t ) (S_t,E_t)=\operatorname{Round}(\Sigma_t,r_t) ( S t , E t ) = Round ( Σ t , r t ) at round t t t . If E t > r t δ 0 / 2 E_t > r_t\delta_0/2 E t > r t δ 0 /2 , the attack returns the round. Otherwise it normalizes the signed sum to h ^ t = S t / ∥ S t ∥ 2 \widehat{h}_t = S_t/\lVert S_t\rVert_2 h t = S t / ∥ S t ∥ 2 and updates the covariance by
N ( Σ , h ^ ) = Σ + p p T 1 + ∥ p ∥ 2 2 , p = Σ 1 / 2 h ^ . (19) \mathcal{N}(\Sigma,\widehat{h}) = \frac{\Sigma+ pp^{\mathsf{T}}}{1+\lVert p\rVert_2^2}, \qquad p = \Sigma^{1/2}\widehat{h}. \tag*{(19)} N ( Σ , h ) = 1 + ∥ p ∥ 2 2 Σ + p p T , p = Σ 1/2 h . (19)
If S t = 0 S_t=0 S t = 0 , any unit vector may be used for h ^ t \widehat{h}_t h t . The vector h ^ t \widehat{h}_t h t is a direction in whitened coordinates; p p p maps it back to the noise coordinates. The rank-one addition increases noise along p p p before the Algorithm 2: Sufficient-statistic attack
Input: norm task; threshold ρ ˉ \bar{\rho} ρ ˉ ; round lengths r 0 , … , r T max − 1 , r f i n r_0,\ldots,r_{T_{\max}-1},r_{\mathrm{fin}} r 0 , … , r T m a x − 1 , r fin ; validation level δ 0 = 1 / 20 \delta_0 = 1/20 δ 0 = 1/20
Output: a rejected round and its covariance, or ⊥ \perp ⊥
Σ 0 ← I m / m \Sigma_0 \leftarrow I_m/m Σ 0 ← I m / m
for t = 0 , … , T max − 1 t = 0,\ldots,T_{\max}-1 t = 0 , … , T m a x − 1 do
( S t , E t ) ← Round ( Σ t , r t ) \left(S_t,E_t\right) \leftarrow\operatorname{Round}(\Sigma_t,r_t) ( S t , E t ) ← Round ( Σ t , r t ) // in Algorithm 1
if E t > r t δ 0 / 2 E_t > r_t\delta_0/2 E t > r t δ 0 /2 then
return round t t t and Σ t \Sigma_t Σ t
h ^ t ← S t / ∥ S t ∥ 2 \hat{h}_t \leftarrow S_t/\lVert S_t\rVert_2 h ^ t ← S t / ∥ S t ∥ 2 (any unit vector if S t = 0 S_t = 0 S t = 0 )
Σ t + 1 ← N ( Σ t , h ^ t ) \Sigma_{t+1} \leftarrow\mathcal{N}(\Sigma_t,\hat{h}_t) Σ t + 1 ← N ( Σ t , h ^ t ) // see (19)
if λ max ( Σ t + 1 ) ≥ ρ ˉ \lambda_{\max}(\Sigma_{t+1}) \ge\bar{\rho} λ m a x ( Σ t + 1 ) ≥ ρ ˉ then // threshold reached
Σ o u t ← Σ t + 1 \Sigma_{\mathrm{out}} \leftarrow\Sigma_{t+1} Σ out ← Σ t + 1
( S , E ) ← Round ( Σ o u t , r f i n ) (S,E) \leftarrow\operatorname{Round}(\Sigma_{\mathrm{out}},r_{\mathrm{fin}}) ( S , E ) ← Round ( Σ out , r fin ) // in Algorithm 1
if E > r f i n δ 0 / 2 E > r_{\mathrm{fin}}\delta_0/2 E > r fin δ 0 /2 then
return the final round and Σ o u t \Sigma_{\mathrm{out}} Σ out
return ⊥ \perp ⊥
return ⊥ \perp ⊥
denominator renormalizes the covariance to trace one. The update preserves positive definiteness and trace one.
After each update, the algorithm checks whether the largest eigenvalue has reached the fixed threshold ρ ˉ ∈ ( 1 / m , 1 / 2 ] \bar{\rho} \in(1/m,1/2] ρ ˉ ∈ ( 1/ m , 1/2 ] . Initially, Σ 0 = I m / m \Sigma_0 = I_m/m Σ 0 = I m / m , so λ max ( Σ 0 ) = 1 / m < ρ ˉ \lambda_{\max}(\Sigma_0) = 1/m < \bar{\rho} λ m a x ( Σ 0 ) = 1/ m < ρ ˉ . Each update satisfies λ max ( Σ t + 1 ) ≤ 2 λ max ( Σ t ) \lambda_{\max}(\Sigma_{t+1}) \le2\lambda_{\max}(\Sigma_t) λ m a x ( Σ t + 1 ) ≤ 2 λ m a x ( Σ t ) : the rank-one addition can at most double the largest eigenvalue, and trace normalization can only reduce it. When an update first reaches the threshold, the attack stops updating and runs one final validation round at the resulting covariance Σ o u t \Sigma_{\mathrm{out}} Σ out . Since the preceding covariance was below the threshold,
ρ ˉ ≤ λ max ( Σ o u t ) < 2 ρ ˉ . (20) \bar{\rho} \le\lambda_{\max}(\Sigma_{\mathrm{out}}) < 2\bar{\rho}. \tag*{(20)} ρ ˉ ≤ λ m a x ( Σ out ) < 2 ρ ˉ . (20)
Guarantee and analysis preview
With probability at least 0.9, the attack returns a round containing a constant fraction of errors for the original norm task, as claimed in Theorem 1.2 . On the same success event, if the eigenvalue threshold is reached, the final distribution is hard for every responder for that norm task.
Alignment permits direction estimation. For a sufficient-statistic responder, the conditional mean signed noise is parallel to the signal-estimation direction. Gaussian noise orthogonal to this direction is independent of the statistic, so its correlation with the answer vanishes. Combining this alignment with the gain lemma, validation, and concentration shows that normalizing S t S_t S t estimates the direction accurately enough for the covariance update (Section C.2).
Variance growth justifies the stopping test. On the success event, each covariance update increases V ( Σ t ) \mathcal{V}(\Sigma_t) V ( Σ t ) by a fixed factor greater than one. Controlling the accumulated direction-estimation errors also keeps the variance within a constant factor of the largest possible at the current top eigenvalue:
V ( Σ t ) = Θ ( m λ max ( Σ t ) V ( I m / m ) ) . \mathcal{V}(\Sigma_t) = \Theta\left(m\lambda_{\max}(\Sigma_t)\mathcal{V}(I_m/m)\right). V ( Σ t ) = Θ ( m λ m a x ( Σ t ) V ( I m / m ) ) .
Before the threshold is reached, the upper bound limits variance amplification to O ( m ρ ˉ ) O(m\bar{\rho}) O ( m ρ ˉ ) , allowing only O ( log ( 2 + α 2 k ) ) O(\log(2+\alpha^2 k)) O ( log ( 2 + α 2 k )) accepted updates. At the threshold, the lower bound ensures that the variance is large enough for universal signal-gap hardness. Thus the observable eigenvalue test certifies hardness even though the attacker cannot compute the signal-estimation variance (Section C.3).
Query cost and norm admissibility. As the variance grows, the gain lemma guarantees a stronger correlation, so fewer queries suffice to estimate the direction. The resulting round schedule has total cost O ( k + α 2 k 2 ) O(k + \alpha^{2}k^{2}) O ( k + α 2 k 2 ) , with the direction-estimation cost dominated by the early rounds. Control of the accumulated direction errors also gives
tr ( Σ t 2 ) ≤ 1 / m + O ( ρ ˉ 2 ) \operatorname{tr}(\Sigma_t^{2}) \le1/m + O(\bar{\rho}^{2}) tr ( Σ t 2 ) ≤ 1/ m + O ( ρ ˉ 2 )
throughout the successful execution, including the covariance that crosses the threshold. This maintains the norm admissibility needed for the norm-task guarantees (Section C.1). Section C gives the full proof and an extension to approximate alignment.
Conclusion
At constant accuracy, we establish a near-quadratic limit on adaptive reuse of any fixed linear norm sketch, even with an informed responder that changes its rule after every query. The vulnerability that the attack exploits is that accurate answers expose useful correlations. We also present more efficient attacks for sufficient-statistic responses, which have aligned mean signed noise.
Our lower bound makes the accuracy dependence tight within a broad family of announced query distributions, using a responder that is given the signal direction and noise mean and covariance. The main open question is where the optimal adaptive-query guarantee lies between α 4 k 2 \alpha^{4}k^{2} α 4 k 2 and α 2 k 2 \alpha^{2}k^{2} α 2 k 2 , up to logarithmic factors, when query distributions are unrestricted or the responder lacks distributional information. A further question is whether the logarithmic gap between our query bounds for general and sufficient-statistic responders is necessary. Section A gives context and discusses implications for defenses.
Acknowledgments
Edith Cohen: Partially supported by the Israel Science Foundation (grant 1156/23).
Uri Stemmer: Partially supported by the Israel Science Foundation (grant 1419/24), and the Blavatnik Research Foundation.
AI use statement
This paper was developed from an initial proof sketch by the authors, through many iterations with the help of ChatGPT, Claude, and Gemini. The tools were used for formalizing statements, writing proofs and text, improving proofs and bounds, and looking up relevant literature. The authors are responsible for the content.
Related work and discussion
Related work
Adaptive inputs and robustness. Classical guarantees for randomized algorithms and structures often assume that inputs are independent of the algorithm’s random choices. This assumption can fail when outputs influence subsequent inputs, whether through an adversarial attack or ordinary use within a larger computation. Repeated interaction may reveal enough about the hidden randomness to identify inputs on which the algorithm fails.
This issue has been studied across statistics and adaptive data analysis [9 , 27 , 30 , 39 , 46 , 50 , 55 ] , randomized online and dynamic algorithms [3 , 10 , 11 , 22 , 28 , 31 , 37 , 60 ] , sketching and streaming [7 , 12 , 13 , 40 , 41 , 51 , 62 ] , and machine learning [6 , 32 , 53 , 54 , 56 ] . Sketching provides a clean setting for quantifying how much interaction is needed to compromise a fixed randomized representation.
Defenses and the quadratic guarantee. A simple defense uses independent copies of a randomized structure, answering each query with a fresh copy. This supports a number of adaptive queries roughly linear in the number of copies. Methods developed in adaptive data analysis improve this guarantee to quadratic by limiting what the answers reveal about the reused randomness [9 , 14 , 27 , 41 ] .
For JL or AMS sketches of total dimension k k k , these methods support Ω ~ ( α 4 k 2 ) \widetilde{\Omega}(\alpha^4 k^2) Ω ( α 4 k 2 ) adaptive queries. Each independent copy uses Θ ( α − 2 ) \Theta(\alpha^{-2}) Θ ( α − 2 ) measurements, leaving Θ ( α 2 k ) \Theta(\alpha^2 k) Θ ( α 2 k ) copies for quadratic reuse. The methods use a fixed randomized response rule with fresh randomness suffices.
Quadratic vulnerabilities of sketches. Attacks on sketches differ in the structures they cover, the responders they allow, and the failures they produce [12 , 18 , 19 , 33 , 34 , 40 ] . An attack on a standard estimator may be much cheaper than on one designed to obscure internal parameters.
A line of work establishes quadratic-query vulnerabilities for AMS and CountSketch, MinHash cardinality sketches, monotone composable and linear cardinality sketches, and general linear sketches for norm estimation [1 , 2 , 20 , 24 ] . These results show that the quadratic guarantee is often a barrier, even when the responder can choose how to use the sketch. Our work establishes this vulnerability for Euclidean-norm estimation, for any linear sketch and with unrestricted responders. § 1.3 and Table 1 give the detailed comparison with the closest prior attacks.
Beyond the quadratic barrier. Stronger guarantees are possible when the representation or the allowed interactions change. Recent algorithms for insertion–deletion and resettable streams obtain stronger robustness by maintaining and refreshing representations as the stream evolves [23 , 35 , 36 ] . They process individual stream updates and maintain state tied to the execution of a single stream. These guarantees do not provide a common fixed, composable representation for independently maintained inputs. A different approach retains a fixed cardinality sketch but limits how often each element participates in the queries: the quadratic restriction then applies to each element’s participation rather than to the total number of queries [21 ] . These results highlight the importance of both the representation and the way it is reused.
Implications for prediction and defenses
Connections to adversarial prediction. A predictor can be accurate on independently drawn inputs while interaction with its outputs helps locate failures. This gap has motivated extensive empirical and theoretical work on adversarial examples [8 , 15 , 16 , 26 , 29 , 45 , 52 , 57 , 58 ] . Our attacks share a simple mechanism with black-box attacks on learned models: responses are used to weight sampled perturbations, and their average identifies directions useful to the attack [17 , 44 , 54 ] . The sketching setting lets us quantify this mechanism and the extent to which a responder can delay it.
Accuracy and disclosure. More accurate answers enable cheaper attacks, reaching O ( k ) O(k) O ( k ) queries at α = Θ ( k − 1 / 2 ) \alpha= \Theta(k^{-1/2}) α = Θ ( k − 1/2 ) . Our lower bound also shows a benefit of deliberately limiting response precision. The added noise masks the matrix-dependent estimation error while preserving the required accuracy. Randomization also provides provable protection against bounded input perturbations in learned predictors [25 , 48 ] , making its role in controlling adaptive disclosure a useful direction for further study.
Learning after a fixed compression. Consider a predictor built on a compressive linear layer, as used in neural architectures [42 ] . Suppose the compression remains fixed while the downstream predictor is repeatedly fitted to the current input distribution. This is an idealized setting for adaptation through limited trainable components, including LoRA when applied downstream of the fixed compression [43 ] .
For our Gaussian query family, the Bayes-optimal signal-gap predictor depends only on the scalar statistic T Σ T_{\Sigma} T Σ (Proposition F.1 ). This motivates sufficient-statistic responders as a model of prediction fitted to each distribution. Postprocessing that uses only this prediction and fresh randomness, including noise, rounding, or clipping, preserves the restriction. The more efficient attack therefore applies to these output defenses.
The interaction can be viewed as a search for a distribution on which the fixed representation loses essential information. Accurate predictions guide this search, even as the predictor is adapted to each new distribution. If the responder remains sufficiently accurate whenever a stricter constant tolerance is feasible, the returned distribution is universally hard (Remark B.18). For the sufficient-statistic attack, reaching the eigenvalue threshold also certifies this hardness.
Responses and representations. Our results suggest two complementary approaches to robustness when a fixed compressive component forms an information bottleneck in a larger model. One is to limit what the responses reveal about that component. Fresh output noise can mask information useful to the attacker; dependence on additional sketch information may introduce “decoy” correlations that obscure the useful direction. Our results quantify a benefit of the former and leave open how much additional protection the latter can provide.
Another approach is to periodically replace the compressive component while preserving predictive accuracy on the intended input distribution. Changing which information the representation retains could make directions learned from earlier responses less useful to the attacker. This suggests studying defenses that refresh the representation itself, alongside defenses that modify the responses produced from a fixed representation.
Open problems
Accuracy and distributional information. Our attacks use O ~ ( k + α 2 k 2 ) \widetilde{O}(k + \alpha^{2}k^{2}) O ( k + α 2 k 2 ) queries. For signal–noise attacks with sufficiently concentrated noise energy, we show that a responder given the noise mean and covariance can withstand Ω ( α 2 k 2 ) \Omega(\alpha^{2}k^{2}) Ω ( α 2 k 2 ) queries. Known defenses without distributional information guarantee Ω ~ ( α 4 k 2 ) \widetilde{\Omega}(\alpha^{4}k^{2}) Ω ( α 4 k 2 ) queries. How much of this gap can be closed for unrestricted query distributions, or without distributional information?
More efficient general attacks. Our sufficient-statistic attack saves a logarithmic factor in queries and uses less memory and computation than our general attack. Can general attacks match its query bound and achieve comparable or better memory and computational costs? General responders can use sketch information irrelevant to signal prediction to create correlations that obscure the useful direction. Do these correlations inherently increase the cost of attack?
The gap in adaptive rounds is necessary: at constant accuracy, general responders can require Ω ~ ( k ) \widetilde{\Omega}(k) Ω ( k ) rounds for attacks using polynomially many queries (§ 1.3 ).
Attacks on learned responders. When does fitting a signal-gap predictor to each query distribution, while keeping the compression fixed, leave it vulnerable to the more efficient attack? In particular, how does excess prediction risk control response correlations orthogonal to the signal-estimation direction, and when does this imply the approximate alignment required in Remark C.7 ?
Other tasks. Can attacks with similarly sharp query bounds be obtained for other tasks, such as estimating other ℓ p \ell_p ℓ p norms? More broadly, can response correlations guide attacks that expose information lost by nonlinear representations?
Analysis of the general attack
We prove Theorem 1.1 , then establish the supporting results used in the proof.
Parameters and proof of Theorem 1.1
Parameter choice. The following parameter choices suffice for the covariance-update regime; we make no attempt to optimize the constants. Fix a small absolute constant 0 < c ≤ 1 0 < c \le1 0 < c ≤ 1 and set δ = 0.04 \delta= 0.04 δ = 0.04 . Use ε n c = δ 0 / 8 \varepsilon_{\mathrm{nc}} = \delta_0/8 ε nc = δ 0 /8 and c ρ = ε n c / 8 = δ 0 / 64 c_\rho= \varepsilon_{\mathrm{nc}}/8 = \delta_0/64 c ρ = ε nc /8 = δ 0 /64 in the norm reduction of Lemma B.15 . Choose c e r r ≤ 1 / 16 c_{\mathrm{err}} \le1/16 c err ≤ 1/16 small enough for that lemma. Choose any prescribed set S ⊆ [ n ] S \subseteq[n] S ⊆ [ n ] of m + 1 = 40 k + 1 m + 1 = 40k + 1 m + 1 = 40 k + 1 coordinates, choose h h h uniformly from S S S , and put M = S ∖ { h } M = S \setminus\{h\} M = S ∖ { h } .
Set
C λ = C m a r g c g 2 c 4 , C m a r g = 256 , λ = C λ α 2 , q 0 = 1 − λ m − 1 . C_\lambda= \frac{C_{\mathrm{marg}}}{c_g^2 c^4}, \qquad C_{\mathrm{marg}} = 256, \qquad\lambda= C_\lambda\alpha^2, \qquad q_0 = \frac{1-\lambda}{m-1}. C λ = c g 2 c 4 C marg , C marg = 256 , λ = C λ α 2 , q 0 = m − 1 1 − λ .
The constant C m a r g C_{\mathrm{marg}} C marg is the separation margin established in Section B.4. Choose absolute constants C min ≥ 1 C_{\min} \ge1 C m i n ≥ 1 and α 0 > 0 \alpha_0 > 0 α 0 > 0 so that C min / k ≤ α ≤ α 0 C_{\min}/\sqrt{k} \le\alpha\le\alpha_0 C m i n / k ≤ α ≤ α 0 implies
α ≤ c 20 , 1 m < λ ≤ 1 2 , λ 2 + 1 m − 1 ≤ c ρ α 2 c 4 . (21) \alpha\le\frac{c}{20}, \qquad\frac{1}{m} < \lambda\le\frac{1}{2}, \qquad\lambda^2 + \frac{1}{m-1} \le c_\rho\frac{\alpha^2}{c^4}. \tag*{(21)} α ≤ 20 c , m 1 < λ ≤ 2 1 , λ 2 + m − 1 1 ≤ c ρ c 4 α 2 . (21)
Specifically, take
α 0 2 = min { c 2 400 , 1 2 C λ , c ρ 2 c 4 C λ 2 } , \alpha_0^2 = \min\left\{\frac{c^2}{400}, \frac{1}{2C_\lambda}, \frac{c_\rho}{2c^4 C_\lambda^2}\right\}, α 0 2 = min { 400 c 2 , 2 C λ 1 , 2 c 4 C λ 2 c ρ } ,
C min 2 = max { 1 , 1 20 C λ , c 4 19 c ρ } . C_{\min}^2 = \max\left\{1, \frac{1}{20C_\lambda}, \frac{c^4}{19c_\rho}\right\}. C m i n 2 = max { 1 , 20 C λ 1 , 19 c ρ c 4 } .
The lower endpoint controls the isotropic contribution to the noise norm fluctuations; the upper endpoint controls the covariance spike.
Use the following step size, round budget, and common round length:
η = 1 2 , T max = ⌈ λ q 0 log ( m λ ) + 16 log 2 δ ⌉ + 1 , \eta= \frac{1}{2}, \qquad T_{\max} = \left\lceil\frac{\lambda}{q_0}\log(m\lambda) + 16\log\frac{2}{\delta} \right\rceil+ 1, η = 2 1 , T m a x = ⌈ q 0 λ log ( mλ ) + 16 log δ 2 ⌉ + 1 ,
r = max { 48 m , ⌈ 32 δ 0 2 log 4 T max δ ⌉ } . (22) r = \max\left\{48m,\ \left\lceil\frac{32}{\delta_0^2}\log\frac{4T_{\max}}{\delta}\right\rceil\right\}. \tag*{(22)} r = max { 48 m , ⌈ δ 0 2 32 log δ 4 T m a x ⌉ } . (22)
The same formulas are used with general 0 < δ < 1 0 < \delta< 1 0 < δ < 1 in Section B.5. By [10 ] and [21 ] , every covariance in the search space satisfies
tr ( Σ 2 ) ≤ c ρ α 2 c 4 , ∥ Σ ∥ op ≤ λ = O ( α 2 ) . (23) \operatorname{tr}(\Sigma^2) \le c_{\rho}\frac{\alpha^2}{c^4}, \qquad\lVert\Sigma\rVert_{\operatorname{op}} \le\lambda= O(\alpha^2). \tag*{(23)} tr ( Σ 2 ) ≤ c ρ c 4 α 2 , ∥ Σ ∥ op ≤ λ = O ( α 2 ) . (23)
Proof of Theorem 1.1. First consider C min / k ≤ α ≤ α 0 C_{\min}/\sqrt{k} \le\alpha\le\alpha_0 C m i n / k ≤ α ≤ α 0 . Convert the norm-task answers as in § 3.3 . The resulting answers form an informed signal-gap responder.
With probability at least 0.95 0.95 0.95 over the choice of signal coordinate, either A h = 0 A_h = 0 A h = 0 or 1 / ( 40 k ) ≤ V ( I m / m ) < ∞ 1/(40k) \le\mathcal{V}(I_m/m) < \infty 1/ ( 40 k ) ≤ V ( I m / m ) < ∞ (Corollary B.2). In the latter case, the spike comparator of (33) satisfies
V ( Σ ⋆ ) = m λ V ( I m / m ) ≥ λ , g 2 V ( Σ ⋆ ) ≥ C m a r g = 256. (24) \mathcal{V}(\Sigma_\star) = m\lambda\mathcal{V}(I_m/m) \ge\lambda, \qquad g^2\mathcal{V}(\Sigma_\star) \ge C_{\mathrm{marg}} = 256. \tag*{(24)} V ( Σ ⋆ ) = mλ V ( I m / m ) ≥ λ , g 2 V ( Σ ⋆ ) ≥ C marg = 256. (24)
This is the margin needed for the entropy argument: Proposition B.12 shows that a round must fail validation within T max T_{\max} T m a x rounds with probability at least 1 − δ = 0.96 1-\delta= 0.96 1 − δ = 0.96 , conditional on this initialization. If A h = 0 A_h = 0 A h = 0 , the sketch carries no information about the signal, so every response rule has signal-gap loss 5 / ( 10 + c ) > δ 0 5/(10+c) > \delta_0 5/ ( 10 + c ) > δ 0 ; the validation bound (Lemma B.7 (b)) gives the same rejection probability in the first round. Thus the attack returns a rejected round with probability at least 0.95 ⋅ 0.96 0.95 \cdot0.96 0.95 ⋅ 0.96 .
Each round draws r r r independent queries from its announced distribution, and the stopping rule returns a round with empirical signal-gap loss E t / r > δ 0 / 2 E_t/r > \delta_0/2 E t / r > δ 0 /2 . Every covariance used by the attack is norm-admissible by (23) . For the round length in (22) , Corollary B.17 with N = T max N = T_{\max} N = T m a x and ε = 0.01 \varepsilon= 0.01 ε = 0.01 gives, with probability at least 0.99 0.99 0.99 , the simultaneous bounds
1 r ∑ j = 1 r e t , j n o r m ≥ E t r − δ 0 4 \frac{1}{r}\sum_{j=1}^{r} e_{t,j}^{\mathrm{norm}} \ge\frac{E_t}{r} - \frac{\delta_0}{4} r 1 j = 1 ∑ r e t , j norm ≥ r E t − 4 δ 0
for all executed rounds, where e t , j n o r m e_{t,j}^{\mathrm{norm}} e t , j norm is the loss for the original norm task. Consequently, with probability at least 0.95 ⋅ 0.96 − 0.01 > 0.9 0.95 \cdot0.96 - 0.01 > 0.9 0.95 ⋅ 0.96 − 0.01 > 0.9 , the returned round contains more than a δ 0 / 4 \delta_0/4 δ 0 /4 fraction of norm-task errors.
Since λ ≤ 1 / 2 \lambda\le1/2 λ ≤ 1/2 , λ / q 0 ≤ 2 m λ = 80 C λ α 2 k \lambda/q_0 \le2m\lambda= 80C_\lambda\alpha^2 k λ / q 0 ≤ 2 mλ = 80 C λ α 2 k . Also α 2 k ≥ 1 \alpha^2 k \ge1 α 2 k ≥ 1 , so log ( m λ ) = O ( log ( 2 + α 2 k ) ) \log(m\lambda) = O(\log(2+\alpha^2 k)) log ( mλ ) = O ( log ( 2 + α 2 k )) . Consequently,
T max = O ( 1 + α 2 k log ( 2 + α 2 k ) ) , r = Θ ( k ) , T_{\max} = O(1+\alpha^2 k\log(2+\alpha^2 k)), \qquad r = \Theta(k), T m a x = O ( 1 + α 2 k log ( 2 + α 2 k )) , r = Θ ( k ) ,
where the second bound uses T max ≤ k O ( 1 ) T_{\max} \le k^{O(1)} T m a x ≤ k O ( 1 ) and fixed δ \delta δ . The total query count is
Q = r T max = O ( k + α 2 k 2 log ( 2 + α 2 k ) ) . (25) Q = rT_{\max} = O(k+\alpha^2k^2\log(2+\alpha^2k)). \tag*{(25)} Q = r T m a x = O ( k + α 2 k 2 log ( 2 + α 2 k )) . (25)
All queries are supported on S S S , and Section G.1 gives the stated working-memory and arithmetic bounds.
For 0 < α < C min / k 0 < \alpha< C_{\min}/\sqrt{k} 0 < α < C m i n / k and α ≤ α 0 \alpha\le\alpha_0 α ≤ α 0 , Corollary F.3 with C = C min C = C_{\min} C = C m i n gives the guarantee for either norm task in one round of Θ ( k ) \Theta(k) Θ ( k ) queries, using O ( k ) O(k) O ( k ) working memory and O ( k 2 ) O(k^2) O ( k 2 ) arithmetic operations. Its norm-estimation error threshold α / 16 \alpha/16 α /16 is at least c e r r α c_{\mathrm{err}}\alpha c err α . Take
c f r a c = min { δ 0 4 , δ i s o ( c , C min ) 2 } c_{\mathrm{frac}} = \min\left\{\frac{\delta_0}{4}, \frac{\delta_{\mathrm{iso}}(c,C_{\min})}{2}\right\} c frac = min { 4 δ 0 , 2 δ iso ( c , C m i n ) }
to cover both regimes. Finally, for arbitrary α ∈ ( 0 , 1 ] \alpha\in(0,1] α ∈ ( 0 , 1 ] , run at β = min { α , α 0 } \beta= \min\{\alpha,\alpha_0\} β = min { α , α 0 } . Since α 0 α ≤ β ≤ α \alpha_0\alpha\le\beta\le\alpha α 0 α ≤ β ≤ α , the forced relative error remains Ω ( α ) \Omega(\alpha) Ω ( α ) and the norm gap remains 1 + Θ ( α ) 1+\Theta(\alpha) 1 + Θ ( α ) , while the resource bounds at β \beta β are at most those stated at α \alpha α .
Gaussian geometry and initialization
Gaussian identities and degenerate cases
We collect the scalar-channel definitions and Gaussian identities used below, including the degenerate cases. With K Σ K_{\Sigma} K Σ as in (15) , define the normalized Fisher information for the scalar signal,
I ( Σ ) = { A h T K Σ † A h , A h ∈ im ( K Σ ) , + ∞ , A h ∉ im ( K Σ ) , (26) \mathcal{I}(\Sigma)=
\begin{cases}
A_h^{\mathsf T}K_{\Sigma}^{\dagger}A_h, & A_h\in\operatorname{im}(K_{\Sigma}),\\
+\infty, & A_h\notin\operatorname{im}(K_{\Sigma}),
\end{cases} \tag*{(26)} I ( Σ ) = { A h T K Σ † A h , + ∞ , A h ∈ im ( K Σ ) , A h ∈ / im ( K Σ ) , (26)
and the normalized signal-estimation variance
V ( Σ ) = I ( Σ ) − 1 , (27) \mathcal{V}(\Sigma)=\mathcal{I}(\Sigma)^{-1}, \tag*{(27)} V ( Σ ) = I ( Σ ) − 1 , (27)
with the conventions 1 / ( + ∞ ) = 0 1/(+\infty)=0 1/ ( + ∞ ) = 0 and 1 / 0 = + ∞ 1/0=+\infty 1/0 = + ∞ . The actual Fisher information in the observation y = w A h + c A M u y=wA_h+cA_Mu y = w A h + c A M u is I ( Σ ) / c 2 \mathcal{I}(\Sigma)/c^2 I ( Σ ) / c 2 , and the actual signal-estimation variance is c 2 V ( Σ ) c^2\mathcal{V}(\Sigma) c 2 V ( Σ ) .
For 0 < I ( Σ ) < ∞ 0<\mathcal{I}(\Sigma)<\infty 0 < I ( Σ ) < ∞ , the statistic in (16) is the minimum-variance unbiased estimator in this Gaussian location family [49 ] . It satisfies
T Σ ( y ) = w + c V ( Σ ) a Σ T u , a Σ = A M T K Σ † A h . (28) T_{\Sigma}(y)=w+c\mathcal{V}(\Sigma)a_{\Sigma}^{\mathsf T}u,\qquad a_{\Sigma}=A_M^{\mathsf T}K_{\Sigma}^{\dagger}A_h. \tag*{(28)} T Σ ( y ) = w + c V ( Σ ) a Σ T u , a Σ = A M T K Σ † A h . (28)
In particular, the estimation error in (17) is a linear function of u u u , independent of w w w .
To verify sufficiency directly, put d = V ( Σ ) K Σ † A h d=\mathcal{V}(\Sigma)K_{\Sigma}^{\dagger}A_h d = V ( Σ ) K Σ † A h , ϵ = c A M u \epsilon=cA_Mu ϵ = c A M u , and T = T Σ ( y ) = d T y T=T_{\Sigma}(y)=d^{\mathsf T}y T = T Σ ( y ) = d T y . Since d T A h = 1 d^{\mathsf T}A_h=1 d T A h = 1 ,
T = w + d T ϵ , r = y − A h T = ( I − A h d T ) ϵ . T=w+d^{\mathsf T}\epsilon,\qquad r=y-A_hT=(I-A_hd^{\mathsf T})\epsilon. T = w + d T ϵ , r = y − A h T = ( I − A h d T ) ϵ .
Moreover,
Cov ( r , T − w ) = c 2 ( K Σ d − A h d T K Σ d ) = 0. \operatorname{Cov}(r,T-w)=c^2(K_{\Sigma}d-A_hd^{\mathsf T}K_{\Sigma}d)=0. Cov ( r , T − w ) = c 2 ( K Σ d − A h d T K Σ d ) = 0.
Gaussianity makes r r r independent of T − w T-w T − w . Since w w w is independent of the Gaussian noise, r r r is independent of ( w , T ) (w,T) ( w , T ) . The identity y = A h T + r y=A_hT+r y = A h T + r therefore proves that T T T is sufficient for w w w .
Variational geometry
The scalar-channel variance has a useful geometric description. If A h ∉ im ( A M ) A_h\notin\operatorname{im}(A_M) A h ∈ / im ( A M ) , the sketch has a noiseless signal component and V ( Σ ) = 0 \mathcal{V}(\Sigma)=0 V ( Σ ) = 0 for every covariance. The successful initialization event in Corollary B.2 ensures A h ∈ im ( A M ) A_h\in\operatorname{im}(A_M) A h ∈ im ( A M ) , which is why we may assume this condition in the subsequent optimization. When it holds, let z ∗ z_* z ∗ be the minimum-norm solution of A M z = A h A_Mz=A_h A M z = A h : a noise vector that the sketch maps exactly onto the signal column.
Lemma B.1 (Variational formula). For every positive semidefinite Σ \Sigma Σ ,
I ( Σ ) = min { z T Σ † z : A M z = A h , z ∈ im ( Σ ) } , (29) \mathcal{I}(\Sigma)=\min\left\{z^{\mathsf T}\Sigma^{\dagger}z:\ A_Mz=A_h,\ z\in\operatorname{im}(\Sigma)\right\}, \tag*{(29)} I ( Σ ) = min { z T Σ † z : A M z = A h , z ∈ im ( Σ ) } , (29) where the minimum is + ∞ +\infty + ∞ if the constraint set is empty. Consequently, if A h ∈ im ( A M ) ∖ { 0 } A_h\in\operatorname{im}(A_M)\setminus\{0\} A h ∈ im ( A M ) ∖ { 0 } , then
V ( I m / m ) = 1 m ∥ z ∗ ∥ 2 2 , V ( Σ ) ≤ λ max ( Σ ) ∥ z ∗ ∥ 2 2 = m λ max ( Σ ) V ( I m / m ) (30) \mathcal{V}(I_m/m)=\frac{1}{m\lVert z_*\rVert_2^2},\qquad
\mathcal{V}(\Sigma)\le\frac{\lambda_{\max}(\Sigma)}{\lVert z_*\rVert_2^2}
=m\lambda_{\max}(\Sigma)\mathcal{V}(I_m/m) \tag*{(30)} V ( I m / m ) = m ∥ z ∗ ∥ 2 2 1 , V ( Σ ) ≤ ∥ z ∗ ∥ 2 2 λ m a x ( Σ ) = m λ m a x ( Σ ) V ( I m / m ) (30) for every Σ \Sigma Σ , with equality in the second relation when z ∗ z_* z ∗ is an eigenvector of Σ \Sigma Σ for its largest eigenvalue.
Proof. We first prove the variational formula, then derive the two variance bounds. Put L = Σ 1 / 2 L=\Sigma^{1/2} L = Σ 1/2 , so K Σ = ( A M L ) ( A M L ) T K_{\Sigma}=(A_ML)(A_ML)^{\mathsf{T}} K Σ = ( A M L ) ( A M L ) T and im ( K Σ ) = im ( A M L ) \operatorname{im}(K_{\Sigma})=\operatorname{im}(A_ML) im ( K Σ ) = im ( A M L ) . If A h A_h A h is outside this image, then I ( Σ ) = + ∞ \mathcal{I}(\Sigma)=+\infty I ( Σ ) = + ∞ by definition and the constraint set in (29) is empty.
Otherwise, the minimum-norm solution of a feasible system D q = x Dq=x D q = x has squared norm x T ( D D T ) † x x^{\mathsf{T}}(DD^{\mathsf{T}})^{\dagger}x x T ( D D T ) † x . Apply this identity first to D = A M L D=A_ML D = A M L , then to D = L D=L D = L , and group the feasible vectors q q q according to z = L q z=Lq z = L q . This gives
I ( Σ ) = min A M L q = A h ∥ q ∥ 2 2 = min A M z = A h z ∈ im ( Σ ) min L q = z ∥ q ∥ 2 2 = min A M z = A h z ∈ im ( Σ ) z T Σ † z . \mathcal{I}(\Sigma)=\min_{\substack{A_MLq=A_h}}\|q\|_2^2=\min_{\substack{A_Mz=A_h\\z\in\operatorname{im}(\Sigma)}}\min_{\substack{Lq=z}}\|q\|_2^2=\min_{\substack{A_Mz=A_h\\z\in\operatorname{im}(\Sigma)}}z^{\mathsf{T}}\Sigma^{\dagger}z. I ( Σ ) = A M L q = A h min ∥ q ∥ 2 2 = A M z = A h z ∈ im ( Σ ) min L q = z min ∥ q ∥ 2 2 = A M z = A h z ∈ im ( Σ ) min z T Σ † z .
Now assume A h ∈ im ( A M ) ∖ { 0 } A_h\in\operatorname{im}(A_M)\setminus\{0\} A h ∈ im ( A M ) ∖ { 0 } . For the isotropic covariance, the formula immediately gives I ( I m / m ) = m ∥ z ∗ ∥ 2 2 \mathcal{I}(I_m/m)=m\|z_*\|_2^2 I ( I m / m ) = m ∥ z ∗ ∥ 2 2 . For any nonzero covariance, every feasible z z z satisfies
z T Σ † z ≥ ∥ z ∥ 2 2 λ max ( Σ ) ≥ ∥ z ∗ ∥ 2 2 λ max ( Σ ) . z^{\mathsf{T}}\Sigma^{\dagger}z\geq\frac{\|z\|_2^2}{\lambda_{\max}(\Sigma)}\geq\frac{\|z_*\|_2^2}{\lambda_{\max}(\Sigma)}. z T Σ † z ≥ λ m a x ( Σ ) ∥ z ∥ 2 2 ≥ λ m a x ( Σ ) ∥ z ∗ ∥ 2 2 .
Minimizing and taking reciprocals proves the upper bound on V ( Σ ) \mathcal{V}(\Sigma) V ( Σ ) ; it also holds when the constraint set is empty, since then V ( Σ ) = 0 \mathcal{V}(\Sigma)=0 V ( Σ ) = 0 . If z ∗ z_* z ∗ is a top eigenvector, it is feasible and attains both inequalities, proving equality. Finally, for Σ = 0 \Sigma=0 Σ = 0 , both V ( Σ ) \mathcal{V}(\Sigma) V ( Σ ) and the stated upper bound are zero.
Isotropic initialization on any fixed support
The random-coordinate initialization is the same as that of Ahmadian et al. [2 Lemma 4.5] . Their bound uses m = Ω ( k log 2 k ) m=\Omega(k\log^2 k) m = Ω ( k log 2 k ) noise coordinates and guarantees variance Ω ( 1 / ( k log k ) ) \Omega(1/(k\log k)) Ω ( 1/ ( k log k )) with high constant probability. The leverage-score argument below removes the logarithmic factors: m = Θ ( k ) m=\Theta(k) m = Θ ( k ) coordinates suffice for variance Ω ( 1 / k ) \Omega(1/k) Ω ( 1/ k ) .
Corollary B.2 (Random-signal-coordinate baseline). Fix any set S ⊆ [ n ] S\subseteq[n] S ⊆ [ n ] of m + 1 m+1 m + 1 coordinates, with m + 1 ≥ 2 k / ω m+1\geq2k/\omega m + 1 ≥ 2 k / ω for some ω ∈ ( 0 , 1 ) \omega\in(0,1) ω ∈ ( 0 , 1 ) . Choose h h h uniformly from S S S and put M = S ∖ { h } M=S\setminus\{h\} M = S ∖ { h } . Then with probability at least 1 − ω 1-\omega 1 − ω over h h h , either A h = 0 A_h=0 A h = 0 or
ω 2 k ≤ V ( I m / m ) < ∞ . (31) \frac{\omega}{2k}\leq\mathcal{V}(I_m/m)<\infty. \tag*{(31)} 2 k ω ≤ V ( I m / m ) < ∞. (31) In particular, for m ≥ 40 k m\geq40k m ≥ 40 k this holds with probability at least 0.95 0.95 0.95 and lower bound 1 / ( 40 k ) 1/(40k) 1/ ( 40 k ) .
If A h = 0 A_h=0 A h = 0 , the sketch is independent of the signal, V ( Σ ) = + ∞ \mathcal{V}(\Sigma)=+\infty V ( Σ ) = + ∞ for every Σ \Sigma Σ , and every query law is already universally hard for the signal-gap task. In the covariance-update regime, admissibility transfers this signal-gap hardness to the norm tasks (Lemma B.15 ). In the nonzero case, the successful event also ensures A h ∈ im ( A M ) A_h\in\operatorname{im}(A_M) A h ∈ im ( A M ) . This is a guarantee over the random choice of h h h ; the attacker need not test it.
The proof uses the following identity, a standard consequence of the Sherman–Morrison formula [38 Eq. (2)] applied on im ( C ) \operatorname{im}(C) im ( C ) . We include a direct projector proof that also covers rank-deficient C C C .
Lemma B.3 (Leverage-score representation identity). Let C ∈ R k × s C\in\mathbb{R}^{k\times s} C ∈ R k × s have columns a 1 , … , a s a_1,\ldots,a_s a 1 , … , a s , and let
τ j = a j T ( C C T ) † a j . \tau_j=a_j^{\mathsf{T}}(CC^{\mathsf{T}})^{\dagger}a_j. τ j = a j T ( C C T ) † a j . Let C − j C_{-j} C − j denote the matrix obtained from C C C by deleting its j j j th column. If τ j < 1 \tau_j<1 τ j < 1 , then
min { ∥ z ∥ 2 2 : C − j z = a j } = τ j 1 − τ j . (32) \min\{\|z\|_2^2:C_{-j}z=a_j\}=\frac{\tau_j}{1-\tau_j}. \tag*{(32)} min { ∥ z ∥ 2 2 : C − j z = a j } = 1 − τ j τ j . (32) Consequently, if ω s > k \omega s>k ω s > k , all but an ω \omega ω fraction of the columns satisfy a j ∈ im ( C − j ) a_j\in\operatorname{im}(C_{-j}) a j ∈ im ( C − j ) and
min { ∥ z ∥ 2 2 : C − j z = a j } ≤ k ω s − k . \min\{\|z\|_2^2:C_{-j}z=a_j\}\leq\frac{k}{\omega s-k}. min { ∥ z ∥ 2 2 : C − j z = a j } ≤ ω s − k k .
Proof. Let P = C T ( C C T ) † C P=C^{\mathsf{T}}(CC^{\mathsf{T}})^{\dagger}C P = C T ( C C T ) † C be the orthogonal projector onto the row space of C C C , so P j j = τ j P_{jj}=\tau_j P j j = τ j . For τ j < 1 \tau_j<1 τ j < 1 , the vector r = ( I − P ) e j r=(I-P)e_j r = ( I − P ) e j lies in ker ( C ) \ker(C) ker ( C ) and satisfies r j = ∥ r ∥ 2 2 = 1 − τ j r_j=\lVert r\rVert_2^2=1-\tau_j r j = ∥ r ∥ 2 2 = 1 − τ j . Thus
q = e j − r 1 − τ j satisfies q j = 0 , C q = a j , ∥ q ∥ 2 2 = τ j 1 − τ j . q=e_j-\frac{r}{1-\tau_j}\quad\text{satisfies}\quad q_j=0,\quad Cq=a_j,\quad\lVert q\rVert_2^2=\frac{\tau_j}{1-\tau_j}. q = e j − 1 − τ j r satisfies q j = 0 , C q = a j , ∥ q ∥ 2 2 = 1 − τ j τ j .
Deleting the zero coordinate gives a feasible representation of a j a_j a j . To see that it has minimum norm, take any other q ′ q' q ′ with q j ′ = 0 q'_j=0 q j ′ = 0 and C q ′ = a j Cq'=a_j C q ′ = a j . Then d = e j − q ′ d=e_j-q' d = e j − q ′ lies in ker ( C ) \ker(C) ker ( C ) and has d j = 1 d_j=1 d j = 1 . Since r r r is the projection of e j e_j e j onto this kernel,
1 = ⟨ d , e j ⟩ = ⟨ d , r ⟩ ≤ ∥ d ∥ 2 1 − τ j . 1=\langle d,e_j\rangle=\langle d,r\rangle\leq\lVert d\rVert_2\sqrt{1-\tau_j}. 1 = ⟨ d , e j ⟩ = ⟨ d , r ⟩ ≤ ∥ d ∥ 2 1 − τ j .
It follows that ∥ q ′ ∥ 2 2 = ∥ d ∥ 2 2 − 1 ≥ τ j / ( 1 − τ j ) \lVert q'\rVert_2^2=\lVert d\rVert_2^2-1\geq\tau_j/(1-\tau_j) ∥ q ′ ∥ 2 2 = ∥ d ∥ 2 2 − 1 ≥ τ j / ( 1 − τ j ) , proving the identity. Finally, ∑ j τ j = tr ( P ) = rank ( C ) ≤ k \sum_j\tau_j=\operatorname{tr}(P)=\operatorname{rank}(C)\leq k ∑ j τ j = tr ( P ) = rank ( C ) ≤ k . Hence all but an ω \omega ω fraction of the columns have τ j ≤ k / ( ω s ) < 1 \tau_j\leq k/(\omega s)<1 τ j ≤ k / ( ω s ) < 1 , and for these columns τ j / ( 1 − τ j ) ≤ k / ( ω s − k ) \tau_j/(1-\tau_j)\leq k/(\omega s-k) τ j / ( 1 − τ j ) ≤ k / ( ω s − k ) .
Proof of Corollary B.2. Apply Lemma B.3 to the restricted matrix C = A ∙ S C=A_{\mathord{\bullet}S} C = A ∙ S with s = m + 1 s=m+1 s = m + 1 . With probability at least 1 − ω 1-\omega 1 − ω , A h ∈ im ( A M ) A_h\in\operatorname{im}(A_M) A h ∈ im ( A M ) and
∥ z ∗ ∥ 2 2 ≤ k ω ( m + 1 ) − k ≤ 2 k ω ( m + 1 ) . \lVert z_*\rVert_2^2\leq\frac{k}{\omega(m+1)-k}\leq\frac{2k}{\omega(m+1)}. ∥ z ∗ ∥ 2 2 ≤ ω ( m + 1 ) − k k ≤ ω ( m + 1 ) 2 k .
where the last inequality uses ω ( m + 1 ) ≥ 2 k \omega(m+1)\geq2k ω ( m + 1 ) ≥ 2 k . If A h = 0 A_h=0 A h = 0 , the first alternative holds. Otherwise Lemma B.1 gives
V ( I m / m ) = 1 m ∥ z ∗ ∥ 2 2 ≥ ω ( m + 1 ) 2 k m ≥ ω 2 k . \mathcal{V}(I_m/m)=\frac{1}{m\lVert z_*\rVert_2^2}\geq\frac{\omega(m+1)}{2km}\geq\frac{\omega}{2k}. V ( I m / m ) = m ∥ z ∗ ∥ 2 2 1 ≥ 2 k m ω ( m + 1 ) ≥ 2 k ω .
The hard comparator
On the nonzero successful initialization event, A h ∈ im ( A M ) ∖ { 0 } A_h\in\operatorname{im}(A_M)\setminus\{0\} A h ∈ im ( A M ) ∖ { 0 } . Since every covariance in the search space is positive definite, 0 < V ( Σ ) < ∞ 0<\mathcal{V}(\Sigma)<\infty 0 < V ( Σ ) < ∞ throughout. Recall that z ∗ z_* z ∗ is the minimum-norm solution of A M z = A h A_Mz=A_h A M z = A h , and set v ⋆ = z ∗ / ∥ z ∗ ∥ 2 v_\star=z_*/\lVert z_*\rVert_2 v ⋆ = z ∗ / ∥ z ∗ ∥ 2 and Σ ⋆ = Σ v ⋆ \Sigma_\star=\Sigma_{v_\star} Σ ⋆ = Σ v ⋆ , where
Σ v = q 0 I m + ( λ − q 0 ) v v T , v ∈ S m − 1 . (33) \Sigma_v=q_0I_m+(\lambda-q_0)vv^{\mathsf{T}},\qquad v\in S^{m-1}. \tag*{(33)} Σ v = q 0 I m + ( λ − q 0 ) v v T , v ∈ S m − 1 . (33)
By Lemma B.1, this spike maximizes the signal-estimation variance over K λ \mathcal{K}_\lambda K λ , with
V ( Σ ⋆ ) = m λ V ( I m / m ) . (34) \mathcal{V}(\Sigma_\star)=m\lambda\mathcal{V}(I_m/m). \tag*{(34)} V ( Σ ⋆ ) = mλ V ( I m / m ) . (34)
The comparator is used only in the analysis; the attacker need not compute it. The initialization bound gives V ( Σ ⋆ ) ≥ λ \mathcal{V}(\Sigma_\star)\geq\lambda V ( Σ ⋆ ) ≥ λ when m = 40 k m=40k m = 40 k . The case A h = 0 A_h=0 A h = 0 will be handled separately.
The eigenvalue-cap benchmark. The same benchmark holds without an eigenvalue floor, as needed for the sufficient-statistic attack. For 1 / m ≤ λ ≤ 1 1/m\leq\lambda\leq1 1/ m ≤ λ ≤ 1 ,
max Σ ⪰ 0 , tr Σ = 1 λ max ( Σ ) ≤ λ V ( Σ ) = m λ V ( I m / m ) . (35) \max_{\substack{\Sigma\succeq0,\ \operatorname{tr}\Sigma=1\\ \lambda_{\max}(\Sigma)\leq\lambda}}\mathcal{V}(\Sigma)=m\lambda\mathcal{V}(I_m/m). \tag*{(35)} Σ ⪰ 0 , tr Σ = 1 λ m a x ( Σ ) ≤ λ max V ( Σ ) = mλ V ( I m / m ) . (35)
Indeed, Lemma B.1 gives the upper bound, attained by λ v ⋆ v ⋆ T + ( 1 − λ ) ( I m − v ⋆ v ⋆ T ) / ( m − 1 ) \lambda v_\star v_\star^{\mathsf{T}}+(1-\lambda)(I_m-v_\star v_\star^{\mathsf{T}})/(m-1) λ v ⋆ v ⋆ T + ( 1 − λ ) ( I m − v ⋆ v ⋆ T ) / ( m − 1 ) . The general attack uses this unknown spike as a comparator in its entropy analysis. The sufficient-statistic attack instead preserves a constant fraction of this optimum at its attained top eigenvalue. Norm admissibility additionally requires a bound on tr ( Σ 2 ) \operatorname{tr}(\Sigma^2) tr ( Σ 2 ) , which each attack establishes for the covariances it uses. Neither attack needs to compute z ∗ z_* z ∗ .
Correlation and validation in an adaptive round
Correlation and hardness from the gain lemma
We record the two consequences of Lemma 4.1 used in the attack analyses: a response–noise correlation and a quantitative hardness threshold. The signal density and the proof of the gain lemma are given in Section E.
To express Lemma 4.1 in the noise coordinates, define the response-weighted mean
m ψ ( Σ ) = E [ ψ ( y ) u ] . (36) m_{\psi}(\Sigma) = \mathbb{E}[\psi(y)u]. \tag*{(36)} m ψ ( Σ ) = E [ ψ ( y ) u ] . (36)
For 0 < V ( Σ ) < ∞ 0 < \mathcal{V}(\Sigma) < \infty 0 < V ( Σ ) < ∞ , define the gain
Γ ψ ( Σ ) = E [ ψ ( y ) ( T Σ ( y ) − w ) ] = c V ( Σ ) ⟨ a Σ , m ψ ( Σ ) ⟩ . (37) \Gamma_{\psi}(\Sigma) = \mathbb{E}[\psi(y)(T_{\Sigma}(y)-w)] = c\mathcal{V}(\Sigma)\langle a_{\Sigma},m_{\psi}(\Sigma)\rangle. \tag*{(37)} Γ ψ ( Σ ) = E [ ψ ( y ) ( T Σ ( y ) − w )] = c V ( Σ ) ⟨ a Σ , m ψ ( Σ )⟩ . (37)
The identity follows from (28) . Since the estimation error has mean zero, the gain is its covariance with the response.
Dividing the scalar gain bound of Lemma 4.1 by c V ( Σ ) c\mathcal{V}(\Sigma) c V ( Σ ) gives its vector formulation:
L Σ ( ψ ) ≤ δ 0 ⟹ ⟨ a Σ , m ψ ( Σ ) ⟩ ≥ g . (38) \mathcal{L}_{\Sigma}(\psi) \le\delta_0 \quad\Longrightarrow\quad\langle a_{\Sigma},m_{\psi}(\Sigma)\rangle\ge g. \tag*{(38)} L Σ ( ψ ) ≤ δ 0 ⟹ ⟨ a Σ , m ψ ( Σ )⟩ ≥ g . (38)
The bound holds throughout the positive finite variance range.
The gain lemma also gives a quantitative hardness threshold at the loss level δ 0 \delta_0 δ 0 used in the attack analysis.
Corollary B.5 (Accuracy bounds the variance). Under the hypotheses of Lemma 4.1, any response rule with signal-gap loss at most δ 0 \delta_0 δ 0 satisfies
g 2 V ( Σ ) ≤ 1. (39) g^2\mathcal{V}(\Sigma) \le1. \tag*{(39)} g 2 V ( Σ ) ≤ 1. (39) Consequently, if g 2 V ( Σ ) > 1 g^2\mathcal{V}(\Sigma)>1 g 2 V ( Σ ) > 1 , every signal-gap response rule has loss greater than δ 0 \delta_0 δ 0 .
Proof. Since ∣ ψ ∣ ≤ 1 |\psi| \le1 ∣ ψ ∣ ≤ 1 , Cauchy–Schwarz and (17) bound the left side of (18) by c V ( Σ ) c\sqrt{\mathcal{V}(\Sigma)} c V ( Σ ) . Combining the bounds gives g 2 V ( Σ ) ≤ 1 g^2\mathcal{V}(\Sigma) \le1 g 2 V ( Σ ) ≤ 1 .
The transcript T r i − 1 \mathrm{Tr}_{i-1} Tr i − 1 in Definition 2.1 records the complete execution of both parties through completed query i − 1 i-1 i − 1 . It is available to the responder, but its private part is not available to the attacker. We distinguish two information sets just before the fresh draw of query i i i :
Thus H i − 1 ⊆ F i − 1 \mathcal{H}_{i-1} \subseteq\mathcal{F}_{i-1} H i − 1 ⊆ F i − 1 , the map ψ i \psi_i ψ i is F i − 1 \mathcal{F}_{i-1} F i − 1 -measurable, and freshness of the query randomness gives
v i ∣ F i − 1 ∼ D i , v i ∣ H i − 1 ∼ D i . v_i \mid\mathcal{F}_{i-1} \sim\mathcal{D}_i,\qquad v_i \mid\mathcal{H}_{i-1} \sim\mathcal{D}_i. v i ∣ F i − 1 ∼ D i , v i ∣ H i − 1 ∼ D i .
After the answer and disclosure, both histories contain the generated input, the answer, and the attacker’s sampling variables. The current distribution announcement is additional to T r i − 1 \mathrm{Tr}_{i-1} Tr i − 1 ; the latter always ends at completed query i − 1 i-1 i − 1 .
The realized loss e i e_i e i is observed by the attacker. Its conditional expectation
ε i : = E [ e i ∣ F i − 1 ] \varepsilon_i := \mathbb{E}[e_i \mid\mathcal{F}_{i-1}] ε i := E [ e i ∣ F i − 1 ]
is the predictable loss used in the analysis. Validation relates the average realized loss in a round to the average predictable loss.
Conditioning on H i − 1 \mathcal{H}_{i-1} H i − 1 instead averages over the responder’s private history as well as its current randomization. The sufficient-statistic definition uses precisely this conditional mean; enlarging its conditioning information to the full transcript would be a stronger restriction on the responder. Within a round, we use j j j in place of i i i with the same conventions.
In the interaction, the realized loss is e i = L ( ψ i ( y i ) , w i ) e_i = \mathcal{L}(\psi_i(y_i), w_i) e i = L ( ψ i ( y i ) , w i ) . Conditionally on F i − 1 \mathcal{F}_{i-1} F i − 1 , both the rule and the covariance are fixed, so ε i = L Σ t ( ψ i ) \varepsilon_i = \mathcal{L}_{\Sigma_t}(\psi_i) ε i = L Σ t ( ψ i ) for query i i i in round t t t .
Drift and validation
Fix one round with a positive definite trace-one covariance Σ = R R T \Sigma= RR^{\mathsf{T}} Σ = R R T , and drop the index t t t . For the drift bound assume 0 < V ( Σ ) < ∞ 0 < \mathcal{V}(\Sigma) < \infty 0 < V ( Σ ) < ∞ ; the validation lemma does not require this assumption. Neither lemma requires an eigenvalue floor or cap. Both lemmas hold for either information set from Section Section B.3.2. We first write the proofs with F j − 1 \mathcal{F}_{j-1} F j − 1 and explain the use of H j − 1 \mathcal{H}_{j-1} H j − 1 below. For j = 1 , … , r j = 1, \ldots, r j = 1 , … , r use the enlarged information set F j − 1 \mathcal{F}_{j-1} F j − 1 of Section Section B.3.2, including the responder’s private randomness that selects the current response rule. Thus ψ j \psi_j ψ j is F j − 1 \mathcal{F}_{j-1} F j − 1 -measurable. Put
X j = ψ j ( y j ) z j , μ j = E [ X j ∣ F j − 1 ] , e j = L ( ψ j ( y j ) , w j ) , ε j = E [ e j ∣ F j − 1 ] , (40) X_j = \psi_j(y_j)z_j,\qquad\mu_j = \mathbb{E}[X_j \mid\mathcal{F}_{j-1}],\qquad e_j = \mathcal{L}(\psi_j(y_j), w_j),\qquad\varepsilon_j = \mathbb{E}[e_j \mid\mathcal{F}_{j-1}], \tag*{(40)} X j = ψ j ( y j ) z j , μ j = E [ X j ∣ F j − 1 ] , e j = L ( ψ j ( y j ) , w j ) , ε j = E [ e j ∣ F j − 1 ] , (40)
so that ε j = L Σ ( ψ j ) \varepsilon_j = \mathcal{L}_{\Sigma}(\psi_j) ε j = L Σ ( ψ j ) is the predictable loss. The signed noise sum of the round splits into a predictable drift and a martingale,
S r = ∑ j = 1 r X j = M r + N r , M r = ∑ j = 1 r μ j , N r = ∑ j = 1 r ( X j − μ j ) . (41) S_r = \sum_{j=1}^{r} X_j = M_r + N_r,\qquad M_r = \sum_{j=1}^{r} \mu_j,\qquad N_r = \sum_{j=1}^{r}(X_j-\mu_j). \tag*{(41)} S r = j = 1 ∑ r X j = M r + N r , M r = j = 1 ∑ r μ j , N r = j = 1 ∑ r ( X j − μ j ) . (41)
The attacker observes S r S_r S r and the loss sum E = ∑ j e j E = \sum_j e_j E = ∑ j e j , but neither M r M_r M r nor the ε j \varepsilon_j ε j . The signal-estimation direction in whitened coordinates is
h R = V ( Σ ) R T a Σ , h_R = \sqrt{\mathcal{V}(\Sigma)}\,R^{\mathsf{T}}a_\Sigma, h R = V ( Σ ) R T a Σ ,
a unit vector, since ∥ h R ∥ 2 2 = V ( Σ ) a Σ T Σ a Σ = V ( Σ ) A Σ T K Σ T K Σ K Σ T A h = V ( Σ ) I ( Σ ) = 1 \lVert h_R\rVert_2^2 = \mathcal{V}(\Sigma)\,a_\Sigma^{\mathsf{T}}\Sigma a_\Sigma= \mathcal{V}(\Sigma)\,A_\Sigma^{\mathsf{T}}K_\Sigma^{\mathsf{T}}K_\Sigma K_\Sigma^{\mathsf{T}}A_h = \mathcal{V}(\Sigma)\mathcal{I}(\Sigma) = 1 ∥ h R ∥ 2 2 = V ( Σ ) a Σ T Σ a Σ = V ( Σ ) A Σ T K Σ T K Σ K Σ T A h = V ( Σ ) I ( Σ ) = 1 . Because u = R z u = Rz u = R z , the first moment (36) is m ψ ( Σ ) = R E [ ψ ( y ) z ] m_\psi(\Sigma) = R\,\mathbb{E}[\psi(y)z] m ψ ( Σ ) = R E [ ψ ( y ) z ] , so for every response rule
⟨ h R , E [ ψ ( y ) z ] ⟩ = V ( Σ ) ⟨ a Σ , m ψ ( Σ ) ⟩ . (42) \langle h_R,\mathbb{E}[\psi(y)z]\rangle= \sqrt{\mathcal{V}(\Sigma)}\,\langle a_\Sigma,m_\psi(\Sigma)\rangle. \tag*{(42)} ⟨ h R , E [ ψ ( y ) z ]⟩ = V ( Σ ) ⟨ a Σ , m ψ ( Σ )⟩ . (42)
Lemma B.6 (Drift of an accurate round). Each μ j \mu_j μ j lies in im ( R T A M T ) \operatorname{im}(R^{\mathsf T}A_M^{\mathsf T}) im ( R T A M T ) and has ∥ μ j ∥ 2 ≤ 1 \lVert\mu_j\rVert_2 \le1 ∥ μ j ∥ 2 ≤ 1 , and
E [ ( X j − μ j ) ( X j − μ j ) T ∣ F j − 1 ] ⪯ I m . (43) \mathbb{E}\left[(X_j-\mu_j)(X_j-\mu_j)^{\mathsf T}\mid\mathcal{F}_{j-1}\right]\preceq I_m. \tag*{(43)} E [ ( X j − μ j ) ( X j − μ j ) T ∣ F j − 1 ] ⪯ I m . (43) If r − 1 ∑ j ϵ j ≤ δ 0 r^{-1}\sum_j\epsilon_j\le\delta_0 r − 1 ∑ j ϵ j ≤ δ 0 , then
⟨ h R , M r ⟩ ≥ r g V ( Σ ) . (44) \langle h_R,M_r\rangle\ge rg\sqrt{\mathcal{V}(\Sigma)}. \tag*{(44)} ⟨ h R , M r ⟩ ≥ r g V ( Σ ) . (44) These conclusions hold for every realization of the predictable rules; the drift bound is asserted on the event that their average loss is at most δ 0 \delta_0 δ 0 .
Proof. The query depends on z j z_j z j only through A M R z j A_MRz_j A M R z j , and Gaussian conditioning gives E [ z j ∣ A M R z j ] ∈ im ( R T A M T ) \mathbb{E}[z_j\mid A_MRz_j]\in\operatorname{im}(R^{\mathsf T}A_M^{\mathsf T}) E [ z j ∣ A M R z j ] ∈ im ( R T A M T ) ; hence so is μ j = E [ ψ j ( y j ) E [ z j ∣ w j , A M R z j ] ∣ F j − 1 ] \mu_j=\mathbb{E}[\psi_j(y_j)\mathbb{E}[z_j\mid w_j,A_MRz_j]\mid\mathcal{F}_{j-1}] μ j = E [ ψ j ( y j ) E [ z j ∣ w j , A M R z j ] ∣ F j − 1 ] . For every unit vector b b b , Cauchy–Schwarz gives ∣ ⟨ b , μ j ⟩ ∣ = ∣ E [ ψ j ( y j ) b T z j ∣ F j − 1 ] ∣ ≤ 1 |\langle b,\mu_j\rangle|=|\mathbb{E}[\psi_j(y_j)b^{\mathsf T}z_j\mid\mathcal{F}_{j-1}]|\le1 ∣ ⟨ b , μ j ⟩ ∣ = ∣ E [ ψ j ( y j ) b T z j ∣ F j − 1 ] ∣ ≤ 1 , proving the norm bound. Also,
E [ ( X j − μ j ) ( X j − μ j ) T ∣ F j − 1 ] ⪯ E [ ψ j ( y j ) 2 z j z j T ∣ F j − 1 ] ⪯ I m . \mathbb{E}\left[(X_j-\mu_j)(X_j-\mu_j)^{\mathsf T}\mid\mathcal{F}_{j-1}\right]\preceq\mathbb{E}[\psi_j(y_j)^2z_jz_j^{\mathsf T}\mid\mathcal{F}_{j-1}]\preceq I_m. E [ ( X j − μ j ) ( X j − μ j ) T ∣ F j − 1 ] ⪯ E [ ψ j ( y j ) 2 z j z j T ∣ F j − 1 ] ⪯ I m . For the drift, fix a realization of the rules and let ψ ˉ = r − 1 ∑ j ψ j \bar{\psi}=r^{-1}\sum_j\psi_j ψ ˉ = r − 1 ∑ j ψ j . Evaluate these functions on a fresh generic query from D Σ D_\Sigma D Σ . Loss and first moment commute with averaging, so L Σ ( ψ ˉ ) = r − 1 ∑ j ϵ j ≤ δ 0 \mathcal{L}_\Sigma(\bar{\psi})=r^{-1}\sum_j\epsilon_j\le\delta_0 L Σ ( ψ ˉ ) = r − 1 ∑ j ϵ j ≤ δ 0 and E [ ψ ˉ ( y ) z ] = r − 1 M r \mathbb{E}[\bar{\psi}(y)z]=r^{-1}M_r E [ ψ ˉ ( y ) z ] = r − 1 M r . The vector form (38) of Lemma 4.1 gives ⟨ a Σ , m ψ ˉ ( Σ ) ⟩ ≥ g \langle a_\Sigma,m_{\bar{\psi}}(\Sigma)\rangle\ge g ⟨ a Σ , m ψ ˉ ( Σ )⟩ ≥ g , and (42) turns this into (44) .
Lemma B.7 (Empirical validation). Call the round accepted if E ≤ r δ 0 / 2 E\le r\delta_0/2 E ≤ r δ 0 /2 and rejected otherwise. If r ≥ 32 δ 0 − 2 log ( 2 / δ r d ) r\ge32\delta_0^{-2}\log(2/\delta_{\mathrm{rd}}) r ≥ 32 δ 0 − 2 log ( 2/ δ rd ) , then with probability at least 1 − δ r d 1-\delta_{\mathrm{rd}} 1 − δ rd all three of the following hold:
1 r ∑ j ϵ j < δ 0 ; (45) \frac{1}{r}\sum_j\epsilon_j<\delta_0; \tag*{(45)} r 1 j ∑ ϵ j < δ 0 ; (45) (b) if every response rule has signal-gap loss at least δ 0 \delta_0 δ 0 at Σ \Sigma Σ , then the round is rejected;
(c) if the round is rejected, then r − 1 ∑ j ϵ j > δ 0 / 4 r^{-1}\sum_j\epsilon_j>\delta_0/4 r − 1 ∑ j ϵ j > δ 0 /4 .
Proof. The differences e j − ϵ j e_j-\epsilon_j e j − ϵ j form a martingale difference sequence bounded by one, so the Azuma–Hoeffding inequality gives ∣ r − 1 ∑ j ( e j − ϵ j ) ∣ ≤ δ 0 / 4 \left|r^{-1}\sum_j(e_j-\epsilon_j)\right|\le\delta_0/4 r − 1 ∑ j ( e j − ϵ j ) ≤ δ 0 /4 with probability at least 1 − 2 e − r δ 0 2 / 32 ≥ 1 − δ r d 1-2e^{-r\delta_0^2/32}\ge1-\delta_{\mathrm{rd}} 1 − 2 e − r δ 0 2 /32 ≥ 1 − δ rd . On this event an accepted round has r − 1 ∑ j ϵ j ≤ 3 δ 0 / 4 r^{-1}\sum_j\epsilon_j\le3\delta_0/4 r − 1 ∑ j ϵ j ≤ 3 δ 0 /4 , which is (a); under the hypothesis of (b) every ϵ j ≥ δ 0 \epsilon_j\ge\delta_0 ϵ j ≥ δ 0 , so E / r ≥ 3 δ 0 / 4 > δ 0 / 2 E/r\ge3\delta_0/4>\delta_0/2 E / r ≥ 3 δ 0 /4 > δ 0 /2 ; and a rejected round has r − 1 ∑ j ϵ j > δ 0 / 2 − δ 0 / 4 r^{-1}\sum_j\epsilon_j>\delta_0/2-\delta_0/4 r − 1 ∑ j ϵ j > δ 0 /2 − δ 0 /4 , which is (c).
The same statements hold with H j − 1 \mathcal{H}_{j-1} H j − 1 in place of F j − 1 \mathcal{F}_{j-1} F j − 1 . To compute the conditional means, replace the privately selected rule by ψ ˉ j ( y ) = E [ ψ j ( y ) ∣ H j − 1 ] \bar{\psi}_j(y)=\mathbb{E}[\psi_j(y)\mid\mathcal{H}_{j-1}] ψ ˉ j ( y ) = E [ ψ j ( y ) ∣ H j − 1 ] . Fresh query randomness is independent of this private rule, and both loss and first moment commute with averaging over it. The drift proof therefore applies to ψ ˉ j \bar{\psi}_j ψ ˉ j . The conditional covariance bound still uses the actual bounded answer, and the validation proof uses the actual realized loss. This is the version used by the sufficient-statistic attack.
Separating measurements
We now specialize to the general attack, with Σ = R R T ∈ K λ \Sigma=RR^{\mathsf T}\in\mathcal{K}_\lambda Σ = R R T ∈ K λ and 1 / m < λ ≤ 1 / 2 1/m<\lambda\le1/2 1/ m < λ ≤ 1/2 . Thus q 0 = ( 1 − λ ) / ( m − 1 ) ≥ 1 / ( 2 m ) q_0=(1-\lambda)/(m-1)\ge1/(2m) q 0 = ( 1 − λ ) / ( m − 1 ) ≥ 1/ ( 2 m ) . Use the drift decomposition of Section B.3, with conditioning on F j − 1 \mathcal{F}_{j-1} F j − 1 .
The gain lemma controls the component along h R h_R h R , while the responder can influence the other components. The next inequality shows that these other components cannot eliminate separation from the comparator. Let Σ ⋆ ∈ K λ \Sigma_\star\in\mathcal{K}_\lambda Σ ⋆ ∈ K λ be the comparator and set X ⋆ = R − 1 Σ ⋆ R − T X_\star=R^{-1}\Sigma_\star R^{-\mathsf T} X ⋆ = R − 1 Σ ⋆ R − T .
Lemma B.8 (Comparator separation). For every z ∈ im ( R T A M T ) z \in\operatorname{im}(R^{\mathsf T}A_M^{\mathsf T}) z ∈ im ( R T A M T ) ,
z T X ⋆ z ≥ V ( Σ ⋆ ) V ( Σ ) ⟨ h R , z ⟩ 2 . (46) z^{\mathsf T}X_\star z \ge\frac{\mathcal{V}(\Sigma_\star)}{\mathcal{V}(\Sigma)}\langle h_R,z\rangle^2. \tag*{(46)} z T X ⋆ z ≥ V ( Σ ) V ( Σ ⋆ ) ⟨ h R , z ⟩ 2 . (46)
Proof. Write z = R T A M T ξ z=R^{\mathsf T}A_M^{\mathsf T}\xi z = R T A M T ξ for some ξ ∈ R k \xi\in\mathbb{R}^k ξ ∈ R k . Since A h ∈ im ( K Σ ) A_h \in\operatorname{im}(K_\Sigma) A h ∈ im ( K Σ ) ,
⟨ h R , z ⟩ = V ( Σ ) a Σ T Σ A M T ξ = V ( Σ ) A h T K Σ † K Σ ξ = V ( Σ ) ξ T A h , z T X ⋆ z = ξ T K Σ ⋆ ξ . \langle h_R,z\rangle=\sqrt{\mathcal{V}(\Sigma)}a_\Sigma^{\mathsf T}\Sigma A_M^{\mathsf T}\xi=\sqrt{\mathcal{V}(\Sigma)}A_h^{\mathsf T}K_\Sigma^\dagger K_\Sigma\xi=\sqrt{\mathcal{V}(\Sigma)}\xi^{\mathsf T}A_h,\qquad z^{\mathsf T}X_\star z=\xi^{\mathsf T}K_{\Sigma_\star}\xi. ⟨ h R , z ⟩ = V ( Σ ) a Σ T Σ A M T ξ = V ( Σ ) A h T K Σ † K Σ ξ = V ( Σ ) ξ T A h , z T X ⋆ z = ξ T K Σ ⋆ ξ .
Cauchy–Schwarz gives
( ξ T A h ) 2 = ( ξ T K Σ ⋆ † 1 / 2 K Σ ⋆ † 1 / 2 A h ) 2 ≤ ( ξ T K Σ ⋆ ξ ) I ( Σ ⋆ ) = z T X ⋆ z V ( Σ ⋆ ) , (\xi^{\mathsf T}A_h)^2=(\xi^{\mathsf T}K_{\Sigma_\star}^{\dagger1/2}K_{\Sigma_\star}^{\dagger1/2}A_h)^2\le(\xi^{\mathsf T}K_{\Sigma_\star}\xi)\mathcal{I}(\Sigma_\star)=\frac{z^{\mathsf T}X_\star z}{\mathcal{V}(\Sigma_\star)}, ( ξ T A h ) 2 = ( ξ T K Σ ⋆ † 1/2 K Σ ⋆ † 1/2 A h ) 2 ≤ ( ξ T K Σ ⋆ ξ ) I ( Σ ⋆ ) = V ( Σ ⋆ ) z T X ⋆ z ,
so z T X ⋆ z ≥ V ( Σ ⋆ ) ( ξ T A h ) 2 = ( V ( Σ ⋆ ) / V ( Σ ) ) ⟨ h R , z ⟩ 2 z^{\mathsf T}X_\star z\ge\mathcal{V}(\Sigma_\star)(\xi^{\mathsf T}A_h)^2=(\mathcal{V}(\Sigma_\star)/\mathcal{V}(\Sigma))\langle h_R,z\rangle^2 z T X ⋆ z ≥ V ( Σ ⋆ ) ( ξ T A h ) 2 = ( V ( Σ ⋆ ) / V ( Σ )) ⟨ h R , z ⟩ 2 .
It remains to transfer separation from the conditional means to the observed sum S r = M r + N r S_r=M_r+N_r S r = M r + N r . The covariance floor controls the sampling error in the comparator’s quadratic form:
tr X ⋆ = tr ( Σ ⋆ Σ − 1 ) ≤ tr Σ ⋆ q 0 = 1 q 0 ≤ 2 m . (47) \operatorname{tr}X_\star=\operatorname{tr}(\Sigma_\star\Sigma^{-1})\le\frac{\operatorname{tr}\Sigma_\star}{q_0}=\frac{1}{q_0}\le2m. \tag*{(47)} tr X ⋆ = tr ( Σ ⋆ Σ − 1 ) ≤ q 0 tr Σ ⋆ = q 0 1 ≤ 2 m . (47)
This bound lets us handle dependence between M r M_r M r and N r N_r N r using only martingale second moments.
Lemma B.9 (A measurement from the observed sum). Run one round of r ≥ 48 m r\ge48m r ≥ 48 m queries at Σ = R R T \Sigma=RR^{\mathsf T} Σ = R R T . Let F s t a r t \mathcal{F}_{\mathrm{start}} F start contain the full execution history and the announced covariance before the round’s first query, and let X ⋆ ⪰ 0 X_\star\succeq0 X ⋆ ⪰ 0 be determined by this information with tr X ⋆ ≤ 2 m \operatorname{tr}X_\star\le2m tr X ⋆ ≤ 2 m . Set
q = S r / ∥ S r ∥ 2 , (48) q=S_r/\lVert S_r\rVert_2, \tag*{(48)} q = S r / ∥ S r ∥ 2 , (48) choosing any unit vector if S r = 0 S_r=0 S r = 0 . For every responder there is an event G \mathcal{G} G such that, for every L ≥ 4 L\ge4 L ≥ 4 ,
Pr [ G ∣ F s t a r t ] ≥ p c u t and q T X ⋆ q ≥ c c u t L on G ∩ { M r T X ⋆ M r ≥ r 2 L } , (49) \Pr[\mathcal{G}\mid\mathcal{F}_{\mathrm{start}}]\ge p_{\mathrm{cut}}\qquad\text{and}\qquad q^{\mathsf T}X_\star q\ge c_{\mathrm{cut}}L\text{ on }\mathcal{G}\cap\{M_r^{\mathsf T}X_\star M_r\ge r^2L\}, \tag*{(49)} Pr [ G ∣ F start ] ≥ p cut and q T X ⋆ q ≥ c cut L on G ∩ { M r T X ⋆ M r ≥ r 2 L } , (49) where one may take p c u t = 1 / 2 p_{\mathrm{cut}}=1/2 p cut = 1/2 and c c u t = 1 / 16 c_{\mathrm{cut}}=1/16 c cut = 1/16 .
The probability is conditional on the information before the round. We do not condition on accuracy or acceptance, which may be correlated with G \mathcal{G} G . The implication on the intersection in (49) is what the entropy argument uses.
Proof. All expectations and probabilities are conditional on F s t a r t \mathcal{F}_{\mathrm{start}} F start . By (43) , the martingale differences have conditional covariance at most I m I_m I m , so
E ∥ N r ∥ 2 2 ≤ r m , E [ N r T X ⋆ N r ] ≤ r tr X ⋆ ≤ 2 r m . \mathbb{E}\lVert N_r\rVert_2^2\le rm,\qquad\mathbb{E}[N_r^{\mathsf T}X_\star N_r]\le r\operatorname{tr}X_\star\le2rm. E ∥ N r ∥ 2 2 ≤ r m , E [ N r T X ⋆ N r ] ≤ r tr X ⋆ ≤ 2 r m .
Define
G = { ∥ N r ∥ 2 2 + N r T X ⋆ N r ≤ r 2 } . \mathcal{G}=\{\lVert N_r\rVert_2^2+N_r^{\mathsf T}X_\star N_r\le r^2\}. G = {∥ N r ∥ 2 2 + N r T X ⋆ N r ≤ r 2 } .
Markov’s inequality and r ≥ 48 m r\ge48m r ≥ 48 m give Pr [ G ] ≥ 1 − 3 m / r ≥ 15 / 16 ≥ p c u t \Pr[\mathcal{G}]\ge1-3m/r\ge15/16\ge p_{\mathrm{cut}} Pr [ G ] ≥ 1 − 3 m / r ≥ 15/16 ≥ p cut . Write ∥ v ∥ ⋆ = ( v T X ⋆ v ) 1 / 2 \lVert v\rVert_\star=(v^{\mathsf T}X_\star v)^{1/2} ∥ v ∥ ⋆ = ( v T X ⋆ v ) 1/2 . On G \mathcal{G} G , both ∥ N r ∥ 2 \lVert N_r\rVert_2 ∥ N r ∥ 2 and ∥ N r ∥ ⋆ \lVert N_r\rVert_\star ∥ N r ∥ ⋆ are at most r r r . Since ∥ M r ∥ 2 ≤ r \lVert M_r\rVert_2\le r ∥ M r ∥ 2 ≤ r by Lemma B.6, we have ∥ S r ∥ 2 ≤ 2 r \lVert S_r\rVert_2\le2r ∥ S r ∥ 2 ≤ 2 r . Whenever ∥ M r ∥ ⋆ ≥ r L \lVert M_r\rVert_\star\ge r\sqrt{L} ∥ M r ∥ ⋆ ≥ r L with L ≥ 4 L\ge4 L ≥ 4 , the triangle inequality gives
∥ S r ∥ ⋆ ≥ r ( L − 1 ) ≥ 1 2 r L . \lVert S_r\rVert_\star\ge r(\sqrt{L}-1)\ge\tfrac{1}{2}r\sqrt{L}. ∥ S r ∥ ⋆ ≥ r ( L − 1 ) ≥ 2 1 r L .
In particular, S r ≠ 0 S_r \ne0 S r = 0 on this intersection, and
q ⊤ X ⋆ q = ∥ S r ∥ ∗ 2 ∥ S r ∥ 2 2 ≥ L 16 . q^\top X_\star q = \frac{\lVert S_r\rVert_\ast^2}{\lVert S_r\rVert_2^2} \ge\frac{L}{16}. q ⊤ X ⋆ q = ∥ S r ∥ 2 2 ∥ S r ∥ ∗ 2 ≥ 16 L .
No independence between M r M_r M r and N r N_r N r is required.
To obtain separation from the comparator, we require the comparator margin
g 2 V ( Σ ⋆ ) ≥ C m a r g : = 8 p c u t c c u t = 256 , (50) g^2\mathcal{V}(\Sigma_\star) \ge C_{\mathrm{marg}} := \frac{8}{p_{\mathrm{cut}}c_{\mathrm{cut}}} = 256, \tag*{(50)} g 2 V ( Σ ⋆ ) ≥ C marg := p cut c cut 8 = 256 , (50)
where g = c g c 2 / α g = c_g c^2/\alpha g = c g c 2 / α is defined in Lemma 4.1, and p c u t = 1 / 2 p_{\mathrm{cut}} = 1/2 p cut = 1/2 and c c u t = 1 / 16 c_{\mathrm{cut}} = 1/16 c cut = 1/16 are the constants from Lemma B.9 . By Corollary B.5 , this margin also makes the comparator universally hard for the signal-gap task at loss level δ 0 \delta_0 δ 0 . The attacker need not reach or identify this comparator.
We now express separation in terms of the rank-one measurement used by the algorithm. For Σ = R R ⊤ \Sigma= RR^\top Σ = R R ⊤ , write X ⋆ = R − 1 Σ ⋆ R − ⊤ X_\star= R^{-1}\Sigma_\star R^{-\top} X ⋆ = R − 1 Σ ⋆ R − ⊤ and, for a unit vector q q q , set
a = R − ⊤ q , Z ( q ; Σ ) = q 0 a a ⊤ , a = R^{-\top}q,\qquad Z(q;\Sigma) = q_0aa^\top, a = R − ⊤ q , Z ( q ; Σ ) = q 0 a a ⊤ ,
as in (11) .
Lemma B.10 (Normalized rank-one separator). *For every unit q q q and every Σ ∈ K λ \Sigma\in\mathcal{K}_\lambda Σ ∈ K λ ,
0 ⪯ Z ( q ; Σ ) ⪯ I m , ⟨ Σ , Z ( q ; Σ ) ⟩ = q 0 , ⟨ Σ ⋆ , Z ( q ; Σ ) ⟩ = q 0 q ⊤ X ⋆ q . (51) 0 \preceq Z(q;\Sigma) \preceq I_m,\qquad\langle\Sigma,Z(q;\Sigma)\rangle= q_0,\qquad\langle\Sigma_\star,Z(q;\Sigma)\rangle= q_0q^\top X_\star q. \tag*{(51)} 0 ⪯ Z ( q ; Σ ) ⪯ I m , ⟨ Σ , Z ( q ; Σ )⟩ = q 0 , ⟨ Σ ⋆ , Z ( q ; Σ )⟩ = q 0 q ⊤ X ⋆ q . (51) Proof. Since a ⊤ Σ a = q ⊤ q = 1 a^\top\Sigma a = q^\top q = 1 a ⊤ Σ a = q ⊤ q = 1 and Σ ⪰ q 0 I m \Sigma\succeq q_0I_m Σ ⪰ q 0 I m , q 0 ∥ a ∥ 2 2 ≤ 1 q_0\lVert a\rVert_2^2 \le1 q 0 ∥ a ∥ 2 2 ≤ 1 . Hence q 0 a a ⊤ ⪯ I m q_0aa^\top\preceq I_m q 0 a a ⊤ ⪯ I m and ⟨ Σ , q 0 a a ⊤ ⟩ = q 0 \langle\Sigma,q_0aa^\top\rangle= q_0 ⟨ Σ , q 0 a a ⊤ ⟩ = q 0 . Finally, a ⊤ Σ ⋆ a = q ⊤ R − 1 Σ ⋆ R − ⊤ q = q ⊤ X ⋆ q a^\top\Sigma_\star a = q^\top R^{-1}\Sigma_\star R^{-\top}q = q^\top X_\star q a ⊤ Σ ⋆ a = q ⊤ R − 1 Σ ⋆ R − ⊤ q = q ⊤ X ⋆ q .
Combining the drift, comparator separation, and sampling-error bounds gives the separating measurement needed for the entropy argument.
Lemma B.11 (Separation from an accurate round). *Let the comparator Σ ⋆ \Sigma_\star Σ ⋆ satisfy the margin (50) , and let G G G be the event of Lemma B.9 for the round, with L = C m a r g L = C_{\mathrm{marg}} L = C marg and X ⋆ = R − 1 Σ ⋆ R − ⊤ X_\star= R^{-1}\Sigma_\star R^{-\top} X ⋆ = R − 1 Σ ⋆ R − ⊤ ; (47) verifies its trace assumption. On the event r − 1 ∑ j ϵ j ≤ δ 0 r^{-1}\sum_j\epsilon_j \le\delta_0 r − 1 ∑ j ϵ j ≤ δ 0 , we have
M r ⊤ X ⋆ M r ≥ r 2 g 2 V ( Σ ⋆ ) ≥ r 2 C m a r g . (52) M_r^\top X_\star M_r \ge r^2g^2\mathcal{V}(\Sigma_\star) \ge r^2C_{\mathrm{marg}}. \tag*{(52)} M r ⊤ X ⋆ M r ≥ r 2 g 2 V ( Σ ⋆ ) ≥ r 2 C marg . (52) On the intersection of this event with G G G , the measurement direction satisfies
q ⊤ X ⋆ q ≥ κ : = c c u t C m a r g = 8 p c u t = 16. (53) q^\top X_\star q \ge\kappa:= c_{\mathrm{cut}}C_{\mathrm{marg}} = \frac{8}{p_{\mathrm{cut}}} = 16. \tag*{(53)} q ⊤ X ⋆ q ≥ κ := c cut C marg = p cut 8 = 16. (53) Proof. By Lemma B.6 , M r ∈ im ( R ⊤ A M ⊤ ) M_r \in\operatorname{im}(R^\top A_M^\top) M r ∈ im ( R ⊤ A M ⊤ ) and ⟨ h R , M r ⟩ ≥ r g V ( Σ ) \langle h_R,M_r\rangle\ge r g\sqrt{\mathcal{V}(\Sigma)} ⟨ h R , M r ⟩ ≥ r g V ( Σ ) , so Lemma B.8 at z = M r z=M_r z = M r gives M r ⊤ X ⋆ M r ≥ V ( Σ ⋆ ) r 2 g 2 M_r^\top X_\star M_r \ge\mathcal{V}(\Sigma_\star)r^2g^2 M r ⊤ X ⋆ M r ≥ V ( Σ ⋆ ) r 2 g 2 , and the margin gives the second inequality in (52) . This is the hypothesis of (49) with L = C m a r g L = C_{\mathrm{marg}} L = C marg .
Restoring the round index t t t , every measurement satisfies
0 ⪯ Z t ⪯ I m , ⟨ Σ t , Z t ⟩ = q 0 . 0 \preceq Z_t \preceq I_m,\qquad\langle\Sigma_t,Z_t\rangle= q_0. 0 ⪯ Z t ⪯ I m , ⟨ Σ t , Z t ⟩ = q 0 .
On the validation event of Lemma B.7 , an accepted round also satisfies
⟨ Σ ⋆ , Z t ⟩ ≥ 16 q 0 \langle\Sigma_\star,Z_t\rangle\ge16q_0 ⟨ Σ ⋆ , Z t ⟩ ≥ 16 q 0
whenever its sampling event G t G_t G t occurs. Conditional on the information before the round, G t G_t G t has probability at least 1 / 2 1/2 1/2 . These are the properties used in the entropy argument below.
Entropy progress and termination
We prove the rejection guarantee used in Section B.1. For any failure probability 0 < δ < 1 0 < \delta< 1 0 < δ < 1 , use the round parameters (22) .
Proposition B.12 (Rejection within the round budget). Suppose 1 / m < λ ≤ 1 / 2 1/m < \lambda\le1/2 1/ m < λ ≤ 1/2 , A h ∈ im ( A M ) ∖ { 0 } A_h \in\operatorname{im}(A_M) \setminus\{0\} A h ∈ im ( A M ) ∖ { 0 } , and the spike comparator of (33) satisfies g 2 V ( Σ ⋆ ) ≥ C m a r g = 256 g^2 \mathcal{V}(\Sigma_\star) \ge C_{\mathrm{marg}} = 256 g 2 V ( Σ ⋆ ) ≥ C marg = 256 . Then Algorithm 1, with the parameters (22) , rejects a round within T max T_{\max} T m a x rounds with probability at least 1 − δ 1-\delta 1 − δ against every informed signal-gap responder.
We now show how these measurements control the nonnegative potential D ( Σ ⋆ ∥ Σ t ) D(\Sigma_\star\mathbin\Vert\Sigma_t) D ( Σ ⋆ ∥ Σ t ) .
Lemma B.13 (One multiplicative-weights step). Let Σ = R R T \Sigma= RR^{\mathsf T} Σ = R R T and Σ ⋆ \Sigma_\star Σ ⋆ lie in K λ \mathcal{K}_\lambda K λ , let q q q be a unit vector, and let Σ + \Sigma^+ Σ + be the update along Z = Z ( q ; Σ ) Z = Z(q;\Sigma) Z = Z ( q ; Σ ) with step η > 0 \eta> 0 η > 0 , with unprojected iterate Σ ^ + \widehat{\Sigma}^+ Σ + . Then
D ( Σ ⋆ ∥ Σ + ) ≤ D ( Σ ⋆ ∥ Σ ) − η q 0 q T X ⋆ q + ( e η − 1 ) q 0 . (54) D(\Sigma_\star\mathbin\Vert\Sigma^+) \le D(\Sigma_\star\mathbin\Vert\Sigma) - \eta q_0 q^{\mathsf T}X_\star q + (e^\eta- 1)q_0. \tag*{(54)} D ( Σ ⋆ ∥ Σ + ) ≤ D ( Σ ⋆ ∥ Σ ) − η q 0 q T X ⋆ q + ( e η − 1 ) q 0 . (54)
For η = 1 / 2 \eta= 1/2 η = 1/2 the potential therefore increases by less than 2 q 0 2q_0 2 q 0 after any measurement, and decreases by more than 7 q 0 7q_0 7 q 0 after a measurement with q T X ⋆ q ≥ κ = 16 q^{\mathsf T}X_\star q \ge\kappa= 16 q T X ⋆ q ≥ κ = 16 .
Proof. Since Σ ⋆ ∈ K λ \Sigma_\star\in\mathcal{K}_\lambda Σ ⋆ ∈ K λ , the Pythagorean inequality for the relative-entropy projection [61 Section 5] gives
D ( Σ ⋆ ∥ Σ ^ + ) ≥ D ( Σ ⋆ ∥ Σ + ) + D ( Σ + ∥ Σ ^ + ) ≥ D ( Σ ⋆ ∥ Σ + ) . D(\Sigma_\star\mathbin\Vert\widehat{\Sigma}^+) \ge D(\Sigma_\star\mathbin\Vert\Sigma^+) + D(\Sigma^+\mathbin\Vert\widehat{\Sigma}^+) \ge D(\Sigma_\star\mathbin\Vert\Sigma^+). D ( Σ ⋆ ∥ Σ + ) ≥ D ( Σ ⋆ ∥ Σ + ) + D ( Σ + ∥ Σ + ) ≥ D ( Σ ⋆ ∥ Σ + ) .
The first inequality follows directly from the first-order optimality condition for (14) . Writing Z = tr exp ( log Σ + η Z ) \mathcal{Z} = \operatorname{tr}\exp(\log\Sigma+ \eta Z) Z = tr exp ( log Σ + η Z ) and using tr Σ ⋆ = 1 \operatorname{tr}\Sigma_\star= 1 tr Σ ⋆ = 1 ,
D ( Σ ⋆ ∥ Σ ^ + ) = D ( Σ ⋆ ∥ Σ ) − η ⟨ Σ ⋆ , Z ⟩ + log Z . D(\Sigma_\star\mathbin\Vert\widehat{\Sigma}^+) = D(\Sigma_\star\mathbin\Vert\Sigma) - \eta\langle\Sigma_\star,Z\rangle+ \log\mathcal{Z}. D ( Σ ⋆ ∥ Σ + ) = D ( Σ ⋆ ∥ Σ ) − η ⟨ Σ ⋆ , Z ⟩ + log Z .
Golden–Thompson and 0 ⪯ Z ⪯ I m 0 \preceq Z \preceq I_m 0 ⪯ Z ⪯ I m , which gives e η Z ⪯ I m + ( e η − 1 ) Z e^{\eta Z} \preceq I_m + (e^\eta- 1)Z e η Z ⪯ I m + ( e η − 1 ) Z , imply
Z ≤ tr ( Σ e η Z ) ≤ 1 + ( e η − 1 ) ⟨ Σ , Z ⟩ = 1 + ( e η − 1 ) q 0 . \mathcal{Z} \le\operatorname{tr}(\Sigma e^{\eta Z}) \le1 + (e^\eta- 1)\langle\Sigma,Z\rangle= 1 + (e^\eta- 1)q_0. Z ≤ tr ( Σ e η Z ) ≤ 1 + ( e η − 1 ) ⟨ Σ , Z ⟩ = 1 + ( e η − 1 ) q 0 .
Hence log Z ≤ ( e η − 1 ) q 0 \log\mathcal{Z} \le(e^\eta- 1)q_0 log Z ≤ ( e η − 1 ) q 0 , and Lemma B.10 gives ⟨ Σ ⋆ , Z ⟩ = q 0 q T X ⋆ q \langle\Sigma_\star,Z\rangle= q_0q^{\mathsf T}X_\star q ⟨ Σ ⋆ , Z ⟩ = q 0 q T X ⋆ q . For η = 1 / 2 \eta= 1/2 η = 1/2 , e η − 1 < 0.65 e^\eta- 1 < 0.65 e η − 1 < 0.65 and 8 − 0.65 > 7 8 - 0.65 > 7 8 − 0.65 > 7 .
The starting point of the potential is small. For the spike comparator Σ ⋆ = Σ v ⋆ \Sigma_\star= \Sigma_{v_\star} Σ ⋆ = Σ v ⋆ ,
D ( Σ ⋆ ∥ I m / m ) = λ log ( m λ ) + ( 1 − λ ) log ( m q 0 ) ≤ λ log ( m λ ) , (55) D(\Sigma_\star\mathbin\Vert I_m/m) = \lambda\log(m\lambda) + (1-\lambda)\log(mq_0) \le\lambda\log(m\lambda), \tag*{(55)} D ( Σ ⋆ ∥ I m / m ) = λ log ( mλ ) + ( 1 − λ ) log ( m q 0 ) ≤ λ log ( mλ ) , (55)
since m q 0 ≤ 1 mq_0 \le1 m q 0 ≤ 1 when λ ≥ 1 / m \lambda\ge1/m λ ≥ 1/ m .
Proof of Proposition B.12. Write T = T max T = T_{\max} T = T m a x and X ⋆ , t = R t T Σ ⋆ R t X_{\star,t} = R_t^{\mathsf T}\Sigma_\star R_t X ⋆ , t = R t T Σ ⋆ R t . Let E v a l \mathcal{E}_{\mathrm{val}} E val be the event that Lemma B.7 holds in every executed round. Using δ r d = δ / ( 2 T ) \delta_{\mathrm{rd}} = \delta/(2T) δ rd = δ / ( 2 T ) and taking a union bound gives Pr [ E v a l ] ≥ 1 − δ / 2 \Pr[\mathcal{E}_{\mathrm{val}}] \ge1-\delta/2 Pr [ E val ] ≥ 1 − δ /2 .
For each round t = 0 , … , T − 1 t = 0,\ldots,T-1 t = 0 , … , T − 1 , let G t \mathcal{G}_t G t be the event supplied by Lemma B.9, with L = C m a r g L = C_{\mathrm{marg}} L = C marg and comparator X ⋆ , t X_{\star,t} X ⋆ , t , whose trace is at most 2 m 2m 2 m by (47) . The event G t \mathcal{G}_t G t is defined from the round’s sampling error, whether or not validation accepts the round. After the attack stops, set all later G t \mathcal{G}_t G t to the whole sample space. Each indicator then has conditional mean at least p c u t p_{\mathrm{cut}} p cut given the information before its round. The multiplicative Chernoff bound for adapted indicators gives
Pr [ ∑ t = 0 T − 1 1 G t < p c u t T 2 ] ≤ e − p c u t T / 8 ≤ δ 2 , \Pr\left[\sum_{t=0}^{T-1}1_{\mathcal{G}_t} < \frac{p_{\mathrm{cut}}T}{2}\right] \le e^{-p_{\mathrm{cut}}T/8} \le\frac{\delta}{2}, Pr [ t = 0 ∑ T − 1 1 G t < 2 p cut T ] ≤ e − p cut T /8 ≤ 2 δ ,
where the last inequality uses T ≥ 16 log ( 2 / δ ) T \ge16\log(2/\delta) T ≥ 16 log ( 2/ δ ) . Denote the complementary event by E c u t \mathcal{E}_{\mathrm{cut}} E cut . This bound is unconditional on validation; we intersect the two good events only after bounding their probabilities.
Suppose all T T T rounds are accepted on E v a l ∩ E c u t \mathcal{E}_{\mathrm{val}} \cap\mathcal{E}_{\mathrm{cut}} E val ∩ E cut . Their average predictable losses are below δ 0 \delta_0 δ 0 . By Lemma B.11 , q ^ t T X ⋆ , t q ^ t ≥ κ = 16 \widehat{q}_t^{\mathsf{T}}X_{\star,t}\widehat{q}_t \ge\kappa= 16 q t T X ⋆ , t q t ≥ κ = 16 whenever G t \mathcal{G}_t G t occurs. There are at least p c u t T / 2 p_{\mathrm{cut}}T/2 p cut T /2 such rounds. Summing (54) , and using nonnegativity of the Rayleigh quotient in the other rounds, gives
0 ≤ D ( Σ ⋆ ∥ Σ T ) ≤ D ( Σ ⋆ ∥ I m / m ) − q 0 κ p c u t T 2 + 0.65 q 0 T < λ log ( m λ ) − q 0 T < 0. \begin{aligned}
0 \le D(\Sigma_\star\mathbin{\|} \Sigma_T) \le D(\Sigma_\star\mathbin{\|} I_m/m) - \frac{q_0\kappa p_{\mathrm{cut}}T}{2} + 0.65q_0T \\
&< \lambda\log(m\lambda) - q_0T < 0.
\end{aligned} 0 ≤ D ( Σ ⋆ ∥ Σ T ) ≤ D ( Σ ⋆ ∥ I m / m ) − 2 q 0 κ p cut T + 0.65 q 0 T < λ log ( mλ ) − q 0 T < 0.
Here (55) bounds the initial potential, κ p c u t / 4 = 2 \kappa p_{\mathrm{cut}}/4 = 2 κ p cut /4 = 2 , and T > λ log ( m λ ) / q 0 T > \lambda\log(m\lambda)/q_0 T > λ log ( mλ ) / q 0 . This contradiction proves that a round is rejected with probability at least 1 − δ 1-\delta 1 − δ .
From signal-gap loss to norm errors
We transfer signal-gap guarantees to norm estimation and binary norm-gap queries by controlling the fluctuations of the noise norm. By (6) , the squared query norm differs from w 2 + c 2 w^2+c^2 w 2 + c 2 by c 2 ( ∥ u ∥ 2 2 − 1 ) c^2(\lVert u\rVert_2^2-1) c 2 (∥ u ∥ 2 2 − 1 ) . Since tr Σ = 1 \operatorname{tr}\Sigma=1 tr Σ = 1 ,
E ∥ u ∥ 2 2 = 1 , Var ( c 2 ( ∥ u ∥ 2 2 − 1 ) ) = 2 c 4 tr ( Σ 2 ) . \mathbb{E}\lVert u\rVert_2^2=1,\qquad\operatorname{Var}\left(c^2(\lVert u\rVert_2^2-1)\right)=2c^4\operatorname{tr}(\Sigma^2). E ∥ u ∥ 2 2 = 1 , Var ( c 2 (∥ u ∥ 2 2 − 1 ) ) = 2 c 4 tr ( Σ 2 ) .
The admissibility bound of Definition B.14 controls these fluctuations relative to the signal gap.
Definition B.14 (Norm-admissible covariance). For ρ ∈ [ 1 / m , 1 ] \rho\in[1/m,1] ρ ∈ [ 1/ m , 1 ] , a positive semidefinite trace-one covariance Σ \Sigma Σ is ρ \rho ρ -admissible if tr ( Σ 2 ) ≤ ρ \operatorname{tr}(\Sigma^2)\le\rho tr ( Σ 2 ) ≤ ρ .
The following reduction controls both expected losses and the errors observed in an interaction. For fixed c c c and concentration-failure probability ε n c \varepsilon_{\mathrm{nc}} ε nc , it requires an admissibility bound that is a sufficiently small multiple of α 2 / c 4 \alpha^2/c^4 α 2 / c 4 .
Lemma B.15 (Norm-to-gap reduction). There is a constant c e r r = c e r r ( c ) > 0 c_{\mathrm{err}}=c_{\mathrm{err}}(c)>0 c err = c err ( c ) > 0 and, for every ε n c ∈ ( 0 , 1 ) \varepsilon_{\mathrm{nc}}\in(0,1) ε nc ∈ ( 0 , 1 ) , a constant c ρ = c ρ ( ε n c ) > 0 c_\rho=c_\rho(\varepsilon_{\mathrm{nc}})>0 c ρ = c ρ ( ε nc ) > 0 such that the following holds. Suppose 0 < α ≤ c / 20 0<\alpha\le c/20 0 < α ≤ c /20 and Σ \Sigma Σ is ρ \rho ρ -admissible with
ρ ≤ c ρ α 2 c 4 . (56) \rho\le c_\rho\frac{\alpha^2}{c^4}. \tag*{(56)} ρ ≤ c ρ c 4 α 2 . (56) For a query v = w e h + c ι M u v=we_h+c\iota_Mu v = w e h + c ι M u and a norm estimate r ^ ≥ 0 \widehat r\ge0 r ≥ 0 , use the thresholded response b b b from (8) and the events
E : = { c 2 ∣ ∥ u ∥ 2 2 − 1 ∣ ≤ α / 2 } , A : = { ∣ r ^ − ∥ v ∥ 2 ∣ ≤ c e r r α ∥ v ∥ 2 } . \mathcal{E}:=\{c^2\lvert\lVert u\rVert_2^2-1\rvert\le\alpha/2\},\qquad\mathcal{A}:=\{\lvert\widehat r-\lVert v\rVert_2\rvert\le c_{\mathrm{err}}\alpha\lVert v\rVert_2\}. E := { c 2 ∣∥ u ∥ 2 2 − 1 ∣ ≤ α /2 } , A := {∣ r − ∥ v ∥ 2 ∣ ≤ c err α ∥ v ∥ 2 } . Then the per-query signal-gap loss (5) satisfies, pointwise,
L ( b , w ) ≤ 1 A c + 1 E c , Pr u ∼ N ( 0 , Σ ) [ E c ] ≤ ε n c . (57) \mathcal{L}(b,w)\le\mathbf{1}_{\mathcal{A}^{c}}+\mathbf{1}_{\mathcal{E}^{c}},\qquad\Pr_{u\sim\mathcal{N}(0,\Sigma)}[\mathcal{E}^{c}]\le\varepsilon_{\mathrm{nc}}. \tag*{(57)} L ( b , w ) ≤ 1 A c + 1 E c , u ∼ N ( 0 , Σ ) Pr [ E c ] ≤ ε nc . (57) Consequently, for v ∼ D Σ v\sim D_\Sigma v ∼ D Σ and any norm estimator r ^ = r ^ ( A v ) \widehat r=\widehat r(Av) r = r ( A v ) , let ψ ( y ) \psi(y) ψ ( y ) denote its thresholded response rule. Then
L Σ ( ψ ) ≤ Pr [ ∣ r ^ ( A v ) − ∥ v ∥ 2 ∣ > c e r r α ∥ v ∥ 2 ] + ε n c , (58) \mathcal{L}_\Sigma(\psi)\le\Pr[\lvert\widehat r(Av)-\lVert v\rVert_2\rvert>c_{\mathrm{err}}\alpha\lVert v\rVert_2]+\varepsilon_{\mathrm{nc}}, \tag*{(58)} L Σ ( ψ ) ≤ Pr [∣ r ( A v ) − ∥ v ∥ 2 ∣ > c err α ∥ v ∥ 2 ] + ε nc , (58) and if every signal-gap response rule has loss at least δ \delta δ at Σ \Sigma Σ , then every norm estimator has relative error larger than c e r r α c_{\mathrm{err}}\alpha c err α with probability at least δ − ε n c \delta-\varepsilon_{\mathrm{nc}} δ − ε nc .
Corollary B.16 (Binary norm-gap responses). Under the hypotheses of Lemma B.15 , use the fixed thresholds (7) . These thresholds are independent of Σ \Sigma Σ and satisfy U / L = 1 + Θ ( α ) U/L = 1 + \Theta(\alpha) U / L = 1 + Θ ( α ) for fixed c c c . For every binary answer b ∈ { − 1 , + 1 } b \in\{-1,+1\} b ∈ { − 1 , + 1 } , the signal-gap loss satisfies
L ( b , w ) ≤ e n g ( b , v ) + 1 E ϵ c , Pr [ E c ] ≤ ϵ n c , (59) \mathcal{L}(b,w) \le e_{\mathrm{ng}}(b,v) + \mathbf{1}_{\mathcal{E}}\epsilon_c,\qquad\Pr[\mathcal{E}^{c}] \le\epsilon_{\mathrm{nc}}, \tag*{(59)} L ( b , w ) ≤ e ng ( b , v ) + 1 E ϵ c , Pr [ E c ] ≤ ϵ nc , (59) where E \mathcal{E} E is the noise-concentration event in Lemma B.15 and e n g e_{\mathrm{ng}} e ng is defined using these thresholds. Consequently, signal-gap loss at least δ \delta δ for every response rule implies norm-gap error probability at least δ − ϵ n c \delta-\epsilon_{\mathrm{nc}} δ − ϵ nc for every binary responder.
Corollary B.17 (Empirical transfer to norm errors). Fix 0 < α ≤ c / 20 0 < \alpha\le c/20 0 < α ≤ c /20 , either norm task, and 0 < ϵ < 1 0 < \epsilon< 1 0 < ϵ < 1 . Use the losses and response conversion of Lemma B.15 and Corollary B.16 . Consider at most N N N adaptive rounds, with queries drawn from D Σ t D_{\Sigma_t} D Σ t as in Round. Each covariance and round length are fixed before that round’s queries are drawn. Suppose
r t ≥ 32 δ 0 2 log N ϵ r_t \ge\frac{32}{\delta_0^2}\log\frac{N}{\epsilon} r t ≥ δ 0 2 32 log ϵ N in every round. Set ϵ n c = δ 0 / 8 \epsilon_{\mathrm{nc}}=\delta_0/8 ϵ nc = δ 0 /8 in Lemma B.15 . With probability at least 1 − ϵ 1-\epsilon 1 − ϵ , simultaneously in every executed round whose covariance satisfies (56) ,
1 r t ∑ j = 1 r t e t , j n o r m ≥ E t r t − δ 0 4 , (60) \frac{1}{r_t}\sum_{j=1}^{r_t} e^{\mathrm{norm}}_{t,j} \ge\frac{E_t}{r_t}-\frac{\delta_0}{4}, \tag*{(60)} r t 1 j = 1 ∑ r t e t , j norm ≥ r t E t − 4 δ 0 , (60) where e t , j n o r m e^{\mathrm{norm}}_{t,j} e t , j norm is the loss for the chosen norm task and E t E_t E t is the realized signal-gap loss sum. In particular, a rejected admissible round contains more than a δ 0 / 4 \delta_0/4 δ 0 /4 fraction of norm-task errors.
Proof. Let F t , j = 1 E t , j c F_{t,j}=\mathbf{1}_{\mathcal{E}_{t,j}^{c}} F t , j = 1 E t , j c indicate failure of the noise-concentration event in Lemma B.15 , and let I t I_t I t indicate that the round’s covariance satisfies (56) . The covariance is fixed before the round, so I t I_t I t is known before each query. Even when admissibility holds only on a later success event, the variables I t F t , j I_tF_{t,j} I t F t , j always have conditional mean at most δ 0 / 8 \delta_0/8 δ 0 /8 . Conditional Hoeffding gives
Pr [ 1 r t ∑ j I t F t , j > δ 0 4 | F s t a r t ] ≤ e − r t δ 0 2 / 32 ≤ ϵ N . \Pr\left[\frac{1}{r_t}\sum_j I_tF_{t,j}>\frac{\delta_0}{4}\,\middle|\,\mathcal{F}_{\mathrm{start}}\right]\le e^{-r_t\delta_0^2/32}\le\frac{\epsilon}{N}. Pr [ r t 1 j ∑ I t F t , j > 4 δ 0 F start ] ≤ e − r t δ 0 2 /32 ≤ N ϵ . A union bound over the executed rounds bounds the failure probability by ϵ \epsilon ϵ . In each admissible round I t = 1 I_t=1 I t = 1 , so summing (57) or (59) proves (60) . Rejection means E t / r t > δ 0 / 2 E_t/r_t>\delta_0/2 E t / r t > δ 0 /2 , giving the final claim. □ \square □
The pointwise reductions also transfer universal hardness by taking expectations. The empirical corollary applies to both attacks: the general attack keeps every covariance admissible, whereas the sufficient-statistic attack establishes admissibility on its success event. No conditioning on that event is needed in the corollary.
Proofs
Proof of Lemma B.15 . Since Var ( ∥ u ∥ 2 2 ) = 2 tr ( Σ 2 ) \operatorname{Var}(\lVert u\rVert_2^2)=2\operatorname{tr}(\Sigma^2) Var (∥ u ∥ 2 2 ) = 2 tr ( Σ 2 ) , Chebyshev’s inequality gives
Pr [ E c ] ≤ 8 c 4 tr ( Σ 2 ) α 2 ≤ 8 c 4 ρ α 2 . \Pr[\mathcal{E}^{c}] \le\frac{8c^4\operatorname{tr}(\Sigma^2)}{\alpha^2}\le\frac{8c^4\rho}{\alpha^2}. Pr [ E c ] ≤ α 2 8 c 4 tr ( Σ 2 ) ≤ α 2 8 c 4 ρ .
We may therefore take
c ρ ( ε n c ) : = ε n c 8 . (61) c_{\rho}(\varepsilon_{\mathrm{nc}}) := \frac{\varepsilon_{\mathrm{nc}}}{8}. \tag*{(61)} c ρ ( ε nc ) := 8 ε nc . (61)
The admissibility bound (56) then ensures Pr [ E c ] ≤ ε n c \Pr[\mathcal{E}^{c}] \le\varepsilon_{\mathrm{nc}} Pr [ E c ] ≤ ε nc . Since α ≤ c / 20 \alpha\le c/20 α ≤ c /20 , Definition 3.1 gives 1 / 2 ≤ w ≤ 1 + α + 10 α / c ≤ 2 + c 1/2 \le w \le1+\alpha+10\alpha/c \le2+c 1/2 ≤ w ≤ 1 + α + 10 α / c ≤ 2 + c . The nominal squared norms w 2 + c 2 w^2+c^2 w 2 + c 2 of the two labeled regimes are separated by ( 1 + α ) 2 − 1 ≥ 2 α (1+\alpha)^2-1 \ge2\alpha ( 1 + α ) 2 − 1 ≥ 2 α , so on E \mathcal{E} E we have ∥ v ∥ 2 2 ≤ 1 + c 2 + α / 2 \lVert v\rVert_2^2 \le1+c^2+\alpha/2 ∥ v ∥ 2 2 ≤ 1 + c 2 + α /2 whenever w ≤ 1 w \le1 w ≤ 1 and ∥ v ∥ 2 2 ≥ 1 + c 2 + 3 α / 2 \lVert v\rVert_2^2 \ge1+c^2+3\alpha/2 ∥ v ∥ 2 2 ≥ 1 + c 2 + 3 α /2 whenever w ≥ 1 + α w \ge1+\alpha w ≥ 1 + α .
Choose c e r r = c e r r ( c ) > 0 c_{\mathrm{err}}=c_{\mathrm{err}}(c)>0 c err = c err ( c ) > 0 so that c e r r c / 20 ≤ 1 c_{\mathrm{err}}c/20 \le1 c err c /20 ≤ 1 and 3 c e r r ( ( 2 + c ) 2 + c 2 + c ) ≤ 1 / 4 3c_{\mathrm{err}}((2+c)^2+c^2+c)\le1/4 3 c err (( 2 + c ) 2 + c 2 + c ) ≤ 1/4 . On A \mathcal{A} A , the first condition gives ∣ r ^ 2 − ∥ v ∥ 2 2 ∣ ≤ 3 c e r r α ∥ v ∥ 2 2 |\widehat r^2-\lVert v\rVert_2^2|\le3c_{\mathrm{err}}\alpha\lVert v\rVert_2^2 ∣ r 2 − ∥ v ∥ 2 2 ∣ ≤ 3 c err α ∥ v ∥ 2 2 . On E \mathcal{E} E , we have ∥ v ∥ 2 2 ≤ ( 2 + c ) 2 + c 2 + c \lVert v\rVert_2^2\le(2+c)^2+c^2+c ∥ v ∥ 2 2 ≤ ( 2 + c ) 2 + c 2 + c , using α ≤ c \alpha\le c α ≤ c . The second condition therefore bounds the squared-norm error by α / 4 \alpha/4 α /4 on A ∩ E \mathcal{A}\cap\mathcal{E} A ∩ E . Hence r ^ 2 ≤ 1 + c 2 + 3 α / 4 \widehat r^2\le1+c^2+3\alpha/4 r 2 ≤ 1 + c 2 + 3 α /4 when w ≤ 1 w\le1 w ≤ 1 and r ^ 2 ≥ 1 + c 2 + 5 α / 4 \widehat r^2\ge1+c^2+5\alpha/4 r 2 ≥ 1 + c 2 + 5 α /4 when w ≥ 1 + α w\ge1+\alpha w ≥ 1 + α , so the thresholded response is correct on both labeled regimes and its per-query loss (5) vanishes. Since the loss never exceeds one, this proves (57) . Taking expectations gives (58) , and rearranging yields the final claim.
Proof of Corollary B.16 . On E \mathcal{E} E , w ≤ 1 w\le1 w ≤ 1 implies ∥ v ∥ 2 ≤ L \lVert v\rVert_2\le L ∥ v ∥ 2 ≤ L , whereas w ≥ 1 + α w\ge1+\alpha w ≥ 1 + α implies ∥ v ∥ 2 2 ≥ ( 1 + α ) 2 + c 2 − α / 2 ≥ U 2 \lVert v\rVert_2^2\ge(1+\alpha)^2+c^2-\alpha/2\ge U^2 ∥ v ∥ 2 2 ≥ ( 1 + α ) 2 + c 2 − α /2 ≥ U 2 . Thus a correct norm-gap answer is also a correct signal-gap answer on E \mathcal{E} E . The signal-gap loss is zero between the signal thresholds and at most one elsewhere, proving (59) . Taking expectations proves the hardness claim. Finally, U / L − 1 = α / ( L ( U + L ) ) = Θ ( α ) U/L-1=\alpha/(L(U+L))=\Theta(\alpha) U / L − 1 = α / ( L ( U + L )) = Θ ( α ) , since L L L and U U U are bounded above and away from zero for fixed c c c and 0 < α ≤ c / 20 0<\alpha\le c/20 0 < α ≤ c /20 .
Remark B.18 (Accuracy when feasible yields a hard distribution). Consider either covariance-update attack with C min / k ≤ α ≤ α 0 C_{\min}/\sqrt{k}\le\alpha\le\alpha_0 C m i n / k ≤ α ≤ α 0 , and fix either norm task. Let R ⋆ ( Σ ) R^\star(\Sigma) R ⋆ ( Σ ) be the infimum expected loss on D Σ \mathcal{D}_{\Sigma} D Σ over measurable response rules using the sketch, even knowing A A A and Σ \Sigma Σ . Let R ‾ t \overline{R}_t R t be the responder’s average conditional error probability in round t t t :
R ‾ t = 1 r t ∑ j = 1 r t p t , j . \overline{R}_t=\frac{1}{r_t}\sum_{j=1}^{r_t}p_{t,j}. R t = r t 1 j = 1 ∑ r t p t , j .
where p t , j p_{t,j} p t , j conditions on F j − 1 \mathcal{F}_{j-1} F j − 1 for the general attack and H j − 1 \mathcal{H}_{j-1} H j − 1 for the sufficient-statistic attack. Suppose the responder maintains error at most δ 0 / 8 \delta_0/8 δ 0 /8 whenever error below δ 0 / 16 \delta_0/16 δ 0 /16 is achievable:
R ⋆ ( Σ t ) < δ 0 / 16 ⟹ R ‾ t ≤ δ 0 / 8. (62) R^\star(\Sigma_t)<\delta_0/16 \quad\Longrightarrow\quad\overline{R}_t\le\delta_0/8. \tag*{(62)} R ⋆ ( Σ t ) < δ 0 /16 ⟹ R t ≤ δ 0 /8. (62)
Then, on the success event of the corresponding attack analysis, the returned distribution satisfies R ⋆ ( Σ t ) ≥ δ 0 / 16 R^\star(\Sigma_t)\ge\delta_0/16 R ⋆ ( Σ t ) ≥ δ 0 /16 and is therefore universally hard for the chosen norm task.
Indeed, on this event a rejected round has average conditional signal-gap loss greater than δ 0 / 4 \delta_0/4 δ 0 /4 . Norm admissibility and Lemma B.15 and Corollary B.16 bound this loss by R ‾ t + δ 0 / 8 \overline{R}_t+\delta_0/8 R t + δ 0 /8 . Thus R ‾ t > δ 0 / 8 \overline{R}_t>\delta_0/8 R t > δ 0 /8 , and (62) implies the claimed hardness.
For α < C min / k \alpha<C_{\min}/\sqrt{k} α < C m i n / k , the isotropic construction of Corollary F.3 already yields a universally hard distribution on its success event, without any additional accuracy condition on the responder.
Analysis of the sufficient-statistic attack
We begin with the parameter choices and proof of Theorem 1.2. The remaining subsections establish alignment and direction estimation, the covariance invariants, and termination with the stated query bound. We reuse the geometry, round lemmas, and norm reduction from Section B; the new ingredient is alignment of the mean signed noise with the signal-estimation direction. The last subsection treats approximate alignment.
Parameters and proof of Theorem 1.2
Parameter choice. Use the constants c c c , c ρ c_{\rho} c ρ , c e r r c_{\mathrm{err}} c err , C min C_{\min} C m i n , α 0 \alpha_0 α 0 and ε n c = δ 0 / 8 \varepsilon_{\mathrm{nc}} = \delta_0/8 ε nc = δ 0 /8 from Section B.1. Choose any prescribed set S ⊆ [ n ] S \subseteq[n] S ⊆ [ n ] of 40 k + 1 40k + 1 40 k + 1 coordinates, choose h h h uniformly from S S S , and put M = S ∖ { h } M = S \setminus\{h\} M = S ∖ { h } and m = 40 k m = 40k m = 40 k . For C min / k ≤ α ≤ α 0 C_{\min}/\sqrt{k} \leq\alpha\leq\alpha_0 C m i n / k ≤ α ≤ α 0 , set
ν 0 = 1 40 k , c R = 3 4 , C c a p = 2 c R c g 2 c 4 , ρ ˉ = C c a p α 2 . (63) \nu_0 = \frac{1}{40k}, \qquad c_R = \frac{3}{4}, \qquad C_{\mathrm{cap}} = \frac{2}{c_R c_g^2 c^4}, \qquad\bar{\rho} = C_{\mathrm{cap}}\alpha^2. \tag*{(63)} ν 0 = 40 k 1 , c R = 4 3 , C cap = c R c g 2 c 4 2 , ρ ˉ = C cap α 2 . (63)
The threshold ρ ˉ \bar{\rho} ρ ˉ is fixed throughout the attack. The constants chosen for the general attack also suffice here: since C λ = 96 C c a p C_{\lambda} = 96C_{\mathrm{cap}} C λ = 96 C cap , the corresponding λ = C λ α 2 \lambda= C_{\lambda}\alpha^2 λ = C λ α 2 gives
ρ ˉ = λ 96 , 1 m + 14 ρ ˉ 2 ≤ 1 m − 1 + λ 2 ≤ c ρ α 2 c 4 . (64) \bar{\rho} = \frac{\lambda}{96}, \qquad\frac{1}{m} + 14\bar{\rho}^2 \leq\frac{1}{m-1} + \lambda^2 \leq c_{\rho}\frac{\alpha^2}{c^4}. \tag*{(64)} ρ ˉ = 96 λ , m 1 + 14 ρ ˉ 2 ≤ m − 1 1 + λ 2 ≤ c ρ c 4 α 2 . (64)
Also ρ ˉ ≤ 1 / 192 < 1 / 2 \bar{\rho} \leq1/192 < 1/2 ρ ˉ ≤ 1/192 < 1/2 , while m ρ ˉ ≥ 40 C c a p C min 2 > 1 m\bar{\rho} \geq40C_{\mathrm{cap}}C_{\min}^2 > 1 m ρ ˉ ≥ 40 C cap C m i n 2 > 1 . Thus no further change to C min C_{\min} C m i n or α 0 \alpha_0 α 0 is needed. With g = c g c 2 / α g = c_g c^2/\alpha g = c g c 2 / α and failure probability δ = 0.04 \delta= 0.04 δ = 0.04 , use the following round schedule:
γ = 1 4 , T max = 1 + ⌈ log 1 + γ ( m ρ ˉ ) ⌉ , ℓ δ = log 6 ( T max + 1 ) δ , \gamma= \frac{1}{4}, \qquad T_{\max} = 1 + \left\lceil\log_{1+\gamma}(m\bar{\rho}) \right\rceil, \qquad\ell_{\delta} = \log\frac{6(T_{\max}+1)}{\delta}, γ = 4 1 , T m a x = 1 + ⌈ log 1 + γ ( m ρ ˉ ) ⌉ , ℓ δ = log δ 6 ( T m a x + 1 ) ,
ε t = 1 32 ( 7 8 ) t , V t = ( 1 + γ ) t ν 0 , \varepsilon_t = \frac{1}{32}\left(\frac{7}{8}\right)^t, \qquad V_t = (1+\gamma)^t\nu_0, ε t = 32 1 ( 8 7 ) t , V t = ( 1 + γ ) t ν 0 ,
r t = ⌈ max { 256 ( m + ℓ δ ) ε t 2 g 2 V t , 32 ℓ δ δ 0 2 } ⌉ , r_t = \left\lceil\max\left\{\frac{256(m+\ell_{\delta})}{\varepsilon_t^2g^2V_t},\frac{32\ell_{\delta}}{\delta_0^2}\right\}\right\rceil, r t = ⌈ max { ε t 2 g 2 V t 256 ( m + ℓ δ ) , δ 0 2 32 ℓ δ } ⌉ ,
r f i n = ⌈ max { m , 32 ℓ δ δ 0 2 } ⌉ . (65) r_{\mathrm{fin}} = \left\lceil\max\left\{m,\frac{32\ell_{\delta}}{\delta_0^2}\right\}\right\rceil. \tag*{(65)} r fin = ⌈ max { m , δ 0 2 32 ℓ δ } ⌉ . (65)
All round lengths are fixed in advance. The angular-error targets ε t \varepsilon_t ε t sum to at most 1 / 4 1/4 1/4 over the executed rounds, while the variance lower bounds grow geometrically. The variance lower bound grows faster than the angular-error target decreases, so their product increases geometrically. Thus the direction-estimation term in r t r_t r t decreases geometrically; the validation term is fixed.
The rejection guarantee in Proposition C.6 requires the hardness margin
c R g 2 m ρ ˉ ν 0 > 1. (66) c_R g^2m\bar{\rho}\nu_0 > 1. \tag*{(66)} c R g 2 m ρ ˉ ν 0 > 1. (66)
The choices in (63) make the left side exactly 2.
Proof of Theorem 1.2. First consider C min / k ≤ α ≤ α 0 C_{\min}/\sqrt{k} \leq\alpha\leq\alpha_0 C m i n / k ≤ α ≤ α 0 .
Initialization and rejection. By Corollary B.2, with probability at least 0.95 over h h h , either A h = 0 A_h = 0 A h = 0 or ν 0 ≤ V ( I m / m ) < ∞ \nu_0 \leq\mathcal{V}(I_m/m) < \infty ν 0 ≤ V ( I m / m ) < ∞ . If A h = 0 A_h = 0 A h = 0 , every signal-gap rule has loss p c = 5 / ( 10 + c ) > δ 0 p_c = 5/(10+c) > \delta_0 p c = 5/ ( 10 + c ) > δ 0 , and validation rejects the first round with probability at least 1 − δ 1-\delta 1 − δ . Otherwise, apply Proposition C.6 to the sufficient-statistic answers (after thresholding for norm estimation). The margin (66) holds, so the attack returns a round with empirical signal-gap loss greater than δ 0 / 2 \delta_0/2 δ 0 /2 with probability at least 1 − δ 1-\delta 1 − δ , conditional on successful initialization. On the same event every covariance satisfies tr ( Σ t 2 ) ≤ 1 / m + 14 ρ ˉ 2 \operatorname{tr}(\Sigma_t^2) \leq1/m + 14\bar{\rho}^2 tr ( Σ t 2 ) ≤ 1/ m + 14 ρ ˉ 2 and is therefore admissible by (64) . In the zero-signal case the isotropic covariance satisfies the same bound. The joint rejection and admissibility event has probability at least 0.95 ( 1 − δ ) > 0.91 0.95(1-\delta) > 0.91 0.95 ( 1 − δ ) > 0.91 .
Observed errors and final-distribution hardness. The round schedule meets Corollary B.17 with N = T max + 1 N = T_{\max}+1 N = T m a x + 1 and ε = δ / 6 \varepsilon= \delta/6 ε = δ /6 . This corollary applies even though admissibility was established only on the attack’s success event. Their intersection has probability at least 0.95 ( 1 − δ ) − δ / 6 > 0.9 0.95(1-\delta)-\delta/6 > 0.9 0.95 ( 1 − δ ) − δ /6 > 0.9 , and the returned round contains more than a δ 0 / 4 \delta_0/4 δ 0 /4 fraction of norm-task errors. If the eigenvalue threshold is reached, Proposition C.6 also gives signal-gap loss greater than δ 0 \delta_0 δ 0 for every rule on the final distribution. The expected-loss reductions in Lemma B.15 and Corollary B.16 then give norm-task error probability at least δ 0 − ε n c = 7 δ 0 / 8 \delta_0-\varepsilon_{\mathrm{nc}}=7\delta_0/8 δ 0 − ε nc = 7 δ 0 /8 for every responder.
Resources and remaining accuracy regimes. We have m ρ ˉ = Θ ( α 2 k ) m\bar{\rho}=\Theta(\alpha^2 k) m ρ ˉ = Θ ( α 2 k ) , so T max = O ( log ( 2 + α 2 k ) ) T_{\max}=O(\log(2+\alpha^2 k)) T m a x = O ( log ( 2 + α 2 k )) . In (78) , the direction-estimation term is O ( α 2 k 2 ) O(\alpha^2 k^2) O ( α 2 k 2 ) and the validation term is O ( log k log log k ) = O ( k ) O(\log k\log\log k)=O(k) O ( log k log log k ) = O ( k ) , with fixed constants understood. Together with (79) , this gives
O ( k + α 2 k 2 ) queries , O ( log ( 2 + α 2 k ) ) rounds , O ( k log ( 2 + α 2 k ) ) words of working memory , O ~ ( k 2 + α 2 k 3 ) arithmetic operations . (67) \begin{aligned}
O(k+\alpha^2 k^2)&\qquad\text{queries},\\
O(\log(2+\alpha^2 k))&\qquad\text{rounds},\\
O(k\log(2+\alpha^2 k))&\qquad\text{words of working memory},\\
\widetilde{O}(k^2+\alpha^2 k^3)&\qquad\text{arithmetic operations}. \tag*{(67)}
\end{aligned} O ( k + α 2 k 2 ) O ( log ( 2 + α 2 k )) O ( k log ( 2 + α 2 k )) O ( k 2 + α 2 k 3 ) queries , rounds , words of working memory , arithmetic operations . (67)
Every round has Ω ( k ) \Omega(k) Ω ( k ) queries. Indeed, for t < T max t<T_{\max} t < T m a x , V t ≤ ( 1 + γ ) m ρ ˉ ν 0 V_t\leq(1+\gamma)m\bar{\rho}\nu_0 V t ≤ ( 1 + γ ) m ρ ˉ ν 0 , so g 2 V t ≤ 2 ( 1 + γ ) / c R = 10 / 3 g^2V_t\leq2(1+\gamma)/c_R=10/3 g 2 V t ≤ 2 ( 1 + γ ) / c R = 10/3 and the direction term in r t r_t r t is Ω ( m ) \Omega(m) Ω ( m ) . Also r f i n ≥ m r_{\mathrm{fin}}\geq m r fin ≥ m . All queries are supported on S S S .
For 0 < α < C min / k 0<\alpha<C_{\min}/\sqrt{k} 0 < α < C m i n / k and α ≤ α 0 \alpha\leq\alpha_0 α ≤ α 0 , Corollary F.3 gives the guarantee against every responder in one round of Θ ( k ) \Theta(k) Θ ( k ) queries; its distribution is already universally hard on the success event. Taking the smaller error-fraction constant from the two regimes gives the stated guarantee. For α > α 0 \alpha>\alpha_0 α > α 0 , run at α 0 \alpha_0 α 0 , as in the proof of Theorem 1.1 ; this preserves all guarantees after adjusting absolute constants.
Alignment and direction estimation
For the supporting analysis, fix h , M h,M h , M with A h ∈ im ( A M ) ∖ { 0 } A_h\in\operatorname{im}(A_M)\setminus\{0\} A h ∈ im ( A M ) ∖ { 0 } , so every positive definite covariance has positive finite signal-estimation variance. Fix one round, omit its index t t t , and write R = Σ 1 / 2 R=\Sigma^{1/2} R = Σ 1/2 . Use the shared-information version of Section B.3:
X j = ψ j ( y j ) z j , μ j = E [ X j ∣ H j − 1 ] , S r = M r + N r , X_j=\psi_j(y_j)z_j,\qquad\mu_j=\mathbb{E}[X_j\mid\mathcal{H}_{j-1}],\qquad S_r=M_r+N_r, X j = ψ j ( y j ) z j , μ j = E [ X j ∣ H j − 1 ] , S r = M r + N r ,
where M r = ∑ j μ j M_r=\sum_j\mu_j M r = ∑ j μ j and N r = ∑ j ( X j − μ j ) N_r=\sum_j(X_j-\mu_j) N r = ∑ j ( X j − μ j ) . Also write ε j = E [ e j ∣ H j − 1 ] \varepsilon_j=\mathbb{E}[e_j\mid\mathcal{H}_{j-1}] ε j = E [ e j ∣ H j − 1 ] for the predictable loss; these per-query losses are distinct from the angular targets ε t \varepsilon_t ε t indexed by round.
Define the unit vector
h Σ = V ( Σ ) R a Σ , h_\Sigma=\sqrt{\mathcal{V}(\Sigma)}\,R a_\Sigma, h Σ = V ( Σ ) R a Σ ,
which is h R h_R h R from Section B.3 for this whitening.
Proposition C.1 (Exact alignment). For a sufficient-statistic responder, each conditional first moment is collinear with h Σ h_\Sigma h Σ :
μ j = θ j h Σ (68) \mu_j=\theta_j h_\Sigma \tag*{(68)} μ j = θ j h Σ (68) for an H j − 1 \mathcal{H}_{j-1} H j − 1 -measurable scalar θ j \theta_j θ j . On the event r − 1 ∑ j ε j ≤ δ 0 r^{-1}\sum_j\varepsilon_j\leq\delta_0 r − 1 ∑ j ε j ≤ δ 0 ,
M r = σ h Σ , σ = ∑ j θ j ≥ r g V ( Σ ) . (69) M_r=\sigma h_\Sigma,\qquad\sigma=\sum_j\theta_j\geq rg\sqrt{\mathcal{V}(\Sigma)}. \tag*{(69)} M r = σ h Σ , σ = j ∑ θ j ≥ r g V ( Σ ) . (69)
Proof. Decompose the standard Gaussian as z = ξ h Σ + z ⊥ z=\xi h_\Sigma+z_\perp z = ξ h Σ + z ⊥ , where ξ ∼ N ( 0 , 1 ) \xi\sim N(0,1) ξ ∼ N ( 0 , 1 ) and the centered vector z ⊥ z_\perp z ⊥ is independent of ( w , ξ ) (w,\xi) ( w , ξ ) . The scalar channel is
T Σ ( y ) = w + c V ( Σ ) ξ . T_\Sigma(y)=w+c\sqrt{\mathcal{V}(\Sigma)}\,\xi. T Σ ( y ) = w + c V ( Σ ) ξ .
Thus for every bounded measurable φ \varphi φ ,
E [ φ ( T Σ ( y ) ) z ] = E [ φ ( T Σ ( y ) ) ξ ] h Σ . (70) \mathbb{E}[\varphi(T_\Sigma(y))z]=\mathbb{E}[\varphi(T_\Sigma(y))\xi]h_\Sigma. \tag*{(70)} E [ φ ( T Σ ( y )) z ] = E [ φ ( T Σ ( y )) ξ ] h Σ . (70)
Apply this identity to the averaged rule, conditionally on H j − 1 \mathcal{H}_{j-1} H j − 1 . The lower bound on σ \sigma σ is the drift bound of Lemma B.6 .
Lemma C.2 (Direction estimation in an adaptive round). For every responder, every integer r ≥ 1 r \ge1 r ≥ 1 , and every b > 0 b > 0 b > 0 , with probability at least 1 − e − b 1-e^{-b} 1 − e − b ,
∥ N r ∥ 2 ≤ 8 r ( m + b ) . (71) \lVert N_r\rVert_2 \le8\sqrt{r(m+b)}. \tag*{(71)} ∥ N r ∥ 2 ≤ 8 r ( m + b ) . (71) On this event, if M r = σ h M_r=\sigma h M r = σ h for a unit vector h h h with σ ≥ r g V ( Σ ) \sigma\ge r g\sqrt{\mathcal{V}(\Sigma)} σ ≥ r g V ( Σ ) and
r ≥ 256 ( m + b ) ε g 2 V ( Σ ) , 0 < ε ≤ 1 , (72) r \ge\frac{256(m+b)}{\varepsilon g^2\mathcal{V}(\Sigma)}, \qquad0<\varepsilon\le1, \tag*{(72)} r ≥ ε g 2 V ( Σ ) 256 ( m + b ) , 0 < ε ≤ 1 , (72) then S r ≠ 0 S_r\ne0 S r = 0 and ⟨ S r / ∥ S r ∥ 2 , h ⟩ 2 ≥ 1 − ε \left\langle S_r/\lVert S_r\rVert_2,h\right\rangle^2\ge1-\varepsilon ⟨ S r / ∥ S r ∥ 2 , h ⟩ 2 ≥ 1 − ε . Both probability and implication are valid conditional on the information before the round.
Proof. Fix a unit vector q q q . Given H j − 1 \mathcal{H}_{j-1} H j − 1 , let Y = q ⊤ X j Y=q^\top X_j Y = q ⊤ X j and let Y ′ Y' Y ′ be an independent copy of its conditional law. Since ∣ ψ j ∣ ≤ 1 |\psi_j|\le1 ∣ ψ j ∣ ≤ 1 , we have ∣ Y ∣ ≤ ∣ q ⊤ z j ∣ |Y|\le|q^\top z_j| ∣ Y ∣ ≤ ∣ q ⊤ z j ∣ , with q ⊤ z j ∼ N ( 0 , 1 ) q^\top z_j\sim N(0,1) q ⊤ z j ∼ N ( 0 , 1 ) . For every real λ \lambda λ , symmetrization and convexity of cosh \cosh cosh give
E e λ ( Y − E Y ) ≤ E e λ ( Y − Y ′ ) = E cosh ( λ ( Y − Y ′ ) ) ≤ 1 2 E [ cosh ( 2 λ Y ) + cosh ( 2 λ Y ′ ) ] ≤ e 2 λ 2 . \mathbb{E}e^{\lambda(Y-\mathbb{E}Y)}
\le\mathbb{E}e^{\lambda(Y-Y')}
= \mathbb{E}\cosh(\lambda(Y-Y'))
\le\frac{1}{2}\mathbb{E}\left[\cosh(2\lambda Y)+\cosh(2\lambda Y')\right]
\le e^{2\lambda^2}. E e λ ( Y − E Y ) ≤ E e λ ( Y − Y ′ ) = E cosh ( λ ( Y − Y ′ )) ≤ 2 1 E [ cosh ( 2 λY ) + cosh ( 2 λ Y ′ ) ] ≤ e 2 λ 2 .
All expectations in this display are conditional. Iterating the bound over the round gives Pr [ q ⊤ N r ≥ s ] ≤ e − s 2 / ( 8 r ) \Pr[q^\top N_r\ge s]\le e^{-s^2/(8r)} Pr [ q ⊤ N r ≥ s ] ≤ e − s 2 / ( 8 r ) for every s > 0 s>0 s > 0 . Take a 1 / 2 1/2 1/2 -net of the unit sphere of size at most 5 m 5^m 5 m and use ∥ N r ∥ 2 ≤ 2 max q q ⊤ N r \lVert N_r\rVert_2\le2\max_q q^\top N_r ∥ N r ∥ 2 ≤ 2 max q q ⊤ N r over the net. With s = 4 r ( m + b ) s=4\sqrt{r(m+b)} s = 4 r ( m + b ) , the union bound gives a failure probability at most 5 m e − 2 ( m + b ) ≤ e − b 5^m e^{-2(m+b)}\le e^{-b} 5 m e − 2 ( m + b ) ≤ e − b , proving (71) without a lower bound on r r r .
Under (72) , ∥ N r ∥ 2 ≤ ε σ / 2 \lVert N_r\rVert_2\le\sqrt{\varepsilon}\sigma/2 ∥ N r ∥ 2 ≤ ε σ /2 . The component of S r S_r S r along h h h is at least σ ( 1 − ε / 2 ) > 0 \sigma(1-\sqrt{\varepsilon}/2)>0 σ ( 1 − ε /2 ) > 0 , and its perpendicular component has norm at most ε σ / 2 \sqrt{\varepsilon}\sigma/2 ε σ /2 . Hence
1 − ⟨ S r ∥ S r ∥ 2 , h ⟩ 2 ≤ ε / 4 ( 1 − ε / 2 ) 2 ≤ ε . 1-\left\langle\frac{S_r}{\lVert S_r\rVert_2},h\right\rangle^2
\le\frac{\varepsilon/4}{(1-\sqrt{\varepsilon}/2)^2}
\le\varepsilon. 1 − ⟨ ∥ S r ∥ 2 S r , h ⟩ 2 ≤ ( 1 − ε /2 ) 2 ε /4 ≤ ε .
Variance growth and covariance invariants
We first bound the effect of one update using the variational formula from Lemma B.1 , then combine the bounds along the covariance sequence.
Lemma C.3 (One covariance update). Let Σ ≻ 0 \Sigma\succ0 Σ ≻ 0 have trace one, let h ^ \hat{h} h ^ be a unit vector, and put
Σ + = N ( Σ , h ^ ) , s = h ^ T Σ h ^ , χ = ⟨ h ^ , h Σ ⟩ 2 . \Sigma^+=\mathcal{N}(\Sigma,\hat{h}), \qquad
s=\hat{h}^{\mathsf{T}}\Sigma\hat{h}, \qquad
\chi=\langle\hat{h},h_\Sigma\rangle^2. Σ + = N ( Σ , h ^ ) , s = h ^ T Σ h ^ , χ = ⟨ h ^ , h Σ ⟩ 2 . Then
V ( Σ + ) V ( Σ ) ≥ 2 ( 1 + s ) ( 2 − χ ) , λ max ( Σ + ) ≤ 2 λ max ( Σ ) 1 + s . (73) \frac{\mathcal{V}(\Sigma^+)}{\mathcal{V}(\Sigma)}
\ge\frac{2}{(1+s)(2-\chi)}, \qquad
\lambda_{\max}(\Sigma^+)\le\frac{2\lambda_{\max}(\Sigma)}{1+s}. \tag*{(73)} V ( Σ ) V ( Σ + ) ≥ ( 1 + s ) ( 2 − χ ) 2 , λ m a x ( Σ + ) ≤ 1 + s 2 λ m a x ( Σ ) . (73)
Proof. Write R = Σ 1 / 2 R=\Sigma^{1/2} R = Σ 1/2 and let z Σ = Σ a Σ z_\Sigma=\Sigma a_\Sigma z Σ = Σ a Σ be the minimizer in (29) . Indeed, A M z Σ = A h A_Mz_\Sigma=A_h A M z Σ = A h and z Σ T Σ − 1 z Σ = I ( Σ ) z_\Sigma^{\mathsf{T}}\Sigma^{-1}z_\Sigma=\mathcal{I}(\Sigma) z Σ T Σ − 1 z Σ = I ( Σ ) . The update and its inverse are
Σ + = R ( I m + h ^ h ^ T ) R 1 + s , ( Σ + ) − 1 = ( 1 + s ) R − 1 ( I m − h ^ h ^ T 2 ) R − 1 . (74) \Sigma^+=\frac{R(I_m+\hat{h}\hat{h}^{\mathsf{T}})R}{1+s},
\qquad
(\Sigma^+)^{-1}=(1+s)R^{-1}\left(I_m-\frac{\hat{h}\hat{h}^{\mathsf{T}}}{2}\right)R^{-1}. \tag*{(74)} Σ + = 1 + s R ( I m + h ^ h ^ T ) R , ( Σ + ) − 1 = ( 1 + s ) R − 1 ( I m − 2 h ^ h ^ T ) R − 1 . (74)
Since R − 1 z Σ = I ( Σ ) h Σ R^{-1}z_{\Sigma}=\sqrt{\mathcal{I}(\Sigma)}\,h_{\Sigma} R − 1 z Σ = I ( Σ ) h Σ , evaluating the new variational problem at the old minimizer gives
I ( Σ + ) ≤ z Σ T ( Σ + ) − 1 z Σ = ( 1 + s ) I ( Σ ) ( 1 − χ / 2 ) . \mathcal{I}(\Sigma^{+})\le z_{\Sigma}^{\mathsf T}(\Sigma^{+})^{-1}z_{\Sigma}=(1+s)\mathcal{I}(\Sigma)(1-\chi/2). I ( Σ + ) ≤ z Σ T ( Σ + ) − 1 z Σ = ( 1 + s ) I ( Σ ) ( 1 − χ /2 ) .
Taking reciprocals proves the variance bound. Finally, p p T = R b ^ h T R ⪯ Σ pp^{\mathsf T}=R\hat{b}h^{\mathsf T}R\preceq\Sigma p p T = R b ^ h T R ⪯ Σ , proving the eigenvalue bound.
Lemma C.4 (Progress with angular error). Suppose λ max ( Σ ) ≤ ρ ˉ \lambda_{\max}(\Sigma)\le\bar{\rho} λ m a x ( Σ ) ≤ ρ ˉ , ⟨ b ^ , h Σ ⟩ 2 ≥ 1 − ε \langle\hat{b},h_{\Sigma}\rangle^{2}\ge1-\varepsilon ⟨ b ^ , h Σ ⟩ 2 ≥ 1 − ε , with 0 ≤ ε ≤ 1 0\le\varepsilon\le1 0 ≤ ε ≤ 1 . For R ( Σ ) = V ( Σ ) / λ max ( Σ ) \mathcal{R}(\Sigma)=\mathcal{V}(\Sigma)/\lambda_{\max}(\Sigma) R ( Σ ) = V ( Σ ) / λ m a x ( Σ ) ,
V ( Σ + ) V ( Σ ) ≥ 2 ( 1 + ρ ˉ ) ( 1 + ε ) , R ( Σ + ) R ( Σ ) ≥ 1 1 + ε ≥ e − ε . (75) \frac{\mathcal{V}(\Sigma^{+})}{\mathcal{V}(\Sigma)}\ge\frac{2}{(1+\bar{\rho})(1+\varepsilon)},
\qquad
\frac{\mathcal{R}(\Sigma^{+})}{\mathcal{R}(\Sigma)}\ge\frac{1}{1+\varepsilon}\ge e^{-\varepsilon}. \tag*{(75)} V ( Σ ) V ( Σ + ) ≥ ( 1 + ρ ˉ ) ( 1 + ε ) 2 , R ( Σ ) R ( Σ + ) ≥ 1 + ε 1 ≥ e − ε . (75) If ρ ˉ ≤ 1 / 2 \bar{\rho}\le1/2 ρ ˉ ≤ 1/2 and ε ≤ 1 / 16 \varepsilon\le1/16 ε ≤ 1/16 , then V ( Σ + ) ≥ ( 5 / 4 ) V ( Σ ) \mathcal{V}(\Sigma^{+})\ge(5/4)\mathcal{V}(\Sigma) V ( Σ + ) ≥ ( 5/4 ) V ( Σ ) .
Proof. Since s ≤ ρ ˉ s\le\bar{\rho} s ≤ ρ ˉ and 2 − χ ≤ 1 + ε 2-\chi\le1+\varepsilon 2 − χ ≤ 1 + ε , Lemma C.3 gives the variance bound. Dividing its variance bound by its eigenvalue bound gives
R ( Σ + ) R ( Σ ) ≥ 1 2 − χ ≥ 1 1 + ε ≥ e − ε . \frac{\mathcal{R}(\Sigma^{+})}{\mathcal{R}(\Sigma)}\ge\frac{1}{2-\chi}\ge\frac{1}{1+\varepsilon}\ge e^{-\varepsilon}. R ( Σ ) R ( Σ + ) ≥ 2 − χ 1 ≥ 1 + ε 1 ≥ e − ε .
Finally, 2 / ( ( 3 / 2 ) ( 17 / 16 ) ) = 64 / 51 > 5 / 4 2/((3/2)(17/16))=64/51>5/4 2/ (( 3/2 ) ( 17/16 )) = 64/51 > 5/4 .
Lemma C.5 (Covariance invariants). Consider a sequence of updates starting from I m / m I_m/m I m / m , with squared angular errors at most ε t \varepsilon_t ε t , where
0 ≤ ε t ≤ 1 / 16 , ∑ t ε t ≤ 1 / 4. 0\le\varepsilon_t\le1/16,\qquad\sum_t\varepsilon_t\le1/4. 0 ≤ ε t ≤ 1/16 , t ∑ ε t ≤ 1/4. Suppose λ max ( Σ j ) < ρ ˉ ≤ 1 / 2 \lambda_{\max}(\Sigma_j)<\bar{\rho}\le1/2 λ m a x ( Σ j ) < ρ ˉ ≤ 1/2 before each update. Every iterate, including the one produced by the last update, satisfies
R ( Σ t ) ≥ c R m V ( I m / m ) , Σ t = β t I m + P t , β t > 0 , P t ⪰ 0 , tr P t ≤ 7 ρ ˉ . \mathcal{R}(\Sigma_t)\ge c_Rm\mathcal{V}(I_m/m),\qquad
\Sigma_t=\beta_t I_m+P_t,\qquad
\beta_t>0,\qquad P_t\succeq0,\qquad\operatorname{tr}P_t\le7\bar{\rho}. R ( Σ t ) ≥ c R m V ( I m / m ) , Σ t = β t I m + P t , β t > 0 , P t ⪰ 0 , tr P t ≤ 7 ρ ˉ . Consequently, tr ( Σ t 2 ) ≤ 1 / m + 14 ρ ˉ 2 \operatorname{tr}(\Sigma_t^2)\le1/m+14\bar{\rho}^2 tr ( Σ t 2 ) ≤ 1/ m + 14 ρ ˉ 2 .
Proof. By Lemma C.4 and ∑ t ε t ≤ 1 / 4 \sum_t\varepsilon_t\le1/4 ∑ t ε t ≤ 1/4 ,
R ( Σ t ) ≥ e − 1 / 4 R ( I m / m ) ≥ 3 4 m V ( I m / m ) . \mathcal{R}(\Sigma_t)\ge e^{-1/4}\mathcal{R}(I_m/m)\ge\frac{3}{4}m\mathcal{V}(I_m/m). R ( Σ t ) ≥ e − 1/4 R ( I m / m ) ≥ 4 3 m V ( I m / m ) .
Define s j = h ^ j T Σ j h ^ j s_j=\hat{h}_j^{\mathsf T}\Sigma_j\hat{h}_j s j = h ^ j T Σ j h ^ j and β t = m − 1 ∏ j < t ( 1 + s j ) − 1 \beta_t=m^{-1}\prod_{j<t}(1+s_j)^{-1} β t = m − 1 ∏ j < t ( 1 + s j ) − 1 . The update gives Σ t = β t I m + P t \Sigma_t=\beta_t I_m+P_t Σ t = β t I m + P t with P t ⪰ 0 P_t\succeq0 P t ⪰ 0 , and
tr P t = 1 − m β t ≤ ∑ j < t s j ≤ ∑ j < t λ max ( Σ j ) . \operatorname{tr}P_t=1-m\beta_t\le\sum_{j<t}s_j\le\sum_{j<t}\lambda_{\max}(\Sigma_j). tr P t = 1 − m β t ≤ j < t ∑ s j ≤ j < t ∑ λ m a x ( Σ j ) .
If there are no updates, the conclusion is immediate. Otherwise let T T T be their number. Every update multiplies the variance by at least 1 + γ = 5 / 4 1+\gamma=5/4 1 + γ = 5/4 , and Lemma B.1 bounds V ( Σ T − 1 ) ≤ m ρ ˉ V ( I m / m ) \mathcal{V}(\Sigma_{T-1})\le m\bar{\rho}\mathcal{V}(I_m/m) V ( Σ T − 1 ) ≤ m ρ ˉ V ( I m / m ) . For each j < T j<T j < T , the variance growth and the lower bound on R \mathcal{R} R therefore give
λ max ( Σ j ) ≤ V ( Σ j ) c R m V ( I m / m ) ≤ ρ ˉ c R ( 1 + γ ) − ( T − 1 − j ) . \lambda_{\max}(\Sigma_j)\le\frac{\mathcal{V}(\Sigma_j)}{c_Rm\mathcal{V}(I_m/m)}
\le\frac{\bar{\rho}}{c_R}(1+\gamma)^{-(T-1-j)}. λ m a x ( Σ j ) ≤ c R m V ( I m / m ) V ( Σ j ) ≤ c R ρ ˉ ( 1 + γ ) − ( T − 1 − j ) .
Summing this geometric bound, for every t ≤ T t \le T t ≤ T we obtain
tr P t ≤ ρ ˉ c R ∑ i ≥ 0 ( 1 + γ ) − i = 20 3 ρ < 7 ρ ˉ . \operatorname{tr} P_t \le\frac{\bar{\rho}}{c_R}\sum_{i\ge0}(1+\gamma)^{-i}=\frac{20}{3}\rho<7\bar{\rho}. tr P t ≤ c R ρ ˉ i ≥ 0 ∑ ( 1 + γ ) − i = 3 20 ρ < 7 ρ ˉ .
Finally, put d t = tr P t d_t=\operatorname{tr}P_t d t = tr P t , so m β t + d t = 1 m\beta_t+d_t=1 m β t + d t = 1 . Every update starts below ρ ˉ \bar{\rho} ρ ˉ , so Lemma C.3 gives λ max ( P t ) ≤ λ max ( Σ t ) < 2 ρ ˉ \lambda_{\max}(P_t)\le\lambda_{\max}(\Sigma_t)<2\bar{\rho} λ m a x ( P t ) ≤ λ m a x ( Σ t ) < 2 ρ ˉ , including at the final iterate. Hence
tr ( Σ t 2 ) = 1 − d t 2 m + tr ( P t 2 ) ≤ 1 m + 2 ρ ˉ d t ≤ 1 m + 14 ρ ˉ 2 . \operatorname{tr}(\Sigma_t^2)=\frac{1-d_t^2}{m}+\operatorname{tr}(P_t^2)\le\frac{1}{m}+2\bar{\rho}d_t\le\frac{1}{m}+14\bar{\rho}^2. tr ( Σ t 2 ) = m 1 − d t 2 + tr ( P t 2 ) ≤ m 1 + 2 ρ ˉ d t ≤ m 1 + 14 ρ ˉ 2 .
Termination and query complexity
We combine direction estimation with the covariance invariants to prove the signal-gap guarantee used in Section C.1. The following statement also records the generic dependence on m m m , the initial variance lower bound ν 0 \nu_0 ν 0 , and the failure probability δ \delta δ .
Proposition C.6 (Rejection and threshold hardness). Fix h , M h,M h , M with m ≥ 2 m\ge2 m ≥ 2 and A h ∈ im ( A M ) ∖ { 0 } A_h\in\operatorname{im}(A_M)\setminus\{0\} A h ∈ im ( A M ) ∖ { 0 } , and let α > 0 \alpha>0 α > 0 and 0 < c ≤ 1 0<c\le1 0 < c ≤ 1 . Suppose 0 < ν 0 ≤ V ( I m / m ) 0<\nu_0\le\mathcal{V}(I_m/m) 0 < ν 0 ≤ V ( I m / m ) and 1 / m < ρ ˉ ≤ 1 / 2 1/m<\bar{\rho}\le1/2 1/ m < ρ ˉ ≤ 1/2 . For 0 < δ < 1 0<\delta<1 0 < δ < 1 , use the round schedule (65) . Under the margin (66) , Algorithm 2 returns a rejected round with probability at least 1 − δ 1-\delta 1 − δ against every sufficient-statistic responder. The round has empirical signal-gap loss greater than δ 0 / 2 \delta_0/2 δ 0 /2 .
On the same event, every covariance produced satisfies
tr ( Σ 2 ) ≤ 1 m + 14 ρ ˉ 2 . (76) \operatorname{tr}(\Sigma^2)\le\frac{1}{m}+14\bar{\rho}^2. \tag*{(76)} tr ( Σ 2 ) ≤ m 1 + 14 ρ ˉ 2 . (76) If the final round is reached, its covariance satisfies
ρ ˉ ≤ λ max ( Σ o u t ) < 2 ρ ˉ , \bar{\rho}\le\lambda_{\max}(\Sigma_{\mathrm{out}})<2\bar{\rho}, ρ ˉ ≤ λ m a x ( Σ out ) < 2 ρ ˉ , V ( Σ o u t ) ≥ c R m λ max ( Σ o u t ) V ( I m / m ) ≥ c R m ρ ˉ V ( I m / m ) . (77) \mathcal{V}(\Sigma_{\mathrm{out}})\ge c_Rm\lambda_{\max}(\Sigma_{\mathrm{out}})\mathcal{V}(I_m/m)\ge c_Rm\bar{\rho}\mathcal{V}(I_m/m). \tag*{(77)} V ( Σ out ) ≥ c R m λ m a x ( Σ out ) V ( I m / m ) ≥ c R m ρ ˉ V ( I m / m ) . (77) Consequently, that final distribution is universally hard: every signal-gap rule has loss greater than δ 0 \delta_0 δ 0 on it.
Positive definiteness, trace one, and the eigenvalue bound λ max ( Σ t ) < 2 ρ ˉ \lambda_{\max}(\Sigma_t)<2\bar{\rho} λ m a x ( Σ t ) < 2 ρ ˉ hold on every run. The sharper admissibility bound (76) requires successful direction estimation and is asserted on the theorem’s high-probability event. By Lemma B.1 , (77) attains at least three quarters of the largest variance possible with top eigenvalue at most λ max ( Σ o u t ) \lambda_{\max}(\Sigma_{\mathrm{out}}) λ m a x ( Σ out ) .
There are at most T max T_{\max} T m a x rounds and one final round. The total query count is
Q = O ( m + log ( 1 / δ ) g 2 ν 0 + T max log T max + 1 δ + m ) . (78) Q=O\left(\frac{m+\log(1/\delta)}{g^2\nu_0}+T_{\max}\log\frac{T_{\max}+1}{\delta}+m\right). \tag*{(78)} Q = O ( g 2 ν 0 m + log ( 1/ δ ) + T m a x log δ T m a x + 1 + m ) . (78) The implementation uses
O ( m T max ) words of working memory , O ( Q m T max + m T max 3 ) arithmetic operations . (79) O(mT_{\max})\ \text{words of working memory},\qquad O(QmT_{\max}+mT_{\max}^3)\ \text{arithmetic operations}. \tag*{(79)} O ( m T m a x ) words of working memory , O ( Q m T m a x + m T m a x 3 ) arithmetic operations . (79)
Proof of Proposition C.6. For each executed round, use the validation event of Lemma B.7 and the concentration event of Lemma C.2 with b = ℓ δ b=\ell_\delta b = ℓ δ . Their conditional failure probabilities are at most 2 e − ℓ δ 2e^{-\ell_\delta} 2 e − ℓ δ and e − ℓ δ e^{-\ell_\delta} e − ℓ δ , respectively. Include the final validation event if that round is reached. A union bound gives an event E \mathcal{E} E of probability at least
1 − ( 3 T max + 2 ) e − ℓ δ ≥ 1 − δ / 2 1-(3T_{\max}+2)e^{-\ell_\delta}\ge1-\delta/2 1 − ( 3 T m a x + 2 ) e − ℓ δ ≥ 1 − δ /2
on which all these conclusions hold. No conditioning on acceptance is used to establish this probability bound.
Accepted rounds. Work on E \mathcal{E} E . If round t t t is accepted, its average predictable loss is below δ 0 \delta_0 δ 0 . By induction over accepted rounds and Proposition C.1 and Lemma C.2 ,
V ( Σ t ) ≥ ( 1 + γ ) t V ( I m / m ) ≥ V t , ⟨ h ^ t , h Σ t ⟩ 2 ≥ 1 − ε t . (80) \mathcal{V}(\Sigma_t)\ge(1+\gamma)^t\mathcal{V}(I_m/m)\ge V_t,\qquad\langle\hat{h}_t,h_{\Sigma_t}\rangle^2\ge1-\varepsilon_t. \tag*{(80)} V ( Σ t ) ≥ ( 1 + γ ) t V ( I m / m ) ≥ V t , ⟨ h ^ t , h Σ t ⟩ 2 ≥ 1 − ε t . (80)
Indeed, the variance lower bound holds initially and is preserved by Lemma C.4 . Given that bound, exact alignment and the round length yield the angular estimate. The gain lemma is valid throughout, so no separate variance regime is needed.
Termination and hardness. If all T max T_{\max} T m a x rounds were accepted without reaching the threshold, the variance growth would give V ( Σ T max ) ≥ ( 1 + γ ) T max V ( I m / m ) > m ρ ˉ V ( I m / m ) \mathcal{V}(\Sigma_{T_{\max}})\ge(1+\gamma)^{T_{\max}}\mathcal{V}(I_m/m)>m\bar{\rho}\mathcal{V}(I_m/m) V ( Σ T m a x ) ≥ ( 1 + γ ) T m a x V ( I m / m ) > m ρ ˉ V ( I m / m ) . This contradicts the stopping condition and Lemma B.1 :
V ( Σ ) ≤ m λ max ( Σ ) V ( I m / m ) ≤ m ρ ˉ V ( I m / m ) . (81) \mathcal{V}(\Sigma)\le m\lambda_{\max}(\Sigma)\mathcal{V}(I_m/m)\le m\bar{\rho}\mathcal{V}(I_m/m). \tag*{(81)} V ( Σ ) ≤ m λ m a x ( Σ ) V ( I m / m ) ≤ m ρ ˉ V ( I m / m ) . (81)
Thus a round is rejected or an update reaches the threshold. In the latter case, Lemma C.5 gives (77) , and the margin (66) implies g 2 V ( Σ o u t ) > 1 g^2\mathcal{V}(\Sigma_{\mathrm{out}})>1 g 2 V ( Σ out ) > 1 . By Corollary B.5 , every response rule has loss greater than δ 0 \delta_0 δ 0 there, so the final validation round is rejected. The same covariance-invariants lemma proves (76) in either case, since only accepted rounds produce updates and every update starts below the threshold.
Queries. The direction-estimation terms sum geometrically, because
1 ε t V t = 32 v 0 ( 32 35 ) t . \frac{1}{\varepsilon_t V_t}=\frac{32}{v_0}\left(\frac{32}{35}\right)^t. ε t V t 1 = v 0 32 ( 35 32 ) t .
Also T max = O ( 1 + log ( m ρ ˉ ) ) = O ( log m ) T_{\max}=O(1+\log(m\bar{\rho}))=O(\log m) T m a x = O ( 1 + log ( m ρ ˉ )) = O ( log m ) and ℓ δ = O ( m + log ( 1 / δ ) ) \ell_\delta=O(m+\log(1/\delta)) ℓ δ = O ( m + log ( 1/ δ )) . Summing the direction terms, validation terms, and ceilings, and including the final round, proves (78) . The implementation bounds are proved in Section G.2.
Approximate alignment
The gain lemma gives σ t ≥ r t g V ( Σ t ) > 0 \sigma_t \ge r_t g\sqrt{V(\Sigma_t)} > 0 σ t ≥ r t g V ( Σ t ) > 0 . Here ε t \varepsilon_t ε t is the target squared angular error of the estimated direction, not a tolerance for response errors.
Replace 256 by 1024 in the direction-estimation term of (65) . Then, on the concentration event, the sampling error also has norm at most ε t σ t / 4 \sqrt{\varepsilon_t}\,\sigma_t/4 ε t σ t /4 . Consequently,
∥ S t − σ t h Σ t ∥ 2 ≤ 1 2 ε t σ t . \lVert S_t-\sigma_t h\Sigma_t\rVert_2 \le\frac{1}{2}\sqrt{\varepsilon_t}\,\sigma_t. ∥ S t − σ t h Σ t ∥ 2 ≤ 2 1 ε t σ t .
The same normalization argument as in Lemma C.2 gives squared angular error at most ε t \varepsilon_t ε t . The remaining analysis is unchanged.
A uniform allowance for perpendicular correlation. The geometric choice of ε t \varepsilon_t ε t is convenient but not essential. The covariance analysis only requires ε t ≤ 1 / 16 \varepsilon_t \le1/16 ε t ≤ 1/16 and ∑ t < T max ε t ≤ 1 / 4 \sum_{t<T_{\max}}\varepsilon_t \le1/4 ∑ t < T m a x ε t ≤ 1/4 . This permits a schedule that accommodates the same relative perpendicular correlation in every accurate round. Specifically, suppose
∥ d t ∥ 2 2 σ t 2 ≤ ε ′ ≤ 1 256 T max . \frac{\lVert d_t\rVert_2^2}{\sigma_t^2} \le\varepsilon' \le\frac{1}{256T_{\max}}. σ t 2 ∥ d t ∥ 2 2 ≤ ε ′ ≤ 256 T m a x 1 .
Choose
ε t = max { 1 16 ( t + 1 ) 2 , 16 ε ′ } . \varepsilon_t=\max\left\{\frac{1}{16(t+1)^2},16\varepsilon'\right\}. ε t = max { 16 ( t + 1 ) 2 1 , 16 ε ′ } .
Then the required drift bound holds, each ε t ≤ 1 / 16 \varepsilon_t \le1/16 ε t ≤ 1/16 , and
∑ t < T max ε t ≤ π 2 96 + 1 16 < 1 4 . \sum_{t<T_{\max}}\varepsilon_t \le\frac{\pi^2}{96}+\frac{1}{16}<\frac{1}{4}. t < T m a x ∑ ε t ≤ 96 π 2 + 16 1 < 4 1 .
Moreover, 1 / ε t ≤ 16 ( t + 1 ) 2 1/\varepsilon_t \le16(t+1)^2 1/ ε t ≤ 16 ( t + 1 ) 2 , while the variance lower bound grows as ( 5 / 4 ) t (5/4)^t ( 5/4 ) t . Hence the direction-estimation costs still have a bounded geometric-weighted sum, preserving the same asymptotic query bound.
The extension therefore covers responders that use other sketch components, provided their perpendicular correlations satisfy the stated bound. Applying it to a learned predictor requires establishing this correlation bound; small prediction loss alone does not supply it.
Optimality of the covariance attacks
We use a Gaussian Johnson–Lindenstrauss matrix, sampled once and kept fixed throughout the interaction, together with a constructed responder that uses no interaction history and less distributional information than our informed model allows. We show that they withstand Ω ( k + α 2 k 2 ) \Omega(k+\alpha^2k^2) Ω ( k + α 2 k 2 ) adaptive queries from a broad class of attacks. Specifically, for any fixed target error fraction δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) and constant ℓ > 0 \ell>0 ℓ > 0 , with high constant probability, no consecutive interval of at least ℓ k \ell k ℓ k queries has error fraction at least δ \delta δ .
The attacks use signal–noise distributions whose noise energy is sufficiently concentrated. The signal direction and joint distribution may change after every answer, and the noise may depend on the signal. The responder knows the matrix and task parameters and receives each input through its sketch. Its only additional per-query information is the signal direction and the first two moments of the noise. The constants in the query guarantee and the noise-concentration requirement may depend on δ \delta δ and ℓ \ell ℓ .
The proof uses two facts. First, for any fixed query law, the estimation-error variance of the linear statistic used by our responder is O ( 1 / k ) O(1/k) O ( 1/ k ) except with probability exponentially small in k k k over the Gaussian matrix. Second, while this variance remains O ( 1 / k ) O(1/k) O ( 1/ k ) , the responder can answer accurately while masking the matrix-dependent estimation error with output noise of scale α \alpha α . Each such query contributes only O ( 1 / ( α 2 k ) ) O(1/(\alpha^2 k)) O ( 1/ ( α 2 k )) to a KL divergence bound relative to an ideal interaction that reveals nothing about A A A . Comparing the interactions up to the first selection of a large-variance law shows that reaching such a law with constant probability requires Ω ( α 2 k 2 ) \Omega(\alpha^2 k^2) Ω ( α 2 k 2 ) queries. Concentration then converts the responder’s conditional accuracy into the observed-error guarantee. We first state the model and guarantees, then give the proof.
Attack and responder models
Definition D.1 (Announced signal–noise attacks). Before query i i i , the attacker announces a unit vector s i ∈ R n s_i \in\mathbb{R}^n s i ∈ R n and a joint law P i P_i P i of ( w i , u i ) (w_i,u_i) ( w i , u i ) satisfying
w i ∈ [ 1 / 2 , 2 ] , u i ∈ s i ⊥ almost surely , μ i : = E u i , Γ i : = Cov ( u i ) , tr Γ i ≤ 1. (82) w_i \in[1/2,2], \qquad u_i \in s_i^\perp\text{ almost surely}, \qquad\mu_i := \mathbb{E}u_i,\qquad\Gamma_i := \operatorname{Cov}(u_i),\qquad\operatorname{tr}\Gamma_i \le1. \tag*{(82)} w i ∈ [ 1/2 , 2 ] , u i ∈ s i ⊥ almost surely , μ i := E u i , Γ i := Cov ( u i ) , tr Γ i ≤ 1. (82)
It then takes a fresh draw from this law and queries v i = w i s i + u i v_i = w_i s_i + u_i v i = w i s i + u i . The announcement may depend on its complete previous execution and private randomness. Conditional on that execution and the announcement, the fresh draw is independent of the hidden matrix A A A . The attacker may retain all sampling randomness. It observes the answers, but does not see A A A or the sketches A v i Av_i A v i .
The attacker may change the law after every query and there is no restriction on the number of adaptive rounds. For norm tasks, we additionally require
Var ( ∥ u i ∥ 2 2 ) ≤ c a d α 2 (83) \operatorname{Var}(\lVert u_i\rVert_2^2) \le c_{\mathrm{ad}}\alpha^2 \tag*{(83)} Var (∥ u i ∥ 2 2 ) ≤ c ad α 2 (83)
for a sufficiently small constant c a d > 0 c_{\mathrm{ad}} > 0 c ad > 0 . This is a promise on each announced law, not additional information required by the responder. For centered Gaussian noise, Var ( ∥ u i ∥ 2 2 ) = 2 tr ( Γ i 2 ) \operatorname{Var}(\lVert u_i\rVert_2^2) = 2\operatorname{tr}(\Gamma_i^2) Var (∥ u i ∥ 2 2 ) = 2 tr ( Γ i 2 ) , so a sufficiently small bound on tr ( Γ i 2 ) \operatorname{tr}(\Gamma_i^2) tr ( Γ i 2 ) implies (82). For noncentered Gaussian noise, the variance is 2 tr ( Γ i 2 ) + 4 μ i T Γ i μ i 2\operatorname{tr}(\Gamma_i^2) + 4\mu_i^\mathsf{T}\Gamma_i\mu_i 2 tr ( Γ i 2 ) + 4 μ i T Γ i μ i . For general noise, this variance also depends on fourth moments and need not be controlled by the mean and covariance alone.
This model allows non-Gaussian noise with nonzero mean and signal dependence. Our attacks use the special case s i = e h s_i = e_h s i = e h and u i = c ι M u u_i = c\,\iota_M u u i = c ι M u , where u ∼ N ( 0 , Σ ) u \sim N(0,\Sigma) u ∼ N ( 0 , Σ ) is independent of the signal. Thus μ i = 0 \mu_i = 0 μ i = 0 and Γ i = c 2 ι M Σ ι M T \Gamma_i = c^2\iota_M\Sigma\iota_M^\mathsf{T} Γ i = c 2 ι M Σ ι M T : the noise multiplier c c c is absorbed into u i u_i u i in this section.
The defending responder. Draw A ∈ R k × n A \in\mathbb{R}^{k \times n} A ∈ R k × n with independent N ( 0 , 1 / k ) N(0,1/k) N ( 0 , 1/ k ) entries and keep it fixed. For the current announcement, suppress the query index and put
x = A s , K = A Γ A T , ν = { ( x T K † x ) − 1 , x ∈ im ( K ) ∖ { 0 } , 0 , x ∉ im ( K ) , + ∞ , x = 0. x = As,\qquad K = A\Gamma A^\mathsf{T},\qquad\nu=
\begin{cases}
(x^\mathsf{T}K^\dagger x)^{-1}, & x \in\operatorname{im}(K)\setminus\{0\},\\
0, & x \notin\operatorname{im}(K),\\
+\infty, & x = 0.
\end{cases} x = A s , K = A Γ A T , ν = ⎩ ⎨ ⎧ ( x T K † x ) − 1 , 0 , + ∞ , x ∈ im ( K ) ∖ { 0 } , x ∈ / im ( K ) , x = 0.
Here K † K^\dagger K † denotes the Moore–Penrose inverse. When ν < ∞ \nu< \infty ν < ∞ , it is the variance of the estimation error T − w T-w T − w below; for our Gaussian query family it equals c 2 V ( Σ ) c^2\mathcal{V}(\Sigma) c 2 V ( Σ ) .
Given the sketch y = A v y = Av y = A v , form y ~ = y − A μ \widetilde{y} = y - A\mu y = y − A μ . If 0 < ν < ∞ 0 < \nu< \infty 0 < ν < ∞ , the responder computes
T = ν x T K † y ~ . (84) T = \nu x^\mathsf{T}K^\dagger\widetilde{y}. \tag*{(84)} T = ν x T K † y . (84)
If ν = 0 \nu= 0 ν = 0 , let P P P be the orthogonal projector onto im ( K ) ⊥ \operatorname{im}(K)^\perp im ( K ) ⊥ and use T = ⟨ P x , y ~ ⟩ / ∥ P x ∥ 2 2 T = \langle Px,\widetilde{y}\rangle/\lVert Px\rVert_2^2 T = ⟨ P x , y ⟩ / ∥ P x ∥ 2 2 . This recovers w w w exactly: A ( u − μ ) ∈ im ( K ) A(u-\mu) \in\operatorname{im}(K) A ( u − μ ) ∈ im ( K ) almost surely, since a centered random vector lies in the image of its covariance almost surely. When x = 0 x = 0 x = 0 , set T = 0 T = 0 T = 0 . For adaptive signal directions, we include this exceptional case in the bad event controlled by the proof.
Conditional on A A A , the past, and any announcement with ν < ∞ \nu< \infty ν < ∞ ,
T = w + η , E [ η ] = 0 , E [ η 2 ] = ν . (85) T = w + \eta,\qquad\mathbb{E}[\eta] = 0,\qquad\mathbb{E}[\eta^2] = \nu. \tag*{(85)} T = w + η , E [ η ] = 0 , E [ η 2 ] = ν . (85)
Indeed, when ν > 0 \nu> 0 ν > 0 , η = ν x T K † A ( u − μ ) \eta= \nu x^{\mathsf{T}}K^{\dagger}A(u-\mu) η = ν x T K † A ( u − μ ) and its second moment is ν 2 x T K † K K † x = ν \nu^2x^{\mathsf{T}}K^{\dagger}KK^{\dagger}x = \nu ν 2 x T K † K K † x = ν ; when ν = 0 \nu= 0 ν = 0 , η = 0 \eta= 0 η = 0 . No independence between w w w and u u u is needed.
The responder adds fresh independent output noise,
o = T + ξ , ξ ∼ N ( 0 , σ 2 ) , (86) o = T + \xi,\qquad\xi\sim N(0,\sigma^2), \tag*{(86)} o = T + ξ , ξ ∼ N ( 0 , σ 2 ) , (86)
and answers norm queries using
r ^ = σ 2 + tr Γ + ∥ μ ∥ 2 2 . (87) \widehat{r} = \sqrt{\sigma^2 + \operatorname{tr}\Gamma+ \lVert\mu\rVert_2^2}. \tag*{(87)} r = σ 2 + tr Γ + ∥ μ ∥ 2 2 . (87)
For norm estimation it returns r ^ \widehat{r} r ; for the binary norm gap it returns + 1 +1 + 1 exactly when r ^ 2 ≥ ( L 2 + U 2 ) / 2 \widehat{r}^2 \ge(L^2+U^2)/2 r 2 ≥ ( L 2 + U 2 ) /2 . The responder uses only A A A , s s s , μ \mu μ , Γ \Gamma Γ and the task parameters. It needs neither the signal law nor the full noise law. For the lower bound, we give the attacker the more informative observation o o o itself; the task answer is determined by o o o and the announcement.
For Gaussian noise independent of the signal, T T T is the scalar sufficient statistic used in our attacks. In particular, this responder belongs to the sufficient-statistic class on that query family. We do not require statistical sufficiency for other noise laws.
Lower-bound guarantees
Fix an error fraction δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) and a minimum interval length ℓ k \ell k ℓ k , where ℓ > 0 \ell> 0 ℓ > 0 is constant. We consider either relative norm estimation with tolerance κ α \kappa\alpha κ α , for a fixed κ > 0 \kappa> 0 κ > 0 , or a binary norm gap with fixed thresholds satisfying U 2 − L 2 = α U^2-L^2=\alpha U 2 − L 2 = α . Taking κ = c e r r \kappa=c_{\mathrm{err}} κ = c err recovers our norm-estimation loss; the stated norm-gap width includes our thresholds. Write e i ∈ { 0 , 1 } e_i \in\{0,1\} e i ∈ { 0 , 1 } for the corresponding task-error indicator. An observed-error success means returning a consecutive interval J J J of already queried inputs with ∣ J ∣ ≥ ℓ k \lvert J\rvert\ge\ell k ∣ J ∣ ≥ ℓ k and ∑ i ∈ J e i ≥ δ ∣ J ∣ \sum_{i\in J}e_i \ge\delta\lvert J\rvert ∑ i ∈ J e i ≥ δ ∣ J ∣ . In particular, this includes returning a round with a constant fraction of errors.
Theorem D.2 (Lower bound for announced signal–noise attacks). Fix the norm task, δ \delta δ , and ℓ \ell ℓ as above. There are positive constants C C C , C 1 C_1 C 1 , c 0 c_0 c 0 , c a d c_{\mathrm{ad}} c ad and k 0 k_0 k 0 such that the following holds for every k ≥ k 0 k \ge k_0 k ≥ k 0 , n > k n > k n > k , and
0 < α ≤ 1 , α 2 k ≥ C . 0 < \alpha\le1,\qquad\alpha^2 k \ge C. 0 < α ≤ 1 , α 2 k ≥ C . Let A A A have independent N ( 0 , 1 / k ) N(0,1/k) N ( 0 , 1/ k ) entries. Use the responder (86) –(87) with
σ = α / C 1 , Q 0 = ⌊ c 0 α 2 k 2 ⌋ . \sigma= \alpha/C_1,\qquad Q_0 = \lfloor c_0\alpha^2 k^2\rfloor. σ = α / C 1 , Q 0 = ⌊ c 0 α 2 k 2 ⌋ . Against every attack satisfying Definition D.1 and (83) , with probability at least 0.9 0.9 0.9 we have ν i < 4 e / k \nu_i < 4e/k ν i < 4 e / k for all i ≤ Q 0 i \le Q_0 i ≤ Q 0 . With probability at least 0.8 0.8 0.8 , every consecutive interval J ⊆ { 1 , … , Q 0 } J \subseteq\{1,\ldots,Q_0\} J ⊆ { 1 , … , Q 0 } with ∣ J ∣ ≥ ℓ k \lvert J\rvert\ge\ell k ∣ J ∣ ≥ ℓ k satisfies
1 ∣ J ∣ ∑ i ∈ J e i < δ . (88) \frac{1}{\lvert J\rvert}\sum_{i\in J} e_i < \delta. \tag*{(88)} ∣ J ∣ 1 i ∈ J ∑ e i < δ . (88) The probabilities include the matrix, attacker, and responder randomness. The empirical guarantee controls the fraction of errors in every long enough interval. It does not assert that all answers are correct. It holds even when the attacker chooses the returned interval after seeing all the answers, and does not require the queries within that interval to share a distribution.
Corollary D.3 (Query complexity). In the setting of Theorem D.2 , an attack achieving observed-error success with probability at least 0.9 for every fixed matrix and every informed responder requires Ω ( k + α 2 k 2 ) \Omega(k+\alpha^2k^2) Ω ( k + α 2 k 2 ) queries in the worst case. The same lower bound holds for its worst-case expected query count.
Proof. Average the attack’s success guarantee over Gaussian A A A . The theorem bounds the probability of success using at most Q 0 Q_0 Q 0 queries by 0.2. Thus, if Q Q Q is the total query count, Pr [ Q > Q 0 ] ≥ 0.7 \Pr[Q>Q_0]\ge0.7 Pr [ Q > Q 0 ] ≥ 0.7 and E Q ≥ 0.7 Q 0 \mathbb{E}Q\ge0.7Q_0 E Q ≥ 0.7 Q 0 . Also E Q ≥ 0.9 ℓ k \mathbb{E}Q\ge0.9\ell k E Q ≥ 0.9 ℓ k , since a successful execution returns at least ℓ k \ell k ℓ k queries. The average over A A A lower bounds the worst case over fixed matrices. An attack that terminates early may be padded with arbitrary admissible queries for the purpose of applying the theorem.
Comparison with our attacks. For our centered Gaussian query laws, Var ( ∥ c μ u ∥ 2 2 ) = 2 c 4 tr ( Σ 2 ) \operatorname{Var}(\lVert c_{\mu}u\rVert_2^2)=2c^4\operatorname{tr}(\Sigma^2) Var (∥ c μ u ∥ 2 2 ) = 2 c 4 tr ( Σ 2 ) . The general attack has tr ( Σ 2 ) ≤ λ 2 + 1 / ( m − 1 ) \operatorname{tr}(\Sigma^2)\le\lambda^2+1/(m-1) tr ( Σ 2 ) ≤ λ 2 + 1/ ( m − 1 ) , and the sufficient-statistic attack has tr ( Σ 2 ) ≤ 1 / m + 14 ρ ˉ 2 \operatorname{tr}(\Sigma^2)\le1/m+14\bar{\rho}^2 tr ( Σ 2 ) ≤ 1/ m + 14 ρ ˉ 2 on its success event. Since m = 40 k m=40k m = 40 k and λ , ρ ˉ = Θ ( α 2 ) \lambda,\bar{\rho}=\Theta(\alpha^2) λ , ρ ˉ = Θ ( α 2 ) , both meet (83) after decreasing the fixed upper accuracy cutoff and increasing the fixed lower bound on α 2 k \alpha^2k α 2 k , if necessary. The sufficient-statistic attack can enforce its covariance bound on every execution by aborting before a query that would violate it, without changing its success guarantee. These constant adjustments do not change either query bound. Consequently, the sufficient-statistic attack is optimal within this family, and the general attack is optimal up to its logarithmic factor. The lower bound is witnessed by a distribution over matrices; it does not claim hardness for every fixed matrix.
Proof ingredients
Lemma D.4 (A fixed law rarely has large variance). For any fixed unit vector s s s and covariance Γ ⪰ 0 \Gamma\succeq0 Γ ⪰ 0 with Γ s = 0 \Gamma s=0 Γ s = 0 and tr Γ ≤ 1 \operatorname{tr}\Gamma\le1 tr Γ ≤ 1 , and every v > 0 v>0 v > 0 ,
Pr A [ ν ≥ v ] ≤ ( e k v ) k / 2 . (89) \Pr_A[\nu\ge v]\le\left(\frac{e}{kv}\right)^{k/2}. \tag*{(89)} A Pr [ ν ≥ v ] ≤ ( k v e ) k /2 . (89) In particular, Pr A [ ν ≥ 4 e / k ] ≤ 2 − k \Pr_A[\nu\ge4e/k]\le2^{-k} Pr A [ ν ≥ 4 e / k ] ≤ 2 − k .
Proof. Gaussian rotational invariance and Γ s = 0 \Gamma s=0 Γ s = 0 imply that x = A s ∼ N ( 0 , I k / k ) x=As\sim\mathcal{N}(0,I_k/k) x = A s ∼ N ( 0 , I k / k ) is independent of K = A Γ A T K=A\Gamma A^{\mathsf T} K = A Γ A T . If K K K is singular, then x ∉ im ( K ) x\notin\operatorname{im}(K) x ∈ / im ( K ) almost surely, so ν = 0 \nu=0 ν = 0 . For K ≻ 0 K\succ0 K ≻ 0 and a > 0 a>0 a > 0 , the Gaussian quadratic-form identity gives
Pr [ ν ≥ v ∣ K ] ≤ e a / v E [ e − a x T K − 1 x ∣ K ] = e a / v det ( I k + 2 a k K − 1 ) − 1 / 2 ≤ e a / v ( k 2 a ) k / 2 det K . \Pr[\nu\ge v\mid K]\le e^{a/v}\mathbb{E}\left[e^{-a x^{\mathsf T}K^{-1}x}\mid K\right]
= e^{a/v}\det\left(I_k+\frac{2a}{k}K^{-1}\right)^{-1/2}
\le e^{a/v}\left(\frac{k}{2a}\right)^{k/2}\sqrt{\det K}. Pr [ ν ≥ v ∣ K ] ≤ e a / v E [ e − a x T K − 1 x ∣ K ] = e a / v det ( I k + k 2 a K − 1 ) − 1/2 ≤ e a / v ( 2 a k ) k /2 det K .
Moreover, E det K ≤ k − k \mathbb{E}\det K\le k^{-k} E det K ≤ k − k . To see this, the rows of A Γ 1 / 2 A\Gamma^{1/2} A Γ 1/2 are independent Gaussian vectors with covariance Γ / k \Gamma/k Γ/ k . Gram–Schmidt expresses their Gram determinant as the product of their squared distances from the preceding row spans. Each distance has conditional expectation at most tr Γ / k ≤ 1 / k \operatorname{tr}\Gamma/k\le1/k tr Γ/ k ≤ 1/ k , so successive conditioning gives the bound. Thus E det K ≤ k − k / 2 \mathbb{E}\sqrt{\det K}\le k^{-k/2} E det K ≤ k − k /2 . Averaging the preceding display and taking a = k v / 2 a=kv/2 a = k v /2 proves (89) .
The next lemma converts this small prior probability into a bound for adaptively selected laws. It conditions on the attacker’s complete fresh draw, not just its query. All logarithms below are natural.
Lemma D.5 (Information needed to reach a rare query law). For each announcement D \mathcal{D} D , let Bad ( A , D ) \operatorname{Bad}(A,\mathcal{D}) Bad ( A , D ) be an event with probability at most q q q under the matrix prior, for every fixed D \mathcal{D} D . At query i i i , let Z i Z_i Z i denote the complete fresh draw and suppose the observation is
F i ( A , Z i ) + ξ i , ξ i ∼ N ( 0 , σ 2 ) , F_i(A,Z_i)+\xi_i,\qquad\xi_i\sim N(0,\sigma^2), F i ( A , Z i ) + ξ i , ξ i ∼ N ( 0 , σ 2 ) , with independent fresh ξ i \xi_i ξ i . The functions below may depend on the announcement. Suppose an ideal response f i ( Z i ) f_i(Z_i) f i ( Z i ) does not otherwise depend on A A A , and that whenever the current announcement is not bad,
E [ ( F i ( A , Z i ) − f i ( Z i ) ) 2 ∣ A , past and announcement ] ≤ b . (90) \mathbb{E}\left[(F_i(A,Z_i)-f_i(Z_i))^2\mid A,\text{ past and announcement}\right]\le b. \tag*{(90)} E [ ( F i ( A , Z i ) − f i ( Z i ) ) 2 ∣ A , past and announcement ] ≤ b . (90) Let τ \tau τ be the first query whose announcement is bad. For every horizon N N N with 0 < N q < 1 0<Nq<1 0 < N q < 1 ,
Pr [ τ ≤ N ] ≤ N b / ( 2 σ 2 ) + log 2 log ( 1 / ( N q ) ) . (91) \Pr[\tau\le N]\le\frac{Nb/(2\sigma^2)+\log2}{\log(1/(Nq))}. \tag*{(91)} Pr [ τ ≤ N ] ≤ log ( 1/ ( N q )) N b / ( 2 σ 2 ) + log 2 . (91) Proof. Let P \mathbb{P} P be the joint law of A A A and the attacker’s execution when the responses are real before τ \tau τ and ideal, f i ( Z i ) + ξ i f_i(Z_i)+\xi_i f i ( Z i ) + ξ i , from query τ \tau τ onward. Let Q \mathbb{Q} Q use ideal responses throughout. These modified interactions are used only in the proof. The real interaction and P \mathbb{P} P agree through the announcement at the first bad query, and hence have the same crossing probability. Under Q \mathbb{Q} Q , the attacker’s execution is independent of A A A . A union bound therefore gives Q ( τ ≤ N ) ≤ N q \mathbb{Q}(\tau\le N)\le Nq Q ( τ ≤ N ) ≤ N q .
The two interactions use the same matrix prior, the same adaptive announcement rule, and the same fresh-draw kernels. Conditional on A A A , the past, and Z i Z_i Z i , their observation kernels are Gaussians with common variance σ 2 \sigma^2 σ 2 . The KL chain rule gives
D K L ( P ∥ Q ) = 1 2 σ 2 ∑ i = 1 N E P [ 1 i < τ ( F i ( A , Z i ) − f i ( Z i ) ) 2 ] ≤ N b 2 σ 2 . D_{\mathrm{KL}}(\mathbb{P}\Vert\mathbb{Q})=\frac{1}{2\sigma^2}\sum_{i=1}^{N}\mathbb{E}_{\mathbb{P}}\left[\mathbf{1}_{i<\tau}(F_i(A,Z_i)-f_i(Z_i))^2\right]
\le\frac{Nb}{2\sigma^2}. D KL ( P ∥ Q ) = 2 σ 2 1 i = 1 ∑ N E P [ 1 i < τ ( F i ( A , Z i ) − f i ( Z i ) ) 2 ] ≤ 2 σ 2 N b . The event i < τ i<\tau i < τ is determined before the current fresh draw, so (90) applies. For p = P ( τ ≤ N ) p=\mathbb{P}(\tau\le N) p = P ( τ ≤ N ) , data processing for the indicator of this event gives
D K L ( P ∥ Q ) ≥ p log 1 N q − log 2. D_{\mathrm{KL}}(\mathbb{P}\Vert\mathbb{Q})\ge p\log\frac{1}{Nq}-\log2. D KL ( P ∥ Q ) ≥ p log N q 1 − log 2. Combining the bounds proves the claim. If the event has zero Q \mathbb{Q} Q -probability, it also has zero P \mathbb{P} P -probability by absolute continuity.
Proof of the lower bound
Proof of Theorem D.2. Finding a law with large variance takes many queries. Call an announcement bad when ν i ≥ 4 e / k \nu_i\ge4e/k ν i ≥ 4 e / k , including A S i = 0 A_{S_i}=0 A S i = 0 . By Lemma D.4, its probability is at most 2 − k 2^{-k} 2 − k for every fixed announcement. Apply Lemma D.5 with
F i = T i , f i = w i , b = 4 e / k , q = 2 − k . F_i=T_i,\qquad f_i=w_i,\qquad b=4e/k,\qquad q=2^{-k}. F i = T i , f i = w i , b = 4 e / k , q = 2 − k .
The mean-square bound is (85) . If log N ≤ ( k log 2 ) / 2 \log N\le(k\log2)/2 log N ≤ ( k log 2 ) /2 , then
Pr [ τ ≤ N ] ≤ 4 e log 2 N σ 2 k 2 + 2 k . (92) \Pr[\tau\le N]\le\frac{4e}{\log2}\frac{N}{\sigma^2 k^2}+\frac{2}{k}. \tag*{(92)} Pr [ τ ≤ N ] ≤ log 2 4 e σ 2 k 2 N + k 2 . (92)
With N = Q 0 N=Q_0 N = Q 0 , σ = α / C 1 \sigma=\alpha/C_1 σ = α / C 1 , and c 0 c_0 c 0 sufficiently small relative to C 1 C_1 C 1 , this is at most 0.1 for all sufficiently large k k k . The logarithmic restriction holds because Q 0 ≤ c 0 k 2 Q_0\le c_0k^2 Q 0 ≤ c 0 k 2 .
Below this variance, the responder is accurate. Put ε = δ / 4 \varepsilon=\delta/4 ε = δ /4 . Conditional on A A A , the past, and any announcement with ν i < 4 e / k \nu_i<4e/k ν i < 4 e / k ,
E [ ( o i − w i ) 2 ] ≤ 4 e / k + σ 2 . (93) \mathbb{E}[(o_i-w_i)^2]\le4e/k+\sigma^2. \tag*{(93)} E [( o i − w i ) 2 ] ≤ 4 e / k + σ 2 . (93)
Choose constants a , d > 0 a,d>0 a , d > 0 depending only on the norm task, with a ≤ 1 a\le1 a ≤ 1 . Taking C , C 1 C,C_1 C , C 1 sufficiently large ensures
Pr [ ∣ o i − w i ∣ > α α ] ≤ ε / 2 \Pr[|o_i-w_i|>\alpha\alpha]\le\varepsilon/2 Pr [ ∣ o i − w i ∣ > α α ] ≤ ε /2
by (93) and α 2 k ≥ C \alpha^2k\ge C α 2 k ≥ C . On the complementary event, w i ≤ 2 w_i\le2 w i ≤ 2 and α ≤ 1 \alpha\le1 α ≤ 1 give ∣ o i 2 − w i 2 ∣ ≤ 5 a α |o_i^2-w_i^2|\le5a\alpha ∣ o i 2 − w i 2 ∣ ≤ 5 a α . Also, (83) gives
Pr [ ∣ ∥ u i ∥ 2 2 − tr Γ i − ∥ μ i ∥ 2 2 ∣ > d α ] ≤ c a d / d 2 ≤ ε / 2 , \Pr\left[\left|\|u_i\|_2^2-\operatorname{tr}\Gamma_i-\|\mu_i\|_2^2\right|>d\alpha\right]\le c_{\mathrm{ad}}/d^2\le\varepsilon/2, Pr [ ∥ u i ∥ 2 2 − tr Γ i − ∥ μ i ∥ 2 2 > d α ] ≤ c ad / d 2 ≤ ε /2 ,
after choosing c a d c_{\mathrm{ad}} c ad sufficiently small. The probabilities in these displays have the same conditioning as (93) . Since u i ⊥ s i u_i\perp s_i u i ⊥ s i , outside the two exceptional events,
∣ r ^ i 2 − ∥ v i ∥ 2 2 ∣ ≤ ( 5 a + d ) α . (94) |\widehat r_i^2-\|v_i\|_2^2|\le(5a+d)\alpha. \tag*{(94)} ∣ r i 2 − ∥ v i ∥ 2 2 ∣ ≤ ( 5 a + d ) α . (94)
For the norm gap take a = 1 / 40 a=1/40 a = 1/40 and d = 1 / 8 d=1/8 d = 1/8 . The squared-norm error is at most α / 4 \alpha/4 α /4 , less than the α / 2 \alpha/2 α /2 margin between the decision threshold ( L 2 + U 2 ) / 2 (L^2+U^2)/2 ( L 2 + U 2 ) /2 and either endpoint. For relative norm estimation, take a = min { 1 , κ / 40 } a=\min\{1,\kappa/40\} a = min { 1 , κ /40 } and d = min { 1 / 8 , κ / 8 } d=\min\{1/8,\kappa/8\} d = min { 1/8 , κ /8 } . Then 5 a + d ≤ κ / 4 5a+d\le\kappa/4 5 a + d ≤ κ /4 . Since ∥ v i ∥ 2 2 ≥ w i 2 ≥ 1 / 4 \|v_i\|_2^2\ge w_i^2\ge1/4 ∥ v i ∥ 2 2 ≥ w i 2 ≥ 1/4 ,
∣ r ^ i − ∥ v i ∥ 2 ∣ ∥ v i ∥ 2 ≤ ∣ r ^ i 2 − ∥ v i ∥ 2 2 ∣ ∥ v i ∥ 2 2 ≤ κ α . \frac{|\widehat r_i-\|v_i\|_2|}{\|v_i\|_2}
\le
\frac{|\widehat r_i^2-\|v_i\|_2^2|}{\|v_i\|_2^2}
\le\kappa\alpha. ∥ v i ∥ 2 ∣ r i − ∥ v i ∥ 2 ∣ ≤ ∥ v i ∥ 2 2 ∣ r i 2 − ∥ v i ∥ 2 2 ∣ ≤ κ α .
Thus the conditional task-error probability is at most ε \varepsilon ε whenever ν i < 4 e / k \nu_i<4e/k ν i < 4 e / k .
No long interval has many errors. Define X i = e i 1 i < τ X_i=e_i\mathbf{1}_{i<\tau} X i = e i 1 i < τ . Its conditional mean given A A A and the past is at most ε \varepsilon ε , averaging also over the next announcement if it is randomized. For every θ > 0 \theta>0 θ > 0 ,
E [ e θ X i ∣ A , past ] ≤ 1 − ε + ε e θ . \mathbb{E}[e^{\theta X_i}\mid A,\text{ past}]\le1-\varepsilon+\varepsilon e^\theta. E [ e θ X i ∣ A , past ] ≤ 1 − ε + ε e θ .
Iterating this bound and optimizing over θ \theta θ gives, for every fixed consecutive interval J J J ,
Pr [ ∑ i ∈ J X i ≥ δ ∣ J ∣ ] ≤ exp { − ∣ J ∣ kl ( δ ∥ ε ) } , \Pr\left[\sum_{i\in J}X_i\ge\delta|J|\right]\le\exp\{-|J|\operatorname{kl}(\delta\|\varepsilon)\}, Pr [ i ∈ J ∑ X i ≥ δ ∣ J ∣ ] ≤ exp { − ∣ J ∣ kl ( δ ∥ ε )} ,
where kl ( p ∥ q ) = p log ( p / q ) + ( 1 − p ) log ( ( 1 − p ) / ( 1 − q ) ) \operatorname{kl}(p\|q)=p\log(p/q)+(1-p)\log((1-p)/(1-q)) kl ( p ∥ q ) = p log ( p / q ) + ( 1 − p ) log (( 1 − p ) / ( 1 − q )) . A union bound over at most Q 0 2 Q_0^2 Q 0 2 intervals of length at least ℓ k \ell k ℓ k bounds their total failure probability by
Q 0 2 exp { − ℓ k kl ( δ ∥ ε ) } ≤ 0.1 Q_0^2\exp\{-\ell k\operatorname{kl}(\delta\|\varepsilon)\}\le0.1 Q 0 2 exp { − ℓ k kl ( δ ∥ ε )} ≤ 0.1
for sufficiently large k k k . On τ > Q 0 \tau>Q_0 τ > Q 0 , X i = e i X_i=e_i X i = e i throughout these queries. Combining this estimate with (92) proves (88) .
Proof of the gain lemma
We restate the lemma for reference. The proof uses the scalar Gaussian channel and integration by parts against the signal density.
Lemma 4.1 (General-covariance gain lemma). Let α > 0 \alpha> 0 α > 0 , 0 < c ≤ 1 0 < c \le1 0 < c ≤ 1 , δ 0 = 1 / 20 \delta_0 = 1/20 δ 0 = 1/20 , and c g = 1 / 22 c_g = 1/22 c g = 1/22 . For the query law D Σ \mathcal{D}_{\Sigma} D Σ with signal law W α , c W_{\alpha,c} W α , c , let Σ ⪰ 0 \Sigma\succeq0 Σ ⪰ 0 satisfy tr Σ = 1 \operatorname{tr} \Sigma= 1 tr Σ = 1 and 0 < V ( Σ ) < ∞ 0 < V(\Sigma) < \infty 0 < V ( Σ ) < ∞ . Every measurable response rule ψ : R k → [ − 1 , 1 ] \psi: \mathbb{R}^{k} \to[-1,1] ψ : R k → [ − 1 , 1 ] with L Σ ( ψ ) ≤ δ 0 L_{\Sigma}(\psi) \le\delta_0 L Σ ( ψ ) ≤ δ 0 satisfies
E [ ψ ( y ) ( T Σ ( y ) − w ) ] ≥ c V ( Σ ) g , (95) \mathbb{E}[\psi(y)(T_{\Sigma}(y)-w)] \ge cV(\Sigma)g, \tag*{(95)} E [ ψ ( y ) ( T Σ ( y ) − w )] ≥ c V ( Σ ) g , (95) where
g : = c g c 2 α . g := c_g \frac{c^2}{\alpha}. g := c g α c 2 .
Signal density. Recall ℓ = 10 α / c \ell= 10\alpha/c ℓ = 10 α / c from Definition 3.1 , and put
a = 1 − ℓ , b = 1 + α + ℓ , C W = ( ℓ + α ) − 1 . a = 1-\ell,\qquad b = 1+\alpha+\ell,\qquad C_W = (\ell+\alpha)^{-1}. a = 1 − ℓ , b = 1 + α + ℓ , C W = ( ℓ + α ) − 1 .
Convolving the two uniform densities in Definition 3.1 gives
ν ( w ) = { 0 , w < a or w > b , C W ( w − a ) / ℓ , a ≤ w ≤ 1 , C W , 1 < w < 1 + α , C W ( b − w ) / ℓ , 1 + α ≤ w ≤ b . (96) \nu(w) =
\begin{cases}
0, & w<a\text{ or }w>b,\\
C_W(w-a)/\ell, & a\le w\le1,\\
C_W, & 1<w<1+\alpha,\\
C_W(b-w)/\ell, & 1+\alpha\le w\le b.
\end{cases} \tag*{(96)} ν ( w ) = ⎩ ⎨ ⎧ 0 , C W ( w − a ) / ℓ , C W , C W ( b − w ) / ℓ , w < a or w > b , a ≤ w ≤ 1 , 1 < w < 1 + α , 1 + α ≤ w ≤ b . (96)
Figure 2. The signal density and the two labeled regimes. Each ramp has width ℓ = 10 α / c \ell= 10\alpha/c ℓ = 10 α / c ; the plateau is the unlabeled gap of width α \alpha α . The gap is widened schematically for legibility; horizontal widths are not to scale.
Proof. Fix Σ \Sigma Σ and ψ \psi ψ as in the statement, and write δ : = L Σ ( ψ ) ≤ δ 0 \delta:= L_{\Sigma}(\psi) \le\delta_0 δ := L Σ ( ψ ) ≤ δ 0 .
Reduction to a scalar channel. By (17) ,
T Σ ( y ) = w + X , X ∼ N ( 0 , s 2 ) , s 2 = c 2 V ( Σ ) > 0 , T_{\Sigma}(y) = w + X,\qquad X \sim N(0,s^2),\qquad s^2 = c^2V(\Sigma) > 0, T Σ ( y ) = w + X , X ∼ N ( 0 , s 2 ) , s 2 = c 2 V ( Σ ) > 0 ,
with X X X independent of w w w . Sufficiency of T Σ T_{\Sigma} T Σ gives a measurable function
Ψ ( t ) : = E [ ψ ( y ) ∣ T Σ ( y ) = t ] , ∣ Ψ ( t ) ∣ ≤ 1 , (97) \Psi(t) := \mathbb{E}[\psi(y)\mid T_{\Sigma}(y)=t],\qquad|\Psi(t)|\le1, \tag*{(97)} Ψ ( t ) := E [ ψ ( y ) ∣ T Σ ( y ) = t ] , ∣Ψ ( t ) ∣ ≤ 1 , (97)
such that E [ ψ ( y ) ∣ T Σ ( y ) , w ] = Ψ ( T Σ ( y ) ) \mathbb{E}[\psi(y)\mid T_{\Sigma}(y),w] = \Psi(T_{\Sigma}(y)) E [ ψ ( y ) ∣ T Σ ( y ) , w ] = Ψ ( T Σ ( y )) . Consequently, replacing the response by Ψ ( w + X ) \Psi(w+X) Ψ ( w + X ) preserves both its signal-gap loss and its gain:
G : = Γ ψ ( Σ ) = E [ Ψ ( w + X ) X ] . (98) G := \Gamma_{\psi}(\Sigma) = \mathbb{E}[\Psi(w+X)X]. \tag*{(98)} G := Γ ψ ( Σ ) = E [ Ψ ( w + X ) X ] . (98)
This replacement is only for the proof; the responder may use the full sketch.
An exact formula for the gain. Let ϕ s \phi_s ϕ s be the N ( 0 , s 2 ) N(0,s^2) N ( 0 , s 2 ) density, and define the mean response at signal value w w w by
f ( w ) : = E X [ Ψ ( w + X ) ] = ∫ R Ψ ( t ) ϕ s ( t − w ) d t . f(w) := \mathbb{E}_{X}[\Psi(w+X)] = \int_{\mathbb{R}} \Psi(t)\phi_s(t-w)\,\mathrm{d}t. f ( w ) := E X [ Ψ ( w + X )] = ∫ R Ψ ( t ) ϕ s ( t − w ) d t .
Gaussian convolution makes f f f continuously differentiable, even when Ψ \Psi Ψ is only measurable. Differentiating the density gives
f ′ ( w ) = ∫ R Ψ ( t ) t − w s 2 ϕ s ( t − w ) d t = 1 s 2 E X [ Ψ ( w + X ) X ] . (99) f'(w) = \int_{\mathbb{R}} \Psi(t)\frac{t-w}{s^2}\phi_s(t-w)\,\mathrm{d}t = \frac{1}{s^2}\mathbb{E}_{X}[\Psi(w+X)X]. \tag*{(99)} f ′ ( w ) = ∫ R Ψ ( t ) s 2 t − w ϕ s ( t − w ) d t = s 2 1 E X [ Ψ ( w + X ) X ] . (99)
Thus G = s 2 ∫ R ν ( w ) f ′ ( w ) d w G=s^2\int_{\mathbb{R}}\nu(w)f'(w)\,\mathrm{d}w G = s 2 ∫ R ν ( w ) f ′ ( w ) d w . The trapezoidal density ν \nu ν is continuous, vanishes at a , b a,b a , b , and has derivative C W / ℓ C_W/\ell C W / ℓ on [ a , 1 ] [a,1] [ a , 1 ] , − C W / ℓ -C_W/\ell − C W / ℓ on [ 1 + α , b ] [1+\alpha,b] [ 1 + α , b ] , and zero elsewhere, apart from its breakpoints. Integration by parts therefore yields the exact identity
G = − s 2 ∫ R ν ′ ( w ) f ( w ) d w = C W s 2 ℓ ( ∫ 1 + α b f ( w ) d w − ∫ a 1 f ( w ) d w ) . (100) G=-s^2\int_{\mathbb{R}}\nu'(w)f(w)\,\mathrm{d}w=\frac{C_Ws^2}{\ell}\left(\int_{1+\alpha}^{b}f(w)\,\mathrm{d}w-\int_{a}^{1}f(w)\,\mathrm{d}w\right). \tag*{(100)} G = − s 2 ∫ R ν ′ ( w ) f ( w ) d w = ℓ C W s 2 ( ∫ 1 + α b f ( w ) d w − ∫ a 1 f ( w ) d w ) . (100)
This is the role of the ramps: the gain depends on the difference between the average responses in the two labeled regimes. Continuity of ν \nu ν eliminates boundary terms at the internal breakpoints.
Using the loss bound. Put H − ( w ) : = ( 1 + f ( w ) ) / 2 H_-(w):=(1+f(w))/2 H − ( w ) := ( 1 + f ( w )) /2 and H + ( w ) : = ( 1 − f ( w ) ) / 2 H_+(w):=(1-f(w))/2 H + ( w ) := ( 1 − f ( w )) /2 , both in [ 0 , 1 ] [0,1] [ 0 , 1 ] . The loss condition is
∫ a 1 ν ( w ) H − ( w ) d w + ∫ 1 + α b ν ( w ) H + ( w ) d w = δ . (101) \int_{a}^{1}\nu(w)H_-(w)\,\mathrm{d}w+\int_{1+\alpha}^{b}\nu(w)H_+(w)\,\mathrm{d}w=\delta. \tag*{(101)} ∫ a 1 ν ( w ) H − ( w ) d w + ∫ 1 + α b ν ( w ) H + ( w ) d w = δ . (101)
On [ a + ℓ / 4 , 1 ] [a+\ell/4,1] [ a + ℓ /4 , 1 ] and [ 1 + α , b − ℓ / 4 ] [1+\alpha,b-\ell/4] [ 1 + α , b − ℓ /4 ] , the density is at least C W / 4 C_W/4 C W /4 . The two omitted intervals have total length ℓ / 2 \ell/2 ℓ /2 . Using (101) on the former intervals and H ± ≤ 1 H_\pm\leq1 H ± ≤ 1 on the latter gives
∫ a 1 H − ( w ) d w + ∫ 1 + α b H + ( w ) d w ≤ ℓ 2 + 4 δ C W . \int_{a}^{1}H_-(w)\,\mathrm{d}w+\int_{1+\alpha}^{b}H_+(w)\,\mathrm{d}w\leq\frac{\ell}{2}+\frac{4\delta}{C_W}. ∫ a 1 H − ( w ) d w + ∫ 1 + α b H + ( w ) d w ≤ 2 ℓ + C W 4 δ .
Since each ramp has length ℓ \ell ℓ , it follows that
∫ 1 + α b f ( w ) d w − ∫ a 1 f ( w ) d w = 2 ℓ − 2 ( ∫ a 1 H − ( w ) d w + ∫ 1 + α b H + ( w ) d w ) ≥ ℓ − 8 δ C W ≥ ℓ 2 . \int_{1+\alpha}^{b}f(w)\,\mathrm{d}w-\int_{a}^{1}f(w)\,\mathrm{d}w=2\ell-2\left(\int_{a}^{1}H_-(w)\,\mathrm{d}w+\int_{1+\alpha}^{b}H_+(w)\,\mathrm{d}w\right)\geq\ell-\frac{8\delta}{C_W}\geq\frac{\ell}{2}. ∫ 1 + α b f ( w ) d w − ∫ a 1 f ( w ) d w = 2 ℓ − 2 ( ∫ a 1 H − ( w ) d w + ∫ 1 + α b H + ( w ) d w ) ≥ ℓ − C W 8 δ ≥ 2 ℓ .
The last inequality uses 0 < c ≤ 1 0<c\leq1 0 < c ≤ 1 , which gives C W ℓ = 10 / ( 10 + c ) ≥ 10 / 11 C_W\ell=10/(10+c)\geq10/11 C W ℓ = 10/ ( 10 + c ) ≥ 10/11 , and δ ≤ δ 0 = 1 / 20 ≤ C W ℓ / 16 \delta\leq\delta_0=1/20\leq C_W\ell/16 δ ≤ δ 0 = 1/20 ≤ C W ℓ /16 . Substituting into (100) and using C W = c / ( ( 10 + c ) α ) ≥ c / ( 11 α ) C_W=c/((10+c)\alpha)\geq c/(11\alpha) C W = c / (( 10 + c ) α ) ≥ c / ( 11 α ) , we obtain
G ≥ C W s 2 2 ≥ c s 2 22 α = c g c 3 V ( Σ ) α = c V ( Σ ) g , G\geq\frac{C_Ws^2}{2}\geq\frac{cs^2}{22\alpha}=c_g\frac{c^3\mathcal{V}(\Sigma)}{\alpha}=c\mathcal{V}(\Sigma)g, G ≥ 2 C W s 2 ≥ 22 α c s 2 = c g α c 3 V ( Σ ) = c V ( Σ ) g ,
where s 2 = c 2 V ( Σ ) s^2=c^2\mathcal{V}(\Sigma) s 2 = c 2 V ( Σ ) and c g = 1 / 22 c_g=1/22 c g = 1/22 .
Universal hardness and the isotropic endpoint
We first identify the Bayes-optimal signal-gap response, justifying the sufficient-statistic responder class. Its risk gives a direct hardness bound whenever the scalar-channel standard deviation is a fixed positive multiple of the signal gap. For the high-accuracy isotropic round, a direct norm-hardness argument complements this signal bound, avoiding any change of signal width or norm thresholds. The covariance-update analyses use the separate hardness threshold at loss level δ 0 \delta_0 δ 0 from Corollary B.5 .
Optimal signal-gap prediction
Proposition F.1 (The Bayes signal-gap response). Let α , c > 0 \alpha,c>0 α , c > 0 and 0 < V ( Σ ) < ∞ 0<\mathcal{V}(\Sigma)<\infty 0 < V ( Σ ) < ∞ . For the signal law W α , c W_{\alpha,c} W α , c , the signal-gap risk has a unique minimizing response rule, up to null sets:
ψ B a y e s ( y ) = { − 1 , T Σ ( y ) < 1 + α / 2 , + 1 , T Σ ( y ) > 1 + α / 2. \psi_{\mathrm{Bayes}}(y)=
\begin{cases}
-1, & T_{\Sigma}(y)<1+\alpha/2,\\
+1, & T_{\Sigma}(y)>1+\alpha/2.
\end{cases} ψ Bayes ( y ) = { − 1 , + 1 , T Σ ( y ) < 1 + α /2 , T Σ ( y ) > 1 + α /2. The response at equality is immaterial. In particular, every exactly loss-optimal signal-gap responder satisfies Definition 5.1 whenever the scalar channel has positive finite variance.
Proof. Write d = 1 + α / 2 d=1+\alpha/2 d = 1 + α /2 and s 2 = c 2 V ( Σ ) > 0 s^2=c^2\mathcal{V}(\Sigma)>0 s 2 = c 2 V ( Σ ) > 0 . By sufficiency, the posterior law of w w w depends on the sketch only through T = T Σ ( y ) T=T_{\Sigma}(y) T = T Σ ( y ) . Write ν \nu ν for the signal density (96) , with support endpoints a = 1 − 10 α / c a=1-10\alpha/c a = 1 − 10 α / c and b = 1 + α + 10 α / c b=1+\alpha+10\alpha/c b = 1 + α + 10 α / c . Let ϕ s \phi_s ϕ s be the N ( 0 , s 2 ) N(0,s^2) N ( 0 , s 2 ) density and put
f − ( t ) = ∫ a 1 ν ( w ) ϕ s ( t − w ) d w , f + ( t ) = ∫ 1 + α b ν ( w ) ϕ s ( t − w ) d w . f_-(t)=\int_a^1 \nu(w)\phi_s(t-w)\,dw,\qquad f_+(t)=\int_{1+\alpha}^b \nu(w)\phi_s(t-w)\,dw. f − ( t ) = ∫ a 1 ν ( w ) ϕ s ( t − w ) d w , f + ( t ) = ∫ 1 + α b ν ( w ) ϕ s ( t − w ) d w . These are the unnormalized posterior masses of the two labeled regimes. The density ν \nu ν is symmetric about d d d . Pairing w ≤ 1 w\le1 w ≤ 1 with 2 d − w ≥ 1 + α 2d-w\ge1+\alpha 2 d − w ≥ 1 + α shows that f + ( t ) > f − ( t ) f_+(t)>f_-(t) f + ( t ) > f − ( t ) when t > d t>d t > d : each paired high signal is closer to t t t than its low counterpart. The inequality reverses when t < d t<d t < d . The conditional loss is affine in the response, with coefficient proportional to f − ( t ) − f + ( t ) f_-(t)-f_+(t) f − ( t ) − f + ( t ) , so its unique minimizer is the stated endpoint of [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] . Finally, T T T has a continuous density, so T = d T=d T = d is a null event. □ \square □
A direct hardness bound
Lemma F.2 (Large signal-estimation variance implies signal-gap hardness). Fix constants 0 < c ≤ 5 0<c\le5 0 < c ≤ 5 and 0 < τ ≤ 1 0<\tau\le1 0 < τ ≤ 1 , and put
δ h a r d ( c , τ ) : = c τ 10 + c Φ ( − 1 − 1 2 τ ) > 0 , (102) \delta_{\mathrm{hard}}(c,\tau):=\frac{c\tau}{10+c}\Phi\left(-1-\frac{1}{2\tau}\right)>0, \tag*{(102)} δ hard ( c , τ ) := 10 + c c τ Φ ( − 1 − 2 τ 1 ) > 0 , (102) where Φ \Phi Φ is the standard normal distribution function. If
c V ( Σ ) ≥ τ α , (103) c\sqrt{\mathcal{V}(\Sigma)}\ge\tau\alpha, \tag*{(103)} c V ( Σ ) ≥ τ α , (103) then every measurable response rule ψ : R k → [ − 1 , 1 ] \psi:\mathbb{R}^k\to[-1,1] ψ : R k → [ − 1 , 1 ] satisfies L Σ ( ψ ) ≥ δ h a r d ( c , τ ) L_{\Sigma}(\psi)\ge\delta_{\mathrm{hard}}(c,\tau) L Σ ( ψ ) ≥ δ hard ( c , τ ) ; hence D Σ D_{\Sigma} D Σ is universally hard for the signal gap.
Proof. Let ν \nu ν , ℓ = 10 α / c \ell=10\alpha/c ℓ = 10 α / c , and C W = 1 / ( ℓ + α ) C_W=1/(\ell+\alpha) C W = 1/ ( ℓ + α ) be as in (96) . The two labeled regimes each have probability p c = C W ℓ / 2 = 5 / ( 10 + c ) p_c=C_W\ell/2=5/(10+c) p c = C W ℓ /2 = 5/ ( 10 + c ) . If V ( Σ ) = + ∞ \mathcal{V}(\Sigma)=+\infty V ( Σ ) = + ∞ , the sketch is independent of the signal, so every rule has loss p c ≥ δ h a r d ( c , τ ) p_c\ge\delta_{\mathrm{hard}}(c,\tau) p c ≥ δ hard ( c , τ ) . Otherwise put σ = c V ( Σ ) ≥ τ α > 0 \sigma=c\sqrt{\mathcal{V}(\Sigma)}\ge\tau\alpha>0 σ = c V ( Σ ) ≥ τ α > 0 . By Proposition F.1, thresholding T Σ ( y ) T_{\Sigma}(y) T Σ ( y ) at 1 + α / 2 1+\alpha/2 1 + α /2 minimizes the loss. Symmetry of the signal density about this threshold gives the minimum risk
R ∗ = 2 ∫ 0 ℓ ν ( 1 − x ) Φ ( − α / 2 + x σ ) d x . R^*=2\int_0^\ell\nu(1-x)\Phi\left(-\frac{\alpha/2+x}{\sigma}\right)\,dx. R ∗ = 2 ∫ 0 ℓ ν ( 1 − x ) Φ ( − σ α /2 + x ) d x . Restrict the integral to 0 ≤ x ≤ s : = τ α 0\le x\le s:=\tau\alpha 0 ≤ x ≤ s := τ α . Here s / ℓ = c τ / 10 ≤ 1 / 2 s/\ell=c\tau/10\le1/2 s / ℓ = c τ /10 ≤ 1/2 , so ν ( 1 − x ) = C W ( 1 − x / ℓ ) ≥ C W / 2 \nu(1-x)=C_W(1-x/\ell)\ge C_W/2 ν ( 1 − x ) = C W ( 1 − x / ℓ ) ≥ C W /2 . Also σ ≥ s \sigma\ge s σ ≥ s gives
Φ ( − α / 2 + x σ ) ≥ Φ ( − 1 − 1 2 τ ) . \Phi\left(-\frac{\alpha/2+x}{\sigma}\right)\ge\Phi\left(-1-\frac{1}{2\tau}\right). Φ ( − σ α /2 + x ) ≥ Φ ( − 1 − 2 τ 1 ) . Consequently every response rule has loss at least
R ∗ ≥ C W τ α Φ ( − 1 − 1 2 τ ) = δ h a r d ( c , τ ) . R^*\ge C_W\tau\alpha\Phi\left(-1-\frac{1}{2\tau}\right)=\delta_{\mathrm{hard}}(c,\tau). R ∗ ≥ C W τ α Φ ( − 1 − 2 τ 1 ) = δ hard ( c , τ ) . □ \square □
The very high accuracy regime
For α = O ( k − 1 / 2 ) \alpha= O(k^{-1/2}) α = O ( k − 1/2 ) , the initial isotropic query distribution is already universally hard for both the signal-gap and norm tasks, with high constant probability over random-coordinate initialization. Thus the attack can return its first round, without any covariance updates.
Corollary F.3 (An isotropic round at very high accuracy). Fix constants 0 < c ≤ 1 0 < c \le1 0 < c ≤ 1 and C ≥ 1 C \ge1 C ≥ 1 . For every A ∈ R k × n A \in\mathbb{R}^{k \times n} A ∈ R k × n with n > 40 k n > 40k n > 40 k and 0 < α ≤ min { c / 20 , C / k } 0 < \alpha\le\min\{c/20, C/\sqrt{k}\} 0 < α ≤ min { c /20 , C / k } , use random-coordinate initialization on any prescribed 40 k + 1 40k + 1 40 k + 1 coordinates and run the first round with m = 40 k m = 40k m = 40 k , Σ = I m / m \Sigma= I_m/m Σ = I m / m , and W = W α , c W = W_{\alpha,c} W = W α , c . Keep the thresholds and response conversion of § 3.3 . For a sufficiently large round length r = Θ ( k ) r = \Theta(k) r = Θ ( k ) , returning this round gives the following guarantee against every informed responder.
There is δ i s o = δ i s o ( c , C ) > 0 \delta_{\mathrm{iso}} = \delta_{\mathrm{iso}}(c, C) > 0 δ iso = δ iso ( c , C ) > 0 such that, with probability at least 0.9 0.9 0.9 , both the empirical signal-gap loss and the fraction of norm-task errors are at least δ i s o / 2 \delta_{\mathrm{iso}}/2 δ iso /2 . For norm estimation, an error means relative error greater than α / 16 \alpha/16 α /16 . On the same event, the distribution is universally hard for the signal-gap task and the chosen norm task, with expected loss at least δ i s o \delta_{\mathrm{iso}} δ iso .
Proof. With probability at least 0.95 0.95 0.95 over h h h , Corollary B.2 gives V ( I m / m ) ≥ 1 / ( 40 k ) \mathcal{V}(I_m/m) \ge1/(40k) V ( I m / m ) ≥ 1/ ( 40 k ) , including infinite variance. Thus c V ( I m / m ) ≥ τ α c\sqrt{\mathcal{V}(I_m/m)} \ge\tau\alpha c V ( I m / m ) ≥ τ α for τ = c / ( 40 C ) \tau= c/(\sqrt{40}C) τ = c / ( 40 C ) . By Lemma F.2 , every response rule has signal-gap loss at least δ s g : = δ h a r d ( c , τ ) > 0 \delta_{\mathrm{sg}} := \delta_{\mathrm{hard}}(c,\tau) > 0 δ sg := δ hard ( c , τ ) > 0 .
For the norm task, fix any h h h . Let P P P project onto the row space of A M A_M A M , put q = rank ( A M ) ≤ k q = \operatorname{rank}(A_M) \le k q = rank ( A M ) ≤ k , and set d = m − q ≥ 39 k d = m - q \ge39k d = m − q ≥ 39 k . Even revealing w w w and P u P u P u , which together determine the sketch, leaves an independent Gaussian component in ker A M \ker A_M ker A M . Hence
∥ v ∥ 2 2 = w 2 + c 2 m ( Q + X ) , Q = m ∥ P u ∥ 2 2 ∼ χ q 2 , X ∼ χ d 2 , \lVert v\rVert_2^2 = w^2 + \frac{c^2}{m}(Q + X), \qquad Q = m\lVert P u\rVert_2^2 \sim\chi_q^2, \qquad X \sim\chi_d^2, ∥ v ∥ 2 2 = w 2 + m c 2 ( Q + X ) , Q = m ∥ P u ∥ 2 2 ∼ χ q 2 , X ∼ χ d 2 ,
with X X X independent of the revealed observation. On A : = { w ≤ 1 , q − q ≤ Q ≤ q } \mathcal{A} := \{w \le1,\ q - \sqrt{q} \le Q \le q\} A := { w ≤ 1 , q − q ≤ Q ≤ q } , the event X ≤ d X \le d X ≤ d implies ∥ v ∥ 2 ≤ L \lVert v\rVert_2 \le L ∥ v ∥ 2 ≤ L , whereas X ≥ d + D d X \ge d + D\sqrt{d} X ≥ d + D d implies ∥ v ∥ 2 ≥ U \lVert v\rVert_2 \ge U ∥ v ∥ 2 ≥ U , for a constant D = D ( c , C ) D = D(c,C) D = D ( c , C ) . Indeed, use 1 − w 2 ≤ 20 α / c 1 - w^2 \le20\alpha/c 1 − w 2 ≤ 20 α / c , q − Q ≤ k q - Q \le\sqrt{k} q − Q ≤ k , α k ≤ C \alpha\sqrt{k} \le C α k ≤ C , and the thresholds (7) . The probabilities of q − q ≤ Q ≤ q q - \sqrt{q} \le Q \le q q − q ≤ Q ≤ q , X ≤ d X \le d X ≤ d , and X ≥ d + D d X \ge d + D\sqrt{d} X ≥ d + D d have positive constant lower bounds uniformly in q , d q,d q , d : the central limit theorem gives positive limits, and each of the finitely many remaining probabilities is positive (take Q = 0 Q = 0 Q = 0 when q = 0 q = 0 q = 0 ). Since Pr ( w ≤ 1 ) = 5 / ( 10 + c ) \Pr(w \le1) = 5/(10 + c) Pr ( w ≤ 1 ) = 5/ ( 10 + c ) independently of Q Q Q , A \mathcal{A} A also has constant probability. Conditional on each observation in A \mathcal{A} A , both norm labels therefore have positive constant probability. Every norm-gap responder consequently has expected loss at least some δ n g = δ n g ( c , C ) > 0 \delta_{\mathrm{ng}} = \delta_{\mathrm{ng}}(c,C) > 0 δ ng = δ ng ( c , C ) > 0 . Thresholding as in (8) maps every norm estimate with relative error at most α / 16 \alpha/16 α /16 to a correct gap answer, so the same bound holds for norm-estimation errors.
Set δ i s o = min { δ s g , δ n g } \delta_{\mathrm{iso}} = \min\{\delta_{\mathrm{sg}}, \delta_{\mathrm{ng}}\} δ iso = min { δ sg , δ ng } . On successful initialization, both expected-loss bounds hold conditional on every preceding history. Martingale Hoeffding and a union bound show that both empirical losses are at least δ i s o / 2 \delta_{\mathrm{iso}}/2 δ iso /2 , except with probability at most 2 exp ( − r δ i s o 2 / 2 ) ≤ 0.05 2\exp(-r\delta_{\mathrm{iso}}^2/2) \le0.05 2 exp ( − r δ iso 2 /2 ) ≤ 0.05 for a sufficiently large absolute factor in r = Θ ( k ) r = \Theta(k) r = Θ ( k ) . The overall success probability is at least 0.95 2 > 0.9 0.95^2 > 0.9 0.9 5 2 > 0.9 . No test against δ 0 \delta_0 δ 0 is needed. □
Implementation and resource bounds
We give the eigenvalue formulas and compact covariance representations used to implement the attacks. The bounds count arithmetic operations and words of working memory; they do not include a finite-precision analysis.
The general attack
The iterates have a compact representation: each update adds at most one direction to the subspace on which the covariance differs from an isotropic matrix.
Entropy projection. Diagonalize the unprojected iterate as Σ ^ = U diag ( s ^ 1 , … , s ^ m ) U T \widehat{\Sigma}=U\operatorname{diag}(\widehat{s}_1,\ldots,\widehat{s}_m)U^{\mathsf{T}} Σ = U diag ( s 1 , … , s m ) U T . The search space is orthogonally invariant. For fixed eigenvalues of Σ ′ \Sigma' Σ ′ , the trace inequality maximizes tr ( Σ ′ log Σ ^ ) \operatorname{tr}(\Sigma'\log\widehat{\Sigma}) tr ( Σ ′ log Σ ) by aligning its eigenvectors with those of Σ ^ \widehat{\Sigma} Σ in the same order. The remaining scalar minimization of ∑ i s i log ( s i / s ^ i ) \sum_i s_i\log(s_i/\widehat{s}_i) ∑ i s i log ( s i / s i ) gives
s i = max { q 0 , τ s ^ i } , ∑ i s i = 1. (104) s_i=\max\{q_0,\tau\widehat{s}_i\},\qquad\sum_i s_i=1. \tag*{(104)} s i = max { q 0 , τ s i } , i ∑ s i = 1. (104)
No upper clipping is needed: the floor and trace constraint imply s i ≤ 1 − ( m − 1 ) q 0 = λ s_i\le1-(m-1)q_0=\lambda s i ≤ 1 − ( m − 1 ) q 0 = λ . The scale τ > 0 \tau>0 τ > 0 can be found by sorting the breakpoints q 0 / s ^ i q_0/\widehat{s}_i q 0 / s i and solving the linear equation on the appropriate interval. Equal eigenvalues may be grouped with their multiplicities.
Proposition G.1 (Structure of the iterates). For every t ≥ 0 t\ge0 t ≥ 0 , Σ t = β t I m + U t Λ t U t T \Sigma_t=\beta_t I_m+U_t\Lambda_tU_t^{\mathsf{T}} Σ t = β t I m + U t Λ t U t T for some β t > 0 \beta_t>0 β t > 0 , an m × d t m\times d_t m × d t matrix U t U_t U t with orthonormal columns, d t ≤ min { t , m } d_t\le\min\{t,m\} d t ≤ min { t , m } , and a diagonal matrix Λ t \Lambda_t Λ t .
Proof. Initially Σ 0 = I m / m \Sigma_0=I_m/m Σ 0 = I m / m and d 0 = 0 d_0=0 d 0 = 0 . For the inductive step, let V = im ( U t ) + span ( a t ) V=\operatorname{im}(U_t)+\operatorname{span}(a_t) V = im ( U t ) + span ( a t ) , of dimension at most d t + 1 d_t+1 d t + 1 . Both Σ t \Sigma_t Σ t and Z t Z_t Z t preserve V V V ; on V ⊥ V^\perp V ⊥ they act as β t I \beta_t I β t I and zero. Hence the exponential update also preserves V V V and is isotropic on V ⊥ V^\perp V ⊥ . The projection keeps eigenvectors and maps equal eigenvalues to equal eigenvalues, by (104) . The projected iterate therefore has the asserted form with d t + 1 ≤ min { d t + 1 , m } d_{t+1}\le\min\{d_t+1,m\} d t + 1 ≤ min { d t + 1 , m } .
Arithmetic and working memory. Store Σ t \Sigma_t Σ t as ( β t , U t , Λ t ) (\beta_t,U_t,\Lambda_t) ( β t , U t , Λ t ) . Its square root is
R t = β t I m + U t ( ( β t I + Λ t ) 1 / 2 − β t I ) U t T , R_t=\sqrt{\beta_t}I_m+U_t\left((\beta_t I+\Lambda_t)^{1/2}-\sqrt{\beta_t}I\right)U_t^{\mathsf{T}}, R t = β t I m + U t ( ( β t I + Λ t ) 1/2 − β t I ) U t T ,
and its inverse square root has the analogous form. Applying either matrix to a vector costs O ( m ( 1 + d t ) ) O(m(1+d_t)) O ( m ( 1 + d t )) operations. An update expands the basis by at most one vector, diagonalizes a matrix of order at most d t + 1 d_t+1 d t + 1 , and applies (104) to its eigenvalues and the repeated eigenvalue on V ⊥ V^\perp V ⊥ . Using standard dense linear-algebra costs, this takes O ( m ( 1 + d t ) 2 + ( 1 + d t ) 3 ) O(m(1+d_t)^2+(1+d_t)^3) O ( m ( 1 + d t ) 2 + ( 1 + d t ) 3 ) operations. Since r ≥ 48 m r\ge48m r ≥ 48 m , the round cost is O ( r m ( 1 + d t ) ) O(rm(1+d_t)) O ( r m ( 1 + d t )) .
Writing Q = r T max Q=rT_{\max} Q = r T m a x , the resulting bounds are
O ( Q m min { T max , m } ) arithmetic operations , O ( m min { T max , m } ) words of working memory . (105) \begin{aligned}
O(Qm\min\{T_{\max},m\})&\quad\text{arithmetic operations},\\
O(m\min\{T_{\max},m\})&\quad\text{words of working memory}. \tag*{(105)}
\end{aligned} O ( Q m min { T m a x , m }) O ( m min { T m a x , m }) arithmetic operations , words of working memory . (105)
The working memory includes the current query, the running sums, and the coordinate support. A returned round is identified by its query indices in the attacker’s record of generated inputs and returned answers, which can be written as the interaction proceeds. This record does not include the responder’s private part of T r T_r T r . If an explicit copy of all round vectors is required, its O ( r m ) O(rm) O ( r m ) output storage is additional to the working-memory bound. No list of past covariances is stored.
For the norm-estimation parameters, these bounds become O ~ ( k 2 + α 4 k 4 ) \widetilde{O}(k^2+\alpha^4k^4) O ( k 2 + α 4 k 4 ) operations and O ~ ( k + α 2 k 2 ) \widetilde{O}(k+\alpha^2k^2) O ( k + α 2 k 2 ) working memory. At α = Θ ( k − 1 / 2 ) \alpha=\Theta(k^{-1/2}) α = Θ ( k − 1/2 ) , the cost per query is O ~ ( k ) \widetilde{O}(k) O ( k ) , comparable to writing its nonzero coordinates. At constant α \alpha α , the rank bound permits a full-dimensional representation.
The sufficient-statistic attack
Proposition G.2 (Compact iterates). Every iterate has the form Σ t = β t I m + U t Λ t U t T \Sigma_t = \beta_t I_m + U_t \Lambda_t U_t^{\mathsf{T}} Σ t = β t I m + U t Λ t U t T , with β t > 0 \beta_t > 0 β t > 0 , an m × d t m \times d_t m × d t matrix U t U_t U t with orthonormal columns, d t ≤ min { t , m } d_t \le\min\{t,m\} d t ≤ min { t , m } , and diagonal Λ t ⪰ 0 \Lambda_t \succeq0 Λ t ⪰ 0 . The update and the top eigenvalue needed for the stopping test can be computed in a subspace of dimension at most d t + 1 d_t + 1 d t + 1 .
Proof. The representation holds initially. For the inductive step, put p = Σ t 1 / 2 h ^ t p = \Sigma_t^{1/2}\hat{h}_t p = Σ t 1/2 h ^ t and s = ∥ p ∥ 2 2 s = \lVert p\rVert_2^2 s = ∥ p ∥ 2 2 . The square root is isotropic on im ( U t ) ⊥ \operatorname{im}(U_t)^\perp im ( U t ) ⊥ , so p p p lies in V = im ( U t ) + span ( h ^ t ) V = \operatorname{im}(U_t) + \operatorname{span}(\hat{h}_t) V = im ( U t ) + span ( h ^ t ) . The rank-one update preserves V V V and remains isotropic on V ⊥ V^\perp V ⊥ , with floor β t / ( 1 + s ) > 0 \beta_t/(1+s) > 0 β t / ( 1 + s ) > 0 and a positive semidefinite remainder. Diagonalizing the restriction to V V V therefore gives the next compact representation and its top eigenvalue; eigenvalues outside V V V equal the floor.
Applying the square root to a query costs O ( m ( 1 + d t ) ) O(m(1+d_t)) O ( m ( 1 + d t )) operations. Updating the basis and diagonalizing the restricted covariance costs O ( m ( 1 + d t ) 2 + ( 1 + d t ) 3 ) O(m(1+d_t)^2 + (1+d_t)^3) O ( m ( 1 + d t ) 2 + ( 1 + d t ) 3 ) . Summing over at most T max T_{\max} T m a x updates gives O ( Q m T max + m T max 3 ) O(QmT_{\max} + mT_{\max}^3) O ( Q m T m a x + m T m a x 3 ) operations and O ( m T max ) O(mT_{\max}) O ( m T m a x ) working memory, using d t ≤ min { t , m } d_t \le\min\{t,m\} d t ≤ min { t , m } . As in Section G.1, the returned round is identified by its query indices in the attacker’s record; storing an additional copy of all its vectors is output storage.