Neekon Vafa

STOC Conference 2025 Conference Paper

Oblivious Defense in ML Models: Backdoor Removal without Detection

• Shafi Goldwasser
• Jonathan Shafer
• Neekon Vafa
• Vinod Vaikuntanathan

As society grows more reliant on machine learning, ensuring the security of machine learning systems against sophisticated attacks becomes a pressing concern. A recent result of Goldwasser, Kim, Vaikuntanathan, and Zamir (FOCS ’22) shows that an adversary can plant undetectable backdoors in machine learning models, allowing the adversary to covertly control the model’s behavior. Backdoors can be planted in such a way that the backdoored machine learning model is computationally indistinguishable from an honest model without backdoors. In this paper, we present strategies for defending against backdoors in ML models, even if they are undetectable. The key observation is that it is sometimes possible to provably mitigate or even remove backdoors without needing to detect them, using techniques inspired by the notion of random self-reducibility. This depends on properties of the ground-truth labels (chosen by nature), and not of the proposed ML model (which may be chosen by an attacker). We give formal definitions for secure backdoor mitigation, and proceed to show two types of results. First, we show a “global mitigation” technique, which removes all backdoors from a machine learning model under the assumption that the ground-truth labels are close to a Fourier-heavy function. Second, we consider distributions where the ground-truth labels are close to a linear or polynomial function in ℝ n . Here, we show “local mitigation” techniques, which remove backdoors with high probability for every input of interest, and are computationally cheaper than global mitigation. All of our constructions are black-box, so our techniques work without needing access to the model’s representation (i.e., its code or parameters). Along the way we prove a simple result for robust mean estimation.

STOC Conference 2025 Conference Paper

Symmetric Perceptrons, Number Partitioning and Lattices

• Neekon Vafa
• Vinod Vaikuntanathan

The symmetric binary perceptron ( SBP κ ) problem with parameter κ : ℝ ≥1 → [0,1] is an average-case search problem defined as follows: given a random Gaussian matrix A ∼ N (0,1) n × m as input where m ≥ n , output a vector x ∈ {−1,1} m such that || A x || ∞ ≤ κ( m / n ) · √ m . The number partitioning problem ( NPP κ ) corresponds to the special case of setting n =1. There is considerable evidence that both problems exhibit large computational-statistical gaps. In this work, we show (nearly) tight average-case hardness for these problems, assuming the worst-case hardness of standard approximate shortest vector problems on lattices. • For SBP κ , statistically, solutions exist with κ( x ) = 2 −Θ( x ) (Aubin, Perkins and Zdeborová, Journal of Physics 2019). For large n , the best that efficient algorithms have been able to achieve is a far cry from the statistical bound, namely κ( x ) = Θ(1/√ x ) (Bansal and Spencer, Random Structures and Algorithms 2020). The problem has been extensively studied in the TCS and statistics communities, and Gamarnik, Kızıldağ, Perkins and Xu (FOCS 2022) conjecture that Bansal-Spencer is tight: namely, κ( x ) = Θ(1/√ x ) is the optimal value achieved by computationally efficient algorithms. We prove their conjecture assuming the worst-case hardness of approximating the shortest vector problem on lattices. • For NPP κ , statistically, solutions exist with κ( m ) = Θ(2 − m ) (Karmarkar, Karp, Lueker and Odlyzko, Journal of Applied Probability 1986). Karmarkar and Karp’s classical differencing algorithm achieves κ( m ) = 2 − O (log 2 m ) . We prove that Karmarkar-Karp is nearly tight: namely, no polynomial-time algorithm can achieve κ( m ) = 2 −Ω(log 3 m ) , once again assuming the worst-case subexponential hardness of approximating the shortest vector problem on lattices to within a subexponential factor. Our hardness results are versatile, and hold with respect to different distributions of the matrix A (e.g., i.i.d. uniform entries from [0,1]) and weaker requirements on the solution vector x .

STOC Conference 2024 Conference Paper

Memory Checking Requires Logarithmic Overhead

• Elette Boyle
• Ilan Komargodski
• Neekon Vafa

FOCS Conference 2022 Conference Paper

Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixtures

• Aparna Gupte
• Neekon Vafa
• Vinod Vaikuntanathan

We show direct and conceptually simple reductions between the classical learning with errors (LWE) problem and its continuous analog, CLWE (Bruna, Regev, Song and Tang, STOC 2021). This allows us to bring to bear the powerful machinery of LWE-based cryptography to the applications of CLWE. For example, we obtain the hardness of CLWE under the classical worst-case hardness of the gap shortest vector problem. Previously, this was known only under quantum worst-case hardness of lattice problems. More broadly, with our reductions between the two problems, any future developments to LWE will also apply to CLWE and its downstream applications. As a concrete application, we show an improved hardness result for density estimation for mixtures of Gaussians. In this computational problem, given sample access to a mixture of Gaussians, the goal is to output a function that estimates the density function of the mixture. Under the (plausible and widely believed) exponential hardness of the classical LWE problem, we show that Gaussian mixture density estimation in $\mathbb{R}^{n}$ with roughly $\log n$ Gaussian components given poly $(n)$ samples requires time quasi-polynomial in n. Under the (conservative) polynomial hardness of LWE, we show hardness of density estimation for $n^{\epsilon}$ Gaussians for any constant $\epsilon>0$, which improves on Bruna, Regev, Song and Tang (STOC 2021), who show hardness for at least $\sqrt{n}$ Gaussians under polynomial (quantum) hardness assumptions. Our key technical tool is a reduction from classical LWE to LWE with k-sparse secrets where the multiplicative increase in the noise is only $O(\sqrt{k})$, independent of the ambient dimension n.