The Good, the Bad and the Ugly: Watermarks, Transferable Attacks and Adversarial Defenses

## Abstract

Abstract We formalize and extend existing definitions of backdoor-based watermarks and adversarial defenses as interactive protocols between two players.
The existence of these schemes is inherently tied to the learning tasks for which they are designed.
Our main result shows that for almost every learning task, at least one of the two – a watermark or an adversarial defense – exists.
The term “almost every” indicates that we also identify a third, counterintuitive but necessary option, i.e., a scheme we call a transferable attack .
By transferable attack, we refer to an efficient algorithm computing queries that look indistinguishable from the data distribution and fool all efficient defenders.
To this end, we prove the necessity of a transferable attack via a construction that uses a cryptographic tool called homomorphic encryption.
Furthermore, we show that any task that satisfies our notion of a transferable attack implies a cryptographic primitive , thus requiring the underlying task to be computationally complex.
These two facts imply an “equivalence” between the existence of transferable attacks and cryptography.
Finally, we show that the class of tasks of bounded VC-dimension has an adversarial defense, and a subclass of them has a watermark.

## 1 Introduction

A company invested considerable resources to train a new classifier $f$.
They want to open-source $f$ but also ensure that if someone uses $f$, it can be detected in a black-box manner.
In other words, they want to embed a *watermark* into $f$.(^2^22Note that they want to watermark the model itself, not its outputs.)
Alice, an employee, is in charge of this project.
Bob, a member of an AI Security team, has a different task.
His goal is to make $f$ *adversarially robust*, i.e., to ensure it is hard to find queries that appear unsuspicious but cause $f$ to make mistakes. Alice, after many unsuccessful approaches, reports to her boss that it might be inherently impossible to create a black-box watermark in $f$ that cannot be removed.
After a similar experience, Bob reports to his boss that, due to the sheer number of possible modes of attack, he could only produce an ever-growing, unsatisfactory, and ‘ugly’ defense.

One day, after discussing their work, Alice and Bob realized that their projects are intimately connected.
Alice said that her idea was to plant a backdoor in $f$, creating $f_{A}$, so she could later craft queries with a hidden trigger that activates the backdoor, causing $f_{A}$ to misclassify, while remaining indistinguishable from standard queries.
By sending these tailored queries in a black-box manner to a party suspected of using $f_{A}$, she can detect whether $f_{A}$ is being used based on the responses triggered by her backdoor.
But Bob realized that his defenses were trying to render such a situation impossible.
One of his ideas for defense was to take $f$ and then \saysmooth its outputs to obtain $f_{B}$, aiming for robustness against attacks.
Bob noticed that this procedure removes some of the backdoor-based watermarks that Alice came up with.
Conversely, Alice noticed that any $f$ with a watermark that is difficult to remove implies that some models are inherently difficult to make robust.
Alice and Bob realized that their challenges are two sides of the same coin: the impossibility of one task guarantees the success of the other.

### 1.1 Contributions

This paper initiates a formal study of the above observation that backdoor-based watermarks and adversarial defenses span all possible scenarios.
By scenarios, we refer to learning tasks that $f$ is supposed to solve.

Our main contribution is:

We prove that almost every learning task has at least one of the two:
A Watermark or an Adversarial Defense.

To do that, we formalize and extend existing definitions of watermarks and adversarial defenses, frame Alice and Bob’s dynamic as a formal game, and show that this game is guaranteed to have at least one winner. Along the way to proving the main result, we identify a potential reason why this fact was not discovered earlier.
There is also a third, counterintuitive but necessary option, i.e., there are tasks with neither a Watermark nor an Adversarial Defense.

Imagine that Alice plays the following game. The game is played with respect to a specific learning task $\mathcal{L}=(\mathcal{D},h)$, where $\mathcal{D}$ is the data distribution and $h$ is the ground truth.
Alice sends queries to a player and receives their responses.
She wins if the responses have a lot of errors and if the player cannot distinguish them from the queries from $\mathcal{D}$.
Importantly, whether she wins the game depends on how much compute and data Alice and the player have.
If Alice wins the game against any player having the same amount of resources as her, then we call Alice’s queries a Transferable Attack.
Intuitively, the harder a query becomes, the easier it is to distinguish it from queries from $\mathcal{D}$.
But this seems to indicate that it is hard to design Transferable Attacks.

However, we provably show:

- •
An example of a Transferable Attack defined as above.
Interestingly, the example uses tools from the field of cryptography, namely Fully Homomorphic Encryption (FHE) (Gentry, ).
Notably, a Transferable Attack rules out Watermarks and Adversarial Defenses, thus constituting the third necessary option.
- •
That every Transferable Attack implies a certain cryptographic primitive, i.e., access to samples from the underlying task is enough to build essential parts of encryption systems.
Thus, every task with a Transferable Attack has to be complex in the computational complexity theory sense.

Finally, we complement the above results with instantiations of Watermarks and Adversarial Defenses:

- •
We show the existence of an Adversarial Defense for all learning tasks with bounded Vapnik–Chervonenkis (VC) dimension, thereby ruling out Transferable Attacks in this regime.
- •
We give an example of a black-box Watermark for a class of learning tasks with bounded VC-dimension. Notably, in this case, both a Watermark and an Adversarial Defense exist.

Figure: (a)
Refer to caption: extracted/5919864/figures/crypto-logo2.png

## 2 Related Work

This paper lies at the intersection of machine learning theory, interactive proof systems, and cryptography. We review recent advances and related contributions from these areas that closely align with our research.

##### Interactive Proof Systems in Machine Learning.

Interactive Proof Systems (Goldwasser and Sipser, ) have recently gained considerable attention in machine learning for their ability to formalize and verify complex interactions between agents, models, or even human participants. A key advancement in this area is the introduction of Prover-Verifier Games (PVGs) (Anil et al., ), which employ a game-theoretic approach to guide learning agents towards decision-making with verifiable outcomes. Building on PVGs, Kirchner et al. () enhance this framework to improve the legibility of Large Language Models (LLMs) outputs, making them more accessible for human evaluation. Similarly, Wäldchen et al. () apply the prover-verifier setup to offer interpretability guarantees for classifiers. Extending these concepts, self-proving models Amit et al. () introduce generative models that not only produce outputs but also generate proof transcripts to validate their correctness. In the context of AI safety, scalable debate protocols (Condon et al., ; Irving et al., ; Brown-Cohen et al., ) leverage interactive proof systems to enable complex decision processes to be broken down into verifiable components, ensuring reliability even under adversarial conditions.

Overall, these developments highlight the emerging role of interactive proof systems in addressing key aspects of AI Safety, such as interpretability, verifiability, and alignment. While current research predominantly focuses on applying this framework to improve these safety attributes, our approach takes an orthogonal direction by examining the feasibility of properties related to adversarial robustness and backdoor-based watermarks.

##### Planting Undetectable Backdoors.

A key related work is presented by Goldwasser et al. (), which demonstrates how a learner can plant undetectable backdoors in any classifier, allowing hidden manipulation of the model’s output with minimal perturbation of the input. These backdoors are activated by specific “triggers”, which are subtle changes to the input that cause the model to misclassify any input with the trigger applied, while maintaining its expected behavior on regular inputs. The authors propose two frameworks. The first utilizes digital signature schemes (Goldwasser et al., ) that make backdoored models indistinguishable from the original model to any computationally-bounded observer. The second involves Random Fourier Features (RFF) (Rahimi and Recht, ), which ensures undetectability even with full transparency of the model’s weights and training data.

In a concurrent and independent work, Christiano et al. () introduce a defendability framework that formalizes the interaction between an attacker planting a backdoor and a defender tasked with detecting it.
The attacker modifies a classifier to alter its behavior on a trigger input while leaving other inputs unaffected.
The defender then attempts to identify this trigger during evaluation, and if successful with high probability, the function class is considered defendable.
The authors show an equivalence between their notion of defendability (in a computationally unbounded setting) and Probably Approximately Correct (PAC) learnability, and thus the boundedness of the VC-dimension of a class.
In computationally bounded cases, they propose that efficient defendability serves as an important intermediate concept between efficient learnability and obfuscation.

A major difference between our work and that of Christiano et al. (), is that in their approach, the attacker chooses the distribution, whereas we keep the distribution fixed.
A second major difference is that our main result holds for *all* learning tasks, while the contributions of Christiano et al. () hold for restricted classes only.
However, there are many interesting connections.
Computationally unbounded defendability is shown to be equivalent to PAC learnability, while we, in a similar spirit, show an Adversarial Defense for all tasks with bounded VC-dimension.
They show that efficient PAC learnability implies efficient defendability, and we show that the same fact implies an efficient Adversarial Defense.
Using cryptographic tools, they show that the class of polynomial-size circuits is not efficiently defendable, while we use different cryptographic tools to give a Transferable Attack, which rules out a Defense.

##### Backdoor-Based Watermarks.

In black-box settings, where model auditors lack access to internal parameters, watermarking methods often involve embedding backdoors during training. Techniques by Adi et al. () and Zhang et al. () use crafted input patterns as triggers linked to specific outputs, enabling ownership verification by querying the model with these specific inputs. Advanced methods by Merrer et al. () utilize adversarial examples, which are perturbed inputs that yield predefined outputs. Further enhancements by Namba and Sakuma () focus on the robustness of watermarks, ensuring the watermark remains detectable despite model alterations or attacks.

In the domain of Natural Language Processing (NLP), backdoor-based watermarks have been studied for Pre-trained Language Models (PLMs), as exemplified by works such as (Gu et al., ; Peng et al., ) and (Li et al., ). These approaches embed backdoors using rare or common word triggers, ensuring watermark robustness across downstream tasks and resistance to removal techniques like fine-tuning or pruning. However, it is important to note that these lines of research are predominantly empirical, with limited theoretical exploration.

##### Adversarial Robustness.

As we emphasize, the study of backdoors is closely related to adversarial robustness, which focuses on improving model resilience to adversarial inputs. The extensive literature in this field includes key contributions such as adversarial training (Madry et al., ), which improves robustness by training on adversarial examples, and certified defenses (Raghunathan et al., ), which offer provable guarantees against adversarial attacks by ensuring prediction stability within specified perturbation bounds. Techniques like randomized smoothing (Cohen et al., ) extend these robustness guarantees. Notably, Goldwasser et al. () show that some undetectable backdoors can, in fact, be removed by randomized smoothing, highlighting the intersection of adversarial robustness and backdoor methods.

## 3 Watermarks, Adversarial Defenses and Transferable Attacks

In this section, we outline interactive protocols between a verifier and a prover. Each protocol is designed to address specific tasks such as watermarking, adversarial defense, and transferable attacks. We first introduce the preliminaries before detailing the properties that each protocol must satisfy.

### 3.1 Preliminaries

##### Discriminative Learning Task.

For $n\in\mathbbm{N}$ we define $[n]:=\big{\{}0,1,\dots,n-1\big{\}}$.
A *learning task* $\mathcal{L}$ is a pair $(\mathcal{D},h)$ of a distribution $\mathcal{D}$, $\text{supp}(\mathcal{D})\subseteq{\mathcal{X}}$ (the input space) and a ground truth map $h\colon{\mathcal{X}}\rightarrow{\mathcal{Y}}\cup\{\perp\}$, where ${\mathcal{Y}}$ is a finite space of labels and $\perp$ represents a situation where $h$ is not defined.
To every $f\colon{\mathcal{X}}\rightarrow{\mathcal{Y}}$, we associate

$$ $\text{err}(f):=\mathbb{E}_{x\sim\mathcal{D}}[f(x)\neq h(x)].$ $$

We implicitly assume $h$ does not map to $\perp$ on $\text{supp}(\mathcal{D})$.
We assume all parties have access to i.i.d. samples $(x,h(x))$, where $x\sim\mathcal{D}$, although $\mathcal{D}$ and $h$ are unknown to the parties.

For $q\in\mathbbm{N},\mathbf{x}\in{\mathcal{X}}^{q},\mathbf{y}\in{\mathcal{Y}}^{q}$ we define

$$ $\text{err}(\mathbf{x},\mathbf{y}):=\frac{1}{q}\ \sum_{i\in[q]}\mathbbm{1}_{\{h (x_{i})\neq y_{i},h(x_{i})\neq\perp\}},$ $$

which means that we count $(x,y)\in{\mathcal{X}}\times{\mathcal{Y}}$ as an error if $h$ is well-defined on $x$ and $h(x)\neq y$.

##### Indistinguishability

For an algorithm $\mathcal{A}$ and two distributions $\mathcal{D}_{0},\mathcal{D}_{1}$, 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

$$ $\mathbb{P}[\mathcal{A}\;\;\texttt{wins}]\leq 1/2+\delta\;,$ $$

in the following game:

- 1.
Sender samples a bit $b\sim U(\{0,1\})$ and then draws a random sample from $\mathbf{x}\sim\mathcal{D}_{b}$.
- 2.
$\mathcal{A}$ gets $\mathbf{x}$ and outputs $\hat{b}\in\{0,1\}$. $\mathcal{A}$ wins if $\hat{b}=b$.

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.2 Definitions

In our protocols, Alice ($\mathbf{A}$, verifier) and Bob ($\mathbf{B}$, prover) engage in interactive communication, with distinct roles depending on the specific task. Each protocol is defined with respect to a learning task $\mathcal{L}=(\mathcal{D},h)$, an error parameter $\varepsilon\in\left(0,\frac{1}{2}\right)$, and time bounds $T_{\mathbf{A}}$ and $T_{\mathbf{B}}$. A scheme is successful if the corresponding algorithm satisfies the desired properties with high probability, and we denote the set of such algorithms by $\textsc{Scheme}(\mathcal{L},\varepsilon,T_{\mathbf{A}},T_{\mathbf{B}})$, where Scheme refers to Watermark, Defense, or TransfAttack.

Definition 1 (Watermark, informal).

An algorithm $\mathbf{A}_{\textsc{Watermark}}$, running in time $T_{\mathbf{A}}$, implements a watermarking scheme for the learning task $\mathcal{L}$, with error parameter ${\epsilon}>0$, if an interactive protocol in which $\mathbf{A}_{\textsc{Watermark}}$ computes a classifier $f\colon{\mathcal{X}}\rightarrow{\mathcal{Y}}$ and a sequence of queries $\mathbf{x}\in{\mathcal{X}}^{q}$, and a prover $\mathbf{B}$ outputs $\mathbf{y}=\mathbf{B}(f,\mathbf{x})\in{\mathcal{Y}}^{q}$ satisfies the following properties:

Figure: Figure 2: Schematic overview of the interaction between Alice and Bob in Watermark (Definition 3.2).

- 1.
Correctness: $f$ has low error, i.e.,
$\text{err}(f)\leq{\epsilon}$.
- 2.
Uniqueness:
There exists a prover $\mathbf{B}$, running in
time bounded by $T_{\mathbf{A}}$, which provides low-error
answers, such that $\text{err}(\mathbf{x},\mathbf{y})\leq 2{\epsilon}$.
- 3.
Unremovability:
For every prover $\mathbf{B}$ running in time $T_{\mathbf{B}}$, it holds that $\text{err}(\mathbf{x},\mathbf{y})>2{\epsilon}$.
- 4.
Undetectability:
For every prover $\mathbf{B}$ running in time $T_{\mathbf{B}}$, the advantage of $\mathbf{B}$ in distinguishing the queries $\mathbf{x}$ generated by $\mathbf{A}_{\textsc{Watermark}}$ from random queries sampled from $\mathcal{D}^{q}$ is small.

Note that, due to *uniqueness*, we require that any defender, who *did not use* $f$ and trained a model $f_{\text{Scratch}}$, must be accepted as a distinct model. This requirement is essential, as it mirrors real-world scenarios where independent models could have been trained within the given time constraint $T_{\mathbf{A}}$. Additionally, the property enforces that any successful Watermark must satisfy the condition that Bob’s time is strictly less than $T_{\mathbf{A}}$, i.e., $T_{\mathbf{B}}<T_{\mathbf{A}}$.

Definition 2 (Adversarial Defense, informal).

An algorithm $\mathbf{B}_{\textsc{Defense}}$, running in time $T_{\mathbf{B}}$, implements an adversarial defense for the learning task $\mathcal{L}$ with error parameter ${\epsilon}>0$, if an interactive protocol in which $\mathbf{B}_{\textsc{Defense}}$ computes a classifier $f\colon{\mathcal{X}}\rightarrow{\mathcal{Y}}$, a verifier $\mathbf{A}$ replies with $\mathbf{x}=\mathbf{A}(f)$, where $\mathbf{x}\in{\mathcal{X}}^{q}$, and $\mathbf{B}_{\textsc{Defense}}$ outputs $b=\mathbf{B}_{\textsc{Defense}}(f,\mathbf{x})\in\{0,1\}$, satisfies the following properties:

Figure: Figure 3: Schematic overview of the interaction between Alice and Bob in Adversarial Defense (Definition 3.2).

- 1.
Correctness:
$f$ has low error, i.e., $\text{err}(f)\leq{\epsilon}$.
- 2.
Completeness:
When $\mathbf{x}\sim\mathcal{D}^{q}$, then $b=0$.
- 3.
Soundness: For every $\mathbf{A}$ running in time $T_{\mathbf{A}}$, we have
$\text{err}(\mathbf{x},f(\mathbf{x}))\leq 7{\epsilon}\ \text{ or }\ b=1$.

The key requirement for a successful defense is the ability to *detect when it is being tested*. To bypass the defense, an attacker must provide samples that are both adversarial, causing the classifier to make mistakes, and *indistinguishable* from samples drawn from the data distribution $\mathcal{D}$.

Definition 3 (Transferable Attack, informal).

An algorithm $\mathbf{A}_{\textsc{TransfAttack}}$, running in time $T_{\mathbf{A}}$, implements a transferable attack for the learning task $\mathcal{L}$ with error parameter ${\epsilon}>0$, if an interactive protocol in which $\mathbf{A}_{\textsc{TransfAttack}}$ computes $\mathbf{x}\in{\mathcal{X}}^{q}$ and $\mathbf{B}$ outputs $\mathbf{y}=\mathbf{B}(\mathbf{x})\in{\mathcal{Y}}^{q}$ satisfies the following properties:

Figure: Figure 4: Schematic overview of the interaction between Alice and Bob in Adversarial Defense (Definition 3.2).

- 1.
Transferability:
For every prover $\mathbf{B}$ running in
time $T_{\mathbf{A}}$, we have $\text{err}(\mathbf{x},\mathbf{y})>2{\epsilon}$.
- 2.
Undetectability:
For every prover $\mathbf{B}$ running in
time $T_{\mathbf{B}}$, the advantage of $\mathbf{B}$ in distinguishing the
queries $\mathbf{x}$ generated by $\mathbf{A}_{\textsc{TransfAttack}}$ from random queries sampled from $\mathcal{D}^{q}$ is small.

##### Verifiability of Watermarks.

For a watermarking scheme $\mathbf{A}_{\textsc{Watermark}}$, if the *unremovability* property holds with a stronger guarantee, i.e., much larger than $2{\epsilon}$, then $\mathbf{A}_{\textsc{Watermark}}$ could determine whether $\mathbf{B}$ had stolen $f$.
To achieve this, $\mathbf{A}_{\textsc{Watermark}}$ runs, after completing its interaction with $\mathbf{B}$, the procedure guaranteed by *uniqueness* to obtain $\mathbf{y}^{\prime}$. It then verifies whether $\mathbf{y}$ and $\mathbf{y}^{\prime}$ differ for many queries. If this condition is met, $\mathbf{A}_{\textsc{Watermark}}$ concludes that $\mathbf{B}$ had stolen $f$.(^3^33Observe that this test *would not work*, if there were many valid labels for a given input, i.e., a situation often encountered in large language models.) Alternatively, if *unremovability* holds with $2{\epsilon}$, as originally defined, the test described above may fail.
In this scenario, we consider an external party overseeing the interaction, potentially with knowledge of the distribution and $h$, who can directly compute the necessary errors to make a final decision.
This setup is similar to the use of human judgment oracles in (Brown-Cohen et al., ). An interesting direction for future work would be to explore cases where the parties have access to *restricted* versions of error oracles. While this is beyond the scope of this work, we outline potential avenues for addressing this in Appendix 7.

## 4 Main Result

We are ready to state an informal version of our main theorem.
Please refer to Theorem 5 for the details and full proof. The key idea is to define a zero-sum game between $\mathbf{A}$ and $\mathbf{B}$, where the actions of each player are the possible algorithms or circuits that can be implemented in the given time bound. Notably, this game is finite, but there are exponentially many such actions for each player. We rely on some key properties of such large zero-sum games (Lipton and Young, ; Lipton et al., ) to argue about our main result.
The formal statement and proof is deferred to Appendix C.

###### Theorem 1 ( Main Theorem, informal ) .

For every learning task $\mathcal{L}$ and ${\epsilon}\in\big{(}0,\frac{1}{2}\big{)},T\in\mathbbm{N}$, where a learner exists that runs in time $T$ and, with high probability, learns $f$ satisfying $\text{err}(f)\leq{\epsilon}$, at least one of these three exists:

