Does More Compute Make Every Adversarial Attack Transferable?
TL;DR
This work shows that, when there is a quadratic gap in computational resources between attacker and defender, every learnable classification task admits either a transferable attack or an adversarial defense, and proves a stronger result that implies this failure.
Abstract
Transferable attacks, or transferable jailbreaks, are a particularly strong version of adversarial examples that fool all defenders in a class. In this work, we study when more compute enables transferable attacks. We show that, when there is a quadratic gap in computational resources between attacker and defender, every learnable classification task admits either a transferable attack or an adversarial defense. For generative tasks, this dichotomy fails below a quadratic gap, i.e., more compute for the attacker does not lead to a transferable attack. We prove a stronger result that implies this failure: a defense that spends additional computation after it sees the input can be provably strictly stronger than every defense that publishes a fixed model. This result provides formal evidence that increasing inference-time compute can improve robustness, as empirically observed by Zaremba et al. (2025). We assume the existence of an array of cryptographic primitives: identity-based fully homomorphic encryption, publicly verifiable zero-knowledge succinct non-interactive arguments of knowledge, non-parallelizing languages, and incrementally verifiable computation.
