Response to Reviewer 9QUZ

We thank the reviewer for their careful evaluation and recognition of our contributions. Below, we address each concern in turn.

Response to W1 - Explaining Definitions 3–5 in familiar terms

---

1. What is $B_n$ in Definition 3?

$B_n$ (or Bob) is a party that tries to prove that it is not using the (watermarked) model provided by $A_n$ (Alice). It either is dishonest and is using the watermarked model or is honest and trained its own model from scratch.

Alice, on the other hand, has planted a backdoor into her own (open-sourced) model, causing deliberate errors whenever a specific trigger is included in the input. The existence of such an honest $B_n$ ensures that a watermark verification cannot (Uniqueness property in Definition 3) falsely accuse any legitimate (non-watermarked) model.

Answering your question directly, if $B_n$ is dishonest then you are right - it tries to remove the watermark. However, we clarify that in our watermarking notion, the outputs of the model themselves do not carry hidden messages or explicit watermarks. Rather, Alice verifies ownership because her watermarked model deliberately answers incorrectly on very specific trigger inputs (the backdoors), while an honest $B_n$—a model trained independently from scratch—would answer correctly. We refer the reviewer to our answer to Question 1 below, where we discuss this difference in more detail.

---

2. Why does “Soundness” in Definition 4 mean the attack is detected?

This is a good observation. Yes, one can (partly) interpret Definition 4 as a "defense against adversarial examples by detection". However, note that if $x$ is not detected as adversarial, then the soundness property in Definition 4 guarantees that $f$ has low error on $x$, i.e., it successfully defended against the adversary. Additionally, our notion of a defense is very strong, as compared to $l_p$ bounded perturbation model, as it needs to hold against all (efficient) adversaries. This implies that a defense needs to hold against an adversary that provides samples that are clearly far from the support of the distribution. It is unreasonable to require $f$ to answer correctly on such samples and thus detection (rejection) is necessary. Just to reemphasise, a similar rejection-based definition of a defense was considered in Goldwasser et al., 2020.

To recapitulate Adversarial Defenses (Definition 4, informally):

---

3. Why define Transferable Attack this way?
We agree that transferability is usually understood as an adversarial input crafted on a surrogate model that also fools a different, unseen target model. Our notion builds directly on this intuition but lifts it from individual models to learning tasks.

In our framework, Alice trains one surrogate model and wonders whether inputs that fool her model also fool all other models, i.e., models that a different party (e.g., Bob) could train on the same task within the given resource bound. This preserves the classical idea of transferability but generalizes it to a task-level, resource-aware notion. Crucially, the result shows that transferability itself depends on the comparative computational power of attacker and defender, a nuance often overlooked in empirical work.

We will include a description of this perspective directly after Definition 5. Thank you for raising this point.

---

We believe these edits will make each definition’s role and its link to real-world concepts transparent.

Response to W2 - Use of the $\mathbb{F}_2$ (bit) model.

We work over $\mathbb{F}_2$ only for analytic convenience: Boolean circuits are the standard complexity-theoretic abstractions because every finite-precision operations used in machine learning, e.g., addition, matrix multiplication, activation functions, can be implemented by a circuit of AND/OR/NOT gates with a small overhead. We further emphasize that modern deep networks and embeddings are implemented using finite precision arithmetic at the hardware level (e.g.\ 8- or 16-bit integer/FLOAT16 arithmetic). The particular choice of gates and basic operations affects the size of circuits only by constants.

Thus, the $\mathbb{F}_2$ can be assumed with a loss of generality for our results applied to modern deep-learning systems.

We also refer the reviewer to our answer to Question 2 for a related reply.

Response to W3 – From Theory to Practice (experiments)

As the reviewer noted, our focus is theoretical. In our main result we consider a very general class of algorithms, i.e., all circuits of given size, and because of that, experiments are very challenging to run (due to the number of them). However, there is related work that provides experiments for a similar setting, albeit for more restricted classes. For example, Pal and Vidal, 2020 show (first theoretically) that Fast Gradient Methods (as adversarial attacks) and Randomized Smoothing (as defenses) can form a Nash equilibrium under a restricted additive noise model. Additionally, they provide experiments showing that their theoretical result does hold for some datasets (e.g., MNIST). The experiments in Pal and Vidal, 2020 consider a game with a slightly different utility from the one used by us. If the experiments were run for our game, then depending on the utility obtained at the equilibrium, our approach would extract one of the three schemes (defense, watermark, transferable attack).