$$ Watermark $\displaystyle\left(\mathcal{L},{\epsilon},T,T^{1/\sqrt{\log(T)}}\right),$ Defense $\displaystyle\left(\mathcal{L},{\epsilon},T^{1/\sqrt{\log(T)}},O(T)\right),$ TransfAttack $\displaystyle\Big{(}\mathcal{L},{\epsilon},T,T\Big{)}.$ $$

###### Proof (Sketch)..

The intuition of the proof relies on the complementary nature of Definitions 3.2 and 3.2.
Specifically, every attempt to remove a fixed Watermark can be transformed to a potential Adversarial Defense, and vice versa.
We define a zero-sum game $\mathcal{G}$ between watermarking algorithms $\mathbf{A}$ and algorithms attempting to remove a watermark $\mathbf{B}$.(^4^44Additionally, we require that the algorithms A and B are *succinctly* representable. This requirement forbids a trivial way to circumvent learning by hard-coding the ground-truth classifier in the description of the algorithms. We refer the reader to Appendix C.)
The actions of each player are the class of algorithms that they can run in their respective time bounds, and the payoff is determined by the probability that the errors and rejections meet specific requirements.
According to Nash’s theorem, there exists a Nash equilibrium for this game, characterized by strategies $\mathbf{A}_{\textsc{Nash}}$ and $\mathbf{B}_{\textsc{Nash}}$.
A careful analysis shows that depending on the value of the game, we have a Watermark, an Adversarial Defense, or a Transferable Attack.

In the first case, where the expected payoff at the Nash equilibrium is greater than a threshold, we show there is an Adversarial Defense.
We define $\mathbf{B}_{\textsc{Defense}}$ as follows.
$\mathbf{B}_{\textsc{Defense}}$ first learns a low-error classifier $f$, then sends $f$ to the party that is attacking the Defense, then receives queries $\mathbf{x}$, and simulates $(\mathbf{y},b)=\mathbf{B}_{\textsc{Nash}}(f,\mathbf{x})$.
The bit $b=1$ if $\mathbf{B}_{\textsc{Nash}}$ thinks it is attacked.
Finally, $\mathbf{B}_{\textsc{Defense}}$ replies with $b^{\prime}=1$ if $b=1$, and if $b=0$ it replies with $b^{\prime}=1$ if the fraction of queries on which $f(\mathbf{x})$ and $\mathbf{y}$ differ is high.
Careful analysis shows $\mathbf{B}_{\textsc{Defense}}$ is an Adversarial Defense.
In the second case, where the expected payoff at the Nash equilibrium is below the threshold, we have either a Watermark or a Transferable Attack.
The reason that there are two cases is due to the details of the definition of $\mathcal{G}$. Full proof can be found in Appendix C.
∎

Our Definitions 3.2, 3.2, 3.2 and Theorem 1 are phrased with respect to a *fixed* learning task, while VC-theory takes an alternate viewpoint that tries to show guarantees on the risk (mostly sample complexity-based) for any distribution.
However, for DNNs and other modern architectures, moving beyond classical VC-theory is necessary (Zhang et al., ; Nagarajan and Kolter, ). In our case, due to the requirements of our schemes (e.g., *unremovability* and *undetectability*), it may not be feasible to achieve a formalization that applies to all distributions, as in classical VC-theory. We end this section with the following observation.

###### Fact 1 ( Transferable Attacks are disjoint from Watermarks and Adversarial Defenses ) .

For every learning task $\mathcal{L}$ and ${\epsilon}\in\big{(}0,\frac{1}{2}\big{)},T\in\mathbbm{N}$, if $\textsc{TransfAttack}\ \Big{(}\mathcal{L},{\epsilon},T,T\Big{)}$ exists, then neither $\textsc{Watermark}\left(\mathcal{L},{\epsilon},T,o(T)\right)$ nor $\textsc{Defense}\left(\mathcal{L},{\epsilon},T,T\right)$ exists.

This result follows straightforwardly from rephrasing the Definitions 3.2 to 3.2.
Indeed, a Transferable Attack is a strong notion of an attack, so it rules out a Defense.
Secondly, a Transferable Attack against defenders running in time $T$ rules out a Watermark, since it is in conflict with *uniqueness*.

###### Theorem 1 ( Main Theorem, informal ) .

###### Proof (Sketch)..

###### Fact 1 ( Transferable Attacks are disjoint from Watermarks and Adversarial Defenses ) .

## 5 Transferable Attacks are “equivalent” to Cryptography

In this section, we show that tasks with Transferable Attacks exist.
To construct such examples, we use cryptographic tools.
But importantly, the fact that we use cryptography is not coincidental.
As a second result of this section, we show that every learning task with a Transferable Attack implies a certain cryptographic primitive.
One can interpret this as showing that Transferable Attacks exist only for *complex learning tasks*, in the sense of computational complexity theory.
The two results together justify, why we can view Transferable Attacks and the existence of cryptography as “equivalent”.

### 5.1 A Cryptography-based Task with a Transferable Attack

Next, we give an example of a cryptography-based learning task with a Transferable Attack.
The following is an informal statement of the first theorem of this section.
The formal version (Theorem 7) is given in Appendix E.

###### Theorem 2 ( Transferable Attack for a Cryptography-based Learning Task, informal ) .

There exists a learning task $\mathcal{L}^{\text{crypto}}$ with a distribution $\mathcal{D}$ and hypothesis class $\mathcal{H}$, and $\mathbf{A}$ such that for all ${\epsilon}$ if $h$ is sampled from $\mathcal{H}$ then

$$ $\mathbf{A}\in\textsc{TransfAttack}\left(\left(\mathcal{D},h\right),{\epsilon}, T_{\mathbf{A}}\approx\frac{1}{{\epsilon}},T_{\mathbf{B}}=\frac{1}{{\epsilon}^{ 2}}\right).$ $$

Moreover, the learning task is such that for every ${\epsilon}$, $\approx\frac{1}{{\epsilon}}$ time (and $\approx\frac{1}{{\epsilon}}$ samples) is enough, and $\approx\frac{1}{{\epsilon}}$ samples (and in particular time) is necessary to learn a classifier of error ${\epsilon}$.

Notably, the parameters are set so that $\mathbf{A}$ (the party computing $\mathbf{x}$) has *less* time than $\mathbf{B}$ (the party computing $\mathbf{y}$), specifically $\approx 1/{\epsilon}$ compared to $1/{\epsilon}^{2}$. Furthermore, because of the encryption scheme, this is a setting where a single input maps to multiple outputs, which deviates away from the setting of classification learning tasks considered in Theorem 1.

###### Proof (Sketch)..

We start with a definition of a learning task that will be later augmented with a cryptographic tool to produce $\mathcal{L}^{\text{crypto}}$.

###### Theorem 2 ( Transferable Attack for a Cryptography-based Learning Task, informal ) .

###### Proof (Sketch)..

##### Lines on Circle Learning Task ℒ ∘ superscript ℒ \mathcal{L}^{\circ} caligraphic_L start_POSTSUPERSCRIPT ∘ end_POSTSUPERSCRIPT (Figure 5 ).

Consider a binary classification task $\mathcal{L}^{\circ}$, where the input space is defined as ${\mathcal{X}}=\{x\in\mathbb{R}^{2}\ |\ \|x\|_{2}=1\}$, representing points on the unit circle.
The hypothesis class is given by $\mathcal{H}=\{h_{w}\ |\ w\in\mathbb{R}^{2},\|w\|_{2}=1\}$, where each hypothesis is defined as $h_{w}(x):=\text{sgn}(\langle w,x\rangle)$.
The data distribution $\mathcal{D}$ is uniform on ${\mathcal{X}}$, i.e., $\mathcal{D}=U({\mathcal{X}})$.
Additionally, let $B_{w}(\alpha):=\{x\in{\mathcal{X}}\ |\ |\measuredangle(x,w)|\leq\alpha\}$ denote the set of points within an angular distance up to $\alpha$ to $w$.

##### Fully Homomorphic Encryption (FHE) (Appendix D ).

FHE (Gentry ()) allows for computation on encrypted data without decrypting it.
An FHE scheme allows to encrypt $x$ via an efficient procedure $e_{x}=\textsc{FHE.Enc}(x)$, so that later, for any algorithm $C$, it is possible to run $C$ on $x$ *homomorphically*.
More concretely, it is possible to produce an encryption of the result of running $C$ on $x$, i.e., $e_{C,x}:=\textsc{FHE.Eval}(C,e_{x})$.
Finally, there is a procedure FHE.Dec that, when given a secret key sk, can decrypt $e_{C,x}$, i.e., $y:=\textsc{FHE.Dec}(\text{sk},e_{C,x})$, where $y$ is the result of running $C$ on $x$.
Crucially, encryptions of any two messages are indistinguishable for all efficient adversaries.

##### Cryptography-based Learning Task ℒ crypto superscript ℒ crypto \mathcal{L}^{\text{crypto}} caligraphic_L start_POSTSUPERSCRIPT crypto end_POSTSUPERSCRIPT (Figure 5 ).

$\mathcal{L}^{\text{crypto}}$ is derived from Lines on Circle Learning Task $\mathcal{L}^{\circ}$.
Let $w\in{\mathcal{X}}$.
We define the distribution as an equal mixture of two parts $\mathcal{D}=\frac{1}{2}\mathcal{D}_{\textsc{Clear}}+\frac{1}{2}\mathcal{D}_{
\textsc{Enc}}$.
The first part, i.e.,$\mathcal{D}_{\textsc{Clear}}$, is equal to $x\sim U({\mathcal{X}})$ with label $y=h_{w}(x)$.
The second part, i.e.,$\mathcal{D}_{\textsc{Enc}}$, is equal to $x^{\prime}\sim U({\mathcal{X}}),y^{\prime}=h_{w}(x^{\prime}),(x,y)=(\textsc{
FHE.Enc}(x^{\prime}),\textsc{FHE.Enc}(y^{\prime}))$, which can be thought of as $\mathcal{D}_{\textsc{Clear}}$ under an encryption.
See Figure 5 for a visual representation.

Figure: Figure 5: The left part of the figure represents a Lines on Circle Learning Task $\mathcal{L}^{\circ}$ with a ground truth function denoted by $h$. On the right, we define a cryptography-augmented learning task derived from $\mathcal{L}^{\circ}$. In its distribution, a “clear” or an “encrypted” sample is observed with equal probability. Given their respective times, both $\mathbf{A}$ and $\mathbf{B}$ are able to learn a low-error classifier $h^{\mathbf{A}}$, $h^{\mathbf{B}}$ respectively, by learning only on the *clear samples*. $\mathbf{A}$ is able to compute a Transferable Attack by computing an encryption of a point close to the decision boundary of her classifier $h^{\mathbf{A}}$.

##### Transferable Attack (Figure 5 ).

Consider the following attack strategy $\mathbf{A}$.
First, $\mathbf{A}$ collects $O(1/{\epsilon})$ samples from the distribution $\mathcal{D}_{\textsc{Clear}}$ and learns a classifier $h^{\mathbf{A}}_{w^{\prime}}\in\mathcal{H}$ that is consistent with these samples.
Since the VC-dimension of $\mathcal{H}$ is 2, the hypothesis $h^{\mathbf{A}}_{w^{\prime}}$ has error at most ${\epsilon}$ with high probability.(^5^55$\mathbf{A}$ can also evaluate $h^{\mathbf{A}}_{w^{\prime}}$ homomorphically (i.e., run FHE.Eval) on $\textsc{FHE.Enc}(x)$ to obtain $\textsc{FHE.Enc}(y)$ of error ${\epsilon}$ on $\mathcal{D}_{\textsc{Enc}}$ also. This means that $\mathbf{A}$ is able to learn a low-error classifier on $\mathcal{D}$.)
Next, $\mathbf{A}$ samples a point $x_{\textsc{Bnd}}$ uniformly at random from a region close to the decision boundary of $h^{\mathbf{A}}_{w^{\prime}}$, i.e., $x_{\textsc{Bnd}}\sim U(B_{w^{\prime}}({\epsilon}))$. Finally, with equal probability, $\mathbf{A}$ sets as an attack $\mathbf{x}$ either $\textsc{FHE.Enc}(x_{\textsc{Bnd}})$ or a uniformly random point $\mathcal{D}_{\textsc{Clear}}=U({\mathcal{X}})$.
We claim that $\mathbf{x}$(^6^66In this proof sketch, we have $q=1$, i.e., $\mathbf{A}$ sends only one $x$ to $\mathbf{B}$. This is not true for the formal scheme.) satisfies the properties of a Transferable Attack.

Since $h^{\mathbf{A}}_{w^{\prime}}$ has low error with high probability, $x_{\textsc{Bnd}}$ is a uniformly random point from an arc containing the boundary of $h_{w}$ (see Figure 5).
The running time of $\mathbf{B}$ is upper-bounded by $1/{\epsilon}^{2}$, meaning it can only learn a classifier with error $\gtrapprox 10{\epsilon}^{2}$ (see Lemma 3 for details).
$\mathbf{B}$’s can only learn (Lemma 3) a classifier of error, $\gtrapprox 10{\epsilon}^{2}$.
Taking these two facts together, we expect $\mathbf{B}$ to misclassify $x^{\prime}$ with probability
$\approx\frac{1}{2}\cdot\frac{10{\epsilon}^{2}}{{\epsilon}}=5{\epsilon}>2{
\epsilon},$
where the factor $\frac{1}{2}$ takes into account that we send an encrypted sample only half of the time.
This implies *transferability*.

Note that $\mathbf{x}$ is encrypted with the same probability as in the original distribution because we send $\textsc{FHE.Enc}(x_{\textsc{Bnd}})$ and a uniformly random $\mathbf{x}\sim\mathcal{D}_{\textsc{Clear}}=U({\mathcal{X}})$ with equal probability.
Crucially, $\textsc{FHE.Enc}(x_{\textsc{Bnd}})$ is indistinguishable, for efficient adversaries, from $\textsc{FHE.Enc}(x)$ for any other $x\in{\mathcal{X}}$.
This follows from the security of the FHE scheme.
Consequently, *undetectability* holds.
∎

###### Note 1 .

We want to emphasize that it is crucial (for our construction) that the distribution has both an encrypted ($\mathcal{D}_{\textsc{Enc}}$) and an unencrypted part ($\mathcal{D}_{\textsc{Clear}}$).
If there was no $\mathcal{D}_{\textsc{Clear}}$, then $\mathbf{A}$ would not be able to generate $\textsc{FHE.Enc}(x_{\textsc{Bnd}})$.
The properties of the FHE would allow $\mathbf{A}$ to learn a low-error classifier $h^{\mathbf{A}}_{w^{\prime}}$ but only *under* the FHE encryption.
Although $\mathbf{A}$ can produce encryptions of points of her choice, she knows $w^{\prime}$ only under encryption, so she does not know which point to encrypt!
If there was no $\mathcal{D}_{\textsc{Enc}}$, then everything would happen in the clear and so $\mathbf{B}$ would be able to distinguish $x$’s that appear too close to the boundary.

###### Note 1 .

### 5.2 Tasks with Transferable Attacks imply Cryptography

In this section, we show that a Transferable Attack for any task implies a cryptographic primitive.

#### 5.2.1 EFID pairs

In cryptography, an EFID pair (Goldreich, ) is a pair of distributions $\mathcal{D}_{0},\mathcal{D}_{1}$, that are Efficiently samplable, statistically Far, and computationally Indistinguishable.
By a seminal result (Goldreich, ), we know that the existence of EFID pairs is equivalent to the existence of Pseudorandom Generators (PRG).
A PRG is an efficient algorithm which stretches short seeds into longer output sequences such that the output distribution on a uniformly chosen seed is computationally indistinguishable from a uniform distribution.
Together with what is known about PRGs, this implies that EFID pairs can be used for tasks in cryptography, including encryption and key generation (Goldreich, ).

For two time bounds $T,T^{\prime}$ we call a pair of distributions $(\mathcal{D}_{0},\mathcal{D}_{1})$ a $(T,T^{\prime})-$EFID pair if (i) $\mathcal{D}_{0},\mathcal{D}_{1}$ are samplable in time $T$, (ii) $\mathcal{D}_{0},\mathcal{D}_{1}$ are statistically far, (iii) $\mathcal{D}_{0},\mathcal{D}_{1}$ are indistinguishable for algorithms running in time $T^{\prime}$.

#### 5.2.2 Tasks with Transferable Attacks imply EFID pairs

The second result of this section shows that any task with a Transferable Attack implies the existence of a type of EFID pair.
The full proof is deferred to Appendix F.

###### Theorem 3 ( Tasks with Transferable Attacks imply EFID pairs, informal ) .

For every $\epsilon,T,T^{\prime}\in\mathbbm{N},T\leq T^{\prime}$, every learning task $\mathcal{L}$ if there exists $\mathbf{A}\in\textsc{TransfAttack}\Big{(}\mathcal{L},{\epsilon},T,T^{\prime}
\Big{)}$ and there exists a learner running in time $T$ that, with high probability, learns $f$ such that $\text{err}(f)\leq{\epsilon}$, then there exists a $(T,T^{\prime})$-EFID pair.

###### Proof (Sketch)..

Firstly, define $\mathcal{D}_{0}:=\mathcal{D}^{q}$, where $q$ is the number of samples $\mathbf{A}$ sends in the attack.
Secondly, define $\mathcal{D}_{1}$ to be the distribution of $\mathbf{x}:=\mathbf{A}$.
Note that $\mathbf{x}\in{\mathcal{X}}^{q}$.

Observe that $\mathcal{D}_{0}$ and $\mathcal{D}_{1}$ are samplable in time $T$ as $\mathbf{A}$ runs in time $T$.
Secondly, $\mathcal{D}_{0}$ and $\mathcal{D}_{1}$ are indistinguishable for $T^{\prime}$-bounded adversaries by the *undetectability* property of $\mathbf{A}$.
Finally, the fact that $\mathcal{D}_{0}$ and $\mathcal{D}_{1}$ are statistically far follows from the *transferability* property.
The following procedure, receiving input $\mathbf{x}\in{\mathcal{X}}^{q}$, is a distinguisher:

- 1.
Run the learner (the existence of which is guaranteed by the assumption of the theorem) to obtain $f$.
- 2.
$\mathbf{y}:=f(\mathbf{x})$.
- 3.
If $\text{err}(\mathbf{x},\mathbf{y})\leq 2{\epsilon}$ return 0 0, otherwise return $1$.

If $\mathbf{x}\sim\mathcal{D}_{0}=\mathcal{D}^{q}$ then $\text{err}(f)\leq{\epsilon}$ with high probability.
By Fact 2, we also know that $\text{err}(\mathbf{x},\mathbf{y})\leq 2{\epsilon}$ with high probability and so, the distinguisher will also return 0 0 with high probability.
On the other hand, if $\mathbf{x}\sim\mathcal{D}_{1}=\mathbf{A}$, we know from *transferability* of $\mathbf{A}$ that every algorithm running in time $T^{\prime}$ will return $\mathbf{y}$ such that $\text{err}(\mathbf{x},\mathbf{y})>2{\epsilon}$ with high probability.
By the assumption that $T^{\prime}\geq T$, this also implies that $\text{err}(\mathbf{x},f(\mathbf{x}))>2{\epsilon}$ with high probability.
Consequently, the distinguisher will return $1$ with high probability in this case.
This implies that the distributions are statistically far.
Summarizing, $(\mathcal{D}_{0},\mathcal{D}_{1})$ is a $(T,T^{\prime})-$EFID pair.

###### Note 2 .

We want to emphasize that our distinguisher crucially uses the error oracle in its last step.
So it is possible that it is not implementable for all time bounds!

∎

###### Theorem 3 ( Tasks with Transferable Attacks imply EFID pairs, informal ) .

###### Proof (Sketch)..

###### Note 2 .

## 6 Tasks with Watermarks and Adversarial Defenses

In this section, we give examples of tasks with Watermarks and Adversarial Defenses.
In the first example, we show that hypothesis classes of bounded VC-dimension have Adversarial Defenses against all attackers.
The second example is a learning task of bounded VC-dimension that has a Watermark, which is secure against fast adversaries.
These lemmas demonstrate why the upper bounds on the running time of $\mathbf{A}$ and $\mathbf{B}$ are crucial parameters.
Lemmas are proven in the appendix.

Figure: Figure 6: Overview of the taxonomy of learning tasks, illustrating the presence of Watermarks, Adversarial Defenses, and Transferable Attacks for learning tasks of bounded VC dimension. The axes represent the time bound for the parties in the corresponding schemes. The blue regions depict positive results, the red negative, and the gray regimes of parameters which are not of interest. See Lemma 1 and 2 for details about blue regions. The curved line represents a potential application of Theorem 1, which says that at least one of the three points should be blue.
Refer to caption: x1.png

The first lemma relies heavily on a result from Goldwasser et al. ().
The authors give a defense against arbitrary examples in a transductive model with rejections.
In contrast, our model does not allow rejections, but we do require indistinguishability.
Careful analysis leads to the following result.

###### Lemma 1 ( Adversarial Defense for bounded VC-Dimension, informal ) .

