Rethinking the Stealthiness of Cryptographically Undetectable Backdoors in Practical RFF Learning

Random Fourier Features (RFF) learning is a classical technique in scalable data mining. However, at FOCS 2022, Goldwasser et al. proposed a theoretical framework for planting cryptographically undetectable backdoors in RFF learning based on the hardness of the Continuous Learning With Errors (CLWE) problem. Their construction guarantees white-box undetectability in the model parameter space against any polynomial-time distinguisher. In this paper, we revisit the undetectability of CLWE backdoors from a practical RFF learning perspective. We prove that the operational validity of the CLWE backdoor critically hinges on assumptions that are incompatible with the realistic RFF learning deployment. Specifically, standard data preprocessing required for effective RFF learning fundamentally destroys the input-space stealthiness of CLWE backdoors, inevitably resulting in conspicuous input-level artifacts. We further validate our theoretical findings through extensive experiments on both tabular and image datasets, demonstrating that simple sanity checks at the input level suffice to reliably identify backdoored inputs. In addition, under the same threat model, we analyze the adversarial robustness of RFF learning models and provide a concrete certified robustness analysis, enabling a deeper security assessment of its practical deployment. Overall, our work emphasizes the importance of evaluating theoretical backdoor attacks under realistic machine learning pipelines and offers broader insights into the secure deployment of RFF learning systems.