🤖 AI

The Good, the Bad and the Ugly: Meta-Analysis of Watermarks, Transferable Attacks and Adversarial Defenses

This paper formalizes the trade-off between watermarks and adversarial defenses as an interactive protocol, proving that for any learning task, at least one of a watermark, an adversarial defense, or a transferable attack (constructed via fully homomorphic encryption) must exist, while identifying specific conditions under which defenses or watermarks can be secured.

Original authors: Grzegorz Głuch, Berkant Turan, Sai Ganesh Nagarajan, Sebastian Pokutta

Published 2026-01-22

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Grzegorz Głuch, Berkant Turan, Sai Ganesh Nagarajan, Sebastian Pokutta

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine the world of Artificial Intelligence as a massive, high-stakes game of "Hide and Seek" played between two characters: Alice (the attacker) and Bob (the defender). They are trying to figure out who has the upper hand in a specific learning task, like recognizing cats in photos or answering questions.

This paper, titled "The Good, the Bad and the Ugly," argues that in this game, you can never have it all. For any given task, the rules of the universe dictate that at least one of three specific scenarios must happen. You can't have a perfect world where the model is safe, the owner is protected, and no one can trick the system.

Here are the three possible outcomes, explained with simple analogies:

1. The "Good": The Unremovable Watermark

The Scenario: Alice wants to prove she owns a specific AI model. She plants a secret "backdoor" (a hidden trigger) inside the model during training.
The Analogy: Imagine Alice paints a tiny, invisible dot on a specific type of apple. If you feed that specific apple to the machine, it screams "I'm Alice's apple!"
The Catch: The paper says this is only possible if the "dot" is so subtle that Bob (the defender) cannot see it, even if he looks at the machine's code. However, if Bob is too powerful (has too much computing power), he might be able to scrub the dot off.
The Result: If Alice can plant this secret trigger that Bob can't find or remove, she has a Watermark. This is "Good" for the owner because they can prove ownership.

2. The "Bad": The Unstoppable Defense

The Scenario: Bob wants to build a model that is immune to trickery. He wants to know immediately if someone is trying to fool him with a fake input.
The Analogy: Imagine Bob builds a security guard who can smell a fake apple from a mile away. No matter how good the fake apple looks, the guard says, "Stop! This isn't a real apple!"
The Catch: This only works if the "fake apples" (adversarial attacks) look different enough from real ones that the guard can spot them.
The Result: If Bob can build a system that detects every trick Alice tries, he has an Adversarial Defense. This is "Bad" for the attacker because they can't fool the system.

3. The "Ugly": The Transferable Attack

The Scenario: This is the paper's big new discovery. Sometimes, Alice can create a trick that looks exactly like a real apple, but it still breaks the machine. And the scariest part? This trick works on any machine Bob builds, as long as Bob isn't infinitely smart.
The Analogy: Imagine Alice creates a "magic apple" that looks 100% real to the naked eye and to any standard scanner. But when you bite it, it turns into a bomb.
The Twist: The paper proves that if Alice has access to a specific type of "magic math" (called Fully Homomorphic Encryption, which is like doing math on a locked box without opening it), she can create these magic apples.
The Result: If Alice can do this, she has a Transferable Attack. This is "Ugly" because it means no matter how hard Bob tries to defend his specific model, Alice's trick will work on it. It's a universal key that opens every lock.

The Big "Meta" Conclusion

The paper's main theorem is a bit like a law of physics for AI security. It says:

For any learning task, you are stuck with one of these three:

Alice wins: She can hide a secret watermark that Bob can't find.

Bob wins: He can build a defense that catches every trick Alice tries.

The "Ugly" wins: Alice can create a universal trick (using complex cryptography) that looks real but breaks every defense Bob builds.

Why does this matter?
The paper uses heavy math and game theory to prove that you cannot have a world where:

Watermarks are unbreakable AND Defenses are perfect AND Attacks are impossible.
If you try to make a defense that is too strong, you might accidentally make it impossible to watermark the model.
If you try to make a watermark that is too secret, you might accidentally make the model vulnerable to these "Ugly" universal attacks.

The "Resource" Rule:
The paper also gives a rule of thumb for how much computing power is needed. If an attacker has a budget of $T$ (like time or money), the defender usually needs about $T^2$ (the square of that budget) to build a defense that works. If the defender tries to use less power than that, the "Ugly" attack (the universal trick) becomes possible.

In Summary:
The authors aren't saying "AI is doomed." They are saying, "We need to understand the trade-offs." You can't have perfect security, perfect ownership, and perfect safety all at once. Depending on how much computing power the attacker and defender have, one of these three outcomes is mathematically guaranteed to happen.

Technical Summary: The Good, the Bad and the Ugly: Meta-Analysis of Watermarks, Transferable Attacks and Adversarial Defenses

Problem Statement

The paper addresses the fundamental trade-off between backdoor-based watermarks (used for model ownership verification) and adversarial defenses (used to ensure robustness against input perturbations). While previous empirical works have observed that models robust to adversarial attacks may become vulnerable to backdoor attacks, and vice versa, a formal theoretical understanding of this interplay has been lacking.

The authors formalize this landscape as an interactive protocol between a Verifier (Alice) and a Prover (Bob), accounting for their respective computational resources. The central question is: for any given learning task, which of the following three properties must exist?

Watermark: A mechanism to embed an unremovable, undetectable backdoor.
Adversarial Defense: A mechanism to detect and reject adversarial examples that are indistinguishable from the data distribution.
Transferable Attack: An efficient algorithm that generates queries indistinguishable from the data distribution yet capable of fooling all efficient defenders.

The paper posits that these three options form a "trichotomy" where at least one must be possible for any learning task, depending on the computational constraints of the attacker and defender.

Methodology and Formalization

1. Computational Model

The authors model learning tasks and agents using families of Boolean circuits indexed by a size parameter $n$ . This approach, standard in complexity theory, allows for fine-grained control over computational resources (circuit size) rather than just running time.

Learning Task ( $L$ ): Defined as a sequence of distributions over pairs $(D_n, h_n)$ , where $D_n$ is a data distribution and $h_n$ is a ground-truth labeling function.
Agents: Alice (attacker/watermark embedder) and Bob (defender/watermark remover) are represented as circuits with size bounds $S_A(n)$ and $S_B(n)$ .

2. Definitions of the Three Schemes

The paper formalizes the three concepts as interactive protocols:

Watermark (Definition 3): An efficient algorithm that produces a low-error classifier $f$ $f$ and a set of queries $x$ $x$ .
- Correctness: $f$ has low error.
- Uniqueness: A prover with similar resources (who did not use the watermark) cannot produce low-error answers for $x$ .
- Unremovability: A prover with limited resources ( $S_B$ ) cannot produce low-error answers for $x$ .
- Undetectability: The queries $x$ are computationally indistinguishable from the data distribution $D_n$ .
Adversarial Defense (Definition 4): An efficient algorithm that produces a classifier $f$ $f$ and a detection bit $b$ $b$ .
- Correctness: $f$ has low error.
- Completeness: Natural inputs ( $x \sim D_n$ ) are not flagged ( $b=0$ ).
- Soundness: If an adversary ( $S_A$ ) provides inputs that cause high error, the defense must flag them ( $b=1$ ), provided the inputs are indistinguishable from $D_n$ .
Transferable Attack (Definition 5): An efficient algorithm that generates queries $x$ $x$ .
- Transferability: For any prover with limited resources ( $S_B$ ), the queries $x$ cause high error.
- Undetectability: The queries $x$ are indistinguishable from $D_n$ .
- Note: Unlike standard transferability (which relies on model similarity), this definition requires the attack to succeed against any efficient defender, regardless of architecture.

3. Game-Theoretic Framework

The core theoretical engine is a zero-sum game between Alice (trying to embed a watermark) and Bob (trying to remove it/detect attacks).

The game's payoff depends on whether the watermark is successfully removed or the attack is successfully detected.
Using the Min-Max Theorem and results on large zero-sum games (Lipton and Young, 1994), the authors argue that the game admits a Nash Equilibrium.
The value of this equilibrium determines which of the three schemes exists:
- If the game value is high, an Adversarial Defense exists.
- If the game value is low, either a Watermark or a Transferable Attack exists.

Key Contributions and Results

1. The Main Theorem (Trichotomy)

Theorem 1: For every learning task $L$ learnable to error $\epsilon$ with circuit complexity $S(n)$ , at least one of the following exists:

A Watermark (with defender size $o(\sqrt{S(n)/\log S(n)})$ ).
An Adversarial Defense (with defender size $O(S(n))$ ).
A Transferable Attack (with attacker size $S(n)$ ).

This result implies that it is impossible to simultaneously have a secure watermark, a robust defense against all efficient attackers, and no transferable attacks. The existence of one precludes the others under specific resource constraints.

2. Transferable Attacks and Cryptography

The paper constructs a specific learning task based on Fully Homomorphic Encryption (FHE) to demonstrate the existence of Transferable Attacks.

Construction: The task involves a "Lines on a Circle" learning problem augmented with FHE. The data distribution is a mixture of "clear" samples and "encrypted" samples.
Mechanism: The attacker (Alice) learns a classifier on the clear samples. She then generates queries that are either random clear points or encrypted points near the decision boundary. Due to the security of FHE, these encrypted points are indistinguishable from random encrypted points to any efficient adversary.
Result: The attacker can force high error rates on any defender with limited computational resources (who cannot decrypt the samples to learn the boundary), while maintaining indistinguishability.
Implication: The existence of Transferable Attacks implies the existence of EFID pairs (Efficiently samplable, statistically Far, computationally Indistinguishable), a cryptographic primitive. Thus, Transferable Attacks only exist for computationally complex tasks.

3. Bounded VC-Dimension Results

The paper analyzes tasks with bounded VC-dimension:

Adversarial Defenses: For tasks with bounded VC-dimension, an Adversarial Defense exists against all attackers (even those with unbounded computational power), provided the defender has polynomial resources relative to the VC-dimension. This rules out Transferable Attacks in these settings.
Watermarks: For a subclass of bounded VC-dimension tasks, a Watermark exists that is secure against "fast" adversaries (those with strictly fewer resources than the defender). In this specific regime, both a Watermark and an Adversarial Defense can coexist.

Significance and Claims

The paper claims to provide the first model-agnostic, quantitative framework for understanding the trade-offs between watermarks, defenses, and attacks.

Formalizing the Trade-off: It moves beyond empirical observations to a rigorous theoretical proof that for any learning task, the security landscape is determined by the relative computational resources of the attacker and defender.
The Third Option: It identifies Transferable Attacks as a necessary third option in the trade-off, distinct from standard adversarial examples. These are attacks that are indistinguishable from data but fool all efficient defenders.
Cryptographic Connection: It establishes a direct link between the existence of Transferable Attacks and cryptographic hardness (specifically, the existence of EFID pairs). This suggests that "perfect" robustness (no transferable attacks) is only possible for tasks that are not computationally hard in a cryptographic sense.
Resource Allocation Rule of Thumb: The authors propose a practical heuristic: if an adversary has a computational budget $T$ , allocating $T^2$ resources to the defender is sufficient to construct a defense (if one exists). Conversely, if a $T^2$ -budgeted defense fails, it suggests the task admits Transferable Attacks, which in turn precludes the possibility of secure watermarks in that framework.

The paper concludes that the interplay between these three schemes is not merely a matter of model architecture or dataset, but fundamentally a function of the computational complexity of the learning task and the resource disparity between the parties involved.