Let $d\in\mathbbm{N}$ and $\mathcal{H}$ be a binary hypothesis class on input space ${\mathcal{X}}$ of VC-dimension bounded by $d$.
There exists an algorithm $\mathbf{B}$ such that for every ${\epsilon}\in\left(0,\frac{1}{8}\right)$, $\mathcal{D}$ over ${\mathcal{X}}$ and $h\in\mathcal{H}$ we have

$$ $\mathbf{B}\in\textsc{Defense}\left((\mathcal{D},h),{\epsilon},T_{\mathbf{A}}= \infty,T_{\mathbf{B}}=\poly\left(\frac{d}{{\epsilon}}\right)\right).$ $$

Note that, by the PAC learning bound, this is a setting of parameters, where $\mathbf{B}$ has enough time to learn a classifier of error ${\epsilon}$.
By slightly abusing the notation, we write $T_{\mathbf{A}}=\infty$, meaning that the defense is secure against *all* adversaries regardless of their running time.

###### Lemma 2 ( Watermark for bounded VC-Dimension against fast Adversaries, informal ) .

For every $d\in\mathbbm{N}$ there exists a distribution $\mathcal{D}$ and a binary hypothesis class $\mathcal{H}$ of VC-dimension $d$ there exists $\mathbf{A}$ such that for any ${\epsilon}\in\left(\frac{10000}{d^{2}},\frac{1}{8}\right)$
if $h\in\mathcal{H}$ is taken uniformly at random from $\mathcal{H}$ then

$$ $\mathbf{A}\in\textsc{Watermark}\left((\mathcal{D},h),\epsilon,T_{\mathbf{A}}=O \left(\frac{d}{{\epsilon}}\right),T_{\mathbf{B}}=\frac{d}{100}\right).$ $$

Note that the setting of parameters is such that $\mathbf{A}$ can learn (with high probability) a classifier of error $\epsilon$, but $\mathbf{B}$ is *not* able to learn a low-error classifier in its allotted time $t$.
This contrasts with Lemma 5, where $\mathbf{B}$ has enough time to learn.
This is the regime of interest for Watermarks, where the scheme is expected to be secure against fast $\mathbf{B}$’s.

###### Lemma 1 ( Adversarial Defense for bounded VC-Dimension, informal ) .

###### Lemma 2 ( Watermark for bounded VC-Dimension against fast Adversaries, informal ) .

## 7 Beyond Classification

Inspired by Theorem 2, we conjecture a possibility of generalizing our results to generative learning tasks.
Instead of a ground truth function, one could consider a ground truth quality oracle $Q$, which measures the quality of every input and output pair.
This model introduces new phenomena *not* present in the case of classification.
For example, the task of *generation*, i.e., producing a high-quality output $y$ on input $x$, is decoupled from the task of *verification*, i.e., evaluating the quality of $y$ as output for $x$.
By decoupled, we mean that there is no clear formal reduction from one task to the other.
Conversely, for classification, where the space of possible outputs is small, the two tasks are equivalent.
Without going into details, this decoupling is the reason why the proof of Theorem 1 does not automatically transfer to the generative case.

This decoupling introduces new complexities, but it also suggests that considering new definitions may be beneficial.
For example, because generation and verification are equivalent for classification tasks, we allowed neither $\mathbf{A}$ nor $\mathbf{B}$ access to $h$, as it would trivialize the definitions.
However, a modification of the Definition 5 (Watermark), where access to $Q$ is given to $\mathbf{B}$ could be investigated in the generative case.
Interestingly, such a setting was considered in (Zhang et al., ), where access to $Q$ was crucial for mounting a provable attack on \sayall strong watermarks.
As we alluded to earlier, Theorem 2 can be seen as an example of a task, where generation is easy but verification is hard – the opposite to what Zhang et al. () posits.

We hope that careful formalizations of the interaction and capabilities of all parties might give insights into not only the schemes considered in this work, but also problems like weak-to-strong generalization (Burns et al., ) or scalable oversight (Brown-Cohen et al., ).

## 8 Implications for AI Security

In contrast to years of adversarial robustness research (Carlini, ), we conjecture that for discriminative learning tasks encountered in safety-critical regimes, an Adversarial Defense *will* exist in the future. Three pieces of evidence support this contrarian belief. (i) Theorem 1, (ii) in the security-critical scenarios for Watermarks, the security should hold even against strong defenders, i.e., $T_{\mathbf{B}}$ approaching $T_{\mathbf{A}}$.
In this regime, we believe an analog of Theorem 8 can be shown for Watermarks, given the similarity between the *unremovability* (Definition 3.2) and *transferability* (Definition 3.2) property.
(iii) Transferable Attacks imply cryptography (Theorem 8), which we suspect is rare in practical scenarios.

## Acknowledgement

This research was partially supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy – The Berlin Mathematics Research Center MATH+ (EXC-2046/1, project ID: 390685689).

## Appendix A Additional Methods in Related Work

This section provides an overview of the main areas relevant to our work: Watermarking techniques, adversarial defenses, and transferable attacks on Deep Neural Networks (DNNs). Each subsection outlines important contributions and the current state of research in these areas, offering additional context and details beyond those covered in the main body

### A.1 Watermarking

Watermarking techniques are crucial for protecting the intellectual property of machine learning models. These techniques can be broadly categorized based on the type of model they target. We review watermarking schemes for both discriminative and generative models, with a primary focus on discriminative models, as our work builds upon these methods.

#### A.1.1 Watermarking Schemes for Discriminative Models

Discriminative models, which are designed to categorize input data into predefined classes, have been a major focus of watermarking research. The key approaches in this domain can be divided into black-box and white-box approaches.

##### Black-Box Setting.

In the black-box setting, the model owner does not have access to the internal parameters or architecture of the model, but can query the model to observe its outputs. This setting has seen the development of several watermarking techniques, primarily through backdoor-like methods.

Adi et al. [] and Zhang et al. [] proposed frameworks that embed watermarks using specifically crafted input data (e.g., unique patterns) with predefined outcomes. These watermarks can be verified by feeding these special triggers into the model and checking for the expected outputs, thereby confirming ownership.

Another significant contribution in this domain is by Merrer et al. [], who introduced a method that employs adversarial examples to embed the backdoor. Adversarial examples are perturbed inputs that cause the model to produce specific outputs, thus serving as a watermark.

Namba and Sakuma [] further enhanced the robustness of black-box watermarking schemes by developing techniques that withstand various model modifications and attacks. These methods ensure that the watermark remains intact and detectable even when the model undergoes transformations.

Provable undetectability of backdoors was achieved in the context of classification tasks by Goldwasser et al. []. Unfortunately, it is known [Goldwasser et al., ] that some undetectable watermarks are easily removed by simple mechanisms similar to randomized smoothing [Cohen et al., ].

The popularity of black-box watermarking is due to its practical applicability, as it does not require access to the model’s internal workings. This makes it suitable for scenarios where models are deployed as APIs or services. Our framework builds upon these black-box watermarking techniques.

##### White-Box Setting.

In contrast, the white-box setting assumes that the model owner has full access to the model’s parameters and architecture, allowing for direct examination to confirm ownership. The initial methodologies for embedding watermarks into the weights of DNNs were introduced by Uchida et al. [] and Nagai et al. []. Uchida et al. [] present a framework for embedding watermarks into the model weights, which can be examined to confirm ownership.

An advancement in white-box watermarking is provided by Darvish Rouhani et al. [], who developed a technique to embed an $N$-bit ($N\geq 1$) watermark in DNNs. This technique is both data- and model-dependent, meaning the watermark is activated only when specific data inputs are fed into the model. For revealing the watermark, activations from intermediate layers are necessary in the case of white-box access, whereas only the final layer’s output is needed for black-box scenarios.

Our work does not focus on white-box watermarking techniques. Instead, we concentrate on exploring the interaction between backdoor-like watermarking techniques, adversarial defenses, and transferable attacks. Overall, watermarking through backdooring has become more popular due to its applicability in the black-box setting.

#### A.1.2 Watermarking Schemes for Generative Models

Watermarking techniques for generative models have attracted considerable attention with the advent of Large Language Models (LLMs) and other advanced generative models. This increased interest has led to a surge in research and diverse contributions in this area.

##### Backdoor-Based Watermarking for Pre-trained Language Models.

In the domain of Natural Language Processing (NLP), backdoor-based watermarks have been increasingly studied for Pre-trained Language Models (PLMs), as exemplified by works such as Gu et al. [] and Li et al. []. These methods leverage rare or common word triggers to embed watermarks, ensuring that they remain robust across downstream tasks and resilient to removal techniques like fine-tuning or pruning. While these approaches have demonstrated promising results in practical applications, they are primarily empirical, with theoretical aspects of watermarking and robustness requiring further exploration.

##### Watermarking the Output of LLMs.

Watermarking the generated text of LLMs is critical for mitigating potential harms. Significant contributions in this domain include [Kirchenbauer et al., ], who propose a watermarking framework that embeds signals into generated text that are invisible to humans but detectable algorithmically. This method promotes the use of a randomized set of “green” tokens during text generation, and detects the watermark without access to the language model API or parameters.

Kuditipudi et al. [] introduce robust distortion-free watermarks for language models. Their method ensures that the watermark does not distort the generated text, providing robustness against various text manipulations while maintaining the quality of the output.

Zhao et al. [] presented a provable, robust watermarking technique for AI-generated text. This approach offers strong theoretical guarantees for the robustness of the watermark, making it resilient against attempts to remove or alter it without significantly changing the generated text.

However, Zhang et al. [] highlight vulnerabilities in these watermarking schemes. Their work demonstrates that current watermarking techniques can be effectively broken, raising important considerations for the future development of robust and secure watermarking methods for LLMs.

##### Image Generation Models.

Various watermarking techniques have been developed for image generation models to address ethical and legal concerns. Fernandez et al. [] introduced a method combining image watermarking with Latent Diffusion Models, embedding invisible watermarks in generated images for future detection. This approach is robust against modifications such as cropping. Wen et al. [] proposed Tree-Ring Watermarking, which embeds a pattern into the initial noise vector during sampling, making the watermark robust to transformations like convolutions and rotations. Jiang et al. [] highlighted vulnerabilities in watermarking schemes, showing that human-imperceptible perturbations can evade watermark detection while maintaining visual quality. Zhao et al. [] provided a comprehensive analysis of watermarking techniques for Diffusion Models, offering a recipe for efficiently watermarking models like Stable Diffusion, either through training from scratch or fine-tuning. Additionally, Zhao et al. [] demonstrated that invisible watermarks are vulnerable to regeneration attacks that remove watermarks by adding random noise and reconstructing the image, suggesting a shift towards using semantically similar watermarks for better resilience.

##### Audio Generation Models.

Watermarking techniques for audio generators have been developed for robustness against various attacks. Erfani et al. [] introduced a spikegram-based method, embedding watermarks in high-amplitude kernels, robust against MP3 compression and other attacks while preserving quality. Liu et al. [] proposed DeAR, a deep-learning-based approach resistant to audio re-recording (AR) distortions.

### A.2 Adversarial Defenses

The field of adversarial robustness has a rich and extensive literature [Szegedy et al., , Gilmer et al., , Raghunathan et al., , Wong and Kolter, , Engstrom et al., ]. Adversarial defenses are essential for ensuring the security and reliability of machine learning models against adversarial attacks that aim to deceive them with carefully crafted inputs.

For discriminative models, there has been significant progress in developing adversarial defenses. Techniques such as adversarial training [Madry et al., ], which involves training the model on adversarial examples, have shown promise in improving robustness. Certified defenses [Raghunathan et al., ] provide provable guarantees against adversarial attacks, ensuring that the model’s predictions remain unchanged within a specified perturbation bound. Additionally, methods like randomized smoothing [Cohen et al., ] offer robustness guarantees.

A particularly relevant work for our study is [Goldwasser et al., ], which considers a different model for generating adversarial examples. This approach has significant implications for the robustness of watermarking techniques in the face of adversarial attacks.

In the context of Large Language Models (LLMs), there is a rapidly growing body of research focused on identifying adversarial examples [Zou et al., , Carlini et al., , Wen et al., ]. This research is closely related to the notion of jailbreaking [Andriushchenko et al., , Chao et al., , Mehrotra et al., , Wei et al., ], which involves manipulating models to bypass their intended constraints and protections.

### A.3 Transferable Attacks and Transductive Learning

Transferable attacks refer to adversarial examples that are effective across multiple models. Moreover, transductive learning has been explored as a means to enhance adversarial robustness, and since our Definition 3.2 captures some notion of transductive learning in the context of Transferable Attacks, we highlight significant contributions in these areas.

##### Adversarial Robustness via Transductive Learning.

Transductive learning [Gammerman et al., ] has shown promise in improving the robustness of models by utilizing both training and test data during the learning process. This approach aims to make models more resilient to adversarial perturbations encountered at test time.

One significant contribution is by Goldwasser et al. [], which explores learning guarantees in the presence of arbitrary adversarial test examples, providing a foundational framework for transductive robustness. Another notable study by Chen et al. [] formalizes transductive robustness and proposes a bilevel attack objective to challenge transductive defenses, presenting both theoretical and empirical support for transductive learning’s utility.

Additionally, Montasser et al. [] introduce a transductive learning model that adapts to perturbation complexity, achieving a robust error rate proportional to the VC dimension. The method by Wu et al. [] improves robustness by dynamically adjusting the network during runtime to mask gradients and cleanse non-robust features, validated through experimental results. Lastly, Tramer et al. [] critique the standard of adaptive attacks, demonstrating the need for specific tuning to effectively evaluate and enhance adversarial defenses.

##### Transferable Attacks on DNNs.

Transferable attacks exploit the vulnerability of models to adversarial examples that generalize across different models. For discriminative models, significant works include Liu et al. [], which investigates the transferability of adversarial examples and their effectiveness in black-box attack scenarios, [Xie et al., ], who propose input diversity techniques to enhance the transferability of adversarial examples across different models, and [Dong et al., ], which presents translation-invariant attacks to evade defenses and improve the effectiveness of transferable adversarial examples.

In the context of generative models, including large language models (LLMs) and other advanced generative architectures, relevant research is rapidly emerging, focusing on the transferability of adversarial attacks. This area is crucial as it aims to understand and mitigate the risks associated with adversarial examples in these powerful models. Notably, Zou et al. [] explored universal and transferable adversarial attacks on aligned language models, highlighting the potential vulnerabilities and the need for robust defenses in these systems.

**Table 1: Overview of properties across various watermarking schemes. The symbol ✔ denotes properties with formal guarantees or where proof is plausible, whereas ✗ indicates the absence of such guarantees. Entries marked with ✔^(E) represent properties observed empirically; these lack formal proof in the corresponding literature, suggesting that deriving such proof may present substantial challenges. The LLM watermarking schemes refer to those applied to text generated by these models.**
|  |  | Undetectability | Unremovability | Uniqueness |
| --- | --- | --- | --- | --- |
|  | Goldwasser et al. [] | ✔ | $\begin{subarray}{c}\text{robust to some}\\<br>\text{smoothing attacks}\end{subarray}$ | ✔^(E) |
| Classification | Adi et al. [], Zhang et al. [] | ✔^(E) | ✗ | ✔^(E) |
|  | Merrer et al. [] | ✔^(E) | $\begin{subarray}{c}\text{robust to fine tunning}\\<br>\text{attacks}\end{subarray}$ | ✔^(E) |
|  | Christ et al. [], Kuditipudi et al. [] | ✔ | ✗ | ✔ |
|  | Zhao et al. [] | ✗ | $\begin{subarray}{c}\text{robust to edit}\\<br>\text{distance attacks only}\end{subarray}$ | ✔ |
| LLMs | Tiffany Hsu [] | ✔^(E) | ✗ | ✔ |
|  | Kirchenbauer et al. [] | ✗ | ✗ | ✔ |

## Appendix B Formal Definitions

###### Definition 4 ( Succinct Circuits ) .

Let $C$ be a circuit of width $w$ and depth $d$.
We will denote $\text{size}(C):=w\cdot d$.
We say that $C$ is succinctly representable if there exists a circuit of size $100\log(\text{size}(C))$(^7^77Constant $100$ is chosen arbitrarily. One often considers circuits representable by $\polylog$-sized circuits. But for us, the constants play a role and this is why we formulate Definition 4.) that accepts as input $i\in[w],j,j_{1},j_{2}\in[d],g\in[O(1)]$, where $g$ represents a gate from a universal constant-sized gate set, and returns 0 0 or $1$, depending if $g$ appears in location $(i,j)$ in $C$ and if it is connected to gates in locations $(i-1,j_{1})$ and $(i-1,j_{2})$.

We are ready to state formal versions of our main definitions.

###### Definition 5 ( Watermark ) .

Let $\mathcal{L}=\left(\mathcal{D},h\right)$ be a learning task. Let $T,t,q\in\mathbbm{N},{\epsilon}\in\left(0,\frac{1}{2}\right),l,c,s\in(0,1),s<c$, where $t$ bounds the running time of $\mathbf{B}$, and $T$ the running time of $\mathbf{A}$, $q$ the number of queries, ${\epsilon}$ the risk level, $c$ probability that *uniqueness* holds, $s$ probability that *unremovability* and *undetectability* holds, $l$ the learning probability.

We say that a succinctly representable circuit $\mathbf{A}_{\textsc{Watermark}}$ of size $T$ implements a watermarking scheme for $\mathcal{L}$, denoted by $\mathbf{A}_{\textsc{Watermark}}\in\textsc{Watermark}(\mathcal{L},\epsilon,q,T,
t,l,c,s)$, if an interactive protocol in which $\mathbf{A}_{\textsc{Watermark}}$ computes $(f,\mathbf{x})$, $f:{\mathcal{X}}\rightarrow{\mathcal{Y}},\mathbf{x}\in{\mathcal{X}}^{q}$, and $\mathbf{B}$ outputs $\mathbf{y}=\mathbf{B}(f,\mathbf{x}),\mathbf{y}\in{\mathcal{Y}}^{q}$ satisfies the following

- •
Correctness ($f$ has low error).
With probability at least $l$
$\text{err}(f)\leq{\epsilon}.$
- •
Uniqueness (models trained from scratch give low-error answers).
There exists a succinctly representable circuit $\mathbf{B}$ of size $T$ such that with probability at least $c$
$\text{err}(\mathbf{x},\mathbf{y})\leq 2{\epsilon}.$
- •
Unremovability (fast $\mathbf{B}$ gives high-error answers).
For every succinctly representable circuit $\mathbf{B}$ of size at most $t$ we have that with probability at most $s$
$\text{err}(\mathbf{x},\mathbf{y})\leq 2{\epsilon}.$
- •
Undetectability (fast $\mathbf{B}$ cannot detect that they are tested).
Distributions $\mathcal{D}^{q}$ and $\mathbf{x}\sim\mathbf{A}_{\textsc{Watermark}}$ are $\frac{s}{2}$-indistinguishable for a class of succinctly representable circuits $\mathbf{B}$ of size at most $t$.

###### Definition 6 ( Adversarial Defense ) .

Let $\mathcal{L}=\left(\mathcal{D},h\right)$ be a learning task. Let $T,t,q\in\mathbbm{N},{\epsilon}\in\left(0,\frac{1}{2}\right),l,c,s\in(0,1),s<c$, where $t$ bounds the running time of $\mathbf{A}$, and $T$ the running time of $\mathbf{B}$, $q$ the number of queries, ${\epsilon}$ the error parameter, $c$ the completeness, $s$ the soundness, $l$ the learning probability.

We say that a succinctly representable circuit $\mathbf{B}_{\textsc{Defense}}$ of size $T$ implements an adversarial defense for $\mathcal{L}$, denoted by
$\mathbf{B}_{\textsc{Defense}}\in\textsc{Defense}(\mathcal{L},\epsilon,q,t,T,l,
c,s)$, if an interactive protocol in which $\mathbf{B}_{\textsc{Defense}}$ computes $f:{\mathcal{X}}\rightarrow{\mathcal{Y}}$, $\mathbf{A}$ replies with $\mathbf{x}=\mathbf{A}(f),\mathbf{x}\in{\mathcal{X}}^{q}$, and $\mathbf{B}_{\textsc{Defense}}$ outputs $b=\mathbf{B}_{\textsc{Defense}}(f,\mathbf{x}),b\in{\{0,1\}}$ satisfies the following.

- •
Correctness ($f$ has low error).
With probability at least $l$
$\text{err}(f)\leq{\epsilon}.$
- •
Completeness (if $\mathbf{x}$ came from the right distribution $\mathbf{B}_{\textsc{Defense}}$ does not signal it is attacked).
When $\mathbf{x}\sim\mathcal{D}^{q}$ then with probability at least $c$
$b=0.$
- •
Soundness (fast attacks creating $\mathbf{x}$ on which $f$ makes mistakes are detected). For every succinctly representable circuit $\mathbf{A}$ of size at most $t$ we have that with probability at most $s$,
$\text{err}(\mathbf{x},f(\mathbf{x}))>7{\epsilon}\ \text{and}\ b=0.$

###### Definition 7 ( Transferable Attack ) .

Let $\mathcal{L}=\left(\mathcal{D},h\right)$ be a learning task. Let $T,t,q\in\mathbbm{N},{\epsilon}\in\left(0,\frac{1}{2}\right),c,s\in(0,1)$, where $T$ bounds the running time of $\mathbf{A}$ and $\mathbf{B}$, $q$ the number of queries, ${\epsilon}$ the error parameter, $c$ the *transferability* probability, $s$ the *undetectability* probability.

