Response to Reviewer fUbR

We thank the reviewer for their comments relating to definitions of adversarial defenses and robust learnability. Below, we address the specific points raised.

---

On Our Adversarial Defense Definition

We would first like to clarify that the model of Adversarial Defense we work with is similar to models where abstaining from responding is allowed, i.e., Selective Classification. To this end, our result shows the existence of a defense for tasks with bounded VC-dimension, using the algorithm of [Goldwasser et al., 2020] as a subroutine. This ensures that there is no restriction on the model of attack of the adversaries.

Furthermore, finding adversarial examples and defending against adversaries are problems inherently limited by computation ([Garg et al., 2020] and [Bubeck et al., 2019]). Hence, we believe it is natural to model adversaries as computationally limited entities.

Importantly, our definition also allows adversaries that are unbounded. For instance, we show the existence of an adversarial defense in the case of learning tasks with bounded VC-dimension, even when attackers are computationally unbounded.

---

On the Applicability of Lower Bounds of [Montasser et al., 2019]

In our framework, the function output by the defense algorithm may differ from the hypothesis class of the target labeling function. This means our approach falls under the improper learning framework, and thus we believe there is no contradiction with the lower bounds presented in [Montasser et al., 2019].

---

Additional Notes

We hope that our responses clarify the concerns raised. If there are any remaining questions or points requiring further elaboration, we kindly ask the reviewer to let us know. We greatly appreciate your constructive feedback and its contribution to improving the paper.

---

References

• Bubeck, Sébastien, et al. "Adversarial examples from computational constraints." International Conference on Machine Learning. PMLR, 2019.
• Garg, Sanjam, et al. "Adversarially Robust Learning Could Leverage Computational Hardness." Algorithmic Learning Theory. PMLR, 2020.
• Montasser, Omar, Steve Hanneke, and Nathan Srebro. "VC classes are adversarially robustly learnable, but only improperly." Conference on Learning Theory. PMLR, 2019.

Response to Reviewer tRxz

We thank Reviewer tRxz for their time and effort in providing detailed and constructive feedback on our work. Below, we address each of the points raised, organized into sections for clarity.

1. Prior Work on Trade-offs

Reviewer Comment:

“There are multiple prior works that have investigated the trade-off between adversarial robustness and backdoors/watermarks... Although most of these papers are more empirical, this paper completely ignores an entire line of work.”

Response:

We appreciate the reviewer highlighting the importance of prior work on adversarial robustness and backdoor trade-offs. While our work primarily focuses on a theoretical framework, we agree that an explicit discussion of how our results relate to existing empirical studies would enhance the paper. To this end:

• In Appendix A.2 (Adversarial Defense), we will add a discussion about our theoretical framework and prior empirical studies, such as [Weng et al., Sun et al., Niu et al., Fowl et al., Tao et al.]. While these works explore empirical trade-offs, our framework formalizes these relationships through interactive proof systems and cryptographic primitives.
• We will emphasize in Section 2 (Related Work) that our framework introduces the concept of transferable attacks to this trade-off, not previously explored in these works, as a theoretical tool to prove the simultaneous failure of adversarial robustness and backdoor defenses.

We will also clarify the phrasing of the statement: “Along the way to proving the main result, we identify a potential reason why this fact was not discovered earlier” (Section 1.1.) to avoid ambiguity. It will explicitly reference the theoretical conditions underpinning our main result, rather than implying the absence of prior work.

---

Reviewer Comment:

“Explicitly state what novel insights their work provides beyond the existing literature.”

Response:

In Section 1.1, we explicitly outline our contributions, which we summarize as follows:

1. We prove that for every learning task, at least one of the following must exist: a backdoor-based watermark, an adversarial defense, or a transferable attack.
   This result extends the empirical observations in prior work by providing a formal theoretical framework that guarantees these outcomes for all learning tasks.

2. We introduce the concept of a transferable attack, a third and previously unexplored option in this trade-off.
   Transferable attacks arise for tasks where neither watermarks nor adversarial defenses can exist. This counterintuitive result broadens the theoretical understanding of trade-offs in robustness and backdoor-based watermarks by identifying scenarios that were overlooked in prior empirical studies.

3. We establish a connection between transferable attacks and cryptographic primitives.
   We show that the existence of a transferable attack for a learning task implies the presence of certain cryptographic properties, emphasizing the computational complexity inherent in these tasks.

---

Reviewer Comment:

“Add a section on potential practical applications or implications of their theoretical results.”

Response:

