Implementing a White-Box Undetectable Backdoor for Random Fourier Features

Paper: 2609.16403 Authors: Michael Collins, Jada Cumberland, Brianne Dunn, Ross Gore, Samuel Jackson, Sachin Shetty Categories: cs.CR, cs.LG

The Gap

Goldwasser et al. showed that undetectable backdoors can be planted in machine learning models trained with the Random Fourier Features algorithm, under a hardness assumption tied to Continuous Learning With Errors. Under standard cryptographic assumptions, even a full white-box audit of a model’s weights cannot detect this class of backdoor.

The gap this paper fills is not a missing theorem. 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.

   THEORY vs ORDINARY CODE

   Goldwasser et al.
     undetectable RFF backdoor
     hardness from CLWE
     full white-box audit cannot detect
         |
         v
   stated as REDUCTIONS + lemmas
     Sparse Gaussian Pancakes
     homogeneous CLWE conditional density
     NO reference implementation
         |
         v
   [GAP]
     can commodity numpy/scipy realize it?
     or does it need specialized crypto infra?
     which steps need derivation not in the paper?

The Increment

One sentence: Before this paper, the CLWE-RFF backdoor existed as a cryptographic construction; after it, an end-to-end numpy/scipy implementation with statistical indistinguishability tests shows no detectable weight- or function-space gap, and documents which steps required extra derivation.

Core Mechanism

The paper implements the white-box CLWE-RFF backdoor construction end to end using only numpy and scipy, explicitly to test whether this threat is realizable with commodity scientific-computing tools or requires specialized cryptographic infrastructure.

The load-bearing piece is sampling. They give two samplers for the core distribution: a rejection-sampling proxy, and an exact closed-form sampler derived from the homogeneous CLWE density and verified against its own analytic form. Having both matters — the proxy checks practicality; the exact sampler checks faithfulness to the construction.

Using this implementation, they run statistical indistinguishability tests, covering both weight-space and functional black-box comparisons, across sparsity ratios. They find no evidence of detectable difference between backdoored and clean models. They also report which parts were straightforward to realize, which required derivation not spelled out in the paper, and which parts they did not attempt to reproduce, including the underlying lattice hardness reduction.

   FROM REDUCTION TO REPO

   implement CLWE-RFF backdoor
     numpy + scipy only
         |
         +-- sampler A: rejection-sampling proxy
         +-- sampler B: exact closed form
         |              verified vs analytic density
         |
         v
   statistical indistinguishability
     weight-space comparison
     functional black-box comparison
     across sparsity ratios rho = d_sparse / D
         |
         v
   NO detectable difference found
   honesty report:
     straightforward steps
     steps needing extra derivation
     steps not attempted (lattice hardness)

Think of it as a locksmith who published a proof that a certain lock can be opened, then this paper builds the pick from hardware-store steel and tries it on real locks under inspection. The proof said the open is possible under hardness assumptions. The build answers a different question: can a skilled person with ordinary tools actually do it, and can inspectors tell the lock was picked by looking? Here the inspectors looking at weights and behavior do not find a gap — which is the engineering confirmation the theory needed, stated without claiming the hardness proof was reproduced.

Key Concepts

• White-box undetectability: full access to weights still does not separate backdoored from clean, under the construction.
• Exact vs proxy sampling: closed-form fidelity versus a practical rejection sampler — two different claims about realism.
• Reproducibility boundaries: commodity numeric code can realize the ML side; the lattice hardness reduction is out of scope.

Framework Shift

Before (crypto-only existence):       After (implemented threat model):
  reduction + lemmas                 numpy/scipy end-to-end
  no reference code                  two samplers, one exact
  "undetectable" as theorem          "undetectable" under tests run
  realizability assumed               realizability demonstrated
  hardness not in scope (still)      hardness still not reproduced

From a paper that proves a backdoor class exists, to a repository that realizes it with ordinary tools and measures detection failure, the core shift is from existence to operability.

Expert Assessment

Problem choice: Excellent security-relevant gap. An undetectable backdoor that cannot be built is a theorem; one that builds in scipy is an ops problem.

Method maturity: Careful, with the right dual samplers. An unexamined assumption to keep visible: that “no evidence of detectable difference” under the tested statistics is close to the theorem’s undetectability. Empirical non-detection on chosen tests is weaker than reduction-based undetectability; the paper mostly respects that boundary, and readers should too.

Experimental integrity: Strongest choice is reporting what was not reproduced (lattice hardness) instead of implying a full cryptographic audit. Indistinguishability on both weight and function space is the right pair of checks.

Writing quality: Clear about derived-not-stated steps. A short threat-model section for practitioners (who can plant this? what training pipeline is assumed?) would help defenders.

Verdict: weak accept — a sober, useful engineering confirmation of a cryptographic ML threat, with explicit reproduction limits.

Takeaways

• Treat “undetectable backdoor in RFF-trained models” as a buildable threat, not only a theory curiosity — numpy is enough.
• If you audit RFF models, do not assume weight inspection or held-out behavior tests will surface this class; design training provenance instead.
• When implementing paper constructions, publish the steps you had to derive yourself; that is often the real reproducibility debt.