We say that a succinctly representable circuit $\mathbf{A}$ running in time $T$ is a transferable adversarial attack, denoted by $\mathbf{A}_{\textsc{TransfAttack}}\in\textsc{TransfAttack}(\mathcal{L},
\epsilon,q,T,t,c,s)$, if an interactive protocol in which $\mathbf{A}_{\textsc{TransfAttack}}$ computes $\mathbf{x}\in{\mathcal{X}}^{q}$, and $\mathbf{B}$ outputs $\mathbf{y}=\mathbf{B}(\mathbf{x}),\mathbf{y}\in{\mathcal{Y}}^{q}$ satisfies the following.

- •
Transferability (fast provers return high error answers).
For every succinctly representable circuit $\mathbf{B}$ of size at most $t$ we have that with probability at least $c$
$\text{err}(\mathbf{x},\mathbf{y})>2{\epsilon}.$
- •
Undetectability (fast provers cannot detect that they are tested).
Distributions $\mathbf{x}\sim\mathcal{D}^{q}$ and $\mathbf{x}:=\mathbf{A}_{\textsc{TransfAttack}}$ are $\frac{s}{2}$-indistinguishable for a class of succinctly representable circuits $\mathbf{B}$ of size at most $t$.

###### Definition 4 ( Succinct Circuits ) .

###### Definition 5 ( Watermark ) .

###### Definition 6 ( Adversarial Defense ) .

###### Definition 7 ( Transferable Attack ) .

## Appendix C Main Theorem

Before proving our main theorem we recall a result from Lipton and Young [] about simple strategies for large zero-sum games.

##### Game theory.

A *two-player zero-sum game* is specified by a payoff matrix $\mathcal{G}$.
$\mathcal{G}$ is an $r\times c$ matrix.
Min, the row player, chooses a probability distribution $p_{1}$ over the rows.
Max, the column player, chooses a probability distribution $p_{2}$ over the columns.
A row $i$ and a column $j$ are drawn from $p_{1}$ and $p_{2}$ and Min pays $\mathcal{G}_{ij}$ to Max.
Min tries to minimize the expected payment; Max tries to maximize it.

By the Min-Max Theorem, there exist optimal strategies for both Min and Max.
Optimal means that playing first and revealing one’s mixed strategy is not a disadvantage.
Such a pair of strategies is also known as a Nash equilibrium.
The expected payoff when both players play optimally is known as the value of the game and is denoted by $\mathcal{V}(\mathcal{G})$.

We will use the following theorem from Lipton and Young [], which says that optimal strategies can be approximated by uniform distributions over sets of pure strategies of size $O(\log(c))$.

###### Theorem 4 ( Lipton and Young [ 1994a ] ) .

Let $\mathcal{G}$ be an $r\times c$ payoff matrix for a two-player zero-sum game.
For any $\eta\in(0,1)$ and $k\geq\frac{\log(c)}{2\eta^{2}}$ there exists a multiset of pure strategies for the Min (row player) of size $k$ such that a mixed strategy $p_{1}$ that samples uniformly from this multiset satisfies

$$ $\max_{j}\sum_{i}p_{1}(i)\mathcal{G}_{ij}\leq\mathcal{V}(\mathcal{G})+\eta( \mathcal{G}_{\text{max}}-\mathcal{G}_{\text{min}}),$ $$

where $\mathcal{G}_{\text{max}},\mathcal{G}_{\text{min}}$ denote the maximum and minimum entry of $\mathcal{G}$ respectively.
The symmetric result holds for the Max player.

###### Theorem 4 ( Lipton and Young [ 1994a ] ) .

##### Succinct Representations.

Before we prove the main theorem we give a short discussion about why we consider succinctly representable circuits.
Additionally, we require that the algorithms A and B in all the schemes to be *succinctly* representable, meaning their code should be much smaller than their running time.
This requirement forbids a trivial way to circumvent learning by hard-coding ground-truth classifier in the description of the Watermark or Adversarial Defense algorithms.(^8^88It is known in certain prover-verifier games to verify classification, described by Anil et al. [], this situation leads to undesirable equilibria, which is dubbed as the “trivial verifier” failure mode.)
Additionally, the succinct representation of algorithms is also in accordance with how learning takes place in practice, for instance, consider DNNs and learning algorithms for those DNNs. The code representing gradient descent algorithms is almost always much shorter than the time required for the optimization of weights. For instance, a provable neural network model that learns succinct algorithms is described by Goel et al. [].

We are ready to prove our main theorem.

###### Theorem 5 .

For every learning task $\mathcal{L}=(\mathcal{D},h)$; and $\epsilon\in(0,\frac{1}{2})$, $T,q\in\mathbbm{N}$, such that there exists a succinctly representable circuit of size $T^{\frac{1}{2^{20}\sqrt{\log(T)}}}$ that learns $\mathcal{L}$ up to error ${\epsilon}$ with probability $1-\frac{1}{192}$, at least one of

$$ Watermark $\displaystyle\left(\mathcal{L},\epsilon,q,T,T^{\frac{1}{2^{20}\sqrt{\log(T)}}} ,l=\frac{10}{24},c=\frac{21}{24},s=\frac{19}{24}\right),$ Defense $\displaystyle\left(\mathcal{L},\epsilon,q,T^{\frac{1}{2^{20}\sqrt{\log(T)}}},2 T,l=1-\frac{1}{48},c=\frac{13}{24},s=\frac{11}{24}\right),$ TransfAttack $\displaystyle\left(\mathcal{L},\epsilon,q,T,T,c=\frac{3}{24},s=\frac{19}{24}\right)$ $$

exists.

###### Proof of Theorem 5 .

Let $\mathcal{L}=\Big{(}\mathcal{D},h\Big{)}$ be a learning task. Let $T,q,C\in\mathbbm{N},{\epsilon}\in\left(0,\frac{1}{2}\right)$.

Let $\mathfrak{Candidate}_{\mathfrak{W}}$ be a set of $T^{\frac{1}{2^{20}\sqrt{\log(T)}}}$-sized succinctly representable circuits computing $(f,\mathbf{x})$, where $f\colon{\mathcal{X}}\rightarrow{\mathcal{Y}}$.
Similarly, let $\mathfrak{Candidate}_{\mathfrak{D}}$ be a set of $T^{\frac{1}{2^{20}\sqrt{\log(T)}}}$-sized succinctly representable circuits accepting as input $(f,\mathbf{x})$ and outputting $(\mathbf{y},b)$, where $\mathbf{y}\in{\mathcal{Y}}^{q},b\in{\{0,1\}}$.
We interpret $\mathfrak{Candidate_{W}}$ as candidate algorithms for a watermark, and $\mathfrak{Candidate_{D}}$ as candidate algorithms for attacks on watermarks.

Define a zero-sum game $\mathcal{G}$ between $(\mathbf{A},\mathbf{B})\in\mathfrak{Candidate_{W}}\times\mathfrak{Candidate_{D}}$.
The payoff is given by

$$ $\displaystyle\mathcal{G}(\mathbf{A},\mathbf{B})$ $\displaystyle=\frac{1}{2}\ \mathbb{P}_{(f,\mathbf{x}):=\mathbf{A},(\mathbf{y}, b):=\mathbf{B}}\Big{[}\text{err}(f)>{\epsilon}\text{ or }\text{err}(\mathbf{x} ,\mathbf{y})\leq 2{\epsilon}\text{ or }b=1\Big{]}$ $\displaystyle+\frac{1}{2}\ \mathbb{P}_{f:=\mathbf{A},\mathbf{x}\sim\mathcal{D} ^{q},(\mathbf{y},b):=\mathbf{B}}\Big{[}\text{err}(f)>{\epsilon}\text{ or }\Big {(}\text{err}(\mathbf{x},\mathbf{y})\leq 2{\epsilon}\text{ and }b=0\Big{)}\Big {]},$ $$

where $\mathbf{A}$ tries to minimize and $\mathbf{B}$ maximize the payoff.

Applying Theorem 4 to $\mathcal{G}$ with $\eta=2^{-8}\leq\frac{1}{192}$ we get two probability distributions, $p$ over a multiset of pure strategies in $\mathfrak{Candidate_{W}}$ and $r$ over a multiset of pure strategies in $\mathfrak{Candidate_{D}}$ that lead to a $2^{-8}$-approximate Nash equilibrium.

The size $k$ of the multisets is bounded

$$ $\displaystyle k$ $\displaystyle\leq 2^{15}\log\left(|\mathfrak{Candidate_{W}}|\right)$ $\displaystyle\leq 2^{15}\log\left(2^{100\log\left(T^{\frac{1}{2^{20}\sqrt{\log (T)}}}\right)}\right)$ Because of the number of possible succinct circuits $\displaystyle\leq 2^{22}\log\left(T^{\frac{1}{2^{20}\sqrt{\log(T)}}}\right)$ $\displaystyle\leq 2^{12}\sqrt{\log\left(T\right)}.$ (1) $$

Next, observe that the mixed strategy corresponding to the distribution $p$ can be represented by a succinct circuit of size

$$ $k\cdot 100\log\left(T^{\frac{1}{2^{20}\sqrt{\log(T)}}}\right)\leq\frac{k}{2^{1 3}}\sqrt{\log(T)},$ (2) $$

because we can create a circuit that is a collection of $k$ circuits corresponding to the multiset of $p$, where each one is of size $100\log\left(T^{\frac{1}{2^{20}\sqrt{\log(T)}}}\right)$.
Combining equation (1) and equation (2) we get that the size of the circuit succinctly representing the strategy $p$ is bounded by

$$ $\displaystyle\frac{k}{2^{13}}\sqrt{\log(T)}$ $\displaystyle\leq 2^{12}\sqrt{\log\left(T\right)}\cdot\frac{1}{2^{13}}\sqrt{ \log(T)}$ $\displaystyle\leq\log(T).$ $$

This implies that $p$ can be implemented by a $T$-sized succinctly representable circuit.
The same hold for $r$.
Let’s call the strategy corresponding to $p$, $\mathbf{A}_{\text{Nash}}$, and the strategy corresponding to $r$, $\mathbf{B}_{\text{Nash}}$.

Consider cases:

###### Theorem 5 .

###### Proof of Theorem 5 .

##### Case 𝒢 ⁢ ( 𝐀 Nash , 𝐁 Nash ) ≥ 151 192 𝒢 subscript 𝐀 Nash subscript 𝐁 Nash 151 192 \mathcal{G}(\mathbf{A}_{\textsc{Nash}},\mathbf{B}_{\textsc{Nash}})\geq\frac{15%
1}{192} caligraphic_G ( bold_A start_POSTSUBSCRIPT Nash end_POSTSUBSCRIPT , bold_B start_POSTSUBSCRIPT Nash end_POSTSUBSCRIPT ) ≥ divide start_ARG 151 end_ARG start_ARG 192 end_ARG .

Define $\mathbf{B}_{\textsc{Defense}}$ to work as follows:

- 1.
Simulate $f:=\mathbf{L}$, where $\mathbf{L}$ is a succinctly representable circuit of size $T^{\frac{1}{2^{20}\sqrt{\log(T)}}}$, such that
$\mathbb{P}\Big{[}\text{err}(f)\leq{\epsilon}\Big{]}\geq 1-\frac{1}{192}.$
- 2.
Send $f$ to $\mathbf{A}$.
- 3.
Receive $\mathbf{x}$ from $\mathbf{A}$.
- 4.
Simulate $(\mathbf{y},b):=\mathbf{B}_{\textsc{Nash}}(f,\mathbf{x})$.
- 5.
Return $b^{\prime}=1$ if $b=1$ or $d(f(\mathbf{x}),\mathbf{y})>3{\epsilon}q$ and $b^{\prime}=0$ otherwise,

where $d(\cdot,\cdot)$ is the Hamming distance.
Note that $\mathbf{B}_{\textsc{Defense}}$ runs in time $2T$ and not $T$ because it first simulates $\mathbf{L}$ and then simulates $\mathbf{B}_{\textsc{Nash}}$.

We claim that

$$ $\mathbf{B}_{\textsc{Defense}}\in\textsc{Defense}\left(\mathcal{L},\epsilon,q,T ^{\frac{1}{2^{20}\sqrt{\log(T)}}},2T,l=1-\frac{1}{48},c=\frac{13}{24},s=\frac{ 11}{24}\right).$ (3) $$

Assume towards contradiction that completeness or soundness of $\mathbf{B}_{\textsc{Defense}}$ as defined in Definition 6 does not hold.

If completeness of $\mathbf{B}_{\textsc{Defense}}$ does not hold, then

$$ $\mathbb{P}_{\mathbf{x}\sim\mathcal{D}^{q}}\Big{[}b^{\prime}=0\Big{]}<\frac{13} {24}.$ (4) $$

Let us compute the payoff of $\mathbf{A}$, which first runs $f:=\mathbf{L}$ and sets $\mathbf{x}\sim\mathcal{D}^{q}$, in the game $\mathcal{G}$, when playing against $\mathbf{B}_{\textsc{Nash}}$

$$ $\displaystyle\mathcal{G}(\mathbf{A},\mathbf{B}_{\textsc{Nash}})$ $\displaystyle=\frac{1}{2}\mathbb{P}_{(f,\mathbf{x}):=\mathbf{A}}\Big{[}\text{ err}(f)>{\epsilon}\text{ or }\text{err}(\mathbf{x},\mathbf{y})\leq 2{\epsilon} \text{ or }b^{\prime}=1\Big{]}$ $\displaystyle+\frac{1}{2}\mathbb{P}_{\begin{subarray}{c}f:=\mathbf{A},\\ \mathbf{x}\sim\mathcal{D}^{q}\end{subarray}}\Big{[}\text{err}(f)>{\epsilon} \text{ or }\Big{(}\text{err}(\mathbf{x},\mathbf{y})\leq 2{\epsilon}\text{ and }b^{\prime}=0\Big{)}\Big{]}$ $\displaystyle\leq\frac{1}{48}+\frac{1}{2}\mathbb{P}_{f:=\mathbf{L},\mathbf{x} \sim\mathcal{D}^{q}}\Big{[}\text{err}(\mathbf{x},\mathbf{y})\leq 2{\epsilon} \text{ or }b^{\prime}=1\Big{]}$ $\displaystyle+\frac{1}{2}\mathbb{P}_{f:=\mathbf{L},\mathbf{x}\sim\mathcal{D}^{ q}}\Big{[}\text{err}(\mathbf{x},\mathbf{y})\leq 2{\epsilon}\text{ and }b^{ \prime}=0\Big{]}$ $\displaystyle\text{Def. of }\mathbf{A},\mathbf{B}_{\textsc{Defense}}\text{, } \mathbb{P}\Big{[}\text{err}(f)\leq{\epsilon}\Big{]}\geq\frac{191}{192}$ $\displaystyle<\frac{1}{192}+\frac{1}{2}+\frac{\frac{13}{24}}{2}$ By equation ( 4 ) $\displaystyle=\frac{149}{192}$ $\displaystyle\leq\mathcal{G}(\mathbf{A}_{\textsc{Nash}},\mathbf{B}_{\textsc{ Nash}}),\ \lightning$ $$

where the contradiction is with the properties of approximate Nash equilibria.

Assume that $\mathbf{A}$ breaks the soundness of $\mathbf{B}_{\textsc{Defense}}$, which translates to

$$ $\mathbb{P}_{\mathbf{x}:=\mathbf{A}(f)}\Big{[}\text{err}(\mathbf{x},f(\mathbf{x }))>7{\epsilon}\ \text{ and }\ b=0\ \text{ and }\ d(f(\mathbf{x}),\mathbf{y})) >3{\epsilon}q\Big{]}>\frac{11}{24}.$ (5) $$

Let $\mathbf{A}^{\prime}$ first simulate $f:=\mathbf{L}$, then runs $\mathbf{x}:=\mathbf{A}(f)$, and returns $(f,\mathbf{x})$.
We have

$$ $\displaystyle\mathcal{G}(\mathbf{A}^{\prime},\mathbf{B}_{\textsc{Nash}})$ $\displaystyle=\frac{1}{2}\ \mathbb{P}_{(f,\mathbf{x}):=\mathbf{A}^{\prime}} \Big{[}\text{err}(f)>{\epsilon}\text{ or }\text{err}(\mathbf{x},\mathbf{y}) \leq 2{\epsilon}\text{ or }b^{\prime}=1\Big{]}$ $\displaystyle+\frac{1}{2}\ \mathbb{P}_{f:=\mathbf{A}^{\prime},\mathbf{x}\sim \mathcal{D}^{q}}\Big{[}\text{err}(f)>{\epsilon}\text{ or }\Big{(}\text{err}( \mathbf{x},\mathbf{y})\leq 2{\epsilon}\text{ and }b^{\prime}=0\Big{)}\Big{]}$ $\displaystyle=\frac{1}{2}\ \mathbb{P}_{f:=\mathbf{L},\mathbf{x}=\mathbf{A}(f)} \Big{[}\text{err}(f)>{\epsilon}\text{ or }\text{err}(\mathbf{x},\mathbf{y}) \leq 2{\epsilon}\text{ or }b^{\prime}=1\Big{]}$ $\displaystyle+\frac{1}{2}\ \mathbb{P}_{f:=\mathbf{L},\mathbf{x}\sim\mathcal{D} ^{q}}\Big{[}\text{err}(f)>{\epsilon}\text{ or }\Big{(}\text{err}(\mathbf{x}, \mathbf{y})\leq 2{\epsilon}\text{ and }b^{\prime}=0\Big{)}\Big{]}$ $\displaystyle\text{By def. of }\mathbf{A}^{\prime}$ $\displaystyle<\frac{1}{2}+\frac{1-\frac{11}{24}}{2}$ By equation ( 5 ) $\displaystyle=\frac{148}{192}$ $\displaystyle\leq\mathcal{G}(\mathbf{A}_{\textsc{Nash}},\mathbf{B}_{\textsc{ Nash}}),\ \lightning$ $$

where the contradiction is with the properties of approximate Nash equilibria. Thus equation (3) holds.

##### Case 𝒢 ⁢ ( 𝐀 Nash , 𝐁 Nash ) < 151 192 𝒢 subscript 𝐀 Nash subscript 𝐁 Nash 151 192 \mathcal{G}(\mathbf{A}_{\textsc{Nash}},\mathbf{B}_{\textsc{Nash}})<\frac{151}{%
192} caligraphic_G ( bold_A start_POSTSUBSCRIPT Nash end_POSTSUBSCRIPT , bold_B start_POSTSUBSCRIPT Nash end_POSTSUBSCRIPT ) < divide start_ARG 151 end_ARG start_ARG 192 end_ARG .

Consider $\mathbf{B}$ that returns $(f(\mathbf{x}),b)$ for a uniformly random $b$.
We have

$$ $\displaystyle\mathcal{G}(\mathbf{A}_{\textsc{Nash}},\mathbf{B})\geq\Big{(}1- \mathbb{P}_{f:=\mathbf{A}_{\textsc{Nash}}}\Big{[}\text{err}(f)\leq{\epsilon} \Big{]}\Big{)}+\mathbb{P}_{f:=\mathbf{A}_{\text{Nash}}}\Big{[}\text{err}(f) \leq{\epsilon}\Big{]}\cdot\frac{1}{2},$ (6) $$

because when $\mathbf{x}\sim\mathcal{D}^{q}$ and $\text{err}(f)\leq{\epsilon}$ the probability that $\text{err}(\mathbf{x},\mathbf{y})\leq 2{\epsilon}\text{ and }b=0$ is $\frac{1}{2}$, and similarly when $\mathbf{x}:=\mathbf{A}_{\textsc{Nash}}$ then the probability that $b=1$ is equal $\frac{1}{2}$.
The properties of approximate Nash equilibria imply that
$\mathcal{G}(\mathbf{A}_{\text{Nash}},\mathbf{B})<\frac{19}{24}=\frac{152}{192}$, which by equation (6) gives $\mathbb{P}_{f:=\mathbf{A}_{\text{Nash}}}[\text{err}(f)\leq{\epsilon}]\geq\frac
{10}{24}$.
This implies that *correctness* holds for $\mathbf{A}_{\text{Nash}}$ with $l=\frac{10}{24}$.

Next, assume towards contradiction that *unremovability* of $\mathbf{A}_{\textsc{Nash}}$ does not hold, i.e., there is $\mathbf{B}$ running in time $t$ such that $\mathbb{P}\big{[}\text{err}(\mathbf{x},\mathbf{y})\leq 2{\epsilon}\big{]}>
\frac{19}{24}$.
Consider $\mathbf{B}^{\prime}$ that on input $(f,\mathbf{x})$ returns $(\mathbf{B}(f,\mathbf{x}),0)$.
Then by definition of $\mathcal{G}$, $\mathcal{G}(\mathbf{A}_{\textsc{Nash}},\mathbf{B}^{\prime})>\frac{19}{24}=
\frac{152}{192}$, which is a contradiction $\lightning$.