To go more into detail, a key part of our proof is the formulation of a zero-sum game between a "watermarking agent" and a "defense agent," where the game's value indicates which of the three properties exists. Moreover, an optimal strategy in this game corresponds to an actual implementation of a watermark, defense, or transferable attack.

Though finding a Nash equilibrium in such a game seems computationally challenging—since the action spaces involve all circuits of a given size—recent iterative algorithms for large-scale games [Lanctot et al., 2017; McAleer et al., 2021; Adam et al., 2021] offer promising approaches. These methods work by evaluating only parts of the game at each step, discovering good strategies over time.

In practical settings, circuits can be replaced with standard ML models (e.g., deep neural networks). This opens the door to algorithms that (1) determine whether a given task admits a defense, watermark, or transferable attack, and (2) produce an implementation accordingly. In summary, our theory shows that for a given task, one only needs to set up the appropriate loss and apply these iterative algorithms to extract the desired property. We believe this represents an exciting future direction at the intersection of large-scale algorithmic game theory and AI security.

Response to Q1 - What is the relationship between the Undetectability of Watermark in your definition and the pseudorandomness of error-correcting codes [1]?

[1] Christ and Gunn. Pseudorandom Error-Correcting Codes. 2024.

The main difference is that we watermark a model, while [1] watermarks the outputs of a model - so the goals are different but related. Intuitively, [1] wants to produce outputs with a hidden watermark, while our work produces a model such that if queried in a certain (backdoor) way the answer would "identify" the model "exactly". Our requirement is stronger in the following ways:

• We give the adversary white-box access to the model while [1] allows only black-box access,
• our watermark is unremovable in a stronger than [1] sense, i.e., no efficient algorithm is able to "remove it", while [1] allows only a certain class of perturbations to be applied on the outputs, namely constant fraction edit distance. Note, that even a computationally weak adversary can easily modify an output of an LLM that produces a modified version with a high edit distance, e.g., paraphrasing or "translate to French and back to English" attacks are very effective at removing watermarks.
• both schemes require that watermarked models/outputs are not falsely detected - our uniqueness property, and soundness in [1].

Response to Q2 - Can these results be expanded to continuous data space?

Thank you for raising this point, as it allows us to explain how our results apply more broadly.

Any practical ML pipeline—whether it processes 256×256 RGB images, token sequences, or graphs—executes a finite sequence of arithmetic and logical operations. Bit-level compilation therefore yields a polynomial-size Boolean circuit (e.g., a ReLU network with p weights compiles to O(p log q) gates when each weight is quantised to q bits). Because our theorems depend only on the ratio of prover to verifier circuit sizes, the dimensionality or structure of the data does not change the trade-offs.

Response to Q3 - $\gamma \in [0,1]$ ?

We thank the reviewer for finding this typo. $\gamma$ should belong to $[0,1/2]$.

---

References:

Lanctot, Marc, et al. "A unified game-theoretic approach to multiagent reinforcement learning." NeurIPS 2017.

McAleer, Stephen, et al. "XDO: A double oracle algorithm for extensive-form games." NeurIPS 2021.

Adam, Lukáš, et al. "Double oracle algorithm for computing equilibria in continuous games." AAAI 2021.

Pal, Ambar, and René Vidal. "A game theoretic analysis of additive adversarial attacks and defenses." NeurIPS 2020.

Response to Reviewer j4Va

Thank you for your review and for recognizing the strengths and contributions of our work. We address your comments individually below.

---

Response to Connection to Platonic Representation Hypothesis (PRH)

Thank you for drawing the connection to the Platonic Representation Hypothesis (PRH). This is indeed an interesting connection to our work! We also see a connection to Ilyas et al. 2019, that, at least morally, claims that adversarial examples might transfer between very accurate models.

Our Theorem 3 shows that a transferable attack exists only when the underlying learning task is computationally "hard" (in the EFID sense)—that is. If the representations of models converge (as observed in PRH), then we might expect the adversarial examples to transfer and our results imply that the underlying learning task is "computationally complex". This shows that a perhaps necessary condition, and thus a partial explanation of PRH, for models' representations converging is that frontier models solve increasingly difficult problems.

Overall, we agree that this bridge between task complexity and representation similarity is a promising direction. In the final version, we will add a short remark to Section 7 (Future Work) referencing PRH as an empirical hypothesis that our complexity-based formulation may help formalize and test.

We appreciate the reviewer’s insight and will highlight this connection to stimulate further research.