We thank the reviewer for this suggestion. The practical implications of our theoretical results are discussed in Section 7 (Implications for AI Safety). In this section, we conjecture that adversarial defenses will exist for safety-critical discriminative learning tasks and provide three supporting arguments based on our theoretical findings, including Theorem 1 and the connection between transferable attacks and cryptographic primitives (Theorem 8). These insights directly contribute to understanding the robustness and security of AI systems in safety-critical regimes.

---

2. Coefficient Before Epsilon in Definition 2.3

Reviewer Comment:

“Why is the coefficient before epsilon, 7?”

Response:

We thank the reviewer for raising this question.

The coefficient $7$ in Definition 2.3 is not a special constant. Intuitively, it comes from a type of "triangle inequality" in the proof of Theorem 1, where one needs to account for multiple sources of error (e.g., $2\epsilon + 2\epsilon + 2\epsilon < 7\epsilon$). We will clarify this reasoning in the final version to improve accessibility by adding an explanation to Appendix C (Main Theorem).

Note: The response continues in the next section.

Response to Reviewer 7Ahn

We thank the reviewer for their thoughtful and detailed feedback, which has helped us identify areas for improvement and clarify our work. Below, we address the comments raised.

1. On the Necessity of the Definition

The definition is necessary since samples that are adversarial could be outside the $supp(D)$. We will make the definition clearer in the main draft.

---

2. Advantage and Indistinguishability

We clarify the concepts of advantage and indistinguishability here, through a game between a sender and a distinguisher.

For an algorithm $\mathcal{A}$ (also known as the distinguisher) and two distributions $\mathcal{D}_0, \mathcal{D}_1$, consider the following game between a sender and the distinguisher:

1. The sender samples a bit $b \sim U(\{0,1\})$ and then draws a random sample $\mathbf{x} \sim \mathcal{D}_b$.
2. $\mathcal{A}$ receives $\mathbf{x}$ and outputs $\hat{b} := \mathcal{A}(\mathbf{x}) \in \{0,1\}$. $\mathcal{A}$ wins if $\hat{b} = b$.

We say that $\delta \in (0, \frac{1}{2})$ is the advantage of $\mathcal{A}$ for distinguishing $\mathcal{D}_0$ from $\mathcal{D}_1$ if:

$$P_{b \sim U(\{0,1\}), \mathbf{x} \sim \mathcal{D}_b}[\mathcal{A}(\mathbf{x}) = b] = \frac{1}{2} + \delta\;,$$

For a class of algorithms, we say that the two distributions $\mathcal{D}_0$ and $\mathcal{D}_1$ are $\delta$-indistinguishable if for any algorithm in the class, its advantage is at most $\delta$.

---

3. Generality of Definitions

The definitions are general, and it could be that the protocols are instantiated with $t \geq T$. For instance, in our Transferable Attack example (Theorem 2), we have $t > T$.

---

4. Comparability of Definitions

In general, these definitions are incomparable:

• You are correct that if the attacker can choose a distribution, it makes defendability (in the sense of Christiano et al.) harder compared to a fixed distribution (as in our model). On the other hand, the backdoor $x^*$ is sampled $\sim \mathcal{D}$ in Christiano et al., i.e., the attacker has no influence over it, while in our model, the attacker can choose $x$'s. In this aspect, defendability is easier in Christiano's model.

• It is interesting to investigate further that both we and Christiano showed a Defense/defendability for bounded VC-dimension classes, albeit with a priori incomparable definitions.

We acknowledge that we did not phrase the comparison perfectly. Our intention was to emphasize the following differences in the respective frameworks:

1. Christiano et al. aim at a taxonomy of representation classes only (independent of $\mathcal{D}$), while our Theorem 1 gives a taxonomy of pairs $(\mathcal{D}, h)$.
2. This allows us to model scenarios where $\mathcal{D}$ is chosen by nature and not just in the worst-case setting.

---

5. Use of Zero-Sum Games

Using zero-sum games for us is a proof strategy and not a modeling choice, as our proof examines how attacks on watermarks can be turned into defenses and vice versa. Hence, zero-sum games are a natural choice. Moreover, zero-sum games are cleaner in the sense that the value of the game is unique, which prevents issues about equilibrium selection.

Regarding other equilibrium notions, such as Stackelberg equilibria, in two-player zero-sum games, the set of Stackelberg equilibria and Nash equilibria is the same. Additionally, one can show that coarse correlated equilibria (CCEs) and Nash equilibria are nearly equivalent for two-player zero-sum games.

We will add more background on two-player zero-sum games and Nash equilibria in the main paper for the final version.

---

6. Succinct Representation

Please see the Succinct Representation paragraph in our response to Reviewer EjNG.

---