Next, assume towards contradiction that *undetectability* of $\mathbf{A}_{\textsc{Nash}}$ does not hold, i.e., there exists $\mathbf{B}$ such that it distinguishes $\mathbf{x}\sim\mathcal{D}^{q}$ from $\mathbf{x}:=\mathbf{A}_{\textsc{Nash}}$ with probability higher than $\frac{19}{24}$.
Consider $\mathbf{B}^{\prime}$ that on input $(f,\mathbf{x})$ returns $(f(\mathbf{x}),\mathbf{B}(f,\mathbf{x}))$.(^9^99Formally $\mathbf{B}$ receives as input $(f,\mathbf{x})$ and not only $\mathbf{x}$.)
Then by definition of $\mathcal{G}$ and properties of approximate Nash equilibria, $\mathcal{G}(\mathbf{A}_{\textsc{Nash}},\mathbf{B}^{\prime})>\frac{19}{24}=
\frac{152}{192}$, which is a contradiction $\lightning$.

There are two further subcases.
If $\mathbf{A}_{\textsc{Nash}}$ satisfies *uniqueness* then

$$ $\mathbf{A}_{\textsc{Nash}}\in\textsc{Watermark}\left(\mathcal{L},\epsilon,q,T, T^{\frac{1}{2^{20}\sqrt{\log(T)}}},l=\frac{10}{24},c=\frac{21}{24},s=\frac{19} {24}\right).$ $$

If $\mathbf{A}_{\textsc{Nash}}$ does not satisfy *uniqueness*, then, by definition, every succinctly representable circuit $\mathbf{B}$ of size $T$ satisfies $\text{err}(\mathbf{x},\mathbf{y})\leq 2{\epsilon}$ with probability at most $\frac{21}{24}$.
Consider the following $\mathbf{A}$.
It computes $(f,\mathbf{x}):=\mathbf{A}_{\text{Nash}}$ , ignores $f$ and sends $\mathbf{x}$ to $\mathbf{B}$.
By the assumption that *uniqueness* is not satisfied for $\mathbf{A}_{\textsc{Nash}}$ we have that *transferability* of Definition 3.2 holds for $\mathbf{A}$ with $c=\frac{3}{24}$.
Note that $\mathbf{B}$ in the transferable attack does not receive $f$ but it makes it no easier for it to satisfy the properties.
Note that *undetectability* still holds with the same parameter.
Thus

$$ $\mathbf{A}_{\textsc{Nash}}\in\textsc{TransfAttack}\left(\mathcal{L},\epsilon,q ,T,T,c=\frac{3}{24},s=\frac{19}{24}\right).$ $$

∎

## Appendix D Fully Homomorphic Encryption (FHE)

We include a definition of fully homomorphic encryption based on the definition from Goldwasser et al. [].
The notion of fully homomorphic encryption was first proposed by Rivest, Adleman and Dertouzos [Rivest et al., ] in 1978. The first fully homomorphic encryption scheme was proposed in a breakthrough work by Gentry [Gentry, ].
A history and recent developments on fully homomorphic encryption is surveyed in [Vaikuntanathan, ].

### D.1 Preliminaries

We say that a function $f$ is negligible in an input parameter $\lambda$, if for all $d>0$, there exists $K$ such that for all $\lambda>K$, $f(\lambda)<\lambda^{-d}$. For brevity, we write: for all sufficiently large $\lambda$, $f(\lambda)=\text{negl}(\lambda)$. We say that a function $f$ is polynomial in an input parameter $\lambda$, if there exists a polynomial $p$ such that for all $\lambda$, $f(\lambda)\leq p(\lambda)$. We write $f(\lambda)=\text{poly}(\lambda)$. A similar definition holds for $\text{polylog}(\lambda)$.
For two polynomials $p,q$, we say $p\leq q$ if for every $\lambda\in\mathbbm{N}$, $p(\lambda)\leq q(\lambda)$.

When saying that a Turing machine $\mathcal{A}$ is p.p.t. we mean that $\mathcal{A}$ is a non-uniform probabilistic polynomial-time machine.

### D.2 Definitions

###### Definition 8 ( Goldwasser et al. [ 2013 ] ) .

A homomorphic (public-key) encryption scheme FHE is a quadruple of polynomial time algorithms (FHE.KeyGen, FHE.Enc, FHE.Dec, FHE.Eval) as follows:

- •
FHE.KeyGen$(1^{\lambda})$ is a probabilistic algorithm that takes as input the security parameter $1^{\lambda}$ and outputs a public key $pk$ and a secret key $sk$.
- •
FHE.Enc$(pk,x\in\{0,1\})$ is a probabilistic algorithm that takes as input the public key $pk$ and an input bit $x$ and outputs a ciphertext $\psi$.
- •
FHE.Dec$(sk,\psi)$ is a deterministic algorithm that takes as input the secret key $sk$ and a ciphertext $\psi$ and outputs a message $x^{*}\in\{0,1\}$.
- •
FHE.Eval$(pk,C,\psi_{1},\psi_{2},\ldots,\psi_{n})$ is a deterministic algorithm that takes as input the public key $pk$, some circuit $C$ that takes $n$ bits as input and outputs one bit, as well as $n$ ciphertexts $\psi_{1},\ldots,\psi_{n}$. It outputs a ciphertext $\psi_{C}$.

Compactness: For all security parameters $\lambda$, there exists a polynomial $p(\cdot)$ such that for all input sizes $n$, for all $x_{1},\ldots,x_{n}$, for all $C$, the output length of FHE.Eval is at most $p(n)$ bits long.

###### Definition 9 ( $C$ -homomorphism Goldwasser et al. [ 2013 ] ) .

Let $C=\{C_{n}\}_{n\in\mathbb{N}}$ be a class of boolean circuits, where $C_{n}$ is a set of boolean circuits taking $n$ bits as input. A scheme FHE is $C$-homomorphic if for every polynomial $n(\cdot)$, for every sufficiently large security parameter $\lambda$, for every circuit $C\in C_{n}$, and for every input bit sequence $x_{1},\ldots,x_{n}$, where $n=n(\lambda)$,

$$ $\mathbb{P}\left[\begin{array}[]{c}(pk,sk)\leftarrow\textsc{FHE.KeyGen}(1^{ \lambda});\\ \psi_{i}\leftarrow\textsc{FHE.Enc}(pk,x_{i})\text{ for }i=1\ldots n;\\ \psi\leftarrow\textsc{FHE.Eval}(pk,C,\psi_{1},\ldots,\psi_{n}):\\ \textsc{FHE.Dec}(sk,\psi)\neq C(x_{1},\ldots,x_{n})\end{array}\right]=\text{ negl}(\lambda),$ $$

where the probability is over the coin tosses of FHE.KeyGen and FHE.Enc.

###### Definition 10 ( Fully homomorphic encryption ) .

A scheme FHE is fully homomorphic if it is homomorphic for the class of all arithmetic circuits over $\mathbb{GF}(2)$.

###### Definition 11 ( Leveled fully homomorphic encryption ) .

A leveled fully homomorphic encryption scheme is a homomorphic scheme where FHE.KeyGen receives an additional input $1^{d}$ and the resulting scheme is homomorphic for all depth-$d$ arithmetic circuits over $\mathbb{GF}(2)$.

###### Definition 12 ( IND-CPA security ) .

A scheme FHE is IND-CPA secure if for any p.p.t. adversary $\mathcal{A}$,

$$ $\displaystyle\Big{|}\ \mathbb{P}\left[(pk,sk)\leftarrow\textsc{FHE.KeyGen}(1^{ \lambda}):\mathcal{A}(pk,\textsc{FHE.Enc}(pk,0))=1\right]+$ $\displaystyle-\mathbb{P}\left[(pk,sk)\leftarrow\textsc{FHE.KeyGen}(1^{\lambda} ):\mathcal{A}(pk,\textsc{FHE.Enc}(pk,1))=1\right]\Big{|}=\text{negl}(\lambda).$ $$

We now state the result of Brakerski, Gentry, and Vaikuntanathan [Brakerski et al., ] that shows a leveled fully homomorphic encryption scheme based on a standard assumption in cryptography called Learning with Errors [Regev, ]:

###### Theorem 6 ( Fully Homomorphic Encryption, definition from Goldwasser et al. [ 2013 ] ) .

Assume that there is a constant $0<\epsilon<1$ such that for every sufficiently large $\ell$, the approximate shortest vector problem gapSVP in $\ell$ dimensions is hard to approximate to within a $2^{O(\ell^{\epsilon})}$ factor in the worst case. Then, for every $n$ and every polynomial $d=d(n)$, there is an IND-CPA secure $d$-leveled fully homomorphic encryption scheme where encrypting $n$ bits produces ciphertexts of length $\text{poly}(n,\lambda,d^{1/\epsilon})$, the size of the circuit for homomorphic evaluation of a function $f$ is $\text{size}(C_{f})\cdot\text{poly}(n,\lambda,d^{1/\epsilon})$ and its depth is $\text{depth}(C_{f})\cdot\text{poly}(\log n,\log d)$.

###### Definition 8 ( Goldwasser et al. [ 2013 ] ) .

###### Definition 9 ( C 𝐶 C italic_C -homomorphism Goldwasser et al. [ 2013 ] ) .

###### Definition 10 ( Fully homomorphic encryption ) .

###### Definition 11 ( Leveled fully homomorphic encryption ) .

###### Definition 12 ( IND-CPA security ) .

###### Theorem 6 ( Fully Homomorphic Encryption, definition from Goldwasser et al. [ 2013 ] ) .

## Appendix E Transferable Attacks exist

##### Learning Theory Preliminaries.

For the next lemma, we will consider a slight generalization of learning tasks to the case where there are many valid outputs for a given input.
This can be understood as the case of generative tasks.
We call a function $h:{\mathcal{X}}\times{\mathcal{Y}}\rightarrow\{0,1\}$ an error oracle for a learning task $(\mathcal{D},h)$ if the error of $f:{\mathcal{X}}\rightarrow{\mathcal{Y}}$ is defined as

$$ $\text{err}(f):=\mathbb{E}_{x\sim\mathcal{D}}[h(x,f(x))],$ $$

where the randomness of expectation includes the potential randomness of $f$.
We assume that all parties have access to samples $(x,y)\in{\mathcal{X}}\times{\mathcal{Y}}$, where $x\sim\mathcal{D}$ and $y\in{\mathcal{Y}}$ is some $y$ such that $h(x,y)=0$.

The following learning task will be crucial for our construction.

###### Definition 13 ( Lines on a Circle Learning Task $\mathcal{L}^{\circ}$ ) .

The input space is ${\mathcal{X}}=\{x\in\mathbb{R}^{2}\ |\ \|x\|_{2}=1\}$, and the output space ${\mathcal{Y}}=\{-1,+1\}$.
The hypothesis class is $\mathcal{H}=\{h_{w}\ |\ w\in\mathbb{R}^{2},\|w\|_{2}=1\}$, where $h_{w}(x):=\text{sgn}(\langle w,x\rangle)$.
Let $\mathcal{D}=U({\mathcal{X}})$ and $\mathcal{L}=(\mathcal{D},\mathcal{H})$.
Note that $\mathcal{H}$ has VC-dimension equal to $2$ so $\mathcal{L}$ is learnable to error ${\epsilon}$ with $O(\frac{1}{{\epsilon}})$ samples.

Moreover, define $B_{w}(\alpha):=\{x\in{\mathcal{X}}\ |\ |\measuredangle(x,w)|\leq\alpha\}$.

###### Lemma 3 ( Learning lower bound for $\mathcal{L}^{\circ}$ ) .

Let $\mathbf{L}$ be a learning algorithm for $\mathcal{L}^{\circ}$ (Definition 13) that uses $K$ samples and returns a classifier $f$.
Then

$$ $\mathbb{P}_{w\sim U({\mathcal{X}}),f\leftarrow\mathbf{L}}\Big{[}\mathbb{P}_{x \sim U({\mathcal{X}})}[f(x)\neq h_{w}(x)]\leq\frac{1}{2K}\Big{]}\leq\frac{3}{1 00}.$ $$

###### Proof.

Consider the following algorithm $\mathcal{A}$.
It first simulates $\mathbf{L}$ on $K$ samples to compute $f$.
Next, it performs a smoothing of $f$, i.e., computes

$$ $f_{\eta}(x):=\begin{cases}+1,&\text{if }\mathbb{P}_{x^{\prime}\sim U(B_{x}(2 \pi\eta))}[f(x^{\prime})=+1]>\mathbb{P}_{x^{\prime}\sim U(B_{x}(2\pi\eta))}[f( x^{\prime})=-1]\\ -1,&\text{otherwise}.\end{cases}$ $$

Note that if $\text{err}(f)\leq\eta$ for a ground truth $h_{w}$ then for every $x\in{\mathcal{X}}\setminus B_{x}(2\pi\eta)$ we have $f_{\eta}(x)=h_{w}(x)$.
This implies that $\mathcal{A}$ can be adapted to an algorithm that with probability $1$ finds $w^{\prime}$ such that $|\measuredangle(w,w^{\prime})|\leq\text{err}(f)$.

Assuming towards contradiction that the statement of the lemma does not hold it means that there is an algorithm using $K$ samples that with probability $\frac{3}{100}$ locates $w$ up to angle $\frac{1}{2K}$.

Consider any algorithm $\mathcal{A}$ using $K$ samples.
Probability that $\mathcal{A}$ does not see any sample in $B_{w}(2\pi\eta)$ is at least

$$ $\left(1-4\eta\right)^{K}\geq\left(\left(1-4\eta\right)^{\frac{1}{4\eta}}\right )^{4\eta K}\geq\left(\frac{1}{2e}\right)^{4\eta K},$ $$

which is bigger than $1-\frac{3}{100}$ if we set $\eta=\frac{1}{2K}$.
But note that if there is no sample in $B_{w}(2\pi\eta)$ then $\mathcal{A}$ cannot locate $w$ up to $\eta$ with certainty.
This proves the lemma.
∎

###### Lemma 4 ( Boosting for $\mathcal{L}^{\circ}$ ) .

Let $\eta,\nu\in(0,\frac{1}{4})$, $\mathbf{L}$ be a learning algorithm for $(\mathcal{D},\mathcal{H})$ that uses $K$ samples and outputs $f:{\mathcal{X}}\rightarrow\{-1,+1\}$ such that with probability $\delta$

$$ $\mathbb{P}_{w\sim U({\mathcal{X}}),x\sim U(B_{w}(2\pi\eta))}[f(x)\neq h_{w}(x) ]\leq\nu.$ (7) $$

Then there exists a learning algorithm $\mathbf{L}^{\prime}$ that uses $\max\left(K,\frac{9}{\eta}\right)$ samples such that with probability $\delta-\frac{1}{1000}$
returns $f^{\prime}$ such that

$$ $\mathbb{P}_{w\sim U({\mathcal{X}}),x\sim U({\mathcal{X}})}[f^{\prime}(x)\neq h _{w}(x)]\leq 4\eta\nu.$ $$

###### Proof.

Let $\mathbf{L}^{\prime}$ first draws $\max\left(K,\frac{9}{\eta}\right)$ samples $Q$ and defines $g:{\mathcal{X}}\rightarrow\{-1,+1,\perp\}$ as, $g$ maps to $-1$ the smallest continuous interval containing all samples from $Q$ with label $-1$.
Similarly $g$ maps to $+1$ the smallest continuous interval containing all samples from $Q$ with label $+1$.
The intervals are disjoined by construction.
Unmapped points are mapped to $\perp$.
Next, $\mathbf{L}^{\prime}$ simulates $\mathbf{L}$ with $K$ samples and gets a classifier $f$ that with probability $\delta$ satisfies the assumption of the lemma.
Finally, it returns

$$ $f^{\prime}(x):=\begin{cases}g(x),&\text{if $g(x)\neq\perp$}\\ f(x),&\text{otherwise}.\end{cases}$ $$

Consider $4$ arcs defined as the $2$ arcs constituting $B_{w}(2\pi\eta)$ divided into $2$ parts each by the line $\{x\in\mathbb{R}^{2}\ |\ \langle w,x\rangle=0\}$.
Let $E$ be the event that some of these intervals do not contain a sample from $Q$.
Observe that

$$ $\mathbb{P}[E]\leq 4(1-\eta)^{\frac{9}{\eta}}\leq\frac{1}{1000}.$ $$

By the union bound with probability $\delta-\frac{1}{1000}$, $f$ satisfies equation (7) and $E$ does not happen.
By definition of $f^{\prime}$ this gives the statement of the lemma.
∎

###### Theorem 7 ( Transferable Attack for a Cryptography based Learning Task ) .

There exists a polynomial $p$ such that for every polynomial $r\geq p$(^10^1010This is only a formal requirement so that the interval $(1/r(\lambda),1/p(\lambda))$ is non-empty.) and for every sufficiently large security parameter $\lambda\in\mathbbm{N}$
there exists a family of distributions $\mathbb{D}_{\lambda}=\{\mathcal{D}_{\lambda}^{k}\}_{k}$, hypothesis class of error oracles $\mathcal{H}_{\lambda}=\{h_{\lambda}^{k}\}_{k}$, distribution $\mathcal{D}_{\mathcal{L}}$ over $k$ such that the following conditions are satisfied.

- 1.
There exists $\mathbf{A}$ such that for all ${\epsilon}\in\left(\frac{1}{r(\lambda)},\frac{1}{p(\lambda)}\right)$ if $k\sim\mathcal{D}_{\mathcal{L}}$ then
$\displaystyle\mathbf{A}\in\textsc{TransfAttack}\Big{(}\left(\mathcal{D}_{
\lambda}^{k},h_{\lambda}^{k}\right),{\epsilon},q=\frac{16}{{\epsilon}},T=\frac
{10^{3}}{{\epsilon}^{1.3}},t=\frac{1}{{\epsilon}^{2}},c=1-\frac{1}{10},s=\text
{negl}(\lambda)\Big{)}.$
- 2.
There exists a learner $\mathbf{L}$ such that for every ${\epsilon}\in\left(\frac{1}{r(\lambda)},\frac{1}{p(\lambda)}\right)$, with probability $1-\frac{1}{10}$ over the choice of $k$ and the internal randomness of $\mathbf{L}$, $\mathbf{L}$ returns a classifier of error at most ${\epsilon}$.
Additionally, $\mathbf{L}$ runs in time $\frac{10^{3}}{{\epsilon}^{1.3}}$ and uses $\frac{900}{{\epsilon}}$ samples.
- 3.
For every ${\epsilon}\in\left(\frac{1}{r(\lambda)},\frac{1}{p(\lambda)}\right)$, every learner $\mathbf{L}$ using at most $\frac{1}{{\epsilon}}$ samples (and in particular time) the probability over the choice of $k$ and the internal randomness of $\mathbf{L}$ that it returns a classifier of error at most ${\epsilon}$ is smaller than $\frac{1}{10}$.

Next, we give a formal proof.

###### Proof.

The learning task is based on $\mathcal{L}^{\circ}$ from
Definition 13.

###### Definition 13 ( Lines on a Circle Learning Task ℒ ∘ superscript ℒ \mathcal{L}^{\circ} caligraphic_L start_POSTSUPERSCRIPT ∘ end_POSTSUPERSCRIPT ) .

###### Lemma 3 ( Learning lower bound for ℒ ∘ superscript ℒ \mathcal{L}^{\circ} caligraphic_L start_POSTSUPERSCRIPT ∘ end_POSTSUPERSCRIPT ) .

###### Proof.

###### Lemma 4 ( Boosting for ℒ ∘ superscript ℒ \mathcal{L}^{\circ} caligraphic_L start_POSTSUPERSCRIPT ∘ end_POSTSUPERSCRIPT ) .

###### Proof.

###### Theorem 7 ( Transferable Attack for a Cryptography based Learning Task ) .

###### Proof.

##### Setting of Parameters for FHE .

Let FHE be a fully homomorphic encryption scheme from Theorem 6.
We will use the scheme for constant leveled circuits $d=O(1)$.
Let $s(n,\lambda)$ be the polynomial bounding the size of the encryption of inputs of length $n$ with $\lambda$ security as well as bounding size of the circuit for holomorphic evaluation, which is guaranteed to exist by Theorem 6.
Let $\beta\in(0,1)$ and $p$ be a polynomial such that

$$ $s(n^{\beta},\lambda,d)\leq(n\cdot p(\lambda))^{0.1},$ (8) $$

which exist because $s$ is a polynomial.
Let $\lambda\in\mathbbm{N}$ and $n:=p^{1/\beta}(\lambda)$(^11^1111Note that this setting allows to represent points on ${\mathcal{X}}$ up to $2^{-p^{1/\beta}(\lambda)}$ precision and this precision is better than $\frac{1}{r(\lambda)}$ for every polynomial $r$ for sufficiently large $\lambda$. This implies that this precision is enough to allow for learning up to error ${\epsilon}$, because of the setting ${\epsilon}\geq\frac{1}{q(\lambda)}$.) for the length of inputs in the FHE scheme.
Observe

$$ $\displaystyle s(n,\lambda,d))$ $\displaystyle\leq\left(p(\lambda)\cdot p(\lambda)\right)^{0.1}$ By equation ( 8 ) $\displaystyle\leq\frac{1}{{\epsilon}^{0.2}}$ $\displaystyle\text{By }{\epsilon}\in\left(\frac{1}{r(\lambda)},\frac{1}{p( \lambda)}\right).$ (9) $$

##### Learning Task.

We will omit $\lambda$ from indexes of $\mathcal{D},\mathbb{D}$ and $h$ for simplicity of notation.
Let $\mathbb{D}=\{\mathcal{D}^{\text{(pk,sk)}}\}_{\text{(pk,sk)}},\mathcal{H}=\{h^{
\text{(pk,sk,w)}}\}_{\text{(pk,sk,w)}}$ indexed by valid public/secret key pairs of FHE and $w\in{\mathcal{X}}$, with ${\mathcal{X}}$ as in Definition 13.
Let $\mathcal{D}_{\mathcal{L}}$ over $(\text{pk,sk},w)$ be equal to $\textsc{FHE.KeyGen}(1^{\lambda})\times U({\mathcal{X}})$.

For a valid (pk,sk) pair we define $\mathcal{D}^{\text{(pk,sk)}}$ as the result of the following process: $x\sim\mathcal{D}=U({\mathcal{X}})$, with probability $\frac{1}{2}$ return $(0,x,\text{pk})$ and with probability $\frac{1}{2}$ return $(1,\textsc{FHE.Enc}(\text{pk},x),\text{pk})$, where the first element of the triple describes if the $x$ is encrypted or not.
$x$ is represented as a number $\in(0,1)$ using $n$ bits.(^12^1212Note that the space over which $\mathcal{D}^{\text{(pk,sk)}}$ is defined on is *not* ${\mathcal{X}}$.)

For a valid (pk,sk) pair and $w\in{\mathcal{X}}$ we define $h^{\text{(pk,sk,w)}}((b,x,\text{pk}),y)$ as a result of the following process: if $b=0$ return $\mathbbm{1}_{h_{w}(x)=y}$, otherwise let $x_{\textsc{Dec}}\leftarrow\textsc{FHE.Dec}(\text{sk},x),y_{\textsc{Dec}}
\leftarrow\textsc{FHE.Dec}(\text{sk},y)$ and if $x_{\textsc{Dec}},y_{\textsc{Dec}}\neq\perp$ (decryption is succesful) return $\mathbbm{1}_{h_{w}(x_{\textsc{Dec}})=y_{\textsc{Dec}}}$ and return $1$ otherwise.

###### Note 3 ( $\Omega(\frac{1}{{\epsilon}})$ -sample learning lower bound. ) .

Note, that by construction any learner using $K$ samples for learning task $\{\mathcal{D}^{\text{(pk,sk)}}\}_{\text{(pk,sk)}},\{h^{\text{(pk,sk,w)}}\}_{
\text{(pk,sk,w)}}$ can be transformed (potentially computationally inefficiently) into a learner using $K$ samples for the task from Defnition 13 that returns a classifier of at most the same error.
This together with a lower bound for learning from Lemma 3 proves point 3 of the lemma.

Figure: Algorithm 1 $\textsc{TransfAttack}(\mathcal{D}^{k}_{\lambda},\mathcal{H}_{\lambda},{ \epsilon},\lambda)$

###### Note 3 ( Ω ⁢ ( 1 ϵ ) Ω 1 italic-ϵ \Omega(\frac{1}{{\epsilon}}) roman_Ω ( divide start_ARG 1 end_ARG start_ARG italic_ϵ end_ARG ) -sample learning lower bound. ) .

##### Definition of 𝐀 𝐀 \mathbf{A} bold_A (Algorithm 1 ).

$\mathbf{A}$ draws $N$ samples $Q=\{((b_{i},x_{i},\text{pk}),y_{i})\}_{i\in[N]}$ for $N:=\frac{900}{{\epsilon}}$.

Next, $\mathbf{A}$ chooses a subset $Q_{\textsc{Clear}}\subseteq Q$ of samples for which $b_{i}=0$.
It trains a classifier $f_{w^{\prime}}(\cdot):=\text{sgn}(\langle w^{\prime},\cdot\rangle)$ on $Q_{\textsc{Clear}}$ by returning any $f_{w^{\prime}}$ consistent with $Q_{\textsc{Clear}}$.
This can be done in time

$$ $N\cdot n\leq\frac{900}{{\epsilon}}\cdot p^{1/\beta}(\lambda)\leq\frac{900}{{ \epsilon}^{1.1}}$ (10) $$

by keeping track of the smallest interval containing all samples in $Q_{\textsc{Clear}}$ labeled with $+1$ and then returning any $f_{w^{\prime}}$ consistent with this interval.

###### Note 4 ( $O(\frac{1}{{\epsilon}^{1.3}})$ -time learning upper bound. ) .

First note that $\mathbf{A}$ learns well, i.e., with probability at least
$1-2\left(1-\frac{{\epsilon}}{100}\right)^{\frac{900}{{\epsilon}}}\geq 1-\frac{
1}{1000}$
we have that

$$ $|\measuredangle(w,w^{\prime})|\leq\frac{2\pi{\epsilon}}{100}$ (11) $$

Moreover, $f_{w^{\prime}}(x)$ can be implemented by a circuit $C_{f_{w^{\prime}}}$ that compares $x$ with the endpoints of the interval.
This can be done by a constant leveled circuit.
Moreover $C_{f_{w^{\prime}}}$ can be evaluated with FHE.Eval in time

$$ $\text{size}(C_{f_{w^{\prime}}})s(n,\lambda,d)\leq 10n\cdot s(n,\lambda,d)\leq 1 0p^{1/\beta}(\lambda)s(n,\lambda,d)\leq\frac{10}{{\epsilon}^{0.3}},$ $$

where the last inequality follows from equation (9).
This implies that $\mathbf{A}$ can, in time $T$, return a classifier of error $\leq{\epsilon}$ for $(\mathcal{D}^{\text{(pk,sk)}},h^{\text{(pk,sk,w)}})$.
This proves point 2. of the lemma.

Next, $\mathbf{A}$ prepares $\mathbf{x}$ as follows.
It samples $q=\frac{16}{{\epsilon}}$ points $\{x^{\prime}_{i}\}_{i\in[q]}$ from ${\mathcal{X}}$ uniformly at random.
It chooses a uniformly random subset $S\subseteq[q]$.
Next, $\mathbf{A}$ generates $q-|S|$ inputs using the following process: $x_{\textsc{Bnd}}\sim U(B_{w^{\prime}}(2\pi({\epsilon}+\frac{{\epsilon}}{100})))$ ($x_{\textsc{Bnd}}$ is close to the decision boundary of $f_{w^{\prime}}$),
return $\textsc{FHE.Enc}(\text{pk},x_{\textsc{Bnd}})$.
Call the set of $q-|S|$ points $E_{\textsc{Bnd}}$.
$\mathbf{A}$ defines:

$$ $\mathbf{x}:=\{(0,x^{\prime}_{i},\text{pk})\ |\ i\in[q]\setminus S\}\ \cup\ \{( 1,x^{\prime},\text{pk})\ |\ x^{\prime}\in E_{\textsc{Bnd}}\}.$ $$

The running time of this phase is dominated by evaluations of FHE.Eval, which takes

$$ $q\cdot s(n,\lambda,d)\leq\frac{16}{{\epsilon}}\cdot\frac{1}{{\epsilon}^{0.2}} \leq\frac{16}{{\epsilon}^{1.2}},$ (12) $$

where the first inequality follows from equation (9).
Taking the sum of equation (10) and equation (12) we get that the running time of $\mathbf{A}$ is smaller than the required $T=\nicefrac{{10^{3}}}{{{\epsilon}^{1.3}}}$.

###### Note 4 ( O ⁢ ( 1 ϵ 1.3 ) 𝑂 1 superscript italic-ϵ 1.3 O(\frac{1}{{\epsilon}^{1.3}}) italic_O ( divide start_ARG 1 end_ARG start_ARG italic_ϵ start_POSTSUPERSCRIPT 1.3 end_POSTSUPERSCRIPT end_ARG ) -time learning upper bound. ) .

##### 𝐀 𝐀 \mathbf{A} bold_A constitutes a Transferable Attack.

Now, consider $\mathbf{B}$ that runs in time $t=\frac{1}{{\epsilon}^{2}}$.
By the assumption $t\leq r(\lambda)$, which implies that the security guarantees of FHE hold for $\mathbf{B}$.

We first claim that $\mathbf{x}$ is indistinguishable from $\mathcal{D}^{\text{(pk,sk)}}$ for $\mathbf{B}$.
Observe that by construction the distribution of ratio of encrypted and not encrypted $x$’s in $\mathbf{x}$ is identical to that of $\mathcal{D}^{\text{(pk,sk)}}$.
Moreover, the distribution of unencrypted $x$’s is identical to that of $\mathcal{D}^{\text{(pk,sk)}}$ by construction.
Finally, by the IND-CPA security of FHE and the fact that the running time of $\mathbf{B}$ is bounded by $q(\lambda)$ for some polynomial $q$ we have that $\textsc{FHE.Enc}(\text{pk},x_{\textsc{Bnd}})$ is distinguishable from $x\sim{\mathcal{X}},\textsc{FHE.Enc}(\text{pk},x)$ with advantage at most $\text{negl}(\lambda)$.
Thus *undetectability* holds with near perfect soundness $s=\frac{1}{2}+\text{negl}(\lambda)$.

Next, we claim that $\mathbf{B}$ cannot return low-error answers on $\mathbf{x}$.

Assume towards contradiction that with probability $\frac{5}{100}$

$$ $\mathbb{P}_{w\sim U({\mathcal{X}}),x\sim U(B_{w}(2\pi{\epsilon}))}[f(x)\neq h_ {w}(x)]\leq 10{\epsilon}.$ (13) $$

We can apply Lemma 4 to get that there exists a learner using $t+\frac{9}{{\epsilon}}$ samples that with probability $\frac{4}{100}$ returns $f^{\prime}$ such that

$$ $\mathbb{P}_{w\sim U({\mathcal{X}}),x\sim U({\mathcal{X}})}[f^{\prime}(x)\neq h _{w}(x)]\leq 40{\epsilon}^{2}.$ (14) $$

Applying Lemma 3 to equation (14) we know that

$$ $40{\epsilon}^{2}\geq\frac{1}{2(t+\frac{9}{{\epsilon}})},$ $$

which implies

$$ $t\geq\frac{10}{{\epsilon}^{2}},$ $$

which is a contradiction with the assumed running time of $\mathbf{B}$.
Thus equation (13) does not hold and in consequence using equation (11) we have that with probability $1-\frac{6}{100}$