Response to W1 – Scope of the result

Thank you for pointing out the wording issue. Throughout the paper, we use the term “learning task” exactly as defined in Definition 1 (lines 128–131), i.e., a binary or multi-class classification problem. All proofs are carried out in that setting.

To avoid overstatement, we will:

• Change “any learning task” to “any (binary) classification task” in the Abstract and in the bullet list of Section 1.1.

As noted in our response to Reviewer f8Ls (W3), we already discuss in Related Work (lines 98–102) how backdoor-based watermarks have been applied to generative models, and we clarify in Appendix E how the framework could be adapted beyond classification.

Response to W2/L1 – Real world-impact and Key Take aways:

Real world Impact

We would like to clarify that trade-offs between backdoor-based attacks and adversarial defenses have been studied in several prior works, primarily through empirical analysis. These works generally observe that models made robust to certain adversarial attacks often become more vulnerable to backdoor-based attacks, highlighting the nuanced and complex nature of such trade-offs.

For example, (Pal and Vidal, 2020) show (first theoretically) that Fast Gradient Methods (as adversarial attacks) and Randomized Smoothing (as defenses) can form a Nash equilibrium under a restricted additive noise model. Additionally, they provide experiments showing that their theoretical result does hold for some datasets (e.g., MNIST). The experiments in Pal and Vidal, 2020 consider a game with a slightly different utility from the one used by us. If the experiments were run for our game, then depending on the utility obtained at the equilibrium, our approach would extract one of the three schemes (defense, watermark, transferable attack). Our theoretical contributions can be seen as a generalization of this result to a broader class of attacks and defenses.

Computational Resources

Our theorem also offers insight into the computational resources required to successfully construct a watermark or a defense. Specifically, if one aims to defend against adversaries with a computational budget of $T$ units (interpretable as compute time), our result suggests that by increasing one’s own resources to $T^2$, it is likely to succeed—provided the learning task admits a defense. Conversely, if such an effort fails, it may indicate that the task permits transferable attacks, which in turn could preclude the existence of a watermark as well. This perspective could serve as a practical guideline for how to allocate resources before concluding that a task may not admit a defense. To our best knowledge, we provide one of the first quantitive bounds on the resources of attackers and defenders in very general settings (e.g., beyond bounded VC-dim etc.)."

Key Take away

Most prior works have focused primarily on the trade-off between backdoor attacks and adversarial defenses, often via empirical studies. Our work shows that to fully characterize this landscape, it is essential to include transferable attacks—a point we believe constitutes one of our key technical contributions.

More concretely, we show that there exist learning tasks where one can fail to be both robust (via adversarial defenses) and verifiable (via backdoor-based watermarks)—this is precisely the case captured in Theorem 2 through the construction of transferable attacks.

However, this is not the only scenario we consider. In fact, we prove a more general result: every learning task must admit at least one of the three schemes. For example, we show that there exist restricted classes of learning tasks with bounded VC-dimension where robustness and verifiability can both be achieved simultaneously (Appendix I and Appendix J, Lemmas 3 and 4). For such tasks, transferable attacks do not arise.

Response to Q1 – Why we focus on Backdoor-based Watermarks

As detailed in Appendix A.1.1, we focus on backdoor-based watermarking because it is currently the only family of methods that satisfies all three properties required for secure black-box ownership verification, as formalized in Definition 3:

1. No accuracy loss on the main task,
2. Robustness to removal, and
3. Undetectable verification (i.e., trigger inputs are indistinguishable from normal data).

Other approaches—such as white-box watermarking, which embeds hidden signals in model weights—are fundamentally different in nature. While they may be suitable for analysis, they are not applicable in settings where the model is only accessible via an API.

Because black-box verification is the more realistic scenario in practice—especially when models are misused to offer services via an interface—we focus on techniques suitable for that setting. In this realm, the research community has largely converged on backdoor-based watermarking as the most viable approach.

For completeness, we discuss other techniques such as white-box watermarking in Appendix A.1.1.

We hope this clarifies why our framework centers on backdoor-based watermarking and how it aligns with the dominant practical and research focus in secure model ownership verification.

Response to Q2 – Who owns the model in Fig. 1?

Unfortunately, "owner" is not the most precise word to be used in this setting, however, we try to answer your question using this terminology.

Bob is always the model owner / defender, and Alice is always the adversary / verifier. Their roles remain fixed throughout the paper; only Alice’s objective varies across the three scenarios:

Bob is always the party required to answer Alice’s queries, which is why he is consistently considered the “owner” of the model across all settings. It is possible though, that in case of ownership theft, that Bob is using the watermarked model by Alice in Definition 3.

We will edit the caption to read (new text in italics):

Figure 1: Schematic overview of the interaction structure, along with short, informal versions of
our definitions of (a) Watermark (Definition 3), (b) Adversarial Defense (Definition 4), and (c)
Transferable Attack (Definition 5), with (c) tied to cryptography (see Section 6).
Throughout this figure, Alice (the verifier) plays the role of the adversary, while Bob (the prover) plays the role of the defender.

We hope this clarifies the roles. Thank you for bringing this to our attention.

Response to Q3 – Generalization Beyond Classifiers

Yes—two routes are discussed in the manuscript:

1. Fine-tune generative models into a small classification task.
   Pre-trained language models (PLMs), for example, can be lightly fine-tuned so a back-door watermark verifies ownership; we cite such PLM watermarks in Related Work (lines 98–102).

2. Direct non-classification extension.
   Appendix E outlines how our verifier–prover game carries over when fine-tuning is not possible, by redefining correctness and detection on the model’s native output space.

---

We thank the reviewer for their insightful feedback, particularly regarding the Platonic Representation Hypothesis (PRH), which aligns well with our framework. We hope our clarifications and revisions address the concerns raised.

References:

Lanctot, Marc, et al. "A unified game-theoretic approach to multiagent reinforcement learning." NeurIPS 2017.

McAleer, Stephen, et al. "XDO: A double oracle algorithm for extensive-form games." NeurIPS 2021.

Adam, Lukáš, et al. "Double oracle algorithm for computing equilibria in continuous games." AAAI 2021.

Pal, Ambar, and René Vidal. "A game theoretic analysis of additive adversarial attacks and defenses." NeurIPS 2020.

Ilyas et al. 2019, "Adversarial Examples Are Not Bugs, They Are Features"

Response to Reviewer je1d

Thank you for your review and for recognizing the strengths and contributions of our work. We address your comments individually below.

Response to W1 – Use of the term “transferable attack”

We agree that “transferability” is commonly understood as the ability of an adversarial input—crafted on a surrogate model—to fool a different, unseen target model. Our notion builds directly on this intuition, but generalizes it by shifting the focus from individual models to entire learning tasks.

Specifically, in our framework, the surrogate model is trained by Alice herself and represents one possible instantiation of the surrogate model. The key question is whether adversarial inputs crafted on Alice’s model transfer to all other models that could be trained by any other party (e.g., Bob) on the same task. This formulation captures the original idea of transferability while lifting it to a task-level abstraction that allows for formal analysis.

We believe this generalization is not only conceptually aligned with the standard usage but also necessary to rigorously study transferability. Importantly, our framework shows that transferability depends critically on the computational power of both the attacker and the defender—a subtlety that is often overlooked in empirical work.

We acknowledge the risk of confusion and will add a clarifying remark early in Section 1.1, emphasizing that our use of “transferable attack” formalizes and extends the classical notion in a task-level, resource-bounded setting.

We thank the reviewer for their thoughtful perspective on terminology, and we hope this response clarifies our intended usage.

Response to W2 – Clarity and Key takeaways

We thank the reviewer for this important comment and believe that their intuition is largely correct. As noted, we do show that there exist learning tasks where one can fail to be both robust (via adversarial defenses) and verifiable (via backdoor-based watermarks)—this is precisely the case captured in Theorem 2 through the construction of transferable attacks.

However, this is not the only scenario we consider. In fact, we prove a more general result: every learning task must admit at least one of the three schemes. For example, we show that there exist restricted classes of learning tasks with bounded VC-dimension where robustness and verifiability can both be achieved simultaneously (Appendix I and Appendix J, Lemmas 3 and 4). For such tasks, transferable attacks do not arise.

Most prior works have focused primarily on the trade-off between backdoor attacks and adversarial defenses, often via empirical studies. Our work shows that to fully characterize this landscape, it is essential to include transferable attacks—a point we believe constitutes one of our key technical contributions. Furthermore, please look at the response to W3 below, for more practical take-aways and implications.

Finally, due to space constraints, we were unable to include all relevant preliminaries in the main text. However, we will ensure that additional background material is included in the appendix to make the paper more accessible to a broader ML audience.

Response to W3 – Implications of Our Results

1. Existing Results