7. Transferable Attack and LWE Clarification

We are not entirely sure how to construct the Transferable Attack example without using FHE, as the learning procedure requires computation on encrypted data. We would be open to learning about other methods if they simplify the construction.

Regarding the reviewer's question about the LWE problem, we note the following:

1. LWE is used to build FHE, so it is unclear if the proposed construction uses a weaker assumption.
2. If we understand your point correctly, the two distributions you define, i.e., LWE and uniform, are indeed indistinguishable as required by undetectability in Definition 3. However, we do not see how transferability is satisfied or how the ground truth is defined in the first place.

Additional Notes

We kindly ask you to confirm whether our responses have resolved your concerns and clarified the issues raised. If there are any remaining questions or points requiring further elaboration, please let us know. Your thoughtful feedback is valuable in helping us improve our work.

Response to Reviewer EjNG

We sincerely thank the reviewer EjNG for their thoughtful and constructive feedback. Below, we address each of the concerns raised and provide clarifications where necessary.

When writing this paper, we made a deliberate design choice to present the results in a manner that is accessible to a broad ML audience. Most research fields have an implicitly agreed-upon level of formality, which is not yet established for topics such as watermarks, adversarial defenses, and AI security more broadly. In our paper, we aim to bridge practical and theoretical perspectives.

To this end, our definitions are designed to model very general threat scenarios, ensuring practical relevance. At the same time, we strive to provide formal and complete proofs to uphold theoretical rigor. Balancing these objectives is inherently challenging, and as you noted, the desired generality can make the presentation more complex.

With this in mind, we fully agree that our paper is a theory-driven work and requires rigorous treatment. In some aspects, particularly in the main body, we may have oversimplified certain definitions and proofs. We will address your detailed comments below and aim to convince you that all notions can indeed be made formal. Naturally, we will incorporate your feedback into the final version of the paper.

On Modeling

Size Parameter

We believe that a big part of the confusion stems from the fact that the size parameter is not present in our modeling. In computational complexity, one studies models of computations like DFAs, Turing Machines, and circuits. When studying DFAs, the size parameter is not present as the same automaton is used for all input sizes.

In contrast, when analyzing the running time of Turing Machines or the sizes of circuits, one often evaluates complexity in terms of input length. Introducing a size parameter enables discussions about complexity classes like linear, polynomial, or exponential, without being constrained by constants. However, once an algorithm is instantiated in practice, the input size becomes fixed, and these constants start to matter.

In our work, both the definitions and the main result (Theorem 1) are framed without a size parameter, focusing instead on a fixed learning task with a fixed-sized representation of samples. This choice stems from the observation that for the most general learning tasks, there is no clear, universally appropriate size parameter. For instance, should ImageNet be parameterized by the number of pixels? Such ambiguity underscores our decision to avoid introducing a size parameter unnecessarily.

Succinctness

You are correct in noticing that the succinct representation prevents hardcoding of the function, but our motivation stems from how learning happens in practice. More precisely, in our framework, the learning task is a fixed distribution and target labeling function. By using succinct representation, we enforce the lack of knowledge about the task, which prevents hardcoding $f$.

In practice, we are often given fixed learning tasks, and constraints are imposed on the learning algorithm (e.g., gradient descent on a specific architecture or a time bound). As we mentioned in the paper, our model covers the case of neural networks because succinct circuits can represent gradient descent on NNs. In summary, both in practice and in our framework, it is impossible to hardcode the true labeling functions for non-trivial learning tasks, which are the ones we care about.

Cryptography

In Section 5.1 (Theorem 2, also see Theorem 7 with all parameters), we use the size parameter. This is because we leverage existing cryptographic tools, such as FHE, where efficiency/security is defined as polynomial/polynomial indistinguishability. Our construction considers a family of distributions (that define the learning task) parameterized by $\lambda$ (see Theorem 7). However, in practice, the parties receive samples only from one of these distributions.

In Section 5.2, where we discuss EFID pairs, we do not use the size parameter. We acknowledge that this could lead to confusion and will emphasize this distinction more clearly. As you point out, the usual definition of EFID pairs considers ensembles and polynomial indistinguishability.

We also appreciate your observation regarding the Goldreich construction of pseudorandom generators, which does not apply in our case due to the reliance on randomness during EFID pair generation. However, we believe a more careful adaptation of the construction might still yield a pseudorandom generator in our framework.

In summary, we agree that the title of this section might be too provocative, as we demonstrate the existence of an EFID pair rather than addressing all cryptography. However, we stand by the justification that the pair of distributions we define can be considered a type of EFID pair.

Note: The response continues in the next section.