I MPLEMENTING A W HITE -B OX U NDETECTABLE BACKDOOR FOR R ANDOM F OURIER F EATURES
arXiv:2609.16403v1 [cs.CR] 14 Sep 2026
A P REPRINT Michael Collins Laboratory for Advanced Cybersecurity Research Laurel, MD 20707 [email protected]
Jada Cumberland School of Cybersecurity Old Dominion University Norfolk, VA 23259 [email protected]
Ross Gore Center for Secure and Intelligent Critical Systems Old Dominion University Norfolk, VA 23259 [email protected]
Brianne Dunn Old Dominion University Norfolk, VA 23259 [email protected]
Samuel Jackson Old Dominion University Norfolk, VA 23259 [email protected]
Sachin Shetty Center for Secure and Intelligent Critical Systems Department of Electrical and Computer Engineering Old Dominion University Norfolk, VA 23259 [email protected]
September 16, 2026
A BSTRACT Goldwasser et al. showed that undetectable backdoors can be planted in machine learning models trained with the Random Fourier Features (RFF) algorithm, under a hardness assumption tied to the Continuous Learning With Errors (CLWE) problem. Under standard cryptographic assumptions, even a full white-box audit of a model’s weights cannot detect this class of backdoor. The construction is stated in terms of cryptographic reductions and probabilistic lemmas, without a reference implementation, and relies on secondary machinery such as the Sparse Gaussian Pancakes distribution and a homogeneous CLWE conditional density. Its realizability in ordinary numerical code is not obvious from the paper alone. This paper implements the white-box CLWE-RFF backdoor construction end to end using only numpy and scipy, to test whether this threat is realizable with commodity scientific-computing tools or requires specialized cryptographic infrastructure. We give two samplers for the core GPd (bk ) distribution. The first is a rejection-sampling proxy. The second is an exact closed-form sampler derived from the homogeneous CLWE density and verified against its own analytic form. Using this implementation, we run statistical indistinguishability tests, covering both weight-space and functional black-box comparisons. We find no evidence of detectable difference between backdoored and clean models across a range of sparsity ratios ρ = dsparse /D. We report which parts of the construction were straightforward to realize, which required derivation not spelled out in the paper. We also highlight which parts we did not attempt to reproduce, including the underlying lattice hardness reduction. We see this work as a contribution to understanding the practical realizability of the Goldwasser white-box CLWE core, not as a new theoretical result. Keywords continuous learning with errors · random fourier features · machine learning security · reproducibility · lattice-based cryptography
Implementing a White-Box Undetectable Backdoor for Random Fourier Features
1
A P REPRINT
Introduction
Machine-learning-as-a-service settings raise a basic trust question. If a client outsources training to an untrusted party, can the returned model be audited for hidden malicious behavior? Goldwasser et al. [1] show that, for a broad class of settings, the answer is no. They construct undetectable backdoors. These are classifiers that remain computationally indistinguishable from clean models, even with full white-box access to the model’s weights. At the same time, a small, secretly chosen perturbation can cause them to misclassify any input. Their strongest result targets the Random Fourier Features (RFF) learning paradigm of Rahimi and Recht [5], resting on the conjectured hardness of the Continuous Learning With Errors (CLWE) problem introduced by Bruna et al. [2]. For several years, the security community treated backdoor detection as a largely empirical, adversarial problem. An attack is proposed, such as BadNets [6]. A defense follows, such as spectral signatures [7] or robust-statistics-based filtering [8]. The cycle repeats without either side offering a formal guarantee. Goldwasser et al. [1] broke from this pattern. They proved that a class of backdoors is undetectable under standard cryptographic assumptions. This matters for the community because it means no statistical defense can close the gap for these constructions, unless the underlying hardness assumption is false. A proof of undetectability only matters if practitioners know when it applies. Assessing supply-chain risk in outsourced ML pipelines means knowing whether this threat requires specialized cryptographic tooling to carry out, or whether ordinary numerical libraries are enough to build it. If ordinary tools suffice, the threat is more urgent, since anyone with basic scientific-Python skills could plant it. If instead a straightforward translation of the paper’s algorithms into code runs into gaps, that result is just as valuable. It tells defenders which parts of the construction are harder to realize in practice than the theory suggests. We take up this task. This paper documents what it takes to go from the algorithm statements in [1] to working, statistically-validated code, using nothing beyond standard numerical libraries. We treat this as similar in spirit to reproducibility studies in other areas of applied cryptography and security. The value is not a new attack or a new theorem, but a documented answer to whether this construction works as described and how hard it is to make it work. Our contributions are as follows. We implement the two-stage GPd (bk ) sampling procedure, covering secret sparsification and conditional sampling, that underlies Algorithms 4 and 5 of [1], using a rejection-sampling proxy for the CLWE-conditioned distribution. We also derive a second, exact closed-form sampler by completing the square on the homogeneous CLWE density of Bruna et al. [2]. This sampler draws directly from the discrete-Gaussian-weighted mixture-of-Gaussians identity that the rejection sampler only approximates. Furthermore, we verify it against its own analytic density. We implement a branch-free version of the backdoor activation from Algorithm 6 of [1], where the sign flip comes from the learned classifier’s structure rather than from explicit trigger-detection logic. Section 3 discusses this distinction in detail, since conflating the two is a common source of unfaithful implementations. We run an empirical battery of white-box (weight-space) and black-box (functional-space) statistical indistinguishability tests. These include a sweep over the sparsity ratio ρ = dsparse /D to check whether the indistinguishability gap widens as the secret becomes less sparse relative to the ambient dimension. Finally, we give an explicit account of what remains unimplemented, including the CLWE hardness reduction itself. Section 2 covers background and related work on CLWE and backdoor detection. Section 3 explains the black-box and white-box distinction underlying Goldwasser et al.’s definitions, since it is central to interpreting our results correctly. Section 4 describes our implementation and where it departs from the paper. Section 5 reports the empirical results and the reasoning behind each validation check. Section 6 covers what still remains open.
2
Background
This section covers the technical building blocks needed to follow the rest of the paper. These include lattice-based hardness assumptions, the Learning With Errors problem and its continuous variant, the Random Fourier Features learning paradigm, and how Goldwasser et al. combine these pieces into a backdoor construction. 2.1
Lattices and Learning With Errors
A lattice is a discrete subgroup of Rn generated by integer combinations of a set of basis vectors. Many computational problems on lattices, such as finding the shortest nonzero vector, are believed to be hard even for quantum computers, and this hardness is the foundation for a large family of cryptographic constructions [14]. Regev [13] introduced the Learning With Errors (LWE) problem as a bridge between this lattice hardness and usable cryptography. In LWE, a distinguisher is given samples of the form (a, ⟨a, s⟩ + e mod q), where a is drawn uniformly from Znq , s is a fixed secret vector, and e is a small error term. The task is to recover s, or even just to distinguish these samples from uniformly 2
Implementing a White-Box Undetectable Backdoor for Random Fourier Features
A P REPRINT
Figure 1: Why the homogeneous CLWE distribution is called Gaussian Pancakes. Left: the 1D marginal density along the secret direction u = ω/∥ω∥, for γ = 8 and two values of β, compared against a standard Gaussian. The density concentrates in evenly-spaced bands instead of spreading smoothly across the real line. Right: 2D samples in the plane spanned by the secret direction and one orthogonal direction. Clean Gaussian samples (gray) form a smooth, round cloud. hCLWE samples (blue) cluster into parallel stripes perpendicular to the secret direction, which is the banded structure that gives the distribution its name.
random pairs. Regev showed a quantum reduction from worst-case lattice problems to LWE, which means that breaking LWE on average would imply an efficient algorithm for lattice problems that are believed to be hard in the worst case. This reduction is what makes LWE, and its descendants, credible as hardness assumptions. 2.2
Continuous LWE
Bruna et al. [2] introduced Continuous LWE (CLWE) as a continuous analogue of LWE. Instead of discrete samples over Znq , a CLWE instance gives the distinguisher samples in Rn , drawn either from a standard Gaussian N (0, In ) or from a Gaussian secretly modulated along a hidden direction ω. This second distribution is called the homogeneous CLWE distribution. Restricted to the projection onto ω, it takes the form of a discrete-Gaussian-weighted mixture of Gaussians, stated formally in their Definition 2.19. Bruna et al. proved a polynomial-time quantum reduction from worst-case lattice problems to CLWE, giving it hardness guarantees comparable to LWE, and used this to resolve an open question about the computational hardness of learning Gaussian mixtures without separability assumptions. Vafa et al. [3] later gave a direct, simpler reduction from classical LWE to CLWE, holding under classical rather than only quantum worst-case lattice assumptions, and sharpening the Gaussian mixture learning hardness result along the way. It is this pair of reductions, not the distribution’s statistical properties alone, that Goldwasser et al. later build on. 2.3
Random Fourier Features
Rahimi and Recht [5] introduced Random Fourier Features (RFF) as a way to approximate shift-invariant kernel methods with linear models, at much lower computational cost. Here, kernel refers to the machine-learning sense of the term: a similarity function k(x, x′ ) that implicitly defines an inner product in a (possibly infinite-dimensional) feature space, as used in support vector machines and Gaussian processes, unrelated to the algebraic sense of a kernel as the set of elements a homomorphism maps to the identity. The idea is to map each input x ∈ RD through a random feature map Φ(x) = cos(2π(Gx + b)), where the rows of G ∈ Rm×D are drawn i.i.d. from a Gaussian distribution and b is drawn uniformly. A linear classifier h(x) = sgn(w⊤ Φ(x)) is then trained on top of these features. Because G is random and untrained, the method is popular for large-scale kernel approximation: it turns an expensive kernel computation into ordinary linear regression or classification over random features [15]. This same randomness in G is what Goldwasser et al. exploit. Since G is supposed to look random regardless of the training data, a party who controls how G is sampled can hide structure inside it without changing what a clean training run is expected to look like. 3
Implementing a White-Box Undetectable Backdoor for Random Fourier Features
2.4
A P REPRINT
The CLWE-RFF backdoor construction
Goldwasser et al. [1] combine CLWE and RFF as follows. Rather than sampling the rows of G from an ordinary Gaussian, the backdoored training procedure samples them from a distribution GPd (bk ), informally called Sparse Gaussian Pancakes. This distribution behaves like a standard Gaussian in most coordinates, but is secretly correlated with a sparse key bk along a d-dimensional support, using the homogeneous CLWE density described above. Under the hardness of CLWE, GPd (bk ) is computationally indistinguishable from a clean Gaussian matrix. At the same time, shifting any input x by bk forces the inner product ⟨Gj , x + bk ⟩ to concentrate near a half-integer for every feature row j. This flips the sign of cos(2π·) for every feature simultaneously, which in turn flips the sign of the trained classifier’s output. Goldwasser et al. formalize a backdoor as a pair of algorithms (Backdoor, Activate). Backdoor is a training procedure that returns both a classifier h and a secret key bk . Activate maps an input x and the key bk to a nearby input x′ = x + bk 1 that reliably changes h’s prediction. They give three constructions with different guarantees. The first is a black-box undetectable backdoor applicable to any model class. The second is the white-box undetectable backdoor for RFF based on CLWE. The third is a preliminary white-box construction for single-hidden-layer ReLU networks based on the hardness of sparse PCA. Section 3 explains what distinguishes the black-box and white-box guarantees, and why this paper targets the latter.
3
White-Box Versus Black-Box Undetectability
Goldwasser et al. [1] do not define undetectability as a single notion. They define two, distinguished by how much access the auditor is given to the model. This distinction matters because it determines how detectable a backdoor’s secret trigger is. 3.1
Two levels of auditor access
In the black-box setting, a distinguisher may only query the model on inputs of its choosing and observe the outputs. It never sees the model’s internal parameters. Undetectability here means no efficient distinguisher can tell a backdoored model apart from a clean one using query access alone. Goldwasser et al. show this is achievable for any model class, using digital signature schemes to plant the backdoor [1]. In the white-box setting, the distinguisher is given the complete description of the model. This includes every weight, every parameter, and the training data itself. Undetectability here means no efficient distinguisher can tell the two apart even with this full view. This is a strictly stronger guarantee, since anything a black-box distinguisher can check, a white-box distinguisher can also check, along with everything else visible in the model’s internals. Goldwasser et al. prove this stronger guarantee for the CLWE-RFF construction specifically, under the hardness of CLWE [1, 2]. 3.2
Why white-box is the harder case to realize
The black-box guarantee is easier to reason about, because it only constrains observable behavior. A backdoor built from a digital signature scheme can plant an arbitrary decision rule, since nothing about the internal parameters is ever exposed to scrutiny. The white-box guarantee has no such room. Every parameter the backdoored training procedure produces must be indistinguishable from what a clean run of the same procedure would produce, not just on held-out queries, but as a complete object. This is why the CLWE-RFF construction cannot simply hide a decision rule inside the weights. It has to make the entire feature matrix G statistically indistinguishable from a cleanly-sampled Gaussian matrix, while still embedding a usable trigger. The Sparse Gaussian Pancakes distribution introduced in Section 2 is the mechanism that makes this possible, concentrating predictably along one secret direction while remaining indistinguishable from Gaussian elsewhere. Achieving both properties at once, full statistical camouflage and a reliable trigger, is a substantially harder design problem than the black-box case, and it is the reason we chose to focus this paper’s implementation effort there. 3.3
What this means for our implementation and tests
Because the white-box guarantee concerns the parameters themselves, not just the model’s behavior on queries, our implementation cannot rely on any check, branch, or conditional logic tied to the secret key appearing anywhere in the model’s forward pass. Section 4 describes how we enforce this. The activation mechanism in our implementation is branch-free, so there is no piece of code a white-box auditor could point to as evidence of a hidden trigger. Here + denotes ordinary coordinate-wise addition in the input space RD . The construction therefore assumes a continuous vector representation in which the perturbed input remains meaningful to the model. 1
4
Implementing a White-Box Undetectable Backdoor for Random Fourier Features
A P REPRINT
Figure 2: Architecture of the implementation, mapped onto the two halves of the Goldwasser et al. backdoor scheme, with the specific algorithms, lemma, and function names used in this paper. Left: the Backdoor pipeline (Algorithms 4 and 5, Lemma 6.2), from sample_Wd() and embed_sparse_secret() through parameter derivation, the rejection and exact samplers described in this section, and the branch-free classifier. Right: the Activate trigger (Algorithm 6), which shifts an input by the secret key bk and relies on the Lemma 6.2 half-integer concentration guarantee to flip the classifier’s output. Dashed arrows indicate that the same trained classifier h and feature matrix G produced by Backdoor are reused at activation time. The same distinction also shapes how we test the construction. A test that only compares model outputs on chosen inputs is a black-box test. A test that inspects the sampled feature matrix G directly is a white-box test. Section 5 reports both kinds separately, weight-space tests on G itself, and functional-space tests on model behavior, because passing only one of them would not support the stronger claim this paper is actually interested in testing.
4
Implementation
We implemented the construction as a standalone package. We kept it separate from any specific downstream demonstration, so the CLWE-RFF core could be evaluated and iterated on its own terms. Figure 2 gives an overview of how the pieces described in this section map onto the two halves of the Goldwasser et al. backdoor scheme, before we walk through each component in detail. 4.1
Secret and feature sampling
We followed Algorithms 4 and 5 of [1] and split √ the construction into two stages. First, a sparse secret ω ∼ Wd is drawn as a random unit vector scaled by γ = 2 d. This secret is embedded into a random d-element support of the ambient D coordinates to form the backdoor key bk (sample_Wd, embed_sparse_secret). Second, the m rows of the feature matrix G are sampled from GPd (bk ). On-support coordinates are drawn from the conditional distribution in Eq. (1). Off-support coordinates are drawn as independent standard Gaussians, matching the definition of Sparse Gaussian Pancakes stated in Lemma 1 below. 5
Implementing a White-Box Undetectable Backdoor for Random Fourier Features
A P REPRINT
Lemma 1 (Sparse Gaussian Pancakes, informal; [1], Lemma 6.2, via Lemma 6.6). There is a distribution Wd over sparse unit-norm-scaled vectors ω ∈ Rd and a distribution GPd (bk ) over RD , parameterized by β, τ derived from d and a target failure probability δ, such that (i) GPd (bk ) is computationally indistinguishable from N (0, ID ) under the hardness of CLWE, and (ii) for g ∼ GPd (bk ), ⟨g, bk ⟩ mod 1 lies within τ of 1/2 except with probability at most δ. The distribution GPd (bk ) factors through the homogeneous CLWE density of Bruna et al. [2]. Restricted to the projection t = ⟨g, u⟩ onto the secret direction u = ω/∥ω∥, this density is, by their Definition 2.19, a discrete-Gaussianweighted mixture of Gaussians: X 2 (k + s − γt)2 , (1) p(t) ∝ e−t /2 exp − 2β 2 k∈Z
where γ = ∥ω∥ and s ∈ {0, 12 } selects the homogeneous (s = 0) or half-integer-shifted (s = 21 ) variant. The backdoor construction requires the s = 21 variant. It is the half-integer concentration that flips the cosine feature’s sign. Lemma 1’s guarantee is parameterized by (i, b, β, τ ), subject to a deviation-probability constraint tied to a target failure probability δ. We implemented a direct search (derive_params) over integer exponents i, b satisfying exp(−(τ /β)2 /2) ≤ δ with β = d−i and τ = d−b . We also enforced the Algorithm 5 requirement m ≥ d. 4.2
Two samplers for GPd (bk )
We implemented two independent samplers for the on-support coordinate of GPd (bk ). Each realizes the distribution in Lemma 1 a different way, as shown on the left side of Figure 2. The first is a rejection sampler and serves as a proxy for the exact distribution. It draws y ∼ N (0, Id ), forms z = γ⟨y, u⟩ + e (mod 1) with e ∼ N (0, β 2 ), and accepts y only if z lands within τ of 12 . This is a direct proxy for the near-half-integer concentration claimed in Lemma 1. It is a hard-threshold approximation of a distribution that Eq. (1) defines with a soft, Gaussian weighting, and its acceptance rate is only about 2τ . As a result, it discards most proposals. Rejection sampling of this kind is standard practice for distributions with intractable normalizing constants [4], but the discarded-proposal cost grows quickly as τ shrinks. This is problematic for the small failure probabilities the construction targets. The second sampler draws directly from Eq. (1) in closed form, by completing the square. The mixture layer k is drawn from discrete-Gaussian weights wk ∝ exp(−(k + s)2 /2(β 2 + γ 2 )). Given a layer, the secret-direction coordinate is p drawn from a Gaussian centered at µk = γ(k + s)/(β 2 + γ 2 ) with standard deviation σ = β/ β 2 + γ 2 . Orthogonal coordinates are drawn as independent standard Gaussians. We verified this completing-the-square identity against the raw density in Eq. (1) numerically. Agreement held to within ∼ 3 × 10−16 , which is machine precision. Both samplers are exposed through the same model constructor. The rejection sampler is the default (method="rejection"), and the exact sampler is opt-in (method="exact"). Unless noted otherwise, the results in Section 5 use the default rejection sampler. 4.3
Branch-free activation
The forward pass of the model is Φ(x) = cos(2π(Gx + b)), h(x) = sgn(w⊤ Φ(x)), with no branching or explicit trigger-detection logic. The activation is simply x′ = x + bk (Algorithm 6), shown on the right side of Figure 2. Whether h(x′ ) ̸= h(x) is determined entirely by the learned weights w interacting with the CLWE structure in G, matching the mechanism described in [1]. This branch-free design is what Section 3 requires for the white-box undetectability argument to hold.
5
Empirical Results
We evaluated the implementation with a series of statistical tests. We ran these tests both at a single representative operating point and swept across a range of sparsity ratios. Each test in this section is chosen to match a specific claim from Section 2 or Section 3. 5.1
Sampler verification
Before trusting any downstream claim about the feature matrix G, we first need evidence that our two samplers draw from the distributions we claim they draw from. We used a Kolmogorov-Smirnov (KS) goodness-of-fit test [9, 10] 6
Implementing a White-Box Undetectable Backdoor for Random Fourier Features
A P REPRINT
against the exact sampler’s own analytic density (Eq. (1)). This test checks whether empirical draws are consistent with the target density, rather than with some other distribution that happens to match on a few moments. We also compared the two samplers head-to-head on the half-integer concentration of γ⟨g, ω⟩. This is the property Lemma 1 exists to guarantee. At d = 10, D = 64, the exact sampler’s secret-direction projection matches the analytic density under the KS test (KS statistic ≈ 0.004, p ≈ 0.54). This confirms the sampler draws from the distribution it is supposed to draw from. The two samplers also differ on the property the construction actually needs. The half-integer concentration of γ⟨g, ω⟩ is 1.000 for the exact sampler versus 0.960 for the rejection proxy. The exact sampler achieves this at an acceptance rate of 1.0, compared to only ≈ 0.198 for the rejection proxy, making it roughly 5× more sample-efficient at these parameters. Off-support marginals remain clean N (0, 1) under both samplers (KS p ≈ 0.69), confirming neither sampler distorts the coordinates that are not supposed to carry the secret. 5.2
Backdoor efficacy and indistinguishability
Having validated the sampler in isolation, the next question is whether a full trained model built on top of it satisfies the construction’s two central claims. The first claim is that the backdoor works, meaning the real key flips predictions and a fake key does not. The second claim is that the backdoor is undetectable, in both the white-box and black-box sense described in Section 3. We measured efficacy through flip rate under the real key versus a random fake key. A large real-key flip rate paired with a chance-level fake-key flip rate indicates a working, key-specific backdoor rather than a generic instability in the classifier. At D = 64, m = 1200, dsparse = 10, n = 6000 training samples, target failure probability δ = 10−6 , and 800 training epochs, the backdoored model reaches clean accuracy 0.688. This is close to 0.684 for a clean model on the same data. This confirms the backdoor does not degrade ordinary performance. The backdoor itself is also key-specific. It fires under the real key at rate 0.869, but only 0.489 under a random fake key, which is indistinguishable from chance. Together, these two results are the signature we expect from a working, key-specific backdoor rather than a generic instability in the classifier. This flip rate is below the certainty Theorem 6.4 of [1] guarantees. The shortfall is related to a specific parameterselection choice, not a flaw in our code. The theorem’s proof sets the sparsification exponent to b = a + 10, where a comes from the exponent of m in Assumption 6.3. This is a constant about the trained classifier’s margin on all inputs that cannot be computed in advance. It is a proof device, not something derive_params can target directly. Even in [1], the choice b > a + 10 is not carefully justified. The final step of the proof needs the interval indicated by the last displayed line to miss zero, which follows if m1/2 d−b < m−a . This is equivalent to m1/2−a < db . It is a statement about the polynomial relationship between m and d, not about b and a alone. The requisite b can be pinned down using the theorem’s assumption that d, 1/ε, and log(1/δ) are polynomially related, together with the choice of m in Algorithm 5 as m(d, ε, δ). The point that matters √ for us is simpler. It is that b is a free constant, and it can always be taken large enough that the aggregate error term m d−b falls below the classifier’s margin. The function derive_params, however, searches for the smallest (i, b) pair satisfying Lemma 1’s deviation-probability constraint, and stops as soon as one is found. At every point in our sweep (Table 2), this terminates at b = 1. This is the smallest exponent satisfying the constraint, and unfortunately also the worst choice for the margin bound. It √ √ gives m d−b = 1200/10√≈ 3.46, which is not small, and the 0.869 flip rate reflects that. Across the sparsity sweep, where b = 1 throughout but m d−b ranges from 6.93 down to 0.87 as dsparse and m vary, the flip rate rises from 0.754 √ to 0.968. This monotonic increase is in line with m d−b . Enforcing a larger b in derive_params should recover a flip rate closer to Theorem 6.4’s asymptotic guarantee, at the cost of a lower acceptance rate for the rejection sampler (Section 4). It is important to note that the exact sampler would be unaffected since it does not reject proposals. We verify this directly in Section 5.4, against the indistinguishability battery described in Table 1. Table 1 summarizes the weight-space and functional-space indistinguishability tests. The weight-space tests target the claim in Lemma 1 that G is statistically indistinguishable from a cleanly-sampled Gaussian matrix. The functional-space tests target the complementary claim that the backdoored and clean models behave identically on held-out inputs. None of the six tests rejects indistinguishability at α = 0.05. A functional-space test can pass simply because it lacks statistical power, not because the two models are actually indistinguishable. To rule this out, we ran the identical set of tests between two independently-sampled clean models, a known-null comparison with no backdoor involved at all. If the tests had power to detect a real difference, we would 7
Implementing a White-Box Undetectable Backdoor for Random Fourier Features
A P REPRINT
Table 1: Indistinguishability tests comparing the backdoored model against a clean model. Weight-space tests examine the feature matrix G directly. Functional-space tests compare model behavior on held-out inputs. None reject indistinguishability at α = 0.05. Test
Domain
Statistic
p-value
KS vs. N (0, 1) Shapiro-Wilk normality [11] Marchenko-Pastur outlier count [12] Logit distribution Prediction base rate Standardized confidence-margin shape
Weight-space Weight-space Weight-space Functional-space Functional-space Functional-space
— — 0 outliers — — —
0.394 0.178 — 0.081 0.737 0.306
Table 2: Weight-space and functional-space KS statistics and p-values across the sparsity-ratio sweep. Flip rate is the fraction of held-out inputs whose prediction changes under the real backdoor key. ρ
D
dsparse
m
KSwt
pwt
KSfunc
pfunc
0.078 0.078 0.156 0.156 0.156 0.156 0.250 0.312 0.312 0.500
64 128 64 128 64 64 96 64 128 64
5 10 10 20 10 10 24 20 40 32
1200 1200 1200 1200 600 2400 1200 1200 1200 1200
0.0031 0.0017 0.0026 0.0020 0.0060 0.0021 0.0020 0.0032 0.0024 0.0031
0.455 0.776 0.663 0.592 0.120 0.510 0.724 0.399 0.332 0.439
0.0233 0.0227 0.0180 0.0147 0.0250 0.0330 0.0263 0.0167 0.0247 0.0143
0.388 0.424 0.716 0.904 0.306 0.076 0.249 0.799 0.321 0.918
expect at least some of them to reject in this null setting, since two independently-sampled models are never identical. Instead, we found the same pattern as before. No test statistic crossed the α = 0.05 threshold. This null comparison also shaped two design choices in the functional-space battery. First, we use a prediction base-rate test rather than raw pointwise decision agreement. Independently-sampled RFF bases make two clean models’ decisions unrelated at the input level, even when no backdoor is present, so pointwise agreement would fail even between two clean models and would not be a meaningful test. Second, we use a per-model-standardized margin-shape test rather than raw margin magnitude, since each model’s output scale is arbitrary and not comparable across independently-trained models. No test statistic rejects indistinguishability at α = 0.05. This holds for the weight-space and functional-space tests in Table 1, for the null-comparison replication, and across both random seeds. 5.3
Robustness across sparsity ratios
All of the results above hold at a single (D, dsparse , m) operating point. The CLWE hardness assumption is expected to weaken as the secret’s sparsity dsparse grows relative to the ambient dimension D, since a less sparse secret is an easier statistical target [2, 3]. It is therefore important to check whether the empirical indistinguishability gap widens as ρ = dsparse /D increases, rather than assuming the single operating point above is representative. We swept ρ from 0.078 to 0.500 across ten grid points (Table 2), rebuilding fresh backdoored and clean models at each point and re-running the weight-space and functional-space KS tests. Figure 3 plots the two KS statistics against ρ directly, and Figure 4 plots the corresponding p-values against the α = 0.05 significance threshold. The trend across this sweep is flat. An ordinary-least-squares fit gives a slope of +0.00051 for the weight-space KS statistic and −0.0179 for the functional-space KS statistic as functions of ρ. Neither shows evidence of an increasing trend. This flat trend is not simply because the tests stopped being meaningful at higher ρ. The minimum p-value across the sweep is 0.120 for the weight-space test and 0.076 for the functional-space test. Both of these are above α = 0.05, and the flip rate stays above 0.75 at every grid point. The backdoor keeps firing throughout the sweep. The flat trend reflects indistinguishability, not a backdoor that quietly stopped working. 8
Implementing a White-Box Undetectable Backdoor for Random Fourier Features
A P REPRINT
Figure 3: Weight-space and functional-space KS statistics as a function of the sparsity ratio ρ = dsparse /D, across the ten-point sweep grid. Neither statistic trends upward with ρ.
Enforcing a larger b closes the flip-rate gap
5.4
Section 5.2 identified the flip-rate gap as a consequence of derive_params choosing the smallest valid b rather than a large one. We tested this directly by constraining derive_params to b = 3 instead of b = 1, at the same D = 64, m = 1200, dsparse = 10 operating point. The real-key flip rate rises to 0.998 under the rejection sampler and to 0.999 under the exact sampler. The fake-key flip rate stays at chance (0.49–0.50) under both. The fix sharpens the trigger. It does not destabilize the classifier. We reapplied the full indistinguishability battery from Table 1, including the on-support marginal check, at b = 3 for both samplers. Table 3 reports the result. All six tests pass. The null-comparison calibration described above applies here as well. Table 3: Full indistinguishability battery at D = 64, m = 1200, dsparse = 10, comparing the default b = 1 against the fix b = 3, for both samplers. All tests pass (p > 0.05, or 0 Marchenko-Pastur outliers) at every setting. b
Sampler
Flip (real)
Flip (fake)
KS p
Shapiro p
MP outliers
Fisher p
Logit p
Margin p
1 3 3
rejection rejection exact
0.828 0.998 0.999
0.490 0.488 0.500
0.394 0.415 0.981
0.407 0.329 0.276
0 0 0
0.599 0.514 0.797
0.229 0.292 0.270
0.053 0.454 0.875
We then reapplied the sparsity sweep from Table 2, re-deriving b = 3 at every grid point. Table 4 reports the result. Flip rate saturates to 0.999–1.000 across every ρ = dsparse /D we tested, compared to 0.738–0.963 at b = 1. Weight-space p-values stay well above threshold everywhere, with a minimum of 0.086. They show no trend with ρ in either direction. This matches the flat trend in Table 2. This sweep uses the exact sampler throughout. The reason is computational, not statistical. At dsparse ≥ 32, τ = d−3 sparse drops into the 10−5 range. The rejection sampler’s acceptance rate collapses to match, and drawing m = 1200 on-support rows then requires on the order of 107 –108 proposals. The exact sampler has no such cost, since it never rejects a proposal. We recommend it whenever b is enforced to 3 or higher, particularly at the higher end of the sparsity range the construction is meant to cover. 9
Implementing a White-Box Undetectable Backdoor for Random Fourier Features
A P REPRINT
Figure 4: Corresponding KS test p-values against ρ, with the α = 0.05 significance threshold marked. All grid points remain above threshold. Table 4: Sparsity sweep with b = 3 (exact sampler), and b = 1. Flip rate is measured on held-out inputs under the real key.
6
b=1 KSw p
ρ
D
dsparse
m
Flip
0.078 0.078 0.156 0.156 0.156 0.156 0.250 0.312 0.312 0.500
64 128 128 64 64 64 96 64 128 64
5 10 20 10 10 10 24 20 40 32
1200 1200 1200 1200 600 2400 1200 1200 1200 1200
0.738 0.857 0.921 0.843 0.865 0.963 0.940 0.930 0.963 0.945
0.455 0.776 0.592 0.663 0.120 0.510 0.724 0.399 0.332 0.439
Flip
b=3 KSw p
0.999 1.000 1.000 1.000 1.000 1.000 1.000 1.000 1.000 1.000
0.314 0.086 0.749 0.998 0.997 0.399 0.933 0.918 0.841 0.313
Discussion
Sections 4 and 5 show that the core sampling, training, and activation mechanics of the construction are realizable, and that the resulting models behave as predicted across a range of sparsity ratios. This section covers what we did not implement, and what closing each gap would require. 6.1
The hardness reduction itself
Our exact sampler makes the homogeneous CLWE distribution concrete and numerically tractable. It does not touch the question of whether that distribution is hard to distinguish from Gaussian. That question is answered by the worst-case-lattice-to-CLWE reductions of [2, 3], which we cite rather than reproduce. Implementing a reduction of this kind means writing code that turns a CLWE distinguisher into a lattice-problem solver, then testing it against known 10
Implementing a White-Box Undetectable Backdoor for Random Fourier Features
A P REPRINT
hard lattice instances [14]. This is a proof-theoretic exercise, not a sampling and training exercise, and it falls outside the scope of a paper focused on realizing the construction’s mechanics. A related point is that we did not characterize the regime of (d, D) in which the underlying hardness reduction is actually meaningful. The reductions in [2, 3] are asymptotic statements. They do not imply that CLWE is hard at every dimension, only that hardness holds as the parameters grow, in the same way that factoring is a hard problem in general even though specific small or structured moduli are easy on a classical computer. Our empirical sweep covers D up to 128 and dsparse up to 40, chosen for computational convenience rather than validated against any known hardness threshold. Nothing in our results should be read as evidence that these particular parameter values are cryptographically meaningful, only that the construction’s mechanics behave as predicted at the scales we tested. 6.2
Adaptive and adversarial detection
Our undetectability tests, both weight-space and functional-space, compare fixed, non-adaptive distributions of clean inputs. A more demanding test would let an adversary query the model adaptively, choosing inputs based on prior responses in an attempt to expose the backdoor, in the spirit of query-based black-box detection methods [16] and stateful defenses against repeated adversarial queries [17]. Building such an adversary requires a concrete attack strategy, not just a statistical comparison. Evaluating against it would move this work from validating a construction to red-teaming one, a natural next step once the base construction is confirmed to work. A related but distinct gap concerns operational use rather than model inspection. The undetectability guarantee we test is about a single snapshot of the model, its weights or its behavior on a fixed input distribution, not about a log of activations accumulated over time. In practice, activating the backdoor means applying the same fixed offset bk repeatedly, whenever the key holder wants to force a misclassification. If input logs are retained, that repeated use could in principle create a detectable pattern, for example, the same offset recurring across many otherwise unrelated submitted inputs, even though the model itself remains statistically indistinguishable from clean in the sense Goldwasser et al. prove. Characterizing this operational, log-level detection risk is outside the scope of the model-level guarantee studied here, but it is a natural extension of the adaptive-detection question raised above. 6.3
Persistence and immunization
Goldwasser et al. also study whether a planted backdoor survives further gradient-descent training, and propose an evaluation-time immunization strategy based on randomized smoothing of inputs [18, 19]. We did not evaluate either. Persistence testing requires training the backdoored model further on new data, then re-running the efficacy and detectability battery from Section 5 after each additional pass. Immunization testing requires implementing the smoothing defense and measuring how much it degrades the real-key flip rate. Both are natural extensions of the evaluation pipeline built here, and need no new theoretical machinery, only more experiments. 6.4
Fidelity of the secret distribution
√ Our secret distribution Wd is instantiated as a random unit vector scaled by 2 d, embedded on a random sparse support. We verified the properties Lemma 1 depends on, but not every distributional detail of the paper’s formal definition of Wd . A fuller treatment would derive and check that complete specification directly, connecting it to the broader literature on the statistical-computational gaps in sparse recovery problems [20].
7
Conclusion
The core algorithmic machinery of the Goldwasser et al. [1] white-box CLWE-RFF backdoor is realizable in ordinary Python. This includes sparse-secret sampling, conditional feature generation, and branch-free activation, all built with no cryptographic primitives beyond standard random sampling in numpy and scipy. We also derived and verified an exact closed-form sampler for the underlying homogeneous CLWE density. The resulting construction empirically satisfies both white-box and black-box indistinguishability criteria [7, 8] across a range of sparsity ratios. We found no evidence of the indistinguishability gap widening as sparsity decreases relative to ambient dimension. For the security community, we take this as evidence that the threat this construction represents is not gated behind specialized cryptographic tooling. Ordinary scientific-computing competence is enough to realize it. The main remaining gap between our implementation and the paper’s full guarantee is not computational; it is foundational. Undetectability still rests on the conjectured hardness of CLWE [2, 3], which no numerical implementation 11
Implementing a White-Box Undetectable Backdoor for Random Fourier Features
A P REPRINT
can establish on its own. That hardness assumption remains the right target for future cryptanalytic scrutiny, along with the adaptive-detection and persistence questions raised in Section 6.
Code Availability The implementation described in this paper, including both GPd (bk ) samplers, the branch-free activation, and the statistical test battery used to produce the results in Section 5, is publicly available at https://github.com/rossgore/ weird_machine_gadgets/tree/main/model-backdoor-work/section6.
Author Contributions
Michael Collins Jada Cumberland Brianne Dunn Ross Gore Samuel Jackson Sachin Shetty
X
X
X
n
X
X
X
X
X
X X X X
n atio Va lid
per vis ion Su
stra mi ni Ad jec t Pro
X X X X X
tio
siti on qui Ac Fu
Wr
ndi
ng
g– Ed Rev itin iew g &
itin
g– Dr Orig aft ina l
itin Wr
n atio Vis u
aliz
So ftw are
s sou rce Re
dol ogy tho Me
tio n iga
ysi al A nal
Inv est
Co
nce
ptu
Author
Fo rm
aliz a
tio
s
n
The following author contributions are categorized in Table 7 according to the CRediT (Contributor Roles Taxonomy) [21]. The author order in this paper is strictly alphabetical and does not imply relative levels of contribution.
X X X X X
X
X
X
X
X
X X X X X
Acknowledgments This work was supported by an INSuRE+C AY 25-26 grant through the National Center of Academic Excellence in Cybersecurity (NCAE). Computational resources were provided by Old Dominion University. We also acknowledge the support of an anonymous reviewer whose guidance and support greatly improved this work as it took shape.
References [1] Shafi Goldwasser, Michael P. Kim, Vinod Vaikuntanathan, and Or Zamir. Planting undetectable backdoors in machine learning models. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 931–942. IEEE, 2022. [2] Joan Bruna, Oded Regev, Min Jae Song, and Yi Tang. Continuous LWE. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 694–707, 2021. [3] Neekon Vafa, Vinod Vaikuntanathan, et al. Continuous LWE is as hard as LWE & applications to learning Gaussian mixtures. arXiv preprint arXiv:2204.02550, 2022. [4] C. P. Robert and G. Casella. Monte Carlo Statistical Methods. Springer Texts in Statistics. Springer, New York, 2nd edition, 2004. [5] Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Advances in Neural Information Processing Systems (NeurIPS), volume 20, 2007. [6] Tianyu Gu, Brendan Dolan-Gavitt, and Siddharth Garg. BadNets: Identifying vulnerabilities in the machine learning model supply chain. arXiv preprint arXiv:1708.06733, 2017. [7] Brandon Tran, Jerry Li, and Aleksander Madry. Spectral signatures in backdoor attacks. In Advances in Neural Information Processing Systems (NeurIPS), volume 31, 2018. [8] Jonathan Hayase, Weihao Kong, Raghav Somani, and Sewoong Oh. SPECTRE: Defending against backdoor attacks using robust statistics. In Proceedings of the 38th International Conference on Machine Learning (ICML), pages 4129–4139. PMLR, 2021. [9] Andrey N. Kolmogorov. Sulla determinazione empirica di una legge di distribuzione. Giornale dell’Istituto Italiano degli Attuari, 4:83–91, 1933. [10] Nikolai V. Smirnov. Table for estimating the goodness of fit of empirical distributions. Annals of Mathematical Statistics, 19(2):279–281, 1948. 12
Implementing a White-Box Undetectable Backdoor for Random Fourier Features
A P REPRINT
[11] Samuel S. Shapiro and Martin B. Wilk. An analysis of variance test for normality (complete samples). Biometrika, 52(3-4):591–611, 1965. [12] Vladimir A. Marchenko and Leonid A. Pastur. Distribution of eigenvalues for some sets of random matrices. Matematicheskii Sbornik, 114(4):507–536, 1967. [13] Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), pages 84–93, 2005. [14] Daniele Micciancio and Oded Regev. Lattice-based cryptography. In Post-Quantum Cryptography, pages 147–191. Springer, 2009. [15] Alessandro Rudi and Lorenzo Rosasco. Generalization properties of learning with random features. In Advances in Neural Information Processing Systems (NeurIPS), volume 30, 2017. [16] Yinpeng Dong, Xiao Yang, Zhijie Deng, Tianyu Pang, Zihao Xiao, Hang Su, and Jun Zhu. Black-box detection of backdoor attacks with limited information and data. arXiv preprint arXiv:2103.13127, 2021. [17] Steven Chen, Nicholas Carlini, and David Wagner. Stateful detection of black-box adversarial attacks. In Proceedings of the 3rd ACM Workshop on Security and Privacy on Artificial Intelligence, pages 30–39, 2020. [18] Jeremy Cohen, Elan Rosenfeld, and J. Zico Kolter. Certified adversarial robustness via randomized smoothing. In International Conference on Machine Learning, pages 1310–1320. PMLR, 2019. [19] Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In 2019 IEEE Symposium on Security and Privacy (SP), pages 656–672. IEEE, 2019. [20] Quentin Berthet and Philippe Rigollet. Computational lower bounds for sparse PCA. arXiv preprint arXiv:1304.0828, 2013. [21] Liz Allen, Alison O’Connell, and Veronique Kiermer. How can we ensure visibility and diversity in research contributions? How the Contributor Role Taxonomy (CRediT) is helping the shift from authorship to contributorship. Learned Publishing, 32(1):71–74, 2019.
13