We would like to clarify that trade-offs between backdoor-based attacks and adversarial defenses have been studied in several prior works, primarily through empirical analysis. These works generally observe that models made robust to certain adversarial attacks often become more vulnerable to backdoor-based attacks, highlighting the nuanced and complex nature of such trade-offs.

For example, (Pal and Vidal, 2020) show (first theoretically) that Fast Gradient Methods (as adversarial attacks) and Randomized Smoothing (as defenses) can form a Nash equilibrium under a restricted additive noise model. Additionally, they provide experiments showing that their theoretical result does hold for some datasets (e.g., MNIST). The experiments in Pal and Vidal, 2020 consider a game with a slightly different utility from the one used by us. If the experiments were run for our game, then depending on the utility obtained at the equilibrium, our approach would extract one of the three schemes (defense, watermark, transferable attack). Our theoretical contributions can be seen as a generalization of this result to a broader class of attacks and defenses.

2. Computational Resources

Our theorem also offers insight into the computational resources required to successfully construct a watermark or a defense. Specifically, if one aims to defend against adversaries with a computational budget of $T$ units (interpretable as compute time), our result suggests that by increasing one’s own resources to $T^2$, it is likely to succeed—provided the learning task admits a defense. Conversely, if such an effort fails, it may indicate that the task permits transferable attacks, which in turn could preclude the existence of a watermark as well. This perspective could serve as a practical guideline for how to allocate resources before concluding that a task may not admit a defense. To our best knowledge, we provide one of the first quantitive bounds on the resources of attackers and defenders in very general settings (e.g., beyond bounded VC-dim etc.).

We respectfully disagree that the paper offers limited new insight, and hope that the clarifications and proposed revisions make its contributions and takeaways more apparent.

Response to W4 – From Theory to Practice

A key part of our proof is the formulation of a zero-sum game between a "watermarking agent" and a "defense agent," where the game's value indicates which of the three properties exists. Moreover, an optimal strategy in this game corresponds to an actual implementation of a watermark, defense, or transferable attack.

Though finding a Nash equilibrium in such a game seems computationally challenging—since the action spaces involve all circuits of a given size—recent iterative algorithms for large-scale games [Lanctot et al., 2017; McAleer et al., 2021; Adam et al., 2021] offer promising approaches. These methods work by evaluating only parts of the game at each step, discovering good strategies over time. Recall that our model captures examples like (Pal and Vidal, 2020).

In practical settings, circuits can be replaced with standard ML models (e.g., deep neural networks). This opens the door to algorithms that (1) determine whether a given task admits a defense, watermark, or transferable attack, and (2) produce an implementation accordingly. In summary, our theory shows that for a given task, one only needs to set up the appropriate loss and apply these iterative algorithms to extract the desired property. We believe this represents an exciting future direction at the intersection of large-scale algorithmic game theory and AI security.

---

We sincerely appreciate the reviewer’s critical perspective and constructive remarks. We hope that the above clarifications and proposed revisions effectively address the concerns raised and contribute to improving the paper’s clarity.

---

References:

Lanctot, Marc, et al. "A unified game-theoretic approach to multiagent reinforcement learning." NeurIPS 2017.

McAleer, Stephen, et al. "XDO: A double oracle algorithm for extensive-form games." NeurIPS 2021.

Adam, Lukáš, et al. "Double oracle algorithm for computing equilibria in continuous games." AAAI 2021.

Pal, Ambar, and René Vidal. "A game theoretic analysis of additive adversarial attacks and defenses." NeurIPS 2020.

Thank you for your review and recognizing our contributions. We address your points below.

Response to W1- Practical Implications

1. Existing Results

We would like to clarify that trade-offs between backdoor-based attacks and adversarial defenses have been studied in several prior works, primarily through empirical analysis. These works generally observe that models made robust to certain adversarial attacks often become more vulnerable to backdoor-based attacks, highlighting the nuanced and complex nature of such trade-offs.

For example, (Pal and Vidal, 2020) show (first theoretically) that Fast Gradient Methods (as adversarial attacks) and Randomized Smoothing (as defenses) can form a Nash equilibrium under a restricted additive noise model. Additionally, they provide experiments showing that their theoretical result does hold for some datasets (e.g., MNIST). The experiments in Pal and Vidal, 2020 consider a game with a slightly different utility from the one used by us. If the experiments were run for our game, then depending on the utility obtained at the equilibrium, our approach would extract one of the three schemes (defense, watermark, transferable attack). Our theoretical contributions can be seen as a generalization of this result to a broader class of attacks and defenses.

2. Computational Resources

Our theorem also offers insight into the computational resources required to successfully construct a watermark or a defense. Specifically, if one aims to defend against adversaries with a computational budget of $T$ units (interpretable as compute time), our result suggests that by increasing one’s own resources to $T^2$ , it is likely to succeed—provided the learning task admits a defense. Conversely, if such an effort fails, it may indicate that the task permits transferable attacks, which in turn could preclude the existence of a watermark as well. This perspective could serve as a practical guideline for how to allocate resources before concluding that a task may not admit a defense. To our best knowledge, we provide one of the first quantitative bounds on the resources of attackers and defenders in very general settings (e.g., beyond bounded VC-dim etc.).

Response to W2- Boolean Circuits

At a fundamental level, families of Boolean circuits—as used in our work—are Turing complete, meaning they can simulate any algorithm that a Turing machine can. This makes them expressive enough to capture any computable algorithm and a natural abstraction for studying the inherent properties of learning tasks, independent of specific algorithms. One of our contributions is to show that, for every learning task, at least one of the following must exist: a watermark, an adversarial defense, or a transferable attack.

While, as the reviewer notes, this may not have immediate practical utility, our existence result can guide practical efforts by informing where to search. A key part of our proof is the formulation of a zero-sum game between a "watermarking agent" and a "defense agent," where the game's value indicates which of the three properties exists. Moreover, an optimal strategy in this game corresponds to an actual implementation of a watermark, defense, or transferable attack.

Though finding a Nash equilibrium in such a game seems computationally challenging—since the action spaces involve all circuits of a given size—recent iterative algorithms for large-scale games [Lanctot et al., 2017; McAleer et al., 2021; Adam et al., 2021] offer promising approaches. These methods work by evaluating only parts of the game at each step, discovering good strategies over time. Recall that our model captures examples like (Pal and Vidal, 2020).

In practical settings, circuits can be replaced with standard ML models (e.g., deep neural networks). This opens the door to algorithms that (1) determine whether a given task admits a defense, watermark, or transferable attack, and (2) produce an implementation accordingly. In summary, our theory shows that for a given task, one only needs to set up the appropriate loss and apply these iterative algorithms to extract the desired property. We believe this represents an exciting future direction at the intersection of large-scale algorithmic game theory and AI security.

Response to W3 – Why the exemplar task uses FHE

Section 6 proves that transferable attacks imply the existence of EFID pairs (Theorem 3). This shows that some computational assumptions are necessary for the existence of transferable attacks. It is possible that a weaker assumption than FHE is enough to construct transferable attacks. We left this question for future work.

The key reason why some computational assumptions are necessary is the undetectability property of transferable attacks, i.e., the adversarial examples should be indistinguishable from normal samples. Standard arguments from computational complexity imply that if adversarial examples can be efficiently generated and are indistinguishable, then computational assumptions are necessary.

Response to notation comment (lines 206 & 217)

We thank the reviewer for pointing out this typo. But additionally, the two representations are equivalent:

({0,1}^n)^q = {0,1}^n × ... × {0,1}^n (q times) ≅ {0,1}^{nq}

so the original x ∈ {0,1}^{nq} is correct.
However, we agree that ({0,1}^n)^q makes the “tuple of q inputs” interpretation clearer.
We will therefore adopt the reviewer’s notation in lines 206, 217.

Response to Q1 – Binary vs. continuous input spaces

Thank you for raising this point, as it allows us to explain how our results apply more broadly.

Any practical ML pipeline—whether it processes 256×256 RGB images, token sequences, or graphs—executes a finite sequence of arithmetic and logical operations. Bit-level compilation therefore yields a polynomial-size Boolean circuit (e.g., a ReLU network with p weights compiles to O(p log q) gates when each weight is quantised to q bits). Because our theorems depend only on the ratio of prover to verifier circuit sizes, the dimensionality or structure of the data does not change the trade-offs.

To answer your question directly, our framework already encompasses the continuous input spaces.

Response to Q2 – What we mean by “complementary”

We use “complementary” in two ways:

1. At the mechanism level:

   • A Watermark (Definition 3) allows the defender to prove authorship by planting backdoors that can later be triggered to cause specific errors, serving as evidence of ownership.
   • A defense (Definition 4) helps the defender detect or reject adversarial manipulations.
     These serve different purposes and can be applied together.