$$ $\mathbb{P}_{w\sim U({\mathcal{X}}),x\sim U(B_{w^{\prime}}(2\pi({\epsilon}+ \frac{{\epsilon}}{10}))}[f(x)\neq h_{w}(x)]\geq\frac{10}{14}\cdot 10{\epsilon} \geq 7{\epsilon},$ (15) $$

where crucially $x$ is sampled from $U(B_{w^{\prime}})$ and not $U(B_{w})$.
By Fact 2 we know that $|S|\geq\frac{q}{3}$ with probability at least

$$ $1-2e^{-\frac{q}{72}}=1-2e^{-\frac{1}{8{\epsilon}}}\geq 1-\frac{1}{1000}.$ $$

Another application of the Chernoff bound and the union bound we get from equation (15) that with probability at least $1-\frac{1}{10}$ we have that $\text{err}(\mathbf{x},\mathbf{y})$ is larger than $2{\epsilon}$ by the setting of $q=\frac{16}{{\epsilon}}$.

∎

###### Note 5 .

We want to emphasize that it is crucial (for our construction) that the distribution has both an encrypted and an unencrypted part.

As mentioned before, if there was no $\mathcal{D}_{\textsc{Clear}}$ then $\mathbf{A}$ would see only samples of the form

$$ $(\textsc{FHE.Enc}(x),\textsc{FHE.Enc}(y))$ $$

and would not know which of them lie close to the boundary of $h_{w}$, and so it would not be able to choose tricky samples.
$\mathbf{A}$ would be able to learn a low-error classifier, but *only* under the encryption.
More concretely, $\mathbf{A}$ would be able to homomorphically evaluate a circuit that, given a training set and a test point, learns a good classifier and classifies the test point with it.
However, it would *not* be able to, with high probability, generate $\textsc{FHE.Enc}(x)$, for $x$ close to the boundary as it would not know (in the clear) where the decision boundary is.

If there was no $\mathcal{D}_{\textsc{Enc}}$ then everything would happen in the clear and so $\mathbf{B}$ would be able to distinguish $x$’s that appear too close to the boundary.

###### Fact 2 ( Chernoff-Hoeffding ) .

Let $X_{1},\dots,X_{k}$ be independent Bernoulli variables with parameter $p$. Then for every $0<\epsilon<1$

$$ $\mathbb{P}\left[\left|\frac{1}{k}\sum_{i=1}^{k}X_{i}-p\right|>\epsilon\right] \leq 2e^{-\frac{\epsilon^{2}k}{2}}$ $$

and

$$ $\mathbb{P}\left[\frac{1}{k}\sum_{i=1}^{k}X_{i}\leq(1-{\epsilon})p\right]\leq e ^{-\frac{{\epsilon}^{2}kp}{2}}.$ $$

Also for every $\delta>0$

$$ $\mathbb{P}\left[\frac{1}{k}\sum_{i=1}^{k}X_{i}>(1+\delta)p\right]\leq e^{- \frac{\delta^{2}kp}{2+\delta}}$ $$

###### Note 5 .

###### Fact 2 ( Chernoff-Hoeffding ) .

## Appendix F Transferable Attacks imply Cryptography

### F.1 EFID pairs

The typical way in which security of EFID pairs is defined, e.g., in [Goldreich, ], is that they should be secure against all polynomial-time algorithms.
However, for the case of pseudorandom generators (PRGs), which are known are equivalent to EFIDs pairs, more granular notions of security were considered.
For instance in [Nisan, ] the existence of PRGs secure against time and space bounded adversaries was considered.
In a similar spirit we consider EFID pairs that are secure against adversaries with a fixed time bound.

###### Definition 14 ( Total Variation ) .

For two distrbutions $\mathcal{D}_{0},\mathcal{D}_{1}$ over a finite domain ${\mathcal{X}}$ we define their *total variation distance* as

$$ $\triangle(\mathcal{D}_{0},\mathcal{D}_{1}):=\sum_{x\in{\mathcal{X}}}\frac{1}{2 }|\mathcal{D}_{0}(x)-\mathcal{D}_{1}(x)|.$ $$

###### Definition 15 ( EFID pairs ) .

For parameters $\eta,\delta\in(0,1)$ we call a pair of distributions $(\mathcal{D}_{0},\mathcal{D}_{1})$ a $(T,T^{\prime},\eta,\delta)-$EFID pair if

- 1.
$\mathcal{D}_{0},\mathcal{D}_{1}$ are samplable in time $T$,
- 2.
$\triangle(\mathcal{D}_{0},\mathcal{D}_{1})\geq\eta$,
- 3.
$\mathcal{D}_{0},\mathcal{D}_{1}$ are $\delta$-indistinguishable for adversaries running in time $T^{\prime}$.

###### Definition 14 ( Total Variation ) .

###### Definition 15 ( EFID pairs ) .

### F.2 Transferable Attacks imply EFID pairs

###### Theorem 8 ( Tasks with Transferable Attacks imply EFID pairs ) .

For every $\epsilon,T,T^{\prime}\in\mathbbm{N},T\leq T^{\prime}$, every learning task $\mathcal{L}$ if there exists $\mathbf{A}\in\textsc{TransfAttack}\ \Big{(}\mathcal{L},{\epsilon},q,T,T^{
\prime},c,s\Big{)}$ and there exists a learner running in time $T$ that, with probability $p$, learns $f$ such that $\text{err}(f)\leq{\epsilon}$, then there exists a $(T,T^{\prime},\frac{1}{2}(p+c-1-e^{-\frac{\epsilon q}{3}}),\frac{s}{2})-$EFID pair.

###### Proof.

Let ${\epsilon},T,T^{\prime},q,c,s,\mathcal{L}=(\mathcal{D},h)$ and $\mathbf{A}$ be as in the assumption of the theorem.
Firstly, define $\mathcal{D}_{0}:=\mathcal{D}^{q}$, where $q$ is the number of samples $\mathbf{A}$ sends in the attack.
Secondly, define $\mathcal{D}_{1}$ to be the distribution of $\mathbf{x}:=\mathbf{A}$.
Note that $\mathbf{x}\in{\mathcal{X}}^{q}$.

Observe that $\mathcal{D}_{0},\mathcal{D}_{1}$ are samplable in time $T$ as $\mathbf{A}$ runs in time $T$.
Secondly, $\mathcal{D}_{0},\mathcal{D}_{1}$ are $\frac{s}{2}$-indistinguishable for $T^{\prime}$-bounded adversaries by *undetectability* of $\mathbf{A}$.
Finally, the fact that $\mathcal{D}_{0},\mathcal{D}_{1}$ are statistically far follows from *transferability*.
Indeed, the following procedure accepting input $\mathbf{x}\in{\mathcal{X}}^{q}$ is a distinguisher:

- 1.
Run the learner (the existence of which is guaranteed by the assumption of the theorem) to obtain $f$.
- 2.
$\mathbf{y}:=f(\mathbf{x})$.
- 3.
If $\text{err}(\mathbf{x},\mathbf{y})\leq 2{\epsilon}$ return 0 0, otherwise return $1$.

If $\mathbf{x}\sim\mathcal{D}_{0}=\mathcal{D}^{q}$ then $\text{err}(f)\leq{\epsilon}$ with probability $p$.
By Fact 2 and the union bound we also know that $\text{err}(\mathbf{x},\mathbf{y})\leq 2{\epsilon}$ with probability $p-e^{-\frac{\epsilon q}{3}}$ and so, the distinguisher will return 0 0 with probability $p-e^{-\frac{\epsilon q}{3}}$.
On the other hand, if $\mathbf{x}\sim\mathcal{D}_{1}=\mathbf{A}$ we know from *transferability* of $\mathbf{A}$ that every algorithm running in time $T^{\prime}$ will return $\mathbf{y}$ such that $\text{err}(\mathbf{x},\mathbf{y})>2{\epsilon}$ with probability at least $c$.
By the assumption that $T^{\prime}\geq T$ we know that $\text{err}(\mathbf{x},f(\mathbf{x}))>2{\epsilon}$ with probability at least $c$ also.
Consequently, the distinguisher will return $1$ with probability at least $c$ in this case.
By the properties of total variation this implies that $\triangle(\mathcal{D}_{0},\mathcal{D}_{1})\geq\frac{1}{2}(p+c-1-e^{-\frac{
\epsilon q}{3}})$
Summarizing, $(\mathcal{D}_{0},\mathcal{D}_{1})$ is a $(T,T^{\prime},\frac{1}{2}(p+c-1-e^{-\frac{\epsilon q}{3}}),\frac{s}{2})-$EFID pair.

###### Note 6 ( Setting of parameters ) .

Observe that if $p\approx 1$, i.e., it is possible to almost surely learn $f$ in time $T$ such that $\text{err}(f)\leq{\epsilon}$, $c$ is a constant, $q=\Omega(\frac{1}{{\epsilon}})$ then $\triangle(\mathcal{D}_{0},\mathcal{D}_{1})$ is a constant.

∎

###### Theorem 8 ( Tasks with Transferable Attacks imply EFID pairs ) .

###### Proof.

###### Note 6 ( Setting of parameters ) .

## Appendix G Adversarial Defenses exist

Our result is based on [Goldwasser et al., ].
Before we state and prove our result we give an overview of the learning model considered in [Goldwasser et al., ].

### G.1 Transductive Learning with Rejections.

In [Goldwasser et al., ] the authors consider a model, where a learner $\mathbf{L}$ receives a training set of labeled samples from the original distribution $(\mathbf{x}_{\mathcal{D}},\mathbf{y}_{\mathcal{D}}=h(\mathbf{x}_{\mathcal{D}})
),\mathbf{x}\sim\mathcal{D}^{N},\mathbf{y}_{\mathcal{D}}\in\{-1,+1\}^{N}$, where $h$ is the ground truth, together with a test set $\mathbf{x}_{T}\in{\mathcal{X}}^{q}$.
Next, $\mathbf{L}$ uses $(\mathbf{x}_{\mathcal{D}},\mathbf{y}_{\mathcal{D}},\mathbf{x}_{T})$ to compute $\mathbf{y}_{T}\in\{-1,+1,{\ooalign{\lower 1.29167pt\hbox{$\sqcup$}\cr\raise 1.
72218pt\hbox{$\sqcap$}}}\}^{q}$, where
$\sqcup$
$\sqcap$
represents that $\mathbf{L}$ abstains (rejects) from classifying the corresponding $x$.

Before we define when learning is successful, we will need some notation.
For $q\in\mathbbm{N},\mathbf{x}\in{\mathcal{X}}^{q},\mathbf{y}\in\{-1,+1,{\ooalign{
\lower 1.29167pt\hbox{$\sqcup$}\cr\raise 1.72218pt\hbox{$\sqcap$}}}\}^{q}$ we define

$$ $\text{err}(\mathbf{x},\mathbf{y}):=\frac{1}{q}\ \sum_{i\in[q]}\mathbbm{1}_{ \big{\{}h(x_{i})\neq y_{i},y_{i}\neq{\ooalign{\lower 0.90417pt\hbox{$\sqcup$} \cr\raise 1.20552pt\hbox{$\sqcap$}}},h(x_{i})\neq\perp\big{\}}},\ \ \ { \ooalign{\lower 1.29167pt\hbox{$\sqcup$}\cr\raise 1.72218pt\hbox{$\sqcap$}}}( \mathbf{y}):=\frac{1}{q}\Big{|}\Big{\{}i\in[q]:y_{i}={\ooalign{\lower 1.29167 pt\hbox{$\sqcup$}\cr\raise 1.72218pt\hbox{$\sqcap$}}}\Big{\}}\Big{|}\ ,$ $$

which means that we count $(x,y)\in{\mathcal{X}}\times\{-1,+1,{\ooalign{\lower 1.29167pt\hbox{$\sqcup$}
\cr\raise 1.72218pt\hbox{$\sqcap$}}}\}$ as an error if $h$ is well defined on $x$, $y$ is not an abstantion and $h(x)\neq y$.

Learning is successful if it satisfies two properties.

- •
If $\mathbf{x}_{T}\sim\mathcal{D}^{q}$ then with high probability $\text{err}(\mathbf{x}_{T},\mathbf{y}_{T})$ and ${\ooalign{\lower 1.29167pt\hbox{$\sqcup$}\cr\raise 1.72218pt\hbox{$\sqcap$}}}(
\mathbf{y}_{T})$ are small.
- •
For every $\mathbf{x}_{T}\in{\mathcal{X}}^{q}$ with high probability $\text{err}(\mathbf{x}_{T},\mathbf{y}_{T})$ is small.(^13^1313Note that, crucially, in this case ${\ooalign{\lower 1.29167pt\hbox{$\sqcup$}\cr\raise 1.72218pt\hbox{$\sqcap$}}}( \mathbf{y}_{T})$ might be very high, e.g., equal to $1$.)

The formal guarantee of a result from Goldwasser et al. [] are given in Theorem 9.
Let’s call this model Transductive Learning with Rejections (TLR).

Note the differences between TLR and our definition of Adversarial Defenses.
To compare the two models we associate the learner $\mathbf{L}$ from TLR with $\mathbf{B}$ in our setup, and the party producing $\mathbf{x}_{T}$ with $\mathbf{A}$ in our definition.
First, in TLR, $\mathbf{B}$ does not send $f$ to $\mathbf{A}$.
Secondly, and most importantly, we do not allow $\mathbf{B}$ to reply with rejections (
$\sqcup$
$\sqcap$
) but instead require that $\mathbf{B}$ can \saydistinguish that it is being tested (see soundness of Definition 6).
Finally, there are no apriori time bounds on either $\mathbf{A}$ or $\mathbf{B}$ in TLR.
The models are similar but a priori incomparable and any result for TLR needs to be carefully analyzed before being used to prove that it is an Adversarial Defense.

### G.2 Formal guarantee for Transductive Learning with Rejections (TLR)

Theorem 5.3 from Goldwasser et al. [] adapted to our notation reads.

###### Theorem 9 ( TLR guarantee [Goldwasser et al., 2020 ] ) .

For any $N\in\mathbbm{N},\epsilon\in(0,1),h\in\mathcal{H}$ and distribution $\mathcal{D}$ over ${\mathcal{X}}$:

$$ $\mathbb{P}_{\mathbf{x}_{\mathcal{D}},\mathbf{x}_{\mathcal{D}}^{\prime}\sim \mathcal{D}^{N}}\Big{[}\forall\ \mathbf{x}_{T}\in{\mathcal{X}}^{N}:\text{err}( \mathbf{x}_{T},f(\mathbf{x}_{T}))\leq{\epsilon}^{*}\land{\ooalign{\lower 1.291 67pt\hbox{$\sqcup$}\cr\raise 1.72218pt\hbox{$\sqcap$}}}\left(f\left(\mathbf{x} ^{\prime}_{\mathcal{D}}\right)\right)\leq{\epsilon}^{*}\Big{]}\geq 1-{\epsilon},$ $$

where ${\epsilon}^{*}=\sqrt{\frac{2d}{N}\log\left(2N\right)+\frac{1}{N}\log\left(
\frac{1}{{\epsilon}}\right)}$
and $f=\textsc{Rejectron}(\mathbf{x}_{\mathcal{D}},h(\mathbf{x}_{\mathcal{D}}),
\mathbf{x}_{T},{\epsilon}^{*})$, where $f:{\mathcal{X}}\rightarrow\{-1,+1,{\ooalign{\lower 1.29167pt\hbox{$\sqcup$}\cr
\raise 1.72218pt\hbox{$\sqcap$}}}\}$ and $d$ denotes the VC-dimension on $\mathcal{H}$.
Rejectron is defined in Figure 2. in Goldwasser et al. [].

Rejectron is an algorithm that accepts a labeled training set $(\mathbf{x}_{\mathcal{D}},h(\mathbf{x}_{\mathcal{D}}))$ and a test set $\mathbf{x}_{T}$ and returns a classifier $f$, which might reject some inputs.
The learning is successful if with a high probability $f$ rejects a small fraction of $\mathcal{D}^{N}$ and for every $\mathbf{x}_{T}\in{\mathcal{X}}^{N}$ the error on labeled $x$’s in $\mathbf{x}_{T}$ is small.

###### Theorem 9 ( TLR guarantee [Goldwasser et al., 2020 ] ) .

### G.3 Adversarial Defense for bounded VC-dimension

We are ready to state the main result of this section.

###### Lemma 5 ( Adversarial Defense for bounded VC-dimension ) .

Let $d\in\mathbbm{N}$ and $\mathcal{H}$ be a binary hypothesis class on input space ${\mathcal{X}}$ of VC-dimension bounded by $d$.
There exists an algorithm $\mathbf{B}$ such that for every ${\epsilon}\in\left(0,\frac{1}{8}\right)$, $\mathcal{D}$ over ${\mathcal{X}}$ and $h\in\mathcal{H}$ we have

$$ $\displaystyle\mathbf{B}\in\textsc{Defense}\Bigg{(}(\mathcal{D},h),{\epsilon},q =\frac{d\log^{2}(d)}{{\epsilon}^{3}},t=\infty,T=\poly\left(\frac{d}{{\epsilon} }\right),l=1-{\epsilon},c=1-{\epsilon},s={\epsilon}\Bigg{)}.$ $$

###### Proof.

The proof is based on an algorithm from Goldwasser et al. [].

###### Lemma 5 ( Adversarial Defense for bounded VC-dimension ) .

###### Proof.

##### Construction of 𝐁 𝐁 \mathbf{B} bold_B .

Let ${\epsilon}\in(0,1)$ and

$$ $N:=\frac{d\log^{2}(d)}{{\epsilon}^{3}}.$ $$

Let $q:=N$.
First, $\mathbf{B}$, draws $N$ labeled samples $(\mathbf{x}_{\textsc{Fresh}},h(\mathbf{x}_{\textsc{Fresh}}))$.
Next, it finds $f\in\mathcal{H}$ consistent with them and sends $f$ to $\mathbf{A}$.
Importantly this computation is the same as the first step of Rejectron.

Next, $\mathbf{B}$ receives as input $\mathbf{x}\in{\mathcal{X}}^{q}$ from $\mathbf{A}$.
$\mathbf{B}$.
Let ${\epsilon}^{*}:=\sqrt{\frac{2d}{N}\log\left(2N\right)+\frac{1}{N}\log\left(
\frac{1}{{\epsilon}}\right)}$.
Next $\mathbf{B}$ runs $f^{\prime}=\textsc{Rejectron}(\mathbf{x}_{\textsc{Fresh}},h(\mathbf{x}_{
\textsc{Fresh}}),\mathbf{x},{\epsilon}^{*})$,
where Rejectron is starting from the second step of the algorithm (Figure 2 [Goldwasser et al., ]).
Importantly, for every $x\in{\mathcal{X}}$, if $f^{\prime}(x)\neq{\ooalign{\lower 1.29167pt\hbox{$\sqcup$}\cr\raise 1.72218pt
\hbox{$\sqcap$}}}$ then $f(x)=f^{\prime}(x)$.
In words, $f^{\prime}$ is equal to $f$ everywhere where $f^{\prime}$ does not reject.

Finally $\mathbf{B}$ returns $1$ if ${\ooalign{\lower 1.29167pt\hbox{$\sqcup$}\cr\raise 1.72218pt\hbox{$\sqcap$}}}(
f^{\prime}(\mathbf{x}))>\frac{2}{3}{\epsilon}$, and returns 0 0 otherwise.

##### 𝐁 𝐁 \mathbf{B} bold_B is a Defense.

First, by the standard PAC theorem we have that with probability at least $1-{\epsilon}$, $\text{err}(f)\leq\frac{{\epsilon}}{2}$.
This means that *correctness* holds with probability $l=1-{\epsilon}$.

Note that with our setting of $N$, we have that

$$ ${\epsilon}^{*}\leq\frac{{\epsilon}}{2}.$ $$

Theorem 9 guarantees that

- •
if $\mathbf{x}\sim\mathcal{D}^{q}$ then with probability at least $1-{\epsilon}$ we have that
${\ooalign{\lower 1.29167pt\hbox{$\sqcup$}\cr\raise 1.72218pt\hbox{$\sqcap$}}}(
f^{\prime}(\mathbf{x}))\leq\frac{{\epsilon}}{2}.$
which in turn implies that with the same probability $\mathbf{B}$ returns $b=0$.
This implies that *completeness* holds with probability $1-{\epsilon}$.
- •
for every $\mathbf{x}\in{\mathcal{X}}^{q}$ with probability at least $1-{\epsilon}$ we have that
$\text{err}(\mathbf{x},f^{\prime}(\mathbf{x}))\leq\frac{{\epsilon}}{2}.$
To compute soundness we want to upper bound the probability that $\text{err}(\mathbf{x},f(\mathbf{x}))>2{\epsilon}$(^14^1414Note that we measure the error of $f$ not $f^{\prime}$.) and $b=0$.
By construction of $\mathbf{B}$ if $b=0$ then ${\ooalign{\lower 1.29167pt\hbox{$\sqcup$}\cr\raise 1.72218pt\hbox{$\sqcap$}}}(
f^{\prime}(\mathbf{x}))\leq\frac{2{\epsilon}}{3}$, which means that with probability at least $1-{\epsilon}$
$\text{err}(\mathbf{x},\mathbf{y})\leq\frac{2{\epsilon}}{3}+\frac{{\epsilon}}{2
}<2{\epsilon}\text{ or }b=1.$
This translates to *soundness* holding with $s={\epsilon}$.

Rejectron runs in polynomial time in the number of samples and makes $O(\frac{1}{{\epsilon}})$ calls to an Empirical Risk Minimizer on $\mathcal{H}$ (that we assume runs in time polynomial in $d$), which implies the promised running time.
∎

## Appendix H Watermarks exist

###### Lemma 6 ( Watermark for bounded VC-dimension against fast adversaries ) .

For every $d\in\mathbbm{N}$ there exists a distribution $\mathcal{D}$ and a binary hypothesis class $\mathcal{H}$ of VC-dimension $d$ there exists $\mathbf{A}$ such that for any ${\epsilon}\in\left(\frac{10000}{d},\frac{1}{8}\right)$
if $h\in\mathcal{H}$ is taken uniformly at random from $\mathcal{H}$ then

$$ $\displaystyle\mathbf{A}\in\textsc{Watermark}\Bigg{(}(\mathcal{D},h),\epsilon,q =O\left(\frac{1}{{\epsilon}}\right),T=O\left(\frac{d}{{\epsilon}}\right),t= \frac{d}{100},l=1-\frac{1}{100},c=1-\frac{2}{100},s=\frac{56}{100}\Bigg{)}.$ $$

###### Proof.

Let ${\mathcal{X}}=\mathbbm{N}$.
Let $\mathcal{D}$ be the uniform distribution over $[N]$ for $N=100d^{2}$.
Let $\mathcal{H}$ be the concept class of functions that have exactly $d$ $+1$’s in $[N]$.
Note $\mathcal{H}$ has VC-dimension $d$.
Let $h\in\mathcal{H}$ be the ground truth.

###### Lemma 6 ( Watermark for bounded VC-dimension against fast adversaries ) .

###### Proof.

##### Construction of 𝐀 𝐀 \mathbf{A} bold_A .

$\mathbf{A}$ works as follows.
It draws $n=O\left(\frac{d}{{\epsilon}}\right)$ samples from $\mathcal{D}$ labeled with $h$.
Let’s call them $\mathbf{x}_{\textsc{Train}}$.
Let

$$ $A:=\{x\in[N]:\mathbf{x}_{\textsc{Train}},h(x)=+1\},B:=\{x\in[N]:x\in\mathbf{x} _{\textsc{Train}},h(x)=-1\}.$ $$

$\mathbf{A}$ takes a uniformly random subset $A_{w}\subseteq A$ of size $q$.
It defines sets

$$ $\displaystyle A^{\prime}:=A\setminus A_{w},\ B^{\prime}:=B\cup A_{w}.$ $$

$\mathbf{A}$ computes $f$ consistent with the training set $\{(x,+1):x\in A^{\prime}\}\cup\{(x,-1):x\in B^{\prime}\}$.
$\mathbf{A}$ samples $S\sim\mathcal{D}^{q}$.
It defines the watermark to be $\mathbf{x}:=A_{w}$ with probability $\frac{1}{2}$ and $\mathbf{x}:=S$ with probability $\frac{1}{2}$.

$\mathbf{A}$ sends $(f,\mathbf{x})$ to $\mathbf{B}$.
$\mathbf{A}$ can be implemented in time $O\left(\frac{d}{{\epsilon}}\right)$.

##### 𝐀 𝐀 \mathbf{A} bold_A is a Watermark.

We claim that $(f,\mathbf{x})$ constitutes a watermark.

It is possible to construct a watermark of prescribed size, i.e., find a subset $A_{w}$ of a given size, only if $|A|\geq q$.
The probability that a single sample from $\mathcal{D}$ is labeled $+1$ is $\frac{d}{N}$, so by the Chernoff bound (Fact 2) $|A|,|B|>\frac{dn}{2N}\geq q$ with probability $1-\frac{1}{100}$, where we used that $n=O\left(\frac{d}{{\epsilon}}\right),N=100d^{2},q=O(\frac{1}{{\epsilon}})$.

##### Correctness.

Let $h^{\prime}(x):=h(x)$ if $x\in[N]\setminus A_{w}$ and $h^{\prime}(x):=-h(x)$ otherwise.
Note that $h^{\prime}$ has exactly $d-q$ $+1$’s in $[N]$.
By construction, $f$ is a classifier consistent with $h^{\prime}$.
By the PAC theorem we know that with probability $1-\frac{1}{100}$, $f$ has an error at most ${\epsilon}$ wrt to $h^{\prime}$ (because the hypothesis class of functions with *at most* $d$ $+1$’s has a VC dimension of $O(d)$).
$h^{\prime}$ differs from $h$ on $q$ points, so

$$ $\text{err}(f)\leq{\epsilon}+q/N=O\left({\epsilon}+\frac{1}{{\epsilon}d^{2}} \right)=O({\epsilon}).$ (16) $$

with probability $1-\frac{1}{100}$, which implies that *correctness* is satisfied with $l=1-\frac{1}{100}$.

##### Distinguishing of 𝐱 𝐱 \mathbf{x} bold_x and 𝒟 q superscript 𝒟 𝑞 \mathcal{D}^{q} caligraphic_D start_POSTSUPERSCRIPT italic_q end_POSTSUPERSCRIPT .

Note that the distribution of $A_{w}$ is the same as the distribution of a uniformly random subset of $[N]$ of size $q$ (when taking into account the randomness of the choice of $h\sim U(\mathcal{H})$).
Observe that the probability that drawing $q$ i.i.d. samples from $U([N])$ we encounter repetitions is at most

$$ $\frac{1}{N}+\frac{2}{N}+\dots+\frac{q}{N}\leq\frac{3q^{2}}{N}\leq\frac{1}{100},$ $$

because $q<\frac{d}{100}<\frac{\sqrt{N}}{10}$.
This means that $\frac{1}{100}$ is an information-theoretic upper bound on the distinguishing advantage between $\mathbf{x}=A_{w}$ and $\mathcal{D}^{q}$.

Moreover, $\mathbf{B}$ has access to at most $t$ samples and the probability that the set of samples $\mathbf{B}$ draws from $\mathcal{D}^{t}$ and $A_{w}$ have empty intersection is at least $1-\frac{1}{100}$.
It is because it is at least $(1-\frac{t}{N})^{t}\geq(1-\frac{1}{\sqrt{N}})^{\sqrt{N/10}}\geq 1-\frac{1}{100}$, where we used that $t<\frac{\sqrt{N}}{10}$.(^15^1515If the sets were not disjoint then $\mathbf{B}$ could see it as suspicious because $f$ makes mistakes on all of $A_{w}$.)

Note that by construction $f$ maps all elements of $A_{w}$ to $-1$.
The probability over the choice of $F\sim\mathcal{D}^{q}$ that $F\subseteq h^{-1}(\{-1\})$, i.e., all elements of $F$ have true label $-1$, is at least

$$ $\left(1-\frac{d}{N}\right)^{q}\geq 1-\frac{1}{100}.$ $$

The three above observations and the union bound imply that the distinguishing advantage for distinguishing $\mathbf{x}$ from $\mathcal{D}^{q}$ of $\mathbf{B}$ is at most $\frac{4}{100}$ and so the *undetectability* holds with $s=\frac{8}{100}$.

##### Unremovability.

Assume, towards contradiction with *unremovability*, that $\mathbf{B}$ can find $\mathbf{y}$ that with probability $s^{\prime}=\frac{1}{2}+\frac{6}{100}$ satisfies $\text{err}(\mathbf{x},\mathbf{y})\leq 2{\epsilon}$.
Notice, that $\text{err}(A_{w},f(A_{w}))=1$ by construction.

Consider an algorithm $\mathcal{A}$ for distinguishing $A_{w}$ from $\mathcal{D}^{q}$.
Upon receiving $(f,\mathbf{x})$ it first runs $\mathbf{y}=\mathbf{B}(f,\mathbf{x})$ and returns $1$ iff $d(\mathbf{y},f(\mathbf{x}))\geq\frac{q}{2}$.
We know that the distinguishing advantage is at most $\frac{1}{2}+\frac{4}{100}$, so

$$ $\displaystyle\frac{1}{2}\mathbb{P}_{\mathbf{x}:=A_{w}}[\mathcal{A}(f,\mathbf{x })=1]+\frac{1}{2}\mathbb{P}_{\mathbf{x}\sim\mathcal{D}^{q}}[\mathcal{A}(f, \mathbf{x})=0]\leq\frac{1}{2}+\frac{4}{100}.$ $$

But also note that

$$ $\displaystyle s^{\prime}$ $\displaystyle\leq\mathbb{P}_{\mathbf{x}\sim\mathbf{A}}[\text{err}(\mathbf{x}, \mathbf{y})\leq 2{\epsilon}]$ $\displaystyle\leq\frac{1}{2}\mathbb{P}_{\mathbf{x}:=A_{w}}[d(\mathbf{y},f( \mathbf{x}))\geq(1-2{\epsilon})q]+\frac{1}{2}\mathbb{P}_{\mathbf{x}\sim \mathcal{D}^{q}}[d(\mathbf{y},f(\mathbf{x}))\leq(2{\epsilon}+\text{err}(f))q]$ $\displaystyle\leq\frac{1}{2}\mathbb{P}_{\mathbf{x}:=A_{w}}[d(\mathbf{y},f( \mathbf{x}))\geq q/2]+\frac{1}{2}\mathbb{P}_{\mathbf{x}\sim\mathcal{D}^{q}}[d( \mathbf{y},f(\mathbf{x}))\leq q/2]+\frac{1}{100}$ $\displaystyle\leq\frac{1}{2}\mathbb{P}_{\mathbf{x}:=A_{w}}[\mathcal{A}(f, \mathbf{x})=1]+\frac{1}{2}\mathbb{P}_{\mathbf{x}\sim\mathcal{D}^{q}}[\mathcal{ A}(f,\mathbf{x})=0]+\frac{1}{100}.$ $$

Combining the two above equations we get a contradiction and thus the *unremovability* holds with $s^{\prime}=\frac{1}{2}+\frac{6}{100}$.

##### Uniqueness.

The following $\mathbf{B}$ certifies *uniqueness*.
It draws $O\left(\frac{d}{{\epsilon}}\right)$ samples from $\mathcal{D}$, let’s call them $\mathbf{x}^{\prime}_{\textsc{Train}}$ and trains $f^{\prime}$ consistent with it.
By the PAC theorem $\text{err}(f^{\prime})\leq{\epsilon}$ with probability at least $1-\frac{1}{100}$.
Next upon receiving $\mathbf{x}\in{\mathcal{X}}^{q}=[N]^{q}$ it returns $y=f^{\prime}(\mathbf{x})$.
By the fact that $\mathbf{x}$ is a random subset of $[N]$ of size $q$ by the Chernoff bound, the union bound we know that $\text{err}(\mathbf{x},\mathbf{y})=\text{err}(\mathbf{x},f^{\prime}(\mathbf{x})
)\leq 2{\epsilon}$ with probability at least $1-\frac{2}{100}$ over the choice of $h$.
This proves *uniqueness*.
∎

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 3
presentation: 2
questions: Many issues appear to stem from portraying Alice (and Bob) in an “active” or “anthropomorphic” manner, as if she dynamically performs tasks, which is inconsistent with the static nature of non-adaptive computation models like circuits. Circuits compute a fixed function based purely on their inputs.

**Formal specification of Alice and Bob**
1. What mathematical objects represent Alice and Bob? If they are fixed-size circuits, then what is the input and output space of these circuits? How are the input spaces structured, and how are random source bits, which are necessary for a circuit to output a random variable, represented within these spaces? Do they count towards the size of the circuit?
2. Circuits themselves are not formally defined anywhere in the text, so it’s unclear what the authors mean by a “size $s$ circuit” in mathematically. The closest reference is [Appendix B, Definition 4] which defines "succinct circuits" but leaves "width" and "depth" undefined. For instance, what would be the width and depth of a circuit shaped like a pyramid? In addition, are input gates counted as part of the circuit size?

**Specification of the interactive protocol (Section 3.2)**
1. How does the interactive protocol proceed? Does Alice send $(f, x_1,…, x_q)$ to Bob in a single round? Are there multiple rounds?
2. If there are no assumptions on the hypothesis class, how does Alice represent her classifier $f: \mathcal{X} \to \\{0,1\\}$? The only reasonable choice in the absence of structural assumptions on the labeling function seems to be the truth table, i.e., an element of $\\{0,1\\}^{\mathcal{X}}$.
3. It seems weird to compare Alice’s budget $T_A$ and Bob’s budget $T_B$. Within the protocol, they have different inputs and different outputs. Alice must output $(f, x_1, …, x_q)$ which could be potentially much longer than Bob’s $q$ bits to represent $(y_1,…,y_q)$.
4. In the *Transfer Attack* setting, what access does Bob have to the learning task $(D, f^*)$? Figure 4 suggests that Bob is only provided with Alice’s queries. Is it reasonable to expect Bob to achieve low error on Alice’s queries without any access to the labeling function? Moreover, what is the significance of this setup if Bob is not given any information about the learning task itself?

**Other confusions**
1. In [Section 4] (also [Appendix C, Theorem 5]), what is meant by a “learning task $(D, f^*)$ is learned by a circuit up to error $\epsilon$”? How does a circuit solve a learning task? What are its inputs? What is the output? How is the output represented? What kind of “access” does a circuit have to the learning task $(D, f^*)$?

2. If $\mathcal{X} = [N]$, where $N=2^{100}$, $D$ is uniform over $[N]$, $f^* = 1$ everywhere, then what case does the learning task $(D, f^*)$ fall into? If the circuit class size bound for both Alice and Bob are small, say less than $10$, then Alice cannot even write down a description of a single sample from $\mathcal{X}$, which makes the *Watermark* and *Adversarial Defense* schemes ill-defined. On the other hand, the learning task is technically "learnable" since a constant circuit that is not connected to any input gates and outputs $1$ realizes $f^*$.
soundness: 1
strengths: The paper attempts to formalize an intriguing relationship between two phenomena recently studied in machine learning: watermarking (i.e., planting undetectable backdoors [Goldwasser et al., 2022]) and adversarial defense [Cohen et al., 2019]. A watermark for a classifier attempts to hide specific signatures in its error patterns, while an adversarial defense attempts to maintain performance of a given untrusted classifier f across distributions that are “close to” D, which can be formalized via a weakened notion of statistical distance. Intuitively, there is tension between these two objectives, which the authors attempt to formalize as a zero sum game. Addressing these natural questions would be of wide interest to the ML community.
summary: This paper investigates the relationship between watermarks (planted in trained ML models) and adversarial defenses for noiseless classification tasks over a finite set $\mathcal{X}$. For clarity, let us focus on *binary* classification tasks. Here, a learning task (or equivalently, full data distribution) can be represented by a pair $(D, f^*)$, where $D$ is the marginal distribution over $\mathcal{X}$ and $f^*: \mathcal{X} \to \\{0,1\\}$ is the true labeling function.

For any given learning task $(D, f^*)$, consider an interactive protocol in which Alice (ML service provider) interacts with Bob (client). As a service provider, Alice trains a classifier $f: \mathcal{X} \to \\{0,1\\}$ which achieves $\epsilon$-error on $D$, and sends it to Bob. However, Alice is motivated to secretly plant a “watermark” into her trained classifier $f: \mathcal{X} \to \\{0,1\\}$ by making it susceptible to pre-designed adversarial examples. Bob, on the other hand, is motivated to neutralize any backdoors in the classifier f he received from Alice.

The opposing objectives of Alice and Bob in this framework can be formulated as a *zero-sum two-player* game. Furthermore, by modeling Alice and Bob to be circuit classes of fixed size, the pure strategy space for both Alice and Bob become finite, with explicit bounds on their cardinalities. This setup allows previous results on approximate equilibria [Lipton and Young, 1994] to be applied. Using the zero-sum two-player game formulation, the authors show that any “efficiently learnable” classification task $(D, f^*)$ falls into at least one of the following three cases:

1. **Watermarking.** There exists a watermarking scheme for Alice can compute a classifier f and sequence of adversarial (randomized) queries $x_1, …, x_q$ such that for any circuit (”Bob”) whose size is significantly smaller than hers (i.e., y computed by any such small circuit incurs $\mathrm{err}(x, y) \ge 2\epsilon$) the watermark is *unremovable* and the distribution of her queries $x_1, …, x_q$ is indistinguishable from $D$.
2. **Adversarial Defense.** There exists a watermark neutralizing (i.e., adversarial defense) scheme for Bob such that either Alice’s queries $x_1,…,x_q$ are non-adversarial (the avg loss of $f$ on $x_1, …, x_q$ is $\epsilon$-small) or the distribution of Alice’s queries $x_1, …, x_q$ and $D^q$ are distinguishable by small circuits.
3. **Transfer Attack.** A third possibility not covered by the previous two cases, which has left me confused. Please refer to the Questions section for further details.
weaknesses: The main weakness of this paper lies in the **lack of clarity and precision in its definitions and framework**, which significantly undermine the credibility of any theorems that follow. The presentation of key definitions and interactive protocols are “hand-wavy”, leaving substantial ambiguity in how the results should be interpreted and applied. This vagueness makes it difficult to assess the validity of the theoretical claims and fully appreciate the significance of the results.

While the authors give more formal specifications in the Appendix (especially, Appendix B), significant gaps still remain to be filled. In addition, the appendix should provide further technical details after the basic setup and key insights have been presented in the main text, rather than serving as a teaser for readers left confused by the unclear presentation in the body of the work. 

One significant issue is that the modeling of Alice and Bob with size-bounded circuit classes seems to fail a basic type check. In the interactive protocols, Alice and Bob face different tasks that involve different input and output spaces. For instance, in a watermarking scheme for binary classification, Alice is expected to output a representation of a classifier $f: \mathcal{X} \to \\{0,1\\}$ along with queries $ x_1,\ldots,x_q \in \mathcal{X}$ (a separate issue here is Alice's inputs are not specified and the dependence on the input domain’s cardinality doesn't appear anywhere in the quantitative results, which raises concerns). On the other hand, Bob’s inputs are sequences $x_1, \ldots, x_q$ and needs to output $y \in \\{0,1\\}^q$. Without further clarification, it’s unclear how a size $s$ circuit for Alice compares to a size $s$ circuit for Bob since even the input and output domains do not match. This is one of several issues with the paper's framework that, collectively, call into question the overall rigor and applicability of the approach. Please refer to the **Questions** section for additional issues.

Moreover, the paper **incorrectly applies previous results from cryptography**, which indicates a lack of understanding of the field. In particular, the interpretation of the results based on [Goldreich, 1990] in Section 5.2 is incorrect. Goldreich’s result applies to an *ensemble* of random variables, i.e., a *sequence* of distributions, whereas the EFID pairs the authors define in Section 5.2.1 are particular instances of distributions. Moreover, the ensembles used by Goldreich are *uniformly constructible*, meaning that there exists a single Turing machine generating random samples from X_n given the input 1^n. This contrasts with the non-uniform circuits used in this work. Given this misunderstanding, the title of Section 5,  *Transferable Attacks are “Equivalent” to Cryptography* is misleading and unnecessarily provocative. Even if Goldreich’s equivalence result could be applied here (which I find unlikely), the only concrete implication for cryptography is the existence of pseudorandom generators (PRGs), which are basic cryptographic primitives but do not represent the entire research field.

In addition, the restriction to succinct circuits feels somewhat ad hoc, seemingly added specifically to prevent Alice and Bob from hardcoding outputs. It seems likely that the approximate equilibria results (Theorem 1) would still hold without the succinctness assumption, albeit with different bounds, as the key requirement is simply that the pure strategy space remains finite with explicitly known bounds on its cardinality. This raises concerns about the integrity of the formulation, with the succinctness restriction serving more as a workaround than an integral component of the setup.

Overall, the paper would benefit greatly from prioritizing clarity over excessive generality, focusing on straightforward, concrete setups and presenting mathematical results clearly and precisely, without the informal remarks.

**Editorial comments**
- (Abstract) The phrase "almost every" learning task is misleading. Terms like “almost every” carry strong connotations in measure theory. The mere fact that a mathematical object is “irregular” or "very complex" does not imply that it is rare (e.g., from a measure-theoretic perspective). For instance, with respect to the uniform measure on [0,1], “almost every” real number in the unit interval is uncomputable.
- (Line 214) Advantage should be an equal sign.
- (Line 243) The unremovability condition, as stated, is clearly incorrect. Bob can simply respond with random y and the realized error can be 0 with small but non-zero probability. Even if this is intended as an informal simplification of the definitions in Appendix B, it should not be so obviously wrong.
- (Line 248) The term "defender" is used inconsistently alongside other terms like "player", "prover", and "Bob". It would be better to choose a single term for the recurring entities and use it consistently throughout the paper.

---

confidence: 2
contribution: 2
initial_rating: 5
presentation: 3
questions: See above.
soundness: 3
strengths: - Formalization of the relationship between backdoor-based watermarks and adversarial defenses is useful.
summary: This paper explores the relationship between backdoor-based watermarks and adversarial defenses in machine learning.  These concepts are formalized as interactive protocols between two players and proved that for almost every discriminative learning task, at least one of the two exists. The main contribution is the identification of a third, counterintuitive option: a transferable attack.  This term describes an algorithm capable of generating queries that are indistinguishable from the data distribution, yet can deceive even the most effective defenses.  The authors demonstrated the necessity of a transferable attack using homomorphic encryption and proved that any task susceptible to such an attack implies a cryptographic primitive.
weaknesses: - I take umbrage with the following claim: “Along the way to proving the main result, we identify a potential reason why this fact was not discovered earlier.”. There are multiple prior works that have investigated the trade-off between adversarial robustness and backdoors/watermarks [Weng et al,  Sun et al, Gao et al, Niu et al., Fowl et al., related work in Tao et al. is a good summary]. Although most of these papers are more empirical, this paper completely ignores an entire line of work. The paper primarily focuses on theoretical results without providing clear guidance on how these results can be translated into practical applications, and I find it difficult to assess if this paper is saying anything profound beyond what has already been discussed in the referenced papers. This is my main concern. Some suggestions:
    * (1) Include a detailed discussion of how their theoretical results relate to or extend the empirical findings in the papers you cited.
    * (2) Explicitly state what novel insights their work provides beyond the existing literature.
    * (3) Add a section on potential practical applications or implications of their theoretical results.

- In Definition 2.3. Why is the coefficient before epsilon, 7?

- The paper primarily deals with discriminative learning tasks, like classification. These tasks assume a clear relationship between input data (e.g., images) and distinct output labels (e.g., "cat" or "dog").  How can the trade-offs be captured for generative models?


[Weng et al] Weng, Cheng-Hsin, Yan-Ting Lee, and Shan-Hung Brandon Wu. "On the trade-off between adversarial and backdoor robustness." Advances in Neural Information Processing Systems 33 (2020): 11973-11983.

[Sun et al] Sun, Mingjie, Siddhant Agarwal, and J. Zico Kolter. "Poisoned classifiers are not only backdoored, they are fundamentally broken." arXiv preprint arXiv:2010.09080 (2020).

[Gao et al.] https://openreview.net/forum?id=nG4DkcHDw_

[Niu et al.] Niu, Zhenxing, et al. "Towards unified robustness against both backdoor and adversarial attacks." IEEE transactions on pattern analysis and machine intelligence (2024).

[Fowl et al.] Fowl, Liam, et al. "Adversarial examples make strong poisons." Advances in Neural Information Processing Systems 34 (2021): 30339-30351.

[Tao et al.] Tao, Lue, et al. "Better safe than sorry: Preventing delusive adversaries with adversarial training." Advances in Neural Information Processing Systems 34 (2021): 16209-16225.

---

confidence: 4
contribution: 3
initial_rating: 5
presentation: 2
questions: # Main points to be addressed

1. In section 3.1 (line 202), why do we need to define $\perp$, given the fact that $x\sim D$ and $\text{dom}(h)=\text{supp}(D)$? It seems to me that we are never really using the fact (at least in the vicinity of said definition) that $h$ is a partial function? This is causing unneeded confusion at this point. This subtlety can be separately introduced in appendix F and H, where it is actually required.


2. The definition of indistinguishability which forms a cornerstone of most of the concepts in this paper is both _informal_ and _incomplete_.  The authors define the distinguishing game, but abruptly end the definition with $\text{Pr}\left[A\text{ wins}\right]$. 
     - More concretely, the authors should explicitly state what the probability in line 215 is over, and connect the winning probability to the distinguishing game?


3. In definitions 5,6, and 7, it seems to be a straightforward requirement that $t<T$. The authors should include this in the paper.

4. Line 150 onwards: I request the authors for certain clarifications:
   - "_A major difference between our work and that of Christiano et al. (2024), is that in their approach, the attacker chooses the distribution, whereas we keep the distribution fixed._" Does this not imply that the related work proves a *stronger result*? (Note: this does not influence my score. I simply wish to understand this point in some more detail.)

   - "_A second major difference is that our main result holds for all learning tasks, while the contributions of Christiano et al. (2024) hold for restricted classes only._" Earlier, it was stated that the related work "_show(s) an equivalence between their notion of defendability (in a computationally unbounded setting) and PAC learnability._" So what do the authors mean by *restricted classes* in the work of Christiano et al. (2024)?

5. The notions of zero-sum games and Nash equilibria are absent from the main paper. This makes the proof sketch of Theorem 1 highly unreadable without jumping back and forth from appendix C, which defeats the whole purpose of having a simplified main theorem and a proof sketch in the first place.
   - Why do we need to restrict ourselves to zero-sum games instead of focusing on more general interactive protocols? Is it simply because the proof framework demands a certain kind of assumption? In this case, such a setup should be clearly mentioned as an assumption (which is still fine). 
   - The authors should also address why they have only considered Nash equilibria instead of in their setup, if not for other reasons, for the sake pedagogy alone.

6. Succinctly representable circuits are not well-motivated in Appendix C. One the referenced papers uses the notion of Stackelberg equilibrium which is different from Nash equilibrium used in this paper. There needs to be a longer/better discussion on this point.

7. It seems to be that FHE is superfluous in the proof of Theorem 2. Any reasonable encryption task seems to suffice for the purposes of the proof. 
   - On this note, I have the following question for the authors: Consider the Learning with Errors problem (Regev, 2005), where the learner has to figure out if samples are drawn from the LWE distribution or the uniform distribution. The adversary in LWE can be taken as Alice, while the learner, i.e., Bob has to figure out if the samples were drawn from uniform or the LWE distribution.

## Typos
  - Line 1599: "For instance in ? the existence of PRGs secure against time and space bounded adversaries was considered." *Missing reference*.
soundness: 2
strengths: The most important contribution of this manuscript is the proof that the notions adversarial robustness and watermarking schemes is complementary to the notion of cryptographically hard learning schemes. The authors use a lot of existing results across various fields creatively, to arrive at this result, which makes the technical part of the paper interesting in its own right.
summary: The authors provably identify the following trichotomy - for every learnable task there is an adversarial defence and/or a watermarking scheme, while for learning tasks which have associated cryptographic hardness results, there is a transferable attack.
weaknesses: My main concern with the paper is that the definitions (especially the two player games) is too carefully constructed to be readily used in conjunction with existing results from game theory, cryptography, and learning theory. There is lack of justification / discussion on several fronts, which should be addressed for the paper to be useful to the community at large.

A secondary but related weakness is the lack of a technical discussion section. A detailed overview of proof techniques section is much required. I have detailed a list of my questions in the next section.

A better related works section is also warranted. For example, there are certain confusions arising in the discussion containing the comparison with the Christiano et al. (2024) paper. See the questions section.

*Note to the authors:* Regardless of the acceptance results at this conference, I believe the authors should prepare a longer version of this manuscript and submit it to a journal like TMLR. It would be of immense value to the community.


--------
After the rebuttal period, I have decided to raise my score to indicate my positive opinion of the paper. 

*Note:* At this point I cannot justify raising the score any higher due to numerous missing definitions and discussions (detailed in the reviews by myself and other reviewers, and mostly agreed upon by the authors) that should have been included in a theoretical paper in the first place.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: Regarding the differences in definitions (for adversarially robust learning): please provide a detailed comparison between your time-limited adversary definitions and established definitions in adversarial examples literature, and highlight the key differences and justify your choices.

Related to the question above: are you claiming that any PAC learnable problem has adversarially robust learners? This seems to be a very important and technical problem, e.g., see:
https://proceedings.mlr.press/v99/montasser19a/montasser19a.pdf
https://arxiv.org/pdf/1806.01471
I guess the devil is in the details and differences in definitions, but that needs to be much more openly discussed.

Having a comparison of the definitions (yours and previous literature on adversarial examples and adversarially robust learning) partially addresses this issue, but please also make an explicit comparison with the results of the papers above (particularly, the impossibility result of the first paper and how it does not contradict yours).
soundness: 3
strengths: A formalism of the intuition behind the duality of watermarks (for models through backdoor) and adversarial robustness is interesting. 

Also, the paper realizes that formal definitions are needed for such results and takes an effort in that direction.
summary: The paper gives formal definitions of “watermarks” through backdoor (not for LLM’s output, but rather for models themselves) and “adversarial robustness” and “transferable attacks” in their own way. Meaning that the definitions do not necessarily match what is the common usual way of defining them, but the definitions make sense in their own way.

Then, the paper observes that these three notions are complementary for a “learning task”. A task is modeled using a distribution D (on instances) and a function h (to label them) and differs from the method of using a family of h (as hypothesis class). In particular, the paper shows that for each learning task, at least one of the following holds: either we can watermark models that predict that task, or that we can resist backdoor, or that transferability attacks work.

Intuitively, the main result is proved by observing that a watermark through a backdoor aims to plant a backdoor and later use specific queries to detect it (using wrong answer) and this is exactly what a defense against backdoor wants to avoid. So the two notions are rather complementary. Once the paper aims to prove this formally, they show that a third case is also possible, which in their formalism is referred to as the transferability attack.

The paper then shows that “transferability” attacks could probably exist assuming fully homomorphic encryption, and that transferability attacks *require* one-way functions (they say PRG, but that is the same as OWFs), and hence it implies secret key crypto.

Finally, the paper claims that PAC learnable families (ie., those with bounded VC dimension) always can have adversarial robustness and “watermark against fast adversaries”.
weaknesses: The new formalisms for the 3 notions of watermark, robustness and transferability need a lot more scrutiny and discussion. For example, there are limits on the time of the adversary that are needed to make these definitions non-vacuous, but these definitions are different from previously established definitions in this regard (e.g., about adversarial examples) and I see no real effort to compare them. (see my question below)


Also, due to the number of results in the main body, their proofs are deferred to the appendix, and perhaps the most exciting result (saying that bounded VC dimension means we can have adversarial robustness) is pushed to the appendix.

Meta-review: This paper derives a theoretical analysis of the relationship between backdoor-based watermarks and adversarial defenses. The authors show that all discriminative learning tasks can be categorized into one of three classes, which suggests there is an inherent security trade-off in ML applications.

Reviewers generally appreciated the technical depth of the paper and its clever use of existing techniques to derive their theoretical result. However, most reviewers also found the paper's analysis framework to be lacking in precision, leaving much of the derived theoretical result up to interpretation. The paper is also written in a way that is difficult to absorb for the general ML audience. As a result, practical implications of the paper are also unclear. After the rebuttal period, reviewers and AC discussed thoroughly and reached consensus that the paper's weaknesses currently outweigh its strengths. Thus, AC believes the paper is currently not ready for publication, but encourages the authors to taken into account reviewer suggestions and improve the paper's clarity before resubmitting to a future venue.

Decision: Reject