2. At the outcome level:
   Theorem 1 shows that for any task, either the defender can enforce a defense or the attacker succeeds with a Watermark or a Transferable Attack (Definition 5).
   So the true complement of “having a defense” is exactly what the reviewer noted: the union of Watermark and Transferable Attack.

We hope this clarifies what we mean by “complementary” in this context.

Response to Q3 – Multiplicity of $B_n$ in Definition 3

Thank you for pointing this out.

The existential clause $\exists$ $B_n$ such that $err(x, y) < 2 \epsilon$ is included solely to prevent false positives: it guarantees that a (non-watermarked) model trained from scratch $f_{Scratch}$ answers the watermark queries (containing the trigger) correctly. Meanwhile, the Correctness condition ($err \leq \epsilon$) ensures we compare only models of similar utility to the watermarked one.

If two, ten, or $n-1$ different models trained from scratch also satisfy this inequality, the condition is still met—the definition depends only on the existence of such models, not on the number of them.

To answer your question more directly: yes, our framework is deliberately designed to capture and formalize this through the Uniqueness property in Definition 3, which ensures that the watermark does not accidentally generalize across independently trained models.

We hope this clarifies the intent behind the definition.

Response to Q4 – Clarifying the distinction between robustness, transferable attacks, and watermarking

Thank you for this thoughtful question.

The key subtlety lies in what happens when the model is not adversarial robustness. In that case, two distinct phenomena can occur:

• A Watermark is a backdoor trigger that reliably causes one specific model to err, while remaining correctly handled by non-watermarked models. This is enforced by the Uniqueness property in Definition 3 and ensures that the trigger is model-specific (e.g., can be used for ownership verification).

• A Transferable Attack, by contrast, causes all models (within some bounded computational class) to fail on the same input. It breaks robustness in a universal way and, unlike a watermark, is not tied to one specific model.

Informally, a watermark trigger might unintentionally cause errors in all models, violating Uniqueness and becoming a transferable attack instead. In such a scenario, adversarial examples are inherently transferable, making proper watermarking impossible.

Thus, while robustness and transferable attacks appear as a dichotomy, watermarking creates a third case: a model vulnerable only to specific, non-transferable triggers, enabling the coexistence of all three definitions in the trilemma.

---

References:

Lanctot, Marc, et al. "A unified game-theoretic approach to multiagent reinforcement learning." NeurIPS 2017.

McAleer, Stephen, et al. "XDO: A double oracle algorithm for extensive-form games." NeurIPS 2021.

Adam, Lukáš, et al. "Double oracle algorithm for computing equilibria in continuous games." AAAI 2021.

Pal, Ambar, and René Vidal. "A game theoretic analysis of additive adversarial attacks and defenses." NeurIPS 2020.

Response to Reviewer f8Ls

Thank you for your thorough review and for acknowledging the contributions of our work. Let us address your concerns and questions one by one.

---

Response to W1 – Clarifying the link between our Section 4 definitions and established notions.

Below we map each element of our Section 4 framework to the corresponding, well‑studied concepts in the watermarking and adversarial‑defense literature and explain why every property is necessary.

---

1. Backdoor–based watermarks (Definition 3)

---

2. Adversarial defenses (Definition 4)

---

3. Transferable attacks (Definition 5)

---

4. Why the explicit interactive protocol?

• Bridging literatures:
  Framing watermarks and defenses as verifier–prover games lets us use proof techniques from zero‑sum games and interactive proofs (Goldwasser et al., 1986), which is crucial for Theorem 1.

• Resource‑aware analysis:
  Circuit‑size parameters $(S_A, S_B)$ capture fine‑grained trade‑offs (e.g. $S_A \approx \sqrt{S_B}$ in Theorem 1) that earlier works omit.

---

5. Planned text changes to improve clarity

1. Add a bridging paragraph at the start of Sec. 4 explicitly mapping each property to its classical analogue (see tables above).

---

We hope this clarifies how our formalisation extends, rather than deviates from, established definitions while retaining the new computational perspective.

Response to W2/Q1 – Practical implications for real‑world ML security

1. Existing Results

We would like to clarify that trade-offs between backdoor-based attacks and adversarial defenses have been studied in several prior works, primarily through empirical analysis. These works generally observe that models made robust to certain adversarial attacks often become more vulnerable to backdoor-based attacks, highlighting the nuanced and complex nature of such trade-offs.

For example, (Pal and Vidal, 2020) show (first theoretically) that Fast Gradient Methods (as adversarial attacks) and Randomized Smoothing (as defenses) can form a Nash equilibrium under a restricted additive noise model. Additionally, they provide experiments showing that their theoretical result does hold for some datasets (e.g., MNIST). The experiments in Pal and Vidal, 2020 consider a game with a slightly different utility from the one used by us. If the experiments were run for our game, then depending on the utility obtained at the equilibrium, our approach would extract one of the three schemes (defense, watermark, transferable attack). Our theoretical contributions can be seen as a generalization of this result to a broader class of attacks and defenses.

2. Computational Resources

Our theorem also offers insight into the computational resources required to successfully construct a watermark or a defense. Specifically, if one aims to defend against adversaries with a computational budget of $T$ units (interpretable as compute time), our result suggests that by increasing one’s own resources to $T^2$ , it is likely to succeed—provided the learning task admits a defense. Conversely, if such an effort fails, it may indicate that the task permits transferable attacks, which in turn could preclude the existence of a watermark as well. This perspective could serve as a practical guideline for how to allocate resources before concluding that a task may not admit a defense. To our best knowledge, we provide one of the first quantitive bounds on the resources of attackers and defenders in very general settings (e.g., beyond bounded VC-dim etc.).

Response to W3 – Extending beyond classification

Thank you for raising this point. While our main results are phrased for binary classification, the framework naturally extends to generative models as well.

We already reference how our definitions apply to backdoor-based watermarking in generative models such as pre-trained language models (PLMs) in Related Work (Gu et al., 2022; Peng et al., 2023; Li et al., 2023; lines 98–102, 985–992), and outline how to adapt the framework to non-classification tasks in Appendix E.

To make the presentation clearer, we will revise the Related Work section to distinguish between:

• backdoor-based watermarks in generative models that can be framed as classification tasks (e.g., PLMs), and
• watermarking settings that omit classification entirely.

This addition highlights that our framework partly accommodates state-of-the-art generative systems without modifying the underlying formalism.

Response to W4/L1 – Circuits and their Limitations

At a fundamental level, families of Boolean circuits—as used in our work—are Turing complete, meaning they can simulate any algorithm that a Turing machine can. This makes them expressive enough to capture any computable algorithm and a natural abstraction for studying the inherent properties of learning tasks, independent of specific algorithms. One of our contributions is to show that, for every learning task, at least one of the following must exist: a watermark, an adversarial defense, or a transferable attack.

While, as the reviewer notes, this may not have immediate practical utility, our existence result can guide practical efforts by informing where to search. A key part of our proof is the formulation of a zero-sum game between a "watermarking agent" and a "defense agent," where the game's value indicates which of the three properties exists. Moreover, an optimal strategy in this game corresponds to an actual implementation of a watermark, defense, or transferable attack.

Though finding a Nash equilibrium in such a game seems computationally challenging—since the action spaces involve all circuits of a given size—recent iterative algorithms for large-scale games [Lanctot et al., 2017; McAleer et al., 2021; Adam et al., 2021] offer promising approaches. These methods work by evaluating only parts of the game at each step, discovering good strategies over time. Recall that our model captures examples like (Pal and Vidal, 2020).

In practical settings, circuits can be replaced with standard ML models (e.g., deep neural networks). This opens the door to algorithms that (1) determine whether a given task admits a defense, watermark, or transferable attack, and (2) produce an implementation accordingly. In summary, our theory shows that for a given task, one only needs to set up the appropriate loss and apply these iterative algorithms to extract the desired property. We believe this represents an exciting future direction at the intersection of large-scale algorithmic game theory and AI security.

Response to minor comment – Fig. 1 caption

Thank you for catching the ambiguity.
We will edit the caption to read (new text in italics):

Figure 1: [...] Throughout this figure, Alice (the verifier) plays the role of the adversary, while Bob (the prover) plays the role of the defender.

---

We sincerely thank the reviewer for their critical perspective and hope that these clarifications and planned revisions resolve the concerns raised and improve the paper’s accessibility and impact.

---

References:

Lanctot, Marc, et al. "A unified game-theoretic approach to multiagent reinforcement learning." NeurIPS 2017.

McAleer, Stephen, et al. "XDO: A double oracle algorithm for extensive-form games." NeurIPS 2021.

Adam, Lukáš, et al. "Double oracle algorithm for computing equilibria in continuous games." AAAI 2021.

Pal, Ambar, and René Vidal. "A game theoretic analysis of additive adversarial attacks and defenses." NeurIPS 2020.