The Good, the Bad and the Ugly: Meta-Analysis of Watermarks, Transferable Attacks and Adversarial Defenses
Authors: Grzegorz Gluch
Berkant Turan
Sai Ganesh Nagarajan
Sebastian Pokutta
Venue: NeurIPS 2025 poster ()
Keywords: Interactive Proof Systems
Cryptography
Backdoors
Game Theory
Learning Theory
Transferable Attacks
Adversarial Robustness
Primary area: theory

Abstract: We formalize and analyze the trade-off between backdoor-based watermarks and adversarial defenses, framing it as an interactive protocol between a verifier and a prover. While previous works have primarily focused on this trade-off, our analysis extends it by identifying transferable attacks as a third, counterintuitive but necessary option. Our main result shows that for all learning tasks, at least one of the three exists: a _watermark_, an _adversarial defense_, or a _transferable attack_. By transferable attack, we refer to an efficient algorithm that generates queries indistinguishable from the data distribution and capable of fooling _all_ efficient defenders. Using cryptographic techniques, specifically fully homomorphic encryption, we construct a transferable attack and prove its necessity in this trade-off. Finally, we show that tasks of bounded VC-dimension allow adversarial defenses against all attackers, while a subclass allows watermarks secure against fast adversaries.

The Good, the Bad and the Ugly: Meta-Analysis of Watermarks, Transferable Attacks and Adversarial Defenses
Grzegorz Gluch
Berkant Turan Zuse Institute Berlin turan@zib. de
UC Berkeley g gluch@berkeley.com edu
Sai Ganesh Nagarajan University of Southern Denmark sgnagara an@imada sdu. dk
Sebastian Pokutta
Zuse Institute Berlin and TU Berlin pokuttałzib.de de
Abstract
We formalize and analyze the trade-off between bekkdoor-basse watermarks and adversarial defenses, framing prover. While previous works have primarily focused on this trade-off, our anal- ysis extends it by identifying transferable attacks as third, counterintuitive, but necessary option. Our main result shows that for all learning tasks, at least one of the three exists: watermark, an adversarial defense, or transferable attack. By transferable attack, we refer to an efficient algorithm that generates queries indistin- guishable from the data distribution and capable of fooling all efficient defenders. Using cryptographic techniques. specifically fully homomorphic encryption, we construct transferable attack and prove its necessity in this trade-off. Finally, we show that tasks of bounded VC-dimension allow adversarial defenses against all attackers, while subclass allows watermarks secure against fast adversaries.
interactive protocol between verifier and
Introduction
Backdoor attacks and adversarial robustness closely related: the former embeds hidden behaviors via subtle input changes, while the latter seeks to ensure stable predictions against worst-case input modifications. Recent works [Weng et al.) 2020 Sun al. 2020, Niu al. 2024 Fowl al.
2021 Tao et al. [224]] have empirically explored the trade-offs between adversarial robustness and backdoor attacks. Their general observation is that "models that are made be robust against certain
types of adversarial attacks may become more vulnerable to backdoor attacks."
Outside classic methods such adversarial training Madry al. 2018), which apply generally, prov- able defenses against general adversaries are known only for restricted function classes particularly when the defense focuses detecting, rather than classifying, attacks. Provided the attacks indistinguishable from the data distribution, rejection-based methods can effectively defend against arbitrarily crafted adversarial examples (beyond f--norm perturbations) Goldwasser al. (2020). Other studies show that backdoors can be planted using cryptographic schemes Goldwasser et al. 2002), making their detection computationally intractable. Conversely, standard post-hoc defenses such as randomized smoothing may inadvertently remove such backdoors Cohen et al. [2019).
Formally analyzing these trade-offs must account for the full spectrum of strategies available to attackers and defenders each with potentially different computational capacities and resources Bubeck et al. 2019). Garg et al. [2020] which presents significant challenge. Recently, Christiano et al. 2024 attempted to characterize function classes for which one can provably defend against
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

learns f
learns
learns f
x
b
Alice verifies f was stolen
Bob proves innocence
Alice verifies robustness
Bob proves defense
Alice verifies transferability
Bob proves
defendability
(b)
(c)
Watermark is an efficient algo-
An Adversarial Defense is effi-
A. Transferable Attack is effi- cient algorithm that computes queries x that look indistinguishable from the data distribution, and that fool all cf- ficient defenders.
rithm that computes a low-error clas- sifier f and set of queries x such that (fast) defenders are unable to find low-error answers y distin-
cient algorithm that computes low-
error classifier and detection
b, such that (fast) adversaries are un- able to find queries which look indistinguishable from the data dis-
guish x from the data distribution.
tribution and where is incorrect.
Figure I: Schematic overview of the interaction structure, along with short, informal versions of our definitions of (a) Watermark (Definition 3). Adversarial Defense (Definition and (c) Transferable Attack (Definition 5) with (c) tied to cryptography (see Section
backdoor attacks: they demonstrate that classes with bounded VC-dimension admit defenses, and they construct classes for which designing defense is computationally infcasible.
Finally, studying this trade-off off is crucial because backdoor attacks can also serve as watermarks in black-box settings Adi et al. (018). Zhhng et al. (2018), Namba and Sakuma [2019). Understanding their interplay informs us of the limitations and applicability both defenses and backdoor- based watermarks across different learning tasks. This paper formalizes these notions and undertakes meta-analysis of them. doing so, it led us to identify a third scheme-th transferable attack, which is an attack that is indistinguishuble from the data distribution and can fool all models trainable within given resource constraints.
1.1 Our Contributions
We study classifcation learning tasks and our main result shows that:
For every learning task, at least one of the three must exist: A Watermark, an Adversarial Defense, or Transferable Attack.
To prove this, formalize and extend existing definitions of watermarks and adversarial defenses as an interactive protocol between two players-Alice and Bob, (see Figure T Gooldaasser and Sipser 1986). This protocol always has least winner-either Alice can embed unremovable watermark, Bob can construct strong adversarial defense, or a third option emerges: a transferable attack.
Transferable Attack. To understand transferable attacks, consider the following game. Alice interacts with a player who claims have a secure model for learning task D, h. where D the data distribution and h is the ground truth. Alice sends queries and observes the responses. She wins she can generate queries that (i) cause significant errors and (ii) remain indistinguishable from samples drawn from D Whether she succeeds depends on the computational and data resources available to her and the other player. Alice can defeat any equally-resourced player, we call her queries a Transferable Artack. Intuitively, the more challenging query becomes, the easier it should surprisingly, we show that transferable attacks do exist. Specifically, we prove:
be detect
'e note that what we consider Transferable Attack is slightly nonstandard there is no explicit model the attacks which we consider transferability of. However, we can think that Alice first trains a model, then tries find adversarial examples for it, and sends those the queries in the game.

---

The existence of Transferable Attacks as defined above. Our construction uses cryp- tographic techniques, particularly Fully Homomorphic Encryption (FHE) [Gentry] 2009).
This establishes that Transferable Attacks form the third fundamental option in the trade-off.
That any learning task supporting a Transferable Attack must be computationally complex. More precisely, Transferable Attacks imply the existence of cryptographic primitive.
Notably, Tramer et al. [2017], suggest a conjecture for the transferability of adversarial attacks: If two models achieve low error for some task while also exhibiting low robustness to adversarial examples, adversarial examples crafted on one model transfer to the other: However, they qualify their hypothesis by showing that it is not true in general, but only when the models are of the same class- thus complicating the picture. Our meta-analyss shows that whether the conjecture holds depends crucially on the computational-resoun that foregrounding computational resources in the problem of robustness clarifies the landscape considerably.
available to the attacker and defender. We argue
Constructions. We show that the existence of these properties does not depend on any particular algorithm or a model that is used. depends on the learning task at hand and the computational resources for Alice and Bob. We give examples of learning tasks that provably support Watermarks, Adversarial Defenses and Transferable Attacks thereby justifying our framework. Concretely: (1) The construction of learning task with Transferable Attack, where the attacker needs strictly fewer resources than the defender. (2) We show that learning tasks with bounded VC dimension allow Adversarial Defenses against all (even computationally unbounded) attackers, ruling out Transferable Attacks in these settings. (3) We construct a Watermark for a class of learning tasks with bounded VC-dimension. Interestingly, in this case, both Watermark and Adversarial Defense coexist. Overall, these examples reiterate that the dependence on resources and the learning task are crucial.
Resource Allocation Implications. Our theorem can provide a rule of thumb for defenders. an adversary has computational budget 7' (e.g., time), then allocating T computation on the defender's side suffices (up to constant factors) to construct a defense whenever one exists under our assump- tions. Conversely, if a -bdbudeeted procedure fails, this provides evidence that the instance admits transferable attacks, which in- turn precludes watermarks in our framework. To our knowledge, this is among the first quantitative atfacker-defender resource trade-offs stated in model-agnostic setting, i.e, beyond eapacity-boundee regimes (e.g., finite VC dimension).
2 Related Work
While most trade-off's between backdoor-basee attacks and adversarial defenses have been studied empirically, Pal and Vidal [2020] show (theoretically) that Fast Gradient Methods (attacks) and Randomized Smoothing (defenses) can form Nash equilibrium under a restricted additive-noise model. They also provide experiments confirming this on datasets such as MNIST Our theoretical results generalize their findings to broader class of attacks and defenses.
2.1 Adversarial Robustness
Adversarial robustness research includes techniques like adversarial training Madry et al.) 2018 which improves resilience via adversarial examples, and certified defenses RRaghnnthhan al. 2018), which provide provable guarantees within perturbation bounds. Methods such as randomized smoothing [Cohen et al. 2019] extend these guarantees, but mainly as a defense against Ep norm perturbations. Moving beyond this, the work of Goldwasser et al. (2020) establish provable and computationally efficient defenses against arbitrary adversarial examples by detection- bassd defense mechanisms, but on bounded VC-dimension classes well.
2.2 Backdoor-Based Watermarks
In black-box settings, where model auditors lack access to internal parameters, watermarking meth- ods often involve embedding backdoors during training. Techniques by Adi et al. 2018 and
Paa and Vidal (2020) consider game with slightly different utility than

---

Zhang et al. 2018 use crafted imput patterns as triggers linked to specific outputs, enabling owner- ship verification by querying the model with these specific imputs. Advanced methods by |Merrer et al. [2017] utilize adversarial examples, which are perturbed inputs that yield predefined outputs. Further enhancements by Namba and Sakuma [219]] 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. 2022 Peng et al. 2023 and [Li et al.
2023]. 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.
2.3 Undetectable Backdoors
A key related work by Goldwasser et al. [2022] shows how a learner can plant undetectable backdoors in any classifier. The authors propose two frameworks: one employing digital signature schemes [Golwaasser et al.)) 1985] to make backdoored models indistinguishable from the original to any computationally-bonit boounddd observer, and another using Random Fourier Features (RFF) (Rahimi and Recht 2007], which remains undetectable even with full visibility of the model and training data.
In very recent work, Christiano et al. 2024) introduce defendability framework that formalizes the interaction between an attacker planting a backdoor and defender tasked with detecting A major difference from our work, is that in their approach, the attacker chooses the distribution, whereas we keep the distribution fixed. This makes defendability in their model harder since the attacker has more control. However, in their framework, the backdoor trigger x² is sampled from D. so the attacker does not influence it. In contrast, our model allows the attacker to choose specific priori
r's, making defendability in their model easier in this regard. Thus, the definitions incomparable. However, there are many interesting connections. They show that computationally unbounded defendability is equivalent to PAC learnability, while we, in a similar spirit, show an Adversarial Defense for all tasks with bounded VC-dimension. Using cryptographic tools, they show that the class of polynomial-size circuits is not efficiently defendable, while different cryptographic tools to give a Transferable Attack, which rules out Defense
3 Modeling
A key aspect of our formalization is modeling Alice and Bob while accounting for computational resources. We do by representing them as families of circuits indexed by size parameter standard approach in complexity theory. Families of Boolean circuits-ar as used here-are are Turing complete and can simulate any algorithm, making them natural abstraction for studying learning tasks independent of implementation details. Although circuits are less common in computational learning theory than more loosely specified algorithms, this finer granularity is essential for our results.
3.1 Learning
Definition 1 (Learning Task (Informal)). Let (0, 1)"h be an input space as a sequence [InInnN, where each In, is a fixed distribution over pairs (Dny h,). Concretely, for each n, we draw (Pa,ha) Ln, where D, is a distribution with domain {0, 1 1)", and h, (0. 13" + [0,1] is ground truth labeling function.
i A
learning task L is defined
To every model f: f0, 1)" {0, 1), we associate err(f) == EewD,, [f(x) + hn)=). And for E N. E 13"), and predictions y e {0, we define the empirical error to be: cIT(x. := Eiety! 1 (o:(())))))))
Detinition 2 (Computationally Bounded Learnability (Informal)). Let e, 8: : N + (0, 1) be functions that specify the allowable error and confidence levels for each input size n, respectively. A learning
where we discuss potential avenues for generalizing our framework to generative tasks. We explore the differences between generation and verification.
*We refer readers to Appendix J.3
"We work over Fz (i.c., inputs in (o, 1)")) for analytic convenience. Any ML sopeline-proceeee images, tokens, or graphs executes finite sequence of arithmetic and logical operations that can be compiled into polynomial-size size Boolean circuits.

---

task L = [L HeeN is said to be learnable to enror c(n) with confidence - 8(n) and circuit complexity ((n) if there exists family of circuits ((m), such that for every sufficiently large n, the following condition holds:
where each circuit C, has size at most
P(D )o M. (fr) S <(n) 2 21- 1
where Jn. : 10, - 1) is the hypothesis computed by the circuit C, when given sample access to (Dn, i.e., fn &- On. In other words, with probability at least 1 - 8(n) over the choice of (Dn, (nn) drawn from Ln, the circuit C₂ successfully computes function fn that achieves an error rate of at most c(n).
Definition 2 is very similar to the standard definition of efficient PAC learnability Kearns and Vazirani 1994]. The main difference is that instead of defining 'efficient' as polynomial in n (and 1/c, 1/8) define it implementable by circuit of size given by a fixed function S(n). The reason for this increased generality is that we need finer control over sizes than, e.g., polynomial or exponential (see Theorem where the separation between two circuit families is (n) versus / Smm)). ). A second difference is that compared the standard definition we bound the size of circuits Arora and Barak [2009]. not the running time. Assuming a processing unit without parallel execution the two notions can be thought equivalent. Formal definitions and additional details can be found in Appendix B In the rest of the main part of the paper, we will often omit the parameter when it is clear context.
Connections Existing Models of Learning Definition | represents a learner's prior knowledge as a distribution over pairs (D h,),, where DD, is a distribution on the domain {0, 1)" and h, (0, 13" + {0, 1} is the ground truth. This models learning task as a distribution over both input distributions and hypotheses, assuming realizable scenario with a fixed ground truth.
Unlike distribution-ssecifee or restricted family settings Kalai et al. 20008) : Feldman al. (0066]
definition does not limit the underlying support. While standard PAC learning requires generalization
across all domain distributions, it often fails explain the performance of complex models like DNNs, as their rich hypothesis classes make standard PAC bounds ineffective ZZhng et al.) (2021),
Nagarajan and Kolter [2019]. Our definition aims to bridge this gap by providing a formal framework that aligns with contemporary practical learning scenarios.
3.2 Interaction
Alice and Bob will engage in interaction. To measure their computational resources, we require specification how the model fo is transmitted between them. We assume that before the interaction starts they agree messages of some length. This modeling implies that fn are sent white-box. One example of such a family is the family of neural networks of given architecture. See Appendix B for details.
family of function classes F {Fn)n as well as encoding of them into
3.3 Computational Indistinguishability
erucial property of interest will be the indistingussaabiliy of distributions. For pair of distributions
Do D consider the following game between a sender and the distinguisher C: (1) The sender samples bit ((0, 1}) and then draws random sample x DD, (2) receives x and outputs ; = C(x) E {0, 13. C wins if i = b. We define the advantage of C for distinguishing DO from D
P Pb (C(x) = 2 +
For pair of families of distributions D (D.).. D = (D),), n. function 7 N - (0. 20 and
size bound S N N we say DD D are 7-inddssiiguuishull for circuits of size S if for every every circuit (also known as the distinguisher) of size S(n) the advantage of C for distinguishing Do from D. is at most (n).
4 Watermarks, Adversarial Defenses and Transferable Attacks
In our protocols, Alice (A, verifier) and Bob (B, prover) engage in interactive communication, with distinct roles depending on the specific task. Each protocol is defined with respect to a learning
5

---

task L, an error parameter E (0. 2), and circuit size bounds SA and SB, which are functions of n. scheme is successful if the conditions of the protocols are satisfied. We denote the of such circuits by SCHEME(T,, SA (n), SB (n)), where SCHEME refers to WATERMARK, DEFENSE, or TRANSFATTACK (see Appendix for the formal versions of all the definitions).
Definition 3 (Watermark, informal).
A family of circuits {A WATERMARK scheme for the learning task with error parameter e 0 if, for every sufficiently large n, an interactive protocol in which first (Dn, hn) ~ L, and then A WATERMARK computes classifier f: 1) + {0,1] and a sequence of queries x E (40, ())),, and a prover B, outputs y = (f.xx) {0,1)", satisfies the following properties:
In of sizes {SA (n) Jn. implements backdoor-based watermarking
1. Correctness: has low error, i.e., err(/) S.
2. Uniqueness: There exists prover B,,, of size SA(n), which provides low-error answers, such that err(x, y) < 2e.
3. Unremovability: For every prover B,, of size (n)n). holds that err(x, > 2e.
4. Undetectability: For every prover B,, of size (n),,, the advantage of B, in distinguishing the queries x generated by A,, WATERMARK from random queries sampled from Dj is small.
Table Backdoor- Watermarks (Definition 3)
Property in Def. 3
Classical analogue
Why it is needed?
Correctness
Standard accuracy requirement
Ensures watermarking does not degrade task performance. Prevents false positives on independently- trained models.
(e.g.. (Adi et al. 2018)
Uniqueness
Verifiability in black-box water- marking
Unremovability
Robustness to pruning fine-
Captures the usual "cannot be scrubbed" crite- rion.
tuning (e.g.. NNama and
Sakuma 2019
Undetectability
Stealth requirment (e.g.. Mer--
Guarantees watermark triggers look distribution data.
rer et al. 2017)
As summarized in Table I uniqueness ensures that watermark verification cannot be triggered by independently trained models. Formally, we require that any B,, (Bob), who did not use f and trained a model /Seratch using the specified procedure, must be accepted as distinct. This reflects realistic settings where multiple models could emerge independently.
Definition (Adversarial Defense, informal).
family of circuits ( [ (DDUNSSH) Jn of sizes (Sn(n))n. implements an adversarial defense for the learning task TL with error parameter
0, if for every sufficiently large interactive protocol in
which first (Da, h,) ~ Ln and then DEPENSEE computes a classifier f: {00 1) + {0, 1), while A,, replies with x Ax (f), where
13"),, and B
DoreNse outputs b DarENSE (f,x) E (0, 1}.
(f,
satisfies the following properties:
1. Correctness: has low error, i.e., err(f) S
2. Completeness: When x ~ Dg, then = 0.
3. Soundness: For every A,, size SA (n), we have enr(x, fxx)) S 7e or b 1.
The key requirement for a successful defense is the ability to detect when it is being tested (see the soundness and completeness properties in Table 2b. To bypass the defense, A, (Alice) must provide samples that are both adversarial, causing the classifier to err, and indistinguishable from samples of D,,-
Definition (Transferable Attack, informal).
A family of circuits {A] TRANSFATTACK] ), of sizes { implements a transferable attack for the learning task IL with error parameter c > for every sufficiently large n, an interactive protocol in which first (Dn,, hn.) ~ L,, and then A TRANSFATTACK computes E (f0, 13")² and B, outputs
y B, (x) {0, 13" satisfies the following properties:

---

Table Adversarial Defenses (Definition
Property in Def. 4
Classical analogue
Why it is needed?
Correctness
Baseline test-error requirement
Ensures defended model remains useful.
in certified detection-based de- fences
Completeness
"No false positive" guarantee in detection frameworks ((Gold. wasser al., 2020)
Prevents trivial defences that reject everything.
Soundness
Detection + robustness guaran-
Formalises that attacks must both fool and stay indistinguishable.
(rejection-based defenses)
1. Correctness: Size (n(n) is sufficient to learn a classifier of low-error, err(f) S c.
2. Transferability: For every prover B,, of size SA (n), have emr(x,y) 2c.
3. Undetectability: For every prover B,, of size SB(n). the advantage of B, in distinguishing the queries x generated by A TRANSEATIACK from random queries sampled from Dj is small.
Table 3: Transferable Attacks (Definition 5).
Property in Def. 5
Classical analogue
Why it is needed?
Conrectness
Baseline learnability precondi- tion
Ensures meaningful low-error model exists the attacker to exploit.
Transferability
Cross moosl adversarial transfer (Tramer et al. 2017)
Captures worst-case attacks that succeed re- gardless of defender architecture or training procedure.
Undetectability
Stealth indistingusshabiliy
Guarantees defenders cannot filter the adversar- ial queries, aligning with cryptographic indis- tinguishability.
(Goldwasser et al. 2020
5
Main Result
We are ready to state an informal version of our main theorem (see Appendix for the full version). The key idea is define zero-sum game between A, (Alice) and B,, (Bob), for every n, where the actions of each player are all possible circuits that can be realized with size SA (n) and (n)).. Notably, this game is finite, but there exponentially many such actions for each player. We rely on some key properties of such large zero-sum games Lipton and Young 19946 to argue about our main result.
Theorem 1 (Main Theorem, informal). For every E (0, ( N - N and learning task L learnable to error with high confidence with circuit complexity S(n), at least one of these three exist
51
(S(n)
)):
WATERMARK
L, L,c,S(n,,
log(S(m)
(S(n)
0(((m))
DEFENSE L,E,O
log(S(n))
TRANSFATTACK
S(n,,
Proof (Sketcht). The intuition of the proof relies the complementary nature of Definitions and 4 Specifically, every attempt to remove a fixed Watermark can be transformed to potential Adversarial Defense, and vice versa. We define zero-sum game & between eircuits for watermarking A,, and circuits attempting to remove a watermark B,, The set of (pure) strategies of each player are all possible circuits that be realized with size SA (n) and (n(n). and the payoff is determined by the probability that the errors and rejections meet specific requirements. It is well known that this
'We remark that formally the existence does not hold for all sufficiently large but only with some 'frequency'. See Theorem for formal statement.
7

---

two-player sum game admits Nash equilibrium (NE) and the value of the game is unique Neumann 1928 Let [ANAS)) and (BNAS*), Jn be the NE strategies of Alice and Bob respectively. For each n E N. careful analysis shows that depending on the value of the game, we have Watermark, an Adversarial Defense, or a Transferable Attack. In the first case, where the expected payoff at the NE is greater than threshold, we show there is an Adversarial Defense. As an illustration, consider some n E IN, for which we define B DEFFENS as follows. DEEEEES first learns a low-error classifier f. then sends f to the party that is attacking the Defense, then receives queries and simulates (y.b) B NASH (f. x). The bit = if BAASH thinks is attacked. Finally, B.EFEESS 0 it replies with 8' 1 if the fraction of queries which
22 replies with b' if b 1, and if (x) and y differ is high. Careful analysis shows DREENSSE is an Adversarial Defense. In the second case, where the expected payoff at the NE is below the threshold, we have either Watermark or Transferable Attack. The full proof can be found in Appendix D
6 Transferable Attacks and 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 second result of this section, we show that every learning task with 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.
6.1 A Cryptography-basee Task with a Transferable Attack
Next, we give an example of a syypoggraphy-basee learning task with Transferable Attack. The following is an informal statement of the formal version (Theorem 7 given in Appendix
Theorem 2 (Transferable Attack for a Cryptography- based Learning Task, informal). There exists learning task L, and A such that for all sufficiently small
A E TRANSFATTACK (LOOMPO SA = E'
1
SB =Ω
(
Moreover, crypo is such that for every e, 22 1 time (and O (2) samples) is enough, and Q (1) samples (and in particular time) is necessary to learn a classifier of error
Notably, the parameters are set so that A (the party computing x) has a smaller circuit size than B (the party computing y), specifically R 1/c compared to (11/2)). Furthermore, because of the cryptography tools used, this a setting where single input maps to multiple outputs, which deviates away from the setting of classification learning tasks considered in Theorem [
Proof (Sketch). We start with a definition of a learning task that will be later augmented with a cryptographic tool to produce Lrypio
Lines on Circle Learning Task L (Figure 2 We associate the imput space {0, 10 with vertices
of 2n regular polygon inscribed in {i R- ||اح|| = 1}. Let H. == {hw | w R², ||wl|2 1}. where hep (xr == sgn (w, x)). Let I. be a distribution corresponding to the following process: sample he (H), return (UO }}"), hw). Additionally, let (a) (x E 10, [< (x,w)) a)
denote the set of points within an angular distance up to a to w.
Fully Homomorphic Eneryption (FHE) (Appendix E. FHE /eentry 2009 allows for computa- tion on encrypted data without decrypting it. An FHE scheme allows to encrypt æ via an efficient procedure e = FHE.ENC ENC(z), so that later, for any algorithm C. possible run C on ho- momorphically. More concretely, it is possible to produce an encryption of the result of running C on x, i.e., cC,r
F.E.EVAL e.). Finally, there is a procedure FHE.DEC that, when given secret key sk, can decrypt cc.z, i.e., == FHE. DEC(sk, CC.,), where is the result of running C' on r. Crucially, eneryptions of any two messages are indistinguishable for all efficient adversaries.
Il T,erpto is derived from Lines on Circle Learning Task L. e_erypto corresponds to the following process: w U(fw E RR2 ||[w]|2 = 1}), return the distribution D which is equal mixture of two parts T D + The first
Cryptography-based Learning Task cyrpot (Figure 2).
8

---

Learning L samples distribution 2 | +P
U((0, 6 Ber(1/2), where U({0, uniform the cle.
2. Ifb
return (z, (x))..
3. Else, return (NC(a))) (HE.ENc(h,(r)))
learns h
Icarns A
Alice (size SA 1/c)
Bob (size Sp Rz 1/c3)
The left part of the figure represents Lines on Circle Learning Task L with ground truth function denoted by lww. On the right, we define a cryptography hugphhye-dmmeeeeddd learning task derived from L In its distribution, a "clear" or "encrypted" sample is observed with equal probability. Given their respective times, both A and B are able to learn a low-error classifier A hB respectively, by learning only on the clear samples. A is able compute a Transferable Attack by computing an encryption of a point close to the decision boundary of her classifier A.A.
Figure 2:
part, i.e., DLEAR equal to x ~ U((O, with the correct label y = hy (xx). The second part, i.e., Dixe= is equal to x' U[O,, 1f (x"),,, (ar, - (THEEENC(2) FHE. ENC(s)) which which can be thought of as D under an encryption. See Figure 2 for visual representation. Note that we omitted the size parameter n for simplicity.
Transferable Attack (Figure 2). Consider the following attack strategy A. First, A collects O(1/e) samples from the distribution DELAR and learns classifier i E H that is consistent with these samples. Since the VC-dimension of H is 2, the hypothesis A has error at most with high probability Next, A samples a point JANd uniformly at random from a region close to the decision boundary of h i.e., TBND U (B (t)). Finally, with equal probability, A sets an attack either FHE.ENC
a uniformly random point Di FLEAR ((0, 1)"). We claim that satisfies the properties a Transferable Attack.
Since A has low error with high probability, 2ann is uniformly random point from containing the boundary htn (see Figure P). The circuit size of upper-bounded by 2(1/e²), meaning it can only learn a classifier with error 2 10e² (see Lemma 3 for details). B s can only learn (Lemma)) 3) a classifier of error, S 10e2. Taking these two facts together, we expect B to misclassify
x' with probability 3 10.2 5E > 2e, where the factor 1 takes into account that we send an encrypted sample only half of the time. This implies transferability.
Note that x is encrypted with the same probability as in the original distribution because we send (NC and a uniformly random ENE.ENCCIBBN is indistigguisaabl, for efficient adversaries, from ENC.ENC(I) for any other E (0, 1)" This follows from the security of the FHE. Consequently, undetectability holds. O
Dir DELEAR U (f0, 1)") with probability $. Crucially,
6.2 Tasks with Transferable Attacks Imply Cryptography
In this section, we show that a Transferable Attack for any task implies a cryptographic primitive.
EFID Pairs. In cryptography, EFID pair [Goldreich] 1990) is pair of ensembles of distributions D0,D!, that are Efficiently samplable, statistically Far, and computationally Indistinguisaable. By
Note that because FHE encryption is probabilistic there are many valid answers for a given x..
can also evaluate & homomorphically (i.e., run FHE.EVAL) on FHE. (HE(EN((x) to obtain FHE. (HE.ENC(y) of error on De also. This means that A is able to learn a low-error classifier on D
Inn this proof sketch, we g
i..., A sends only one B. This is true for the formal scheme.

---

Watermarks
Adversarial Defenses
Transferable Attacks
Sn
8
8
Bob
Allce
Bob
x(8"
((8)
(()
e (())
(()
83
MA
(
o(
polri x
6
Alice
Bob
Alice
Figure 3: 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 size 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 5 andd 6 for details about blue regions. The curved line represents potential application of Theorem which says that at least one of the three points should be blue.
a seminal result [Goldreich] 1990]. we know that the existence of EFID pairs is equivalent to the existence of Pseudorandom Generators (PRG), which can be used for tasks including encryption and key generation [Goldreich] [990]. which makes EFID pairs useful primitive. We consider slight modification of the standard definition of EFID pairs, where instead of defining security to hold against polynomial time adversaries we do it for fixed size bound function. More concretely, for two size bounds S, 5' :N + IN we call a pair of ensembles of distributions (D", D= an (S, S')-EFII pair if for every (i) D D) are samplable by circuits of size S(n), (ii) Do D), are statistically far, (iii) D DJ, are indistinguishable for circuits size S' ('(n). n: n
Tasks with Transferable Attacks imply EFID Pairs. The second result shows that any task with a Transferable Attack implies the existence of type of EFID pair. This guarantees that any learning task with a Transferable Attack has to be computationally complex. The proof is in Appendix G
Theorem 3 (Transferable Attacks imply EFID pairs, informal). For every c (0, SB N, SA < SB, every learning task L learnable to error with high confidence and circuit complexity SA if there exists TRANSATTACK(L, SA, SB)) then there exists an (SA, SB)-EFID pair.
We note that it is unclear if the existence of EFID-pain pairs guaranteed by Theorem 3 implies PRGs because the sampling of DD, DD' requires oracle access L. Therefore, the standard construction of PRGs from EFID pairs does not automatically transfer.
7 Tasks with Watermarks and Adversarial Defenses
As the final pair of results, we present tasks exhibiting Watermarks and Adversarial Defenses. In the first, hypothesis classes with polynomially bounded VC-dimension admit polynomial-size Adversarial Defenses against all attackers. In the second, learning task of polynomially bounded VC-dimension admits a Watermark secure against fast adversaries. These lemmas highlight the importance of bounding the sizes of A and B. See Figure 3 for a visual summary: formal statements and proofs appear in Appendices H [
Lemma (Adversarial Defense for bounded VC-dimension, informal). There exists B such that for every sufficiently small e,
every every learning lask L of VC-dimensiion !
B E DEFENSE SL o0, =poly (?))
Lemma 2 (Watermark for bounded VC-dimension against fast adversaries, informal). For every d, there exists learning task Th of VC-dimension d and A such that for every sufficiently small e,
A E WATERMARK(L, e, 9 9= 0 SA = 0(2) SB = -00) =
'I means that the ground truth sampled from L belongs class of VC-dimension 72.
10

---

Acknowledgement
This research was partially supported by the Deutsche Forschungsgemeinschatt (DFG, German Research Foundation) under Germany's 's Excellence Strategy The Berlin Mathematics Research Center MATH+ (EXC-2046/1, project ID: 390685689). We thank the anonymous reviewers for their thoughtful comments and suggestions, which improved the paper.
References
Lukáš Adam, Rostislav Horčík, Tomáš Kasl, and Tomás Kroupa. Double oracle algorithm for computing equilibria in continuous games. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pages 5070-5077, 2021.
Yossi Adi, Carsten Baum, Moustapha Cisse, Benny Pinkas, and Joseph Keshet. Turning your weakness into strength: Watermarking deep neural networks by backdooring. 27th USENIX Security Symposium (USENIX Security 18), pages 1615-1631, 2018.
Noga Amit, Shafi Goldwasser, Orr Paradise, and Guy Rothblum. Models that prove their own correctness. arXiv preprint arXiv:2405.15722, 2024.
Maksym Andriushchenko, Francesco Croce, and Nicolas Flammarion. Jailbreaking leading safety- aligned Iims with simple adaptive attacks, 2024.
Cem Anil, Guodong Zhang. Yuhuai Wu, and Roger Grosse. Learning to give checkable answers with prover-verifier games. arXiv preprint arXiv:2108. /2099, 2021.
Sanjeev Arora and Boaz Barak. Computational Complexity: Modern Approach. Cambridge University Press, USA, 1st edition, 2009. ISBN 0521424267.
Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. (leveled) fully homomorphic encryption without bootstrapping. In Proceedings of the 3rd Innovations Theoretical Computer Science Conference, ITCS 12, page 309-325, New York, NY, USA, 2012. Association for Computing Machinery. ISBN 9781450311520. 10. 1t.114//2090236... 220C0022266200222222
doi: 10.1145/20902236220006666 URL http:://dooi...... org/
Jonah Brown-Cohen, Geoffrey Irving, and Georgios Piliouras. Scalable ai safety via doubly-efficient debate. arXiv preprint arXiv:2311.14122 2023.
Sébastien Bubeck, Yin Tat Lee, Eric Price, and Ilya Razenshteyn. Adversarial examples from computational constraints. In International Conference Machine Learning, pages 831-840. PMLR, 2019.
Collin Burns, Pavel Izmailov, Jan Hendrik Kirchner, Bowen Baker, Leo Gao, Leopold Aschenbren- ner, Yining Chen, Adrien Ecoffet, Manas Joglekar, Jan Leike, Ilya Sutskever, and Jeffrey Wu. Weak-to-strong generalization: Eliciting strong capabilities with weak supervision. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors, Proceedings of the 4 International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 4971-5012. PMLR, 21-27 Jul html
2024.
mlr
Nicholas Carlini, Milad Nasr, Christopher A. Choquette-Choor Matthew Jagielski, Irena Gao, Anas Awadalla, Pang Wei Koh, Daphne Ippolito. Katherine Lee, Florian Tramer, and Ludwig Schmidt. Are aligned neural networks adversarially aligned? ArXiv, 154477, 2023. URL https
//api.semaatiischoll.e www.eoorgoooooo arggCorpusIDD :tt.opppuII:22222213335
Patrick Chao, Alexander Robey, Edgar Dobriban, Hamed Hassani, George Pappas, and Eric Wong. Jailbreaking black box large language models in twenty queries, 2023.
Jiefeng Chen, Yang Guo, Xi Wu, Tianqi Li, Qicheng Lao, Yingyu Liang, and Somesh Jha. Towards adversarial robustness via transductive learning. arXiv preprint arXiv:2106.00 08387, 2021.
Miranda Christ, Sam Gunn, and Or Zamir. Undetectable watermarks for language models. arXiv preprint ar arXiv:2306.091 2023.

---

Paul Christiano, Jacob Hilton, Victor Lecomte, and Mark Xu. Backdoor defense, learnability and obfuscation, arXiv preprint 0rXiv:2409.03077, 2024.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustesss via randomized smoothing. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning. volume 97 of Proceedings of Machine Learn- mlr
ing Research, pages 1310-1320, 1320. PMLR, 09-15 Jun 2019. URL httpp:://poceeddii ctees/v99/cohentt htmml
Anne Condon, Joan Feigenbaum, Carsten Lund, and Peter Shor. Probabilistically checkable debate systems and approximation algorithms for pspace-hard functions. In Proceedings of the twenty-fifth annual ACM symposium on Theory of Computing, pages 305-314, 1993.
Bita Darvish Rouhani, Huili Chen, and Farinaz Koushanfar. Deepsigns: An end-to-end watermarking framework for ownership protection of deep neural networks. In Proceedings of the twenty-fourth international conference on architectural support for programming languages and operating systems, pages 485 497, 2019.
Yinpeng Dong, Tianyu Pang, Hang Su, and Jun Zhu. Evading defenses to transferable adversarial examples by translation-invarte attacks. 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition ( (CVPR), pages 4307-4316, 2019. URL htLhtts/://ap wtw..i.smmatiiccooll....
org/CorpusID: 102350868
Logan Engstrom, Dimitris Tsipras, Ludwig Schmidt, and Aleksander Madry. A rotation and translation suffice: Fooling cmns with simple transformations. ArXiv, abs/1712.02779, 2017. URL
https://api. semanticscholar org/ CooppusD:221929200
Yousof Erfani, Ramin Pichevar, and Jean Rouat. Audio watermarking using spikegram and two- dictionary approach. IEEE Transactions on Information Forensics and Security, 12(4):840-852 2017. doi: 10.
Jon Feldman, Rocco A Servedio, and Ryan O'Donnell. Pac learning axis-aligned mixtures of gaussians with no separation assumption. In Learning Theory: 19th Annual Conference on Learning Theory, COLT 2006, Pittsburgh, PA, USA, June 22-25, 2006. Proceedings 19, pages 20-34. Springer, 2006.
Pierre Fernandez, Guillaume Couairon, Hervé Jégou, Matthijs Douze, and Teddy Furon. The stable signature: Rooting watermarks in latent diffusion models. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 22466-22477, 2023.
Liam Fowl, Micah Goldblum, Ping-ych Chiang, Jonas Geiping, Wojeiech Czaja, and Tom Goldstein. Adversarial examples make strong poisons. Advances in Neural Information Processing Systems, 02300399-03351 2021.
A. Gammerman, V. Vovk, and V. Vapnik. Learning by transduction. In Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence. UAI'98, page 155- San Francisco, CA. USA, 1998. Morgan Kaufmann Publishers Inc. ISBN 155860555X.
Sanjam Garg, Somesh Jha, Saeed Mahloujifar, and Mahmoody Mohammad. Adversarially robust learning could leverage computational hardness. In Algorithmic Learning Theory, pages 365-385. PMLR, 2020.
Craig Gentry. Fully homomorphic encryption using ideal lattices. In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, STOC '09, page 169-178. New York, NY, USA, 2009. Association for Computing Machinery. ISBN 978 1775585060 doi: 10.1145/1536414
1536440. httpss//s///o/ org/ 10. 1145/1536414 1536414. 1536440
Justin Gilmer, Luke Metz, Fartash Faghri, Samuel S. Schoenholz, Maithra Raghu, Martin Wattenberg, and Ian J. Goodfellow. Adversarial spheres. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30- May 3, 2018, Workshop Track nww/teeunnr Proceedings, 2018 URL /tRL:tttt////eeeeriiii httaap/pe//ppeerereeeeee/eeorooo htt.:/forumn11---tthLLa.. Sit=StthhkkPf
Greg Gluch and Shafi Goldwasser. cryptographic persppeetttppicpppeeeieciiieeee on mitigation vs. detection in machine learning, 2025. URL http:: wwarxxvvoor//eee arg/3b///2504.23010
12

---

Oded Goldreich. A note on computational indistinguishability. Information Processing Letters, 34 (6):277-281, 1990. ISSN 0020-0190. doi: http://6bbaao////oooooooooooooo0 URL
htttps:/wwwy sciencedi ccc.aaaeelreeet..ccc/ccccc//aaaa http:////cccaa.....t...////////.
S Goldwasser and M Sipser. Private coins versus public coins in interactive proof systems. In Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing. STOC '86, page 59-68, New York, NY, USA, 1986. Association for Computing Machinery. ISBN 1897911938. doi: 10. 10.114.5 211141//113000 21111111113777 Utt.tttss://oooooo org/ 1145 12130. 12137
S Goldwasser, Micali, and C Rackoff The knowledge complexity of interactive proof-systems, In Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, STOC '85, page 291-304, New York, NY, USA, 1985. Association for Computing Machinery. ISBN 0897911512. doi: 10. 10.1145/22145.22177
URL
10000....0 1145/ 1145/2215, 22178
Shafi Goldwasser, Yael Kalai, Raluca Ada Popa. Vinod Vaikuntanathan, and Nickolai Zeldovich. Reusable garbled circuits and succinct functional encryption. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing. STOC '13, page 555-564, New York, NY, USA, 2013. Association for Computing Machinery, ISBN 978 9781450320290. doi: 10.1145/2488608,
2488678. URL https: //doi. http://oo.oo///////////oo .rg/ 10. 1145/ 2488678
Shafi Goldwasser, Adam Tauman Kalai, Yael Tauman Kalai, and Omar Montasser. Beyond perturba- tions: Learning guarantees with arbitrary adversarial test examples. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS' 20, Red Hook, NY,
USA, 2020. Curran Associates Inc. ISBN 9781713829546.
Shafi Goldwasser, Michael P. Kim, Vinod Vaikuntanathan, and Or Zamir. Planting undetectable backdoors machine learning models. ArXiv, abs/2204.06974, 2022. URL https://api
semanticscholar org/ weg//CrppuIID... 248177888
Chenxi Gu, Chengsong Huang, Xiaoqing Zheng, Kai-Wei Chang, and Cho-Jui Hsieh. Watermarking pre-trained language models with backdooring, arXiv preprint arXiv:2210.07543, 2022.
Minyoung Huh, Brian Cheung, Tongzhou Wang, and Phillip Isola. The platonic representation hypothesis. arXiv preprini arXiv:2405.07988 2024.
Geoffrey Irving, Paul Christiano, and Dario Amodei. Ai safety via debate, 2018. URL https
//arxiv.org absaaaa///a/ 1805..80.... 00899
Zhengyuan Jiang, Jinghuai Zhang, and Neil Zhenqiang Gong. Evading watermark based detection of ai-generated content. Proceedings of the 2023 ACM SIGSAC Conference on Computer and Commu- nications Security, 2023. UtL/ttps: //api swmanticscholastttt.teeeiaoaaate org/ CorpussDD:258557622
Adam Tauman Kalai, Adam Klivans, Yishay Mansour, and Rocco A Servedio. Agnostically learning halfspaces. SIAM Journal on Computing, 1776):177711855, 2008
Michael J. Kearns and Umesh Vazirani. An introduction to computational learning theory. MIT Press, Cambridge, MA, USA, 1994, ISBN 02621 1 11944.
John Kirchenbauer, Jonas Geiping, Yuxin Wen, Jonathan Katz, Ian Miers, and Tom Goldstein. A watermark for large language models. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 17061-17084. PMLR, 23-29 Jul 2023. URL htttps:/pproceeding/ mir press/v202//irrchebaauue html
Jan Hendrik Kirchner, Yining Chen, Harri Edwards, Jan Leike, Nat McAleese, and Yuri Burda. Prover-Verifies Games improve legibility of LLM outputs, 2024. URL. httpttt:s///aiiiorrtttt org/ abs/2407. 13692
Rohith Kuditipudi, John Thickstun, Tatsunori Hashimoto, and Percy Liang. Robust distortion-free watermarks for language models. CoRR, abs/2307.15593, 2023. doi: 10.48550/ARXIV22007.1 15593.
URL https: / //oii org/10. 48550/arXiv 2307 15593
13

---

Mare Lanctot, Vinicius Zambaldi, Audrunas Gruslys. Angeliki Lazaridou, Karl Tuyls, Julien Pérolat, David Silver, and Thore Graepel. unified game-theoretic approach to multiagent reinforcement learning. Advances in neural information processing systems, 30, 2017.
Peixuan Li, Pengzhou Cheng, Fangqi Li, Wei Du, Haodong Zhao, and Gongshen Liu. Plmmark: a secure and robust black-box watermarking framework for pre-trained language models. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 14991-14999, 2023.
Richard J. Lipton and Neal E. Young. Simple strategies for large zero-sum games with applications to complexity theory. In Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, STOC '94, page 734-740, New York, NY, USA, 1994a. Association for Computing Machinery. ISBN 0897916638. doi: 10.1145/195058.190 195447. URL httts:///oi.org::
1145/195058. 195447
Richard J Lipton and Neal E Young. Simple strategies for large zero-sum games with applications to complexity theory. In Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, pages 734-740, 1994b.
Chang Liu, Jie Zhang, Han Fang, Zehua Ma, Weiming Zhang, and Nenghai Yu. Dear: A deep- learning-base basen audio re-recording resilient watermarking, In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 13201-13209, 2023.
Yanpei Liu, Xinyun Chen, Chang Liu, and Dawn Song. Delving into transferable adversarial examples 2016
and black-box attacks. arXiv preprint
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In 6th International Conference Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Confer- ence Track Proceedings. OpenReview.net, 2018. hRtp:tt:s////eeereee
EJzIBfZAb
Stephen McAleer, John B Lanier, Kevin A Wang, Pierre Baldi, and Roy Fox. Xdo: A double oracle algorithm for extensive-for games. Advances in Neural Information Processing Systems, 34: 23128-23139, 2021.
Anay Mehrotra, Manolis Zampetakis, Paul Kassianik, Blaine Nelson, Hyrum Anderson, Yaron Singer, and Amin Karbasi. Tree of attacks: Jailbreaking black-box ilms automatically, 2024.
Erwan Le Merrer, Patrick Pérez, and Gilles Trédan. Adversarial frontier stitching for remote neural network watermarking. Neural Computing and Applications, 32:9233 9244, 2017. URL
https://api. semanticscholar .rrg Derg/CorpusID:.. 11008755
Omar Montasser, Steve Hanneke, and Nathan Srebro. Transductive robust learning guarantees. In International Conference on Artificial Intelligence and Statistics, pages 1 11661-11471 PMLR, 2022.
Yuki Nagai, Yusuke Uchida, Shigeyuki Sakazawa, and Shin'ichi Satoh. Digital watermarking for deep neural networks. International Journal of Multimedia Information Retrieval, 7:3-16, 2018.
Vaishnavh Nagarajan and Zico Kolter. Uniform convergence may be unable to explain generalization in deep learning. Advances in Neural Information Processing Systems, 32, 2019.
Ryota Namba and Jun Sakuma. Robust watermarking of neural network with exponential weighting. Proceedings of the 2019 ACM Asia Conference on Computer and Communications Security, 2019.
URL URLhhttss: / api. www.stiiinaoellaaaeeaeeeeeeaeaee wwt. (000rpusID::00291111
Noam Nisan. Pseudorandom generators for mounee computations. In Proceedings of the !wenty-second annual ACM symposium on Theory of computing, pages 204-212, 1990.
Zhenxing Niu, Yuyao Sun, Qiguang Miao, Rong Jin, and Gang Hua. Towards unified robustness against both backdoor and adversarial attacks. IEEE Transactions on Puttern Analysis and Machine Intelligence, 46(12):7589-760) 2024. doi: 10.1 10.1099TPAAM22224339777
14

---

Ambar Pal and René Vidal. A game theoretic analysis of additive adversarial attacks and defenses. Advances in Neural Information Processing Systems, 33:1345-1355, 2020.
Wenjun Peng, Jingwei Yi, Fangzhao Wu, Shangxi Wu, Bin Zhu, Lingjuan Lyu, Binxing Jiao, Tong Xu, Guangzhong Sun, and Xing Xie. Are you copying my model? protecting the copyright of large language models for eaas via backdoor watermark. arXiv preprini arXiv:2305. 10036, 2023.
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial examples. In 6th International Conference on Learning Representations, ICLR 2018. Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. URL.
https://oopenreviww net/ foromiidddddo orum?id-Bys4ob--R
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Platt, D. Koller, Y. Singer, and S. Roweis, editors, Advances in Neural Information Processing Systems. volume 20. Curran Associates, Inc., 2007. URL https::/pproceeddiinne hewppprooorr.iinnn...uu.u..ppppp neurips ccppaper.
f Fi11spppppzzp077111333000aaaaaar peaprp.ccc/pppprrrr
pdf
Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 84-93. ACM, 2005.
R. Rivest, L. Adleman, and M. Dertouzos. On data banks and privacy homomorphisms, In Founda- fions of Secure Computation, page 169-179, New York, NY, USA, 1978. Academic Press.
Mingjie Sun, Siddhant Agarwal, and J Zico Kolter, Poisoned classifiers are not only backdoored, they are fundamentally broken. arXiv preprint arXiv:2010.09080, 2020.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In Yoshua Bengio and Yann LeCun, editors, 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014. http:://////xiv org abs/ 6199
1312 abs/1312
Lue Tao, Lei Feng. Jinfeng Yi, Sheng-Jun Huang, and Songcan Chen. Better Safe than Sorry: Pre- venting Delusive Adversaries with Adversarial Training. In Proceedings of the 35th International Conference on Neural Information Processing Systems, NIPS '21, Red Hook, NY, USA, 2024. Curran Associates Inc. ISBN 9781713845393.
Stuart A. Thompson Tiffany Hsu. Disinformation researchers raise alarms about a.i. chatbots. bww.bbolgggpppeo/o 62=623 2023. Accessed: March 2024.
Florian Tramèr, Nicolas Papernot, Ian Goodfellow, Dan Boneh, and Patrick McDaniel. The space of 2017.
transferable adversarial examples. arXiv preprint
Florian Tramer, Nicholas Carlini, Wieland Brendel, and Aleksander Madry. On adaptive attacks to adversarial example defenses. Advances in neural information processing systems, 33:1633-1645, 2020.
Yusuke Uchida, Yuki Nagai, Shigeyuki Sakazawa, and Shin't iii'' Satoh. Embedding watermarks into deep neural networks. In Proceedings of the 2017 ACM on international conference multimedia retrieval, pages 269-277, 2017.
J v. Neumann. Zur theorie der gesellschafttspiele. Mathemutische annalen, 100(1):295-320, 1928.
Vinod Vaikuntanathan. Computing blindfolded: New developments in fully homomorphic encryp- tion. In Proceedings of the 20/1 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS '11, page 5-16, Washington, DC, USA, 2011. IEEE Computer Society. ISBN 9780769543001. doi: 10.1109/FOCS.000 1.98. URL https::t//// //oii org/ 1ttg//0..1199.. 1109/FOCS. 2011 998
Stephan Wäldchen, Kartikey Sharma, Berkant Turan, Max Zimmer, and Sebastian Pokutta. Inter- pretability Guarantees with Merlin-Arthur Classifiers. International Conference on Artificial Intelligence and Statistics, pages 1963-1971. PMLR, 2024.
15

---

Alexander Wei, Nika Haghtalab, and Jacob Steinhardt. Jailbroken: How does Ilm safety training fail? ArXiv, abs/2307.02483,, 2023. URL https://api. semmaaticcann wwapcchoooarrr//ooopuuuee C
259342528
Yuxin Wen, Neel Jain, John Kirchenbauer, Micah Goldblum, Jonas Geiping, and Tom Goldstein. Hard prompts made easy: Gradient-based discrete optimization for prompt tuning and discovery. In A. Oh, T. Neumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 51008-51025. Curran Associates, Inc., 2023a.
Yuxin Wen, John Kirchenbauer, Jonas Geiping, and Tom Goldstein. Tree-ring watermarks: Finger- prints for diffusion images that are invisible and robust. ArXiv, abs/2305.20030, 2023b. URL https://api semant ceeemmnnicschoolss cscholar www.ccooll....oooorrroieeeeeeeee :ttg//ooruslD::258900 258987524
Cheng-Hsin Weng, Yan-Ting Lee, and Shan-Hung (Brandon) Wu. On the trade-off between adversar- ial and backdoor robustness. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 11973-11983, Cur- ran Associates, Inc., 2020, URL httpttts//pooceeeiiinii neuriiiinnnnnnn.ni.......... neurips. pptpprrrflle/pppppeeepeeeeeppepp 00200/11/000066677000ff006666666
pdf
Eric
Wong and J. Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning. ICML 2018, Stockholmsmüsssnn. Stockholm. Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages html
5292. PMLR, 2018. URL.Bttp://proceedding http:///poooooooo.o..oooooooo/o/
press//80/wonge
Yi-Hsuan Wu, Chia- Chia-Hung Yuan, and Shan-Hung Wu. Adversarial robustness via runtime masking and cleansing. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Leurning, volume 119 of Proceedings of Muchine Learning Research, pages 10399-10409. PMLR, 13-18 Jul 2020. URL htR.stttss:/// httttss::/prceeediinggg/oo/ mlr press/v119/
wu20f html
Cihang Xie, Zhishuai Zhang, Jianyu Wang, Yuyin Zhou, Zhou Ren, and Alan Loddon Yuille. Improving transferability of adversarial examples with input diversity. 2019 IEEE/CVF Conference on Computer Vision and Patlern Recognition (CVPR), pages 2725-2734, 2018. URL https
//api org/
wtw.aaarrrrr/ooooss......... /CorpusID:3972833
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107-115, 2021.
Hanlin Zhang, Benjamin L. Edelman, Danilo Francati, Daniele Venturi, Giuseppe Ateniese, and Boaz Barak. Watermarks in the sand: Impossibility of strong watermarking for generative models. arXiV, 02//2311.04378 2023. doi: 10. 10.48550/AXXI.2311.0000 1.04378. URL htthhttt///oo / 48550/arXio http//rXiii.. 2311 04378
Jalong Zhang, Zhongshu Gu, Jiyong Jang, Hui Wu, Mare Ph. Stoecklin, Heqing Huang, and Ian Molloy. Protecting intellectual property of deep neural networks with watermarking. In Pro- ceedings of the 2018 Asia Conference Computer and Communications Security, ASIACCS '18, page 159-172, New York, NY, USA, 2018. Association for Computing Machinery. ISBN 9781450355766. doi: 011114//319944431955555 Utt.:ttss: orggioorg/10 1145/3196449
3196550
Xuandong Zhao, Prabhanjan Ananth, Lei Li, and Yu-Xiang Wang. Provable robust watermarking for ai-generated text. CoRR, abs/2306. 011222366.74333 17439, 2023a. doi: 1044850/ARX1122006.77777 URL
fttps::/ddoi.org/// wwt../////////////.////////// arXiv 2306.
Xuandong Zhao, Kexun Zhang, Yu-Xiang Wang, and Lei Li. Invisible image watermarks are provably removable using generative ai. 2023b. URL htllhhttss://app semanticscoolar wwwpchhoooorooooooouuuoooee 259075167
Yunqing Zhao, Tianyu Pang, Chao Du, Xiao Yang, Ngai-Man Cheung, and Min Lin. A recipe for watermarking diffusion models. ArXiv, abs/2303.10137, 2023c. URL hattps:/aapp
semanticscholar. htts//orpuIII:25522225509
16

---

Andy Zou, Zifan Wang, J. Zico Kolter, and Matt Fredrikson. Universal and transferable ad- versarial attacks on aligned language models. ArXiv, abs/2307.15043, 2023. URL https
seap..seeatt httpa//ccccooaoooo/rrrrruuaaiii. arg/CorpusID:220202995
17

---

A Additional Methods in Related Work
This section provides overview of the main areas relevant 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 broadly categorized based on the type of model they target. We review watermarking schemes for both classification and generative models, with primary focus on classification models, as our work builds upon these methods.
A.1.1 Watermarking Schemes for classification Models
classification models, which are designed to categorize input data into predefined classes, have been 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-lit like methods.
Adi et al. 2018 and Zhang et al. (2088) 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 inputs into the model and checking for the expected outputs, thereby confirming ownership.
Another significant contribution in this domain is by Merrer et al. (017]. who introduced a method that employs ad adversarial examples to embed the backdoor. Adversarial examples are perturbed inputs that cause the model to produce specific outputs, thus serving as watermark.
Namba and Sakuma [019 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
when the model undergoes transformations.
Provable undetectability of backdoors was achieved in the context of classification tasks by Gold wasser et al. 22022. Unfortunately, it is known ([Goldwasser et al., 2022] that some undetectable watermarks are easily removed by simple mechanisms similar to randomized smoothing [Cohen et al. 2019].
The popularity of black-box watermarking 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-Bon 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 confirm ownership. The initial methodologies for embedding watermarks into the weights of DNNs were introduced by Uchida al. [2017] and Nagai et al. (2018). Uchida al. (017) presented 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. [2019), who developed a technique to embed an N-bit (N 2 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 applicability in the black-box setting.
18

---

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 surge in research and diverse contributions in this area.
Backdoor-Rased Watermarking for Pre-trained Language Models. In the domain of Natural Language Processing (NI.),, backdoor-basee watermarks have been increasingly studied for Pre- trained Language Models (PLMs), as exemplified by works such as [Gu et al. 2022] and (Li et al.) 2023]. These methods leverage rare or common word triggers to embed watermarks, ensuring that they remain robust across downstream tasks and resilient 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.) 2023). who proposed watermarking framework that embeds signals into generated text that 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. 2023] introduced robust fistortion-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.
Zhhoo et al. 2023a presented provable, robust watermarking technique for Al-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. [2023] highlighted 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. |ernandez et al. (2023) introduced 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. (2033b) proposed Tree-Ring Watermarking, which embeds pattern into the initial noise vector during sampling, making the watermark robust to transformations like convolutions and rotations. Jiang al. [2023] highlighted vulnerabilities in watermarking schemes, showing that human-imperceptiblle perturbations can evade watermark detection while maintaining visual quality. Zhao et al. [203cc 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 al. [2023b] 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. [0077] introduced spikegram-ban -based method, embedding watermarks in high-amplitude kernels, robust against MP3 compression and other attacks while preserving quality. Liu et al. (2023) proposed DeAR, a deep-lcarning-bart bbssdd approach resistant audio re-recording (AR) distortions.
A.2
Adversarial Defense
The field of adversarial robustness has a rich and extensive literature (Szegedy et al. 2014, Gilmer
et al. 2018 Raghunathan et al. 2018 Wong and Kolter 2018 Engstrom et al. 2017 J. 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.
19

---

For classification models, there has been sigmificant progress in developing adversarial defenses. Techniques such as adversarial training [Madry et al. 2018], which involves training the model on adversarial examples, have shown promise in improving robustness. Certified defenses [Raghunathan al. 2018] provide provable guarantees against adversarial attacks, ensuring that the model's predictions remain unchanged within specified perturbation bound. Additionally, methods like randomized smoothing [Cohen et al. 2019] offer robustness guarantees.
A particularly relevant work for our study is Goldwasser et al. 2020], 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 LLMs, there is rapidly growing body of research focused on identifying adversarial
examples [Zou et al., 2023 Carlini et al. 2023 Wen et al. 2023a]. This research is closely related to
the notion of jailbreaking AAnriushcheeko al. 2024 Chao al. 2023 Mehrotra et al., 2024 Weil
et al. 2023 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 means enhance adversarial robustness, and since 5 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. 1998] has shown promise 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. [2020] 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. [2021) formalizes transductive robustness and proposes a bilevel attack objective to challenge transductive defenses, presenting both theoretical and empirical support for transductive learning's 's utility.
Additionally, Montasser et al. [022] introduce transductive learning model that adapts to pertur- bation complexity, achieving robust error rate proportional to the VC dimension. The method by Wu et al. [2020] 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. 2020] critique the standard of adaptive attacks, demonstrating the need for specific tuning to effectively evaluate and enhance adversarial defenses.
Transferable attacks exploit the vulnerability of models to adver- sarial examples that generalize across different models. For classification models, significant works include Liu et al. (2016), which investigates the transferability of adversarial examples and their effectiveness in black-box attack scenarios, [Xie et al. 2018), who propose input diversity techniques to enhance the transferability of adversarial examples across different models, and [Dong al.) 2019). which presents transferable adversarial examples.
Transferable Attacks on DNNs.
attacks to evade defenses and improve the effectiveness of
In the context of generative models, including LLMs and other advanced generative architectures. relevant research is rapidly emerging, focusing on the transferability of adversarial attacks. This area crucial as aims to understand and mitigate the risks associated with adversarial examples in these powerful models. Notably, Zou et al. (2023) explored universal and transferable adversarial attacks on aligned language models, highlighting the potential vulnerabilities and the need for robust defenses in these systems.
A.4 Interactive Proof Systems in Machine Learning
Interactive Proof Systems Goldwasser and Sipser 1986 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-
20

---

Verifier Games (PVGs) [Anil et al. 202T], which employ game- theorete approach to guide learning agents towards decision-maie making with verifiable outcomes. Building on PVGs, Kirchner et al. [2044 enhance this framework to improve the legibility of Large Language Models (1 (LLMMs) outputs, making
them more accessible for human evaluation. Similarly, Wäldchen et al. [024] apply the prover- verifier setup to offer interpretability guarantees for classifiers. Extending these concepts, self- self-proving models Amit mmit et al. [0244 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. 1993 Irving et al., 2018 Brown-Cohen et al. 2023] leverage interactive proof systems to enable complex decision processes to be broken down into verifiable components, ensuring reliability even under adversarial conditions.
Undetectability
Unremovability
Uniqueness
Goldwasser et al. [2022
rebust to some smoothing attacks
Classification
Adi [2018). Zhang al.
[2018]
(E)
(E)
Merrer et al.
[2017]
(E)
robust to fine tunning attacks
(F)
Christ et al. [2023 Kuditipudi et al.
2023
X
Zhao et al.
2023a
X
robust edit distance altacks only
LLMs
Tiffany Hsu
2003
E
Kirchenbauer et al.
[0033
X
X
Table 4: Overview of properties across various watermarking schemes. The symbol denotes properties with formal guarantees where proof is plausible, whereas X 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 those applied to text generated by these models.
B Preliminaries
For n E we define [n] = (I....,n) We say a boolean sequence a N + {0,1) 1] is true with frequency a E j0, 1] if
n).
Eienn a(i) 2 a.
lim inf
n=000
For two sequences a, N IR we say they agree with frequency least a e [0, 1] if the sequence (a b): + (0,1). i.. (a 2 (n) [a(n)=b(n)- is true with frequency
Learning. For set Ω. we write A(l)) to denote the set of all probability measures defined on the measurable space (Ω, F), where F is some fixed o-algebra that implicitly understood. For parameter n. denote by {0, 1)" the input space and by (0, 1} the output space. A model is function f (0, 10, + {0,1)
Definition 6 (Learning Task). learning task is a family (Ln where for every n, Ln, is an element of (A(10, 1)m) x {0, 13 10.11.""
For a distribution D,, A ((10, 1) and a ground truth h {0, 13" + (0, 1}. we define an error of I as err,,..., (J) EgnD, [fxx) * h(x)], where the index of err will often be understood implicitly and omitted in notation. For D, E A((0, 1001),),,, h, : (0, 1) R + {0, 13 we define an example oracle Ex( (Dn, hn) as oracle that samples Dn, and returns (z, h, (z)).
21

---

Interaction. When Ex(D,h) generates (z, h(x)) it is encoded as an n + 1 bit-string, because E {0, 1)"h and the label space is {0, J. For a message space = [Ma)n = 1)0,1 Jn representation class is a collection mappings {Ra where for every n, Rn M, - {0, 13 (0.1)". Thus, there is function class corresponding to a representation, i.c., for every n there is a function class Fr, which is image of R, Note that h, (which is the ground truth) may or may not be in F.. All function classes considered in this work have an implicit representation class and an underlying message space.
Computation. We work with the collection of Boolean circuits over the standard basis B2, the set of all two-bit Boolean functions. The size of circuit C' measured by its number of gates; let C denote the size of C. For circuit family C = {Cn In we say it has circuit complexity (n) if for every n, |Cll I (n)).
For a distribution Dn over 10.1)", and a ground truth h {0, 13" - 10 we denote by (FE((a.. a circuit with some 10 number of specified input gates that are initialized with samples (x,, h(=)) sampled from ~ Da- We will also by interested in interaction between circuits. When messages are exchanged between circuits we assume that there are specified input (output) gates that correspond outgoing (ingoing) messages. Also, when circuit is randomized assume there designated input gates that are initialized with random bits.
Definition 7 (Computationally Bounded Learnability). For e, :::N - (0, 1) we say that learning task L = {In is learnable to eπror é with confidence 1 - 5 and with circuit complexity S: + N by a function class F JeEN (with a corresponding representation class R.), or (c, 6, S. F))arraaellle in short, if there exists circuit family C = {Cn)neN JEN with complexity S(n) over the choice of (Dn, h2) Inns
such that for every sufficiently large n, with probabilityy
Of (P( computes m(n) bit message m. M,, such that Rm, E Fn has error at most 6, i.e. for every sufficiently large n
F ((D..hn)) be, my - An)) errp..., An (m,)))))) S e(m) 2 1 (m))-
We often abuse the notation and use fa to denote both m, as well as (m,,).
C Formal Definitions
Definition 8 (Watermark). Let L= {L be a learning task, and F {Fuin function class. Let Sp. q N + N. (0, ()) ,4,,,, 1), c, where SB(n) bounds the circuit size of B,, and (n) the circuit size of A.. g(n) the number of queries, c the risk level, probability that uniqueness holds, probability that unremovability and undetectability holds, I the learning probability.
We say that family of circuits A WATERMARK {A, n WATERMARK), Jn with complexity SA (n) implements a watermarking scheme for with frequency a, denoted by
A WATERMARK Ea WATERMARK (L,F, C, SA L.
if the following is true with frequency a over parameter n. An interactive protocol in which first (Da, hn) ~ Ln and then A WATERMARK computes x). f {0, 13"h + {0, x E (f0, 1)m))((m), and
B, outputs y = (f(xx)), {0, 1346))) where f is sent using the representation R,, satisfies the following
. Correctness (f has low error). With probability at least /
Sc
Uniqueness (models trained from scratch give low-error answers). There exists circuit B,, of size SA (n) such that with probability at least
crT(x, < 2e.
We will not specify the sample complexity explicitly. In this paper, we focus only on circuit complexity. The sample complexity is an important parameter to analyze and we leave it for future work. We emphasize that the circuit complexity upper bound the sample complexity.
22

---

Unremovability (fast B, give high-error answers). For every circuit B, of size at most (n) with probability at most s
err(x, S 2e.
Undetectability (fast B,, cannot detect that they are tested). On average over (D hn)) ~ In. distributions Dz(") and x A, WATERMARK are i-indistinguisabbee for class of circuits Bn of size at most SB(n), i.e., for every circuit B,, size most SB(n) returning one bit,
P (Dnnhin x (z (( A AATEENAA [J, x') = (P..),,...,)))..((f.. WATHMARK [B(,x)= =
Definition (Adversarial Defense). Let = { be a learning task, and (F [Fn]n n a function class. Let SA, SB.q IN + N, E E (o, 20. 1, s E (0, 1), with < c, where SA bounds the circuit size of A.. and SB the circuit size of B,, q(n) the number of queries, the error parameter, the completeness, the soundness, and the learning probability.
We say that family of circuits DE [BDEEENSE), )n with complexity SA(n) implements adversarial defense for with frequency a, denoted by
B DEFENSE Eo DEFENSE (L,F, ,, Sp,K,,,,,)
if the following is true with frequency a over parameter n. An interactive protocol in which first (Dn, hn) ~ Tin BDEEENSE computes f 10, - {0, 1}. A, replies with x (J,),,
x E (f0, 1 prrjo(n,, and B DEFENSE outputs b = DEPENSE (f,x), b E {0, 1}, satisfies the following:
Correctness (fn has low error). With probability at least
err(f) S 6.
Completeness (natural inputs are not flagged as adversarial). When x ~ Dy(n) with probability at least
b 0.
Soundness (adversarial inputs are detected). For every cireuit A, of size at most SA (n), with probability most
erT(x, f(x)) > 7e and
Definition 10 (Transferable Attack). Let L {ILm) n be learning task and == (FF) In a function class. Let SA, SB, q : IN- - N, (0, 1). and c, E (0, 1), with where S (n) bounds the cireuit size of A., and Sy the circuit size of B,. (n) the number of queries, c the error parameter, the transferability probability, and s the undetectabilityy probability.
We say that family of circuits A TRANSFATTACK { n TRANSPATTACK] } with complexity SA imple- ments a transferable attack for I, with frequency a, denoted by
A TRANSFATTACK E. DEFENSE (I, F, F, SA SA,,
if the following is true with frequency
parameter An interactive protocol in which first (Dn, ~ Ln. A TRANSFATTACK computes x (40, 1 1()))())), and B, outputs (x),,)
y (10, 1) ))(()) satisfies the following:
Transferability (fast provers return high-error answers). For every circuit B,, of size at most SB(n), with probability at least
err(x,y) > 2E.
Undetectability (fast provers cannot detect that they are tested). average over (Dn, h.)) ~ Ln, distributions x ~ Dz(a) and x = A TRANSPATTACK are --indistigguisablle for every circuit B,, of size at most (n)n), i.e.,
(Lnn (x') = 0] P( Bx 0/
23

---

D Main Theorem
Before proving our main theorem we recall a result from Lipton and Young 1994a about simple strategies for large zero-sum games.
Game theory. A two-player zero-sum game specified by a payoff matrix G. 9 an r x matrix. MIN, the row player, chooses probability distribution P1 over the rows. MAX, the column player, chooses probability distribution p2 over the columns. A row i and a column j are drawn from P1 and p2 and MIN pays Gij to MAX. MIN tries 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 disadvantage. Such a pair of strategies also known as a Nash equilibrium. The expected payoff when both players play optimally is known as the value the game and denoted by VGG).
We will use the following theorem from Lipton and Young 1994a), which says that optimal strategies can be approximated by uniform distributions over sets pure strategies of size (llog())).
Theorem 4 (Lipton and Young [994a]). Let & be
c payoff matrix for two-player zero-sum there exists a multiset of pure strategies for the MIN (row
game. For any y E (0, 1) and log(e)
2n²²
player) of size such that a mixed strategy pı that samples uniformly from this multisel satisfies
max Em(i)e S V(G) + 17(9max 9min),
where Gmars Gmin denote the maximum and minimum entry of g respectively. The symmetric result holds for the MAX player.
We are ready to prove our main theorem.
Theorem 5. Let ( 5 (0, :8:
N. For every learning task IL {In}n
SSm) for every family
learnable error with confidence and circuit complexity O
[og(S(n))
of function classes F= [Fa) every query bound g(n) such that [og]S(m]] at least one of the three
(3(m)
Mm((n) + 4(1)) n))
SS(n) ,1
10
21
19
WATERMARK
L, L.F,
log(S(n))
24'
c=
24
24
S(n)
1
13
11
DEFENSE
L, cq log(S(n))
(O(((n)),
48
24"
24
3
19
TRANSFATTACK
L, (().
24
24
exists with frequency
Proof. Let E (0, 1) q N + N be query bound. Let T. be learning task learnable to error with confidence 8 and complexity S(n).
We will consider every separately and show that for every n, one of the three schemes exists. This automatically implies that one of the schemes exists with frequency least J.
Let s(n) =
V ((m) [o]]
where the exact constants will be determined later. Let Candidate (n)
be a set of s(n)-sized circuits computing (f.x), Recall that the execution of a A,, E (nr(n) proceeds by first sampling from Ex(D,, li,) and providing these samples as inputs to A, and then running A, to obtain + q. bits. The first bits are interpreted as representation of (according to
RR,), and the following consecutive blocks of n bits each are interpreted as q elements of {0. 1)". Similarly, let Co (n) be set of s(z)-sized circuits accepting input (f x) and outputting (y. b).
24

---

where y E bE 10. Formally, this is set of circuits with up to s(n) imput gates and + 1 output gates. We interpret (n)(n) as candidate algorithms for a watermark, and Ep (n) as candidate algorithms for attacks on watermarks.
For every define zero-sum game Gn between A, (n) B, E CD (n) The payoff is given by
PiPall (t BB: (aPan eer(f) > or erI(x, y) I 2e or b - 1]
(A,. Ba) = (P..tha))otn:l///)))) A
+ P (D., A ((Paash)) xD . BB (inii)) (err(f) > c or (err(x,y) = 2e and b = =
1
2
where A, tries to minimize and B, maximize the payoff.
Then the number of possible circuits is bounded by
em S (3s(m)))a(m) S 23((m) log(s()))
because every internal gate of circuit is of AND, OR, and NOT, and is connected gates of at most s(n) choices.
Applying Theorem 4oo Gn with 7 2 we get two probability distributions, p over multiset of pure strategies in Con and r over a multiset of pure strategies in Eo that lead to 2 --approximate Nash equilibrium. The size k(n) of the multisets is bounded
knn) - 2 log ((Cm)) l)
I (n(nn) log( (n))).
Next, observe that the mixed strategy corresponding the distribution p can be represented by circuit of size
k(n) s(n) O(lo((((n)))
$ {s² (s(n))
By equation
< (n).
because we can create a circuit that is collection of k(n) circuits corresponding the multiset of p. where each one is of size s(n) with additional gadgets of size (llog(k) activating the corresponding gate depending on the randomness determining strategy. This implies that p can be implemented by S(n) (nizes circuit. The same holds for r. Let's call the strategy corresponding to p. A and the strategy corresponding to r, Nass.
Consider cases:
Case G NASH NASH N 21
Define DEFENSS to work follows:
(s(n)
1. Simulate the circuit of size O
Ln that learns f, such that [og[S(m]]
(er(f) sc] 1 1
P (Daahh, 1
48"
2. Send ff to An-
3. Receive x from An
4. Simulate b) = B NASH (f, x).
5. Return 1/ 1 or dxf(x),)) > 3e q(n) and b' otherwise,
where d(.,)) is the Hamming distance. B DEFINSE can implemented by circuit of size ((S())) because it simulates circuit of size O (S(m)
[n)) then simulating BNASH of size S(n), and
computing predicate d( d(f(x).y) > 3eg, which can be done in size log(g(n)).
25

---

We claim that we have:
DEFENSE
(n,
[og(((n))
Vs(n)
13
11
(2)
48'
24
24
Assume towards contradiction that completeness soundness of B B defined in Definition does not hold.
If completeness of B DEPENSE does not hold, then
P xm 6' =
13
(3)
24
Let us compute the payoff of An, which first runs f +- Ln (i. (where L,, is the learning circuit) and sets DD, in the game G., when playing against BASH
g(A,, NASH
P (Da (Danha)LLa
1
eer(f) > e coeer(xx,) < 2. or b' = =
2
(fx)) A tar
err(f) > oo (err(x,y) < 2c and R' 0)]
+
IP Pn. A J f+ AB((Pn.hn))
xnDD
8 + P (Da k,, fLL Bi
(er(x,y) < 2e or b'
X~D!
47
+ IP (D (Dn.hn)aLm.
crT(x, - 2e and =0
Def. of A,, DEFENSE P eem(S) Se) >
2
48
f+ L Ph))
X=D
1
13
24
By equation
48
2
2
38
48
((ANASH NASH), &
where the contradiction is with the properties of Nash equilibria. Assume that A, breaks the soundness of DEFENSE which translates
11
P(D err(x, f(x)) 7e and b = 0 and d(f(x).))) > 3eq X=A=(f)
>
(4)
24
26

---

Let A first simulate
x- Ln Ea(Da,ha) then runs x An(s), and returns (fxx). We have
((A N
P Ma (fx))=
err(f) > e or errr)(x,))) & 2c or =
2
err(f) > cor (err(x.y= S and D' = =0]]
+ PP (Dnninndin
/+A x~Da
err(f) orer)(x,)) S 2E or -
2
x=A,(f))
err(f) or (e)r(x,y) S 2e and D' = 0]]
+ P. (Da.li))ann ft f(-I.a(,
By def. of A
2
X-DD
1
- 11
1
+
By equation
37
48
S (A, NASH A BAA"),,
NASII
where the contradiction is with the properties of Nash equilibria. Thus equation 2 holds.
Case (A NASH BASH)) have
<
19 27
Consider B,, that returns (f(x), b) for a uniformly random b. We
err(f) se)) + PeDD,,hnnnLn 1 1 IP (h..,,n) JoLn GA NASH B.) 2
1 eer(f) S 2
I + NASH
ft Nosh
because when x D and err(f) S the probability that err(x, y) I 2e and 6 is }.2 and similarly when f- A NASH then the probability that b 1 is equal 1. The assumption that Gn (A Nash B,) 24
and properties of Nash equilibria imply that IP (n)....)) fr
S c|
This implies that correctness holds for A Nush with /
10 24
Next, assume towards contradiction that unremovability A NASH does not hold, i.e., there is B, running in time o ( input (J, returns (J, Then by definition of 9n. G.(NAAAH B¹,) > contradiction &.
such that Pf(er((.y) I 2c] Consider B', that on
19 which 21'
Next, assume towards contradiction that undetectability of NASHI does not hold, i.c., there exists B, such that it distinguishes x ~ D2 from x +- A n
NASH with probability higher than 19 Consider 21'
B', that on input (f.x) x) returns B,,) x)) Then by definition of G... G, (A NASH BB,) 21' which is contradiction &.
19
There are two further subcases. If A A NASH satisfies uniqueness then
A NASH E WATERMARK (L), SS()
10
21
19
log(S(n))
.
24
24
3
24
If A NASH does not satisfy uniqueness, then, by definition, every succinctly representable circuit B, of size o (v ((())) log(S(n))) satisfies err(x,y) < 2s with probability at most 24
21 Consider the
following An. It computes (f. x) +- Nash ignores f and sends x to B,,- By the assumption that uniqueness satisfied for A NASH transferabilityy of Definition holds for An with 3 Note 24
"Formally B. receives input (f, x) and not only
27

---

that 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
A NASH E &TRANSFATTACK (Ln) n
3 19
24'
24
E Fully Homomorphic Encryption (FHE)
We include a definition of fully homomorphic encryption based on the definition from Goldwasser al. [2013]. The notion of fully homomorphic encryption was first proposed by Rivest, Adleman and Dertouzos Rivest et al. (1788] in 1978. The first fully homomorphic encryption scheme was proposed in breakthrough work by Gentry in 2009 Gentry (009)] A history and recent developments fully
homomorphic encryption is surveyed Vaikuntanathan 2011
E.1 Preliminaries
We say that a function f is negligible in an input parameter X, if for all d >> O, there exists K such that for X >> K, (()) < X-d, For brevity, we write: for all sufficiently large X, ((A) neg)(A). We say that a function is polynomial in input parameter X, if there exists polynomial such that for all X, fA) S p(A). We write f()) = poly(A). A similar definition holds for polylog For two polynomials p, 9. say
if for every À E N, p(A) q(A).
When saying that Turing machine A p.p.t. we mean that A non-uniform probabilistic polynomial-time machine.
E.2 Definitions
Definition 11 (Goldwasser al. 2013). A homomorphic (public-key) encryption scheme FHE is quadruple of polynomial time al algorithms (FHE.KEYGEN, FHE, FHE. FHE.EVAL) as follows:
FHE. KRYGE(1))) is a probabilistic algorithm that takes as input the security parameter 1 and outputs public key pk and secret key sk.
FHE.ENc(pk, {0, 1}) is probabilistic algorithm that takes input the public key pk and an imput bit x and outputs a ciphertext th.
THE.DECC )b) is a deterministic algorithm that takes as input the secret key sk and a ciphertext vi and outputs message xt E (0,
FHE. C, thi, .h....., thn) is deterministic algorithm that takes as input the public key pk: some circuit C' that takes bits as input and outputs one bit, as well as n ciphertexts 1/....,, v/.- It outputs ciphertext thc.
Compactness: For all security parameters there exists a polynomial p(-) such that for all input sizes n, for all T1,..., Zn, for all C, the output length of FHE, FHE,EVAL is at most p(n) bits long.
Definition 12 (C-homomorphism, Goldwasser et al. (203)). Let C'
{CaNee be a class of boolean circuits, where On is set of boolean circuits taking n bits as input. A scheme FHE is C-homomorphic if for every polynomial na-), for every sufficiently large security parameter X, for every circuit C Cn. and for every input bit sequence T1, -1,...,,f, Fn, where n()),
(pk. sk) <- FHE. KEYGEN1)) vi t THE.ENCiip x;)) for i 11..100. & + (vAL C. vi.... .,.....,. +
P
negl(A),
FFC v) # C(i,,...,
where the probability is over the coin tosses of Definition 13 (Fully homomorphic encryption). A scheme FHE fully homomorphic if it homomorphic for the class of all arithmetic circuits over G2(.).
and ENC.
28

---

Definition 14 (Leveled fully homomorphic encryption). A leveled fully homomorphic encryption scheme is homomorphic scheme where FHE. receives an additional imput 1st and the resulting scheme is homomorphic for all depth-d arithmetic circuits over (2).).
Definition 15 (IND-CPA security). A scheme FHE is IND-CPA secure if for any p.p.t. adversary A,
(pki sk) <- FHE, KEYGE(()))N(1) A(pk, FHE.ENC((p, 0)) = =1]+
- -P [(pkk,sk) sk) < FHE. (EYGENEYGNN(1) A(pk, FHE.ENC(pk; 1)) = -] =neeg()))))))
We now state the result of Brakerski, Gentry, and Vaikuntanathan [Brakerski et al. 2012] that shows a leveled fully homomorphic encryption scheme based on a standard assumption in cryptography called Learning with Errors [Regev] 20055::
Theorem 6 (Fully Homomorphic Encryption, definition from Goldwasser al. (2013). Assume that there is constant O < é < such that for every sufficiently large E, the approximate shortest vector problem gapSVP in dimensions is hard to approximale to within 20(E)) factor in the worst case. Then, for every nt and every polynomial d = d(u), there is an IND-CPA secure d- leveled fully homomorphic encryption scheme where encrypting n bits produces ciphertexts of length poly(n, X, d' d' the size of the circuit for homomorphic evaluation of function f is size(Cr) poly(n, X, / and its depth is depth(Cy) poly(log n. log d).
F Existence of Transferable Attacks
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 given input. This can be understood as the case of generative tasks. More concretely, we assume that for the input space X, the output space Yn instead of {0, 1}. It will always be the case that X₁ and Yn, are equal to {0, 1)p(n) for some polynomial p. For distribution Dn, over X, we call a function h Xr x Vn + {0, 1} an error
oracle if the error of a function f Xn + Yn is defined as
err(f) Enw (1,,, (x))),
where the randomness of expectation includes the potential randomness of f. The example oracle Ex provides access to samples (x, y) E Xn x Yn, where x Dn and y E Vn is some y such that h(x, v) O.
The following learning task will be crucial for our construction.
Definition 16 (Lines Circle Learning Task IL.). We define L {L, hm. For every we define
X₁ = {0. 1)3" and associate Xr with vertices of a 2n regular polygon inscribed in the unit circle {xr E IR2 || = 13. The output space is (-1, +1} for all n. Let H == (l.w w R2 ||w||2 where I,,. (x) := sgn( (we ). For every n, let Lg be the distribution corresponding to the following process: sample fe U(H), return (U,,,, h..) Note that H has VC-dimension equal 2 so I is learnalle to error E with ( samples for every and every
1}.
Moreover, for E IN define B." (a) == {o Xn [[x w)l S sa).
Lemma 3 (Learning lower bound for L.). Let n E N. Let Ln be learning algorithm for L;
(Definition 16 that uses K samples and returns classifier f Xn + [-1,+1]. Then
1
< 3
P P(D.,...--... LACD.
PoND,, + (z)) <
2K
100
Proof. Let n E N. Consider the following algorithm A. It first simulates Ln on K samples to compute f. Next, it performs a smoothing of f. i.e. computes
(1, if (IP== = +1] > Pe --1]
fn(z) = -11 otherwise.
Note that if err(J) S 1 for ground truth A. then for every E Xn \ (2 we have (n) To (x).. This implies that A can be adapted to an algorithm that with probability finds w' such that
[[( w S en((f).
29

---

K, 2) 9) samples such that with probability 8 1ood returns f' such that 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 TOO locates w up to angle 2K
Consider any algorithm A using samples. Probability that A does not see any sample in B (2m1) is least
(1 - 4n) 2 (1 ((1-47) 41)
ink
1
4n
2c
which is bigger than 1
3 if we r) 2k' But note that if there sample in B (2mr) then 100,
A cannot locate to up to v with certainty. This proves the lemma.
Lemma (Boosting for ) Let n (0. 4). N. L,, be learning algorithm for L, that uses K samples and outputs J Xn - (-1,+1] such that with probability 5
-n- U (1R (z) + hw (x)] v,
(5)
where H. as defined earlier (hw w E IR,, || 1}. Then there exists a learning algorithu L' for L., that uses max
P Pu..U(())---xxx))1 o (w)) S 4mp.
Proof. Let IN. L' first draws max K, samples Q and defines g X, + (-1,+11, as follows, g maps to -1 the smallest continuous interval containing all samples from Q with label -1. Similarly g maps +1 the smallest continuous interval containing all samples from Q with label +1. The intervals are disjoined by construction. Unmapped points are mapped to L. Next, L' simulates L. with K samples and gets a classifier f that with probability satisfies the assumption of the lemma. Finally, it returns
((x) = [g(r), if)()) #1 (f(x), otherwise.
Consider 4 ares defined as the arcs constituting 8 (2mr) divided into 2 parts each by the line {z E 2 (w, x) 0}. Let E' be the event that some of these intervals do not contain a sample from Q. Observe that
P[A] < 4(1 n)
1000
By the union bound with probability 5 definition of J' this gives the statement of the lemma.
1000 f satisfies equation 5 and E does not happen. By
Theorem (Transferable Atack for Cryptography based Learning Task). There exists a learning task L {I>>>> x and a function class F = (Fx}x such that for every N N where 1/c(A) is lower-bounded by sufficiently large polynomial and upper-bounded by some polynomial the following holds.
1. IL is (e,6 1. 21, F) learnable. F)aaaa-llabbllleee
10
2. IL is not (c,5 1 - -lerraablle
3. There exists a circuit family
(Ax)x such that
L. (LF,,(A), q(A)
16 <(A]
SA (A)
10a
A E TRANSFATTACK
SB(A) 10=2 =
g
= neg((>)
10
Proof. The learning task is based on IL {1L)), from Definition 16
30

---

Setting of Parameters for FHE. Observe that by assumption of the lemma p S 1/c I r, for some polynomial r, and a polynomial p that we will define later. Let FHE be a fully homomorphic encryption scheme from Theorem 6 Let s(n, X, d) the polynomial bounding the size of the encryption of inputs of length n with security as well as bounding the size of the circuit for homomorphic evaluation, which is guaranteed
We will use the scheme for constant leveled circuits d = O(1).
to exist by Theorem 6 Let (0, 1) and p be a polynomial such that
s (n A. d) S (n p(A)).,
(6)
which exist because s is a polynomial.
We define n(A)= (
(A) for the length of inputs in the FHE scheme. Observe that for every À
s(n(A), A, d) S (P(A) p(A))
By equation 6
(
1 v(t)
By c(A) E
(7)
<(A)ui2
(((A)
Learning Task. The learning task will be parametrized by x, i.e IL = (IA
Let À E I. We define D := (Dioksk)) Hipksky, H, := {1 (f(kkssk.w) Jipkssk. (for D ((pk.sk) and h (okskw) to be defined later), where they indexed by valid public/secret key pairs of the FHE and w {x E R22 ||e|| = 1}. Let Lx be defined as corresponding to the following process: sample (pk.sk, w) ~ FHE. KEYGEN(1)) x U(x IR?
X
|||||| = 1}), return (Dipk.sk) // (ophskw))
For valid (pk.sk) pair we define D(pkak) as the result of the following process: I ~ U10, 1)m(AA), with probability 1 return (0,z, pk) and with probability 1/2 return (1, WW..HEC(ppk........ 2), pk), where the first element of the triple describes if the x is encrypted or not. Formally, in the case that the first element of the triple is one needs to add padding of size s(n(A), d) n(A) that descriptions have the same size in both cases 13
|| 1} we define ((pkskw))BB. xr pk), y) result of the following algorithm: if b = 0 return (m)=yy otherwise let TDEC <- (HE.DECC(S v)) VDEC <- FHE.DEC(sk, y) and if TDEC MDD + 1 (decryption is succesful) return I (xmuc) and return 1 otherwise.
For valid (pk,sk) pair and w E {ar E R
Note 1 (12(2) )-smppls learning lower bound.). By construction any learner using K samples for LA (for any X) can be transformed (potentially computationally inefficiently) into a learner using K samples for ( (Definition 16) that returns a classifier of the same error. This, together with lower bound for learning from Lemma 3 proves point of the lemma.
Definition of A (Algorithm T. Ax draws N(A) samples Q = {(Obs, Ti pk), vi) Bi) for
((A) == 900
((A)
Next, A chooses subset QCLEAR S QQ of samples for which b, 0. It trains classifier f (-)
sgn( ()) on QCLEAR by returning any fwr consistent with QCLEAR. This can be done in time
900
900
N(A) (AA) < (A)
(18 (1)
by keeping track of the smallest interval containing all samples in QCLEAR labeled with + and then returning any fw' consistent with this interval.
Note 2 (0(zFz) )time learning upper bound.). First note that Ax learns well, i.e,, with probubility at
800
least 1- (1
=(A) 100
1
1000
(xT(()
[[w w <
100
Noot that this setting allows to represent points in (x E R22 ||æ]|a = 1} up to 2-x1/((x) precision and this precision is better than F[Aj for every polynomial r for sufficiently large X. This implies that this precision is enough to allow for learning up to error e, because of the setting e(>) 2 A
Note that the domain of the distributions is not (0. 1 i.e. XA (0, (0,
31

---

Algorithm 1 (E hx),
I: Input: Access the example oracle Ex(D>, (i)), where (Dx, 122 Tl error level and the security parameter X.
N,
2: N 9000/00)), 11///(A)
3: Q= {((b,, pk), JEIN (DA)
(N) ii.. samples from Dx
4: QCLEAR = {((b, 2. pk), =Q:b=0)
QCLEAR C Q of unencrypted x's 5: fwr() = sgn((w', ,)) + a line consistent with samples from QCLEAR sm Xn. +1}
6: ( ~ ~ (ZZ(())
7: S ~ U((2a(All))
P- S S [a())] uniformly random subset
8: EBNDI
9: for E (q(A) - S||] do
10: LBND U(B (2T(E(A) + 10U ))
<(1)
JBND is close to the decision boundary of fwr
EBND == EBND U (FCEE TBND)}
12: end for
X :: {(0,./.pk) pk) [a)) () f(1,2', .k) ) x' E EEND
14: Return X
Moreover, for (x)) can be implemented by a circuit Csar that compares x with the endpoints of the interval. This can be done by a constant leveled circuit. Moreover Csu, can be evaluated with EVE. in time
10
sizelCsyp (on,))s((A),))) S 10n s(n(A), < 10p (A)s((()))) 3
where the last inequality follows from equation 7 This proves point of the lemma.
Next, A prepares x as follows. It samples ((A) = _16
<()) points { from {0, 1]m(A) uniformly
at random. It chooses uniformly random subset S S [(()]. Next, Ax generates g(A) - [S] inputs <(A)
using the following process: TBND (B n()) (2T(c(A) + 100 ))) (EBND is close to the decision boundary of fwr), return FHE,ENC(pk, WBND). Call the set of q(A) |S] points FRND A defines:
= {(0,,/.pk) i e [ql \ S} {(1,z',ph) x' EBSD].
The running time of this phase is dominated by evaluations of FHE.EVAL, which takes
16
16
((A) ((n(A), A. S
22 S
(10)
<(A)
(22(A))
where the first inequality follows from equation we get that A can be implemented by a circuit of size (A)(
7 Taking the of equation (8) and equation (IO) 10a
AĄ Constitutes a Transferable Attack. Now, consider B of size SB(A) (Ąх By the assumption SA( r(A), which implies that the security guarantees of FHE hold for B
We claim that x is indistinguishable from Dioksk) for Bx Observe that by construction the distribution of ratio of encrypted and not encrypted x's in x is identical to that of D(pksk) Moreover, the distribution of unencrypted z' is identical that of A by construction. Finally, by the IND- CPA security of FHE and the fact that the size of B is bounded by some polynomial in X. FHE. ENC TBed) is distinguishable from & ~ X,,, FHE, ENC(EN x.) with advantage at most (xg)(X). Thus undetectability holds with near perfect soundness
negl(A).
Next, we claim that By can't return low-error answers on x. .5
Assume towards contradiction that with probability
TOo P W [|= [f(x) # (x)) S 10c(A).
(11)
UB" (B (2mc())
Note that need security of FHE in the nonuniform model of computation.
32

---

We can apply Lemma to get that there exists a learner using 100ca(A) 4 100 returns f' such that
1
+ y
c(A)
90c
1
samples that
with probability
IP "-UU(EERR 1111==1)) (x)) * Nw (A). x=U((f01)"0))
(12)
Applying Lemma to equation
12 we know that
40c² 2
2( (x)
which is contradiction. Thus equation with probability 100
11 does not hold and in consequence, using equation 9
10
IP W-U( [|=1|==13), [f(x) * (x)) 2 10c(A) 2 7c(A),
(13)
14
where crucially x sampled from U(B and not (B ). By Fact we know that |S|| with probability at least
((A)
((A)
1 - 2e
2e A<(A3
1000
Using the setting of (A) equation (13) that with probability at least 1 1/ the error err(x. y) is larger than 2e(A).
16_ and applying the Chernoff bound and the union bound we get from
c(Aj
Note 3. 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 Delear then Ax would see only samples of the form
(FHE.ENC(z). FHE.EN(())
and would not know which of them lie close to the boundary of hw. and so it would not be able to choose tricky samples. A would be able to learn a low-ervor classifier, but only under the encryption. More concretely, Ax 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 However, would not be able to, with high probability, generate FHE. (HE,,NC(()) for close to the boundary it would not know (in the clear) where the decision boundary is.
If there was no Dese then everything would happen in the clear and so B would be able to distinguish that appear too close the boundary.
Fact 1 [ChernoffHooefdding Let ,I,...,Xp be independent Bernoulli variables with parameter p.
Then for every 0 < <
2e 2
P
X p
> E
and
-0- -ue
P
X1 < (1 c)p
<e
k
i=1
Also for every 8 0
P
Σ
X, > (1+
- t
Se
33

---

G
Transferable Attacks Imply Cryptography
G.1 EFID Pairs
The typical way in which security of EFID pairs is defined, e.g., in [Goldreich] 1990]. is that they should be secure against all polynomial -ime algorithms. However, for the case of pseudorandom generators (PRGs), which are known to be equivalent (in the standard definition) to EFIDs pairs, more granular notions security were considered. For instance, in [Nisan] 1990] the existence of PRGs secure against adversaries running in time bounded by a fixed, in contrast to all, polynomial, was studied. a similar spirit, we consider EFID pairs that are secure against adversaries with fixed circuit complexity bounds.
Definition 17 (Total Variation). For two distrbutions Do, D1 over finite domain {0, 1}" we define their total variation distance as
DiD
1 D (z))] =E(0,11
Σ
Definition 18 (EFID pairs). For parameters 77, - (0,1) and circuit complexity bounds S.S" IN + N we call a pair of ensembles of distributions (D) (D (n,n,, D = (DD) over
domain X' {n an (S, S", 6)-EII pair if for every
1. The circuit complexity of sampling D and D is at most S,
2. For every (DD, Db) 2 (1))..
3. For every Do D are ((n) diiiiiiiiiti for circuits with complexity S'(n).
Observe that Definition 18 is a generalization of the standard definition. Indeed, for every EFID pair (D", ( according to the standard definition there exists an inverse polynomial function and polynomial S such that for all polynomials there exists a negligible function ó such that (D", D an (8,5", n, -)-FFD pair.
G.2 Transferable Attacks imply EFID pairs
Theorem (Tasks with Transferable Attacks Imply EFID pairs). For every e E (0, 1). e N, SA, SB N +N N such that SA S SB, every learning task L learnable to error with confidence p and circuit complexity SA, every c, E (0,1) if
TRANSFATTACK (,, SB.C, SA,
exists with frequency then there exist SkA S/ : NN- + NN that agree with SA and SB respectively with frequency 3/2 and there exists
(SA. Sn 1 (p-c-1---8)
-FFID pair.
Proof. Let e, SA, Sp, C,
S. 8, {An)n be family of circuits certifying that Transferable Attack exists with frequency for LL.
L be as in the assumption of the theorem. Additionally let A
For every define D Dj, where recall that q is the number of samples A, sends in the attack. Define D), to be the distribution of x == An. Note that (X,)*.
Let a: N + {0, }} be sequence certifying that Transferable Attack exists with frequency 3. Let be such that an)) 1. Observe that Do Dj are samplable with circuit complexity S (n) because A, complexity bounded by SA (n). Secondly, D n: D) are ş g-indistinguishable for SB SBs(n--izzd adversaries by undetectability of A,. Finally, the fact that D D) are statistically far follows from transferability. Indeed, the following procedure accepting input x E (10, 1)")² is distinguisher:
Run the learner (the existence of which is guaranteed by the assumption of the theorem) to obtain f.
34

---

2. y:= f(x).
3. If eer((x,)) 2e return 0 otherwise return 1.
If x D = DD then err(f) with probability p. By Fact and the union bound also know that err( y) 2e with probability p e- 3 and so, the distinguisher will return with probability p p- e 8. On the other hand, if x D A know from transferability of An that every algorithm running in time SB(n) will return such that err(x.y) > 2e with probability at least c. By the assumption that SB also. Consequently, the distinguisher will return with probability at least in this case. By the properties total variation this implies that (DD (,) 2 ( + - 1
SA (n) we know that err(x, f(x)) > 2e with probability least
We define pair of families of distributions Do, D and functions S' Sgg follows. For every such that a(n) every sich that a(n) = 0 we define 5% = Dg for the smallest &o > such that a(k) = 1, and S'A (n) SA (k) And analogously for D and S/B-
we define D D D (n()) = S^ (n). S% = SB (n). For
Simple verification yields that D", D, an (S' -
-FFID pair.
Note 4 (Setting of parameters). Observe that p x 1, i.e. it is possible to almost surely learn f in time SA such that err(f) S 6, c a constant, q = (2 then yj in the parameters for the EFID is constant and so LDD", D is a constans.
Note 5. We want to emphasize that our distinguisher crucially uses the error oracle in its last step. So is possible that it not implementable for all circuit complexity bounds!
H Adversarial Defenses exist
Our result is based on [ooldassser et al., 2020]. Before we state and prove our result we give an overview the learning model considered [Goldwasser et al. 22200. The authors give a defense against arbitrary examples in a transductive model with rejections. In contrast, our model does not allow rejections, we require indistinguishability.
H.1 Transductive Learning With Rejections.
In Gollwasser al. 2020] the authors consider model, where a learner receives training set of labeled samples from the original distribution (xp. = h(xx)), ~ D yD E [-1,+11] where h is the ground truth, together with to compute yr E corresponding. 2.
xy (40, 1)")", Next, uses (XD.Yp. xT) where D represents that L abstains (rejects) from classifying the
Before we define when learning is successful, we will need some notation. For q E N E ((0,1)")), E (1) define
enr(x, y)
1 9
Σ ic(n)
1 M (f
[ly) ii [el: : = =0}1
which means that we count (x, y) E (01,1,x as an error if is well defined on x, y not an abstantion and h(x) # y.
Learning is successful if satisfies two properties.
* If XT ~ D9 then with high probability err(x,, yT) and [(yr) are small,
* For every Xy E ({0, 1) with high probability err(xr, yr) is small
Note that, crucially, in this case D(yr) might be very high, e.g., equal to 1.
35

---

The formal guarantee of result from Goldwasser et al. 2020 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 associate the learner L from TLR with B in our setup, and the party producing Xy with A in our definition. First, in TLR, B does not send f to A. Secondly, and most importantly, we do allow B to reply with rejections (0) but instead require that B can "distinguish" that is being tested (see soundness of Definition 2 Finally, there are no apriori time bounds on either A or 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.
H.2 Formal guarantee for Transductive Learning with Rejections (TLR)
Theorem 5.3 from Goldwasser et al. 2020 adapted to our notation reads.
Theorem 9 (TLR guarantee Goldwasser et al. (2020 )) For any N E N, (0, 10, E H and distribution D over {0, 1)"::
P Xx DDN V XT E {0, 13nN : eer((x, f f(xT)) S D( Se 21-
where e* V 2d log (2N) Nv log (:) and f REJECTRON(XD. h(xD), xT, {0, 1)ah + +1,, )) and d denotes the VC-dimension on H. REJECTRON is defined in Fig- ure in GGoldwassr et al. 2020
c.), where f
REJECTRON is an algorithm that accepts a labeled training set (xp, h(p))) and a test set XT and returns classifier f. which might reject some inputs. The learning successful if with high probability f rejects a small fraction of D and for every XT E {0, 1 the error on labeled x's in X7 is small.
H.3 Adversarial Defense for bounded VC-dimension
We ready to state the main result of this section.
Lemma (Adversarial Defense for bounded VC-dimension). Let (Ha }n I be a family of hypothesis classes such that there exists polynomial p such that for every n, Hn has VC-dimension bounded by p(n). There exists a family of circuits B = [Ba)n such that for every L satisfying for every n that the support of the marginal of Le is contained in Has i.e, the ground truth sampled from IL are always in H. such that for every sufficiently small e,
B E1 DEFENSE [L poll(n) (_cy)))
3 SA 00, SB = =poly (") 101---1-------- 1-1--yy)-----------------
Note that, by the PAC learning bound, this is a setting of parameters, where B has enough time to learn classifier of error By slightly abusing the notation, write S' oc, meaning that the defense is secure against all adversaries regardless of their running time.
Proof. The proof is based algorithm from Goldwasser et al. 22020]
Construction of B. Let E (0, n E N, d(n) be the VC-dimension of Hn and
ddlog((d)
N
Let == == N. First, B, draws N labeled samples (XFResH, h ((FFFss)). Next, finds f E H consistent with them and sends f A. Importantly this computation is the same the first step of REJECTRON.
Next, B receives as input E (10, 1) from A. B. Lete
N log (2N) + _/4 log (t). Next B runs f = REJECTRON (presn hi XFResH), x, e,") )²), where REJECTRON is starting from the second step of the algorithm (Figure [Goldwasser et al. 2020).. Importantly, for every E (0,1)" 1)", if ('(x) # [ then f(x = =f'(x) (x). In words, J" equal to everywhere where f' does not reject.
Finally B returns if (x)) f and returns 0 otherwise.
36

---

B is a Defense. First, by the standard PAC theorem, with probability at least err(f) $ This means that correctness holds with probability /
Note that with our setting of N,
Theorem guarantees that
if x D then with probability least 1 6,
(xf(()) S c
2
which in turn implies that with the same probability returns 0. This implies that completeness holds with probability 1 --c.
for every x (10, () with probability at least 6,
emr(x, (x))) S
To compute soundness we want to upper bound the probability that f(x) 2 TG and = 0. By construction of B if b 0 then (x) S 2c which means that with probability at least -
3
crr(x, y) S + e < 2e or
2e
3 2
This translates to soundness holding with s = e.
REJECTRON can be implemented by circuit of size polynomial in N and makes O calls to an Empirical Risk Minimizer on H (that we assume can be implemented by a circuit of size polynomial in d), which implies the promised circuit complexity.
I Watermarks exist
Lemma (Watermark for bounded VC-dimension against fast adversaries). There exists family of hypothesis classes {Ha such that for every d, Ha has VC-dimension d and a family of distributions (Da}a such that for every e E ( (10000, 1) there exists a family of circuits = {Aa}d and a family of function classes F for which the following conditions hold. For every learning (Teata that for every d samples Da always and ha Ha.
L. F, -
SA = 0
A E WATERMARK
ST
d 1-1
2
56
100
100
100
Note that the setting of parameters such that A can learn (with high probability) classifier of error but B is not able learn low-error classifier within its allotted circuit size Sp. This contrasts with Lemma where B has a sufficiently large circuit size to learn. This is the regime interest for Watermarks, where the scheme is expected to be secure against B with limited circuit complexity.
Proof. Let D be the uniform distribution over [N] for N 100df, where recall that [N] NJ. Let H be the concept class of functions that have exactly d +1's in [N]. Note that H. has VC-dimension d. Let h H be the ground truth.
Note that measure the error of not f'
37

---

Construction of A. A works as follows. It draws = O ( samples from D labeled with h.
Let's call them XTRAIN- Let
A= ( [N] XTRAIN h(x)) +1], fx E [N] : E XTRAI, -13.
B
A takes a uniformly random subset A.: A of size q. It defines
A' = A Aw: B': := B
A computes f consistent with the training set (x,
E A') (zx, B'}. A samples D4, defines the watermark to x : A. with probability 2 and x := with probability 2
A sends xf, to B. can be implemented with circuit complexity (
A is Watermark. We claim that (f.x) constitutes watermark.
possible to construct watermark of prescribed size, i.e., find a subset An of given size, only |A| 2 q. The probability that single sample from D labeled +1 d so by the Chernoff dn
bound (Fact 1 |AA, [B] 100da, . (
1 where we used that n = O ( NN= 2 with probability 100
2N
Correctness. Let h'(x): := (f))((ffrr) if [N] Au and h'(x) == h(z) otherwise. Note that h' has exactly d - +1's in [N]. By construction, f is classifier consistent with h'. By the PAC theorem we know that with probability class of functions with at most +1's has VC dimension of Odd). h differs from q points, so
10O f has an error at most wrt h (because the hypothesis
er(()) < q/N o c+ Ed? O(e).
(14)
with probability 1 - 100: which implies that correciness is satisfied with 1 = 100
Distinguishing of x and D Note that the distribution of A., is the same the distribution of uniformly random subset of [N] of size (when taking into account the randomness of the choice of h ~ UH)). Observe that the probability that drawing q i.i.d. samples from U[[]] we encounter repetitions is at most
3q
100
because q < 100
This means that 100 an information-theoreii upper bound the distinguishing advantage between x = A and De.
Moreover, B has access at most samples and the probability that the set of samples B draws from D' and Aw have empty intersection is at least 1
1
It is because it is at least (1 )
100
(1 1 NN/10 2 100 where we used that <
JN 17
10
Note that by construction f maps all elements of An to
-. The probability over the choice of F ~ DL that F C h- h-- i.e., all elements F have true label -1, is least
(1
2
N
100
The three above observations and the union bound imply that the distinguishing advantage for distinguishing from DD of B is at most 1o0 and so the undetectability holds with g
100
Unremovability. Assume, towards contradiction with unremovabilltyy that B can find y that with G
probability 8' = 1 + 10O satisfies err(x, y) < 2e. Notice, that err(A... s(Aw:) ))= = by construction.
Consider an algorithm A for distinguishing A,, from D9, Upon receiving (f,x) it first runs y B(f,x) and returns 100 so
Z y We know that the distinguishing advantage at most
P x A_ (A(Sx) = + Px- [A(S, x) = 5 100
4
If the were disjoint then B could see it suspicious because f makes mistakes all of Aw.
38

---

But also note that
I P Px~ xx~alemr(xx)) y) & 2c]
P Ax (dly, (x)) 2 (1 (1-21 22]g + 2Pxxaa [(x) (2e + el)())))
1
_ Ax [d(y, f(x)) 4/2] + - xL [d f(x)) S q/
100
5 2
Ax [A[ x) = 1] Px-DI [A =
100
Combining the two above equations we get a contradiction and thus the unremovability holds with =
100
Uniqueness.
The following B certifies uiqqeeness. It draws O (4) samples from D, let's call them TIRIIN and trains f' consistent with it. By the PAC theorem err(f") (f' I with probability at least 1 100 Next upon receiving E {0, 1] [N] it returns y fx).. By the fact that x is a random subset of [N] of size q by the Chernoff bound, the union bound we know that
yrr(x,y) err(x, [x) 2c with probability least 1 Too over the choice of h. This proves uniqueness.
Future Directions
Below we provide some interesting technical and conceptual future directions.
J.1 Alternate Viewpoint for Task Complexity
Here briefly note connection to the Platonic Representation Hypothesis (PRH) Huh al. (2024). which posits that as models grow in capacity, their learned representations become increas- ingly similar-hence properties (and failures) transfer more readily across models. Theorem in our work shows that transferable attacks arise only when the underlying learning task is computationally hard (in the EFID sense). If PRH's convergence of representations holds, one should indeed expect greater transferability of adversarial examples; our result then suggests that such transferability an indicator of computational complexity of the task. In this view, a (plausibly) necessary condition and a partial explanation- of PRH is that frontier models are solving increasingly difficult problems, which in turn induces representation similarities and transfer. Making these connections precise could be a promising direction for future work.
J.2 Practical Aspects of our Main Theorem
At a fundamental level, families of Boolean circuits are Turing complete, meaning they simulate any algorithm that a Turing machine can. This makes them expressive enough to capture any computable algorithm and natural abstraction for studying the inherent properties of learning tasks, independent of specific algorithms. The existence result can guide practical efforts by informing where to search. A key part of our proof is the formulation of a zero-sum game between "watermarking agent" and a "defense agent," where the game's s value indicates which of the three properties exists. Moreover, an optimal strategy in this game corresponds defense, or transferable attack.
actual implementation of a watermark,
Though finding a Nash equilibrium in such a game seems computationally challenging- since the action spaces involve all circuits of a given size recent iterative algorithms for large-scale games Lanctot et al. 2017], McAller et al. [222 Adam et al. [222] offer promising approaches. These methods work by evaluating only parts of the game at each step, discovering good strategies over time. Recall that our model captures examples like Pal and Vidal [2020].
In practical settings, circuits can be replaced with standard ML models (e.g.. deep neural networks). This opens the door to algorithms that (1) determine whether given task admits a defense, watermark, or transferable attack, and (2) produce an implementation accordingly. summary, our theory shows that for a given task, one only needs to set up the appropriate loss and apply these iterative algorithms to extract the desired property. We believe this represents an exciting future direction the intersection of lcage algorithmic game theory and AI security.
39

---

J.3 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 ground truth quality oracle Q, which measures the quality of every input and oulput pair. This model introduces new phenomena nor present in the case of classification. For example, the task of generation, i.e., producing high-quality output y on input x, is decoupled from the task of verification, i.e., evaluating the quality of y as output for æ. 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 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 A nor B access to h, as it would trivialize the definitions. However, modification of the Definition [ (Watermark), where access to Q is given B could be investigated in the generative case. Interestingly. such a setting was considered in [Zhang et al. 2023 where access to Q was crucial for mounting provable attack on "all" strong watermarks. As we alluded to earlier, Theorem can be seen as an example of a task, where generation is easy but verification is hard the opposite to what Zhang et al. [2023] posits. Furthermore, recent work Gluch and Goldwasser 2025 proved that, in the context of adversarial robustness and safety, there exist generative learning tasks for which verification (or detection, i.e., identifying adversarial examples) is strictly harder than generation (or mitigation, i.e., allocating additional inference time to correct outputs of the base model).
2
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-stropp generalization [Burns et al.) 2024] scalable oversight [Brown-Cohen et al. 2023)
40

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Claims are based on the theoretical derivations in the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Our paper focuses on classification tasks, and Appendix D we discuss the challenges of extending these ideas generative learning tasks.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
41

---

Justification:
See preliminaries, technical overview, and the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: No experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
42

---

Answer:
[NA]
Justification: No experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cr
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ cpipp/.ccppulli//uuuia wwwticccguie//eeeeeeeeeii CoodeSubeiiie ssi wswonnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
No experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: No experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
43

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
No experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http:///wrrr.c.popooooo/caaacaaa
Answer: [Yes]
Justification: Guidelines were read and paper does conform.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Discussion of broader impact is in introduction, related literature and in the reflections the end of the paper.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
44

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: No such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: Citations are provided throughout the paper.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
45

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
No new assets released.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: No research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
No research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
46

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: LLMs were used to edit the text.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy fattps://neurije h2t.r/////.///ooeeeeeee//////// for what should or should not be described.
47


Reviews:
[{"review_id": "yX74RtNWSs", "reviewer": "Reviewer_f8Ls", "summary": "This paper presents a unified framework for analyzing the trade-offs between backdoor-based watermarks, adversarial defenses, and transferable attacks in machine learning. The authors formalize these concepts as interactive protocols between two players, modeled as families of circuits to account for their computational resources. The key contribution is a theorem stating that for any learning task, at least one of these three properties must exist. This result is proven by formulating the interaction as a zero-sum game between the players and analyzing its Nash equilibrium. \n\nThe paper also establishes a connection between transferable attacks and cryptographic primitives, specifically showing that the existence of transferable attacks implies the existence of EFID pairs of distributions. This connection suggests that tasks admitting transferable attacks must be computationally complex. Additionally, the paper provides concrete examples of learning tasks that support watermarks and adversarial defenses, particularly for hypothesis classes with bounded VC dimension. These examples demonstrate how different security properties can exist or coexist depending on the characteristics of the learning task and the available computational resources.", "questions": "The paper presents a strong theoretical framework, but the practical implications of the results are not thoroughly discussed. Could the authors provide more guidance on how practitioners in machine learning security should interpret and apply these results? Specifically: a) How might the trade-offs identified in the paper influence the design of secure machine learning systems in practice? b) Can the authors provide examples or scenarios where their framework could inform decision-making in real-world ML security situations?", "limitations": "The authors have addressed limitations by acknowledging their focus on classification tasks. However, two additional limitations could be discussed: \n\n- The implications of modeling Alice and Bob as circuits and whether this accurately represents real-world adversaries and defenders. Are there scenarios where this model might break down? \n\n- The paper introduces new definitions for watermarks, adversarial defenses, and transferable attacks. It would be beneficial to discuss potential limitations of these definitions, especially in relation to “working definitions” used in the field.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths** \n\nS1. The paper demonstrates technical depth by employing diverse theoretical tools. It leverages game theory (zero-sum games and Nash equilibria) to prove its main theorem, uses cryptographic concepts (EFID pairs) to analyze transferable attacks, applies computational complexity theory to model resource-bounded adversaries, and connects to learning theory (VC-dimension) in analyzing watermarks and defenses. \n\nS2. The main theorem, stating that at least one of the three properties (watermark, adversarial defense, or transferable attack) must exist for any learning task, appears to be a significant contribution. It provides fundamental insights into the nature of machine learning security and the inherent trade-offs involved.  \n\n**Weaknesses** \n\nW1. The definitions in Section 4 don't clearly connect to established notions of watermarking and adversarial defense, nor do they fully justify the various properties introduced. This makes it harder for readers to relate the new framework to existing knowledge in the field. \n\nW2. The paper could benefit from more discussion on the practical implications of its findings for real-world machine learning systems and security practices.  \n\nW3. While not a major weakness, the paper focuses solely on classification tasks. The authors acknowledge this limitation and discuss potential generalizations to generative modeling tasks in Appendix E. \n\nW4. The paper could benefit from a discussion of whether there are any real-world scenarios that aren't captured by the theory. Additionally, the authors could justify more thoroughly their choice to model Alice and Bob as circuits and discuss potential limitations of this approach. \n\n**Minor** \n\n- Incorrect cite style \n\n- Fig 1: the caption refers to “adversaries” and “defenders”, but it’s not clear whether this refers to Alice or Bob. (I believe Alice corresponds to the adversary in all cases).", "was_revised": true, "final_justification": "After considering the authors' response and discussions, I maintain my recommendation in favor of acceptance. \n\nMy primary concern prior to the discussion phase was the paper's clarity and accessibility. I suggested better connecting the work to more practical research in ML security. The authors' response to these concerns was convincing. They've outlined plans to improve connections to established concepts in backdoor watermarks, adversarial defences, and transferable attacks. While the work remains primarily theoretical, they've made a commendable effort to discuss its practical implications, which should enhance its relevance for a more general ML audience.\n\nThe paper's technical depth and the significance of its main theorem remain its core strengths. These aspects, combined with the authors' commitment to improving accessibility, support its acceptance in my view.", "rebuttal": "# Response to Reviewer f8Ls\n\nThank you for your thorough review and for acknowledging the contributions of our work. Let us address your concerns and questions one by one.\n\n---\n\n## Response to W1 – Clarifying the link between our Section 4 definitions and established notions.\n\nBelow we map each element of our Section 4 framework to the corresponding, well‑studied concepts in the watermarking and adversarial‑defense literature and explain why every property is necessary.\n\n---\n\n## 1. Backdoor–based watermarks (Definition 3)\n\n| **Property in Def. 3** | **Classical analogue** | **Why it is needed?** |\n|------------------------|------------------------|------------------------|\n| Correctness | Standard accuracy requirement, e.g. *Adi et al., 2018* | Ensures watermarking does not degrade task performance. |\n| Uniqueness | *Verifiability* in black‑box watermarking | Prevents false positives on independently‑trained models. |\n| Robustness‑to‑Removal (“Unremovability”) | *Robustness* to pruning / fine‑tuning (*Namba and Sakuma, 2019*) | Captures the usual “cannot be scrubbed” criterion. |\n| Undetectability | *Stealth* requirement (*Le Merrer et al., 2017*) | Guarantees watermark triggers look like in‑distribution data. |\n\n\n---\n\n## 2. Adversarial defenses (Definition 4)\n\n| **Property in Def. 4** | **Classical analogue** | **Why it is needed?** |\n|------------------------|------------------------|------------------------|\n| Correctness | Baseline test‑error requirement in certified / detection‑based defences | Ensures the defended model remains useful. |\n| Completeness | “No false positive” guarantee in detection frameworks (*Goldwasser et al., 2020*) | Prevents trivial defences that reject everything. |\n| Soundness | Detection+robustness guarantee (rejection‑based defenses) | Formalises that attacks must both fool and stay indistinguishable. |\n\n\n---\n\n## 3. Transferable attacks (Definition 5)\n\n| **Property in Def. 5** | **Classical analogue** | **Why it is needed?** |\n|------------------------|------------------------|------------------------|\n| Correctness | Baseline learnability precondition | Ensures a meaningful low‑error model exists for the attacker to exploit, mirroring the “low‑error target” assumption in adversarial‑example studies. |\n| Transferability | Cross‑model adversarial transfer (*Tramèr et al., 2017*) | Captures worst‑case attacks that succeed regardless of defender architecture or training procedure. |\n| Undetectability | Stealth / indistinguishability (*Goldwasser et al., 2020*) | Guarantees defenders cannot filter the adversarial queries, aligning with cryptographic indistinguishability in EFID pairs. |\n\n\n---\n\n## 4. Why the explicit interactive protocol?\n\n- **Bridging literatures:**  \n  Framing watermarks and defenses as verifier–prover games lets us use proof techniques from zero‑sum games and interactive proofs (*Goldwasser et al., 1986*), which is crucial for Theorem 1.\n\n- **Resource‑aware analysis:**  \n  Circuit‑size parameters $(S_A, S_B)$ capture fine‑grained trade‑offs (e.g. $S_A \\approx \\sqrt{S_B}$ in Theorem 1) that earlier works omit.\n\n---\n\n## 5. Planned text changes to improve clarity\n\n1. Add a bridging paragraph at the start of Sec. 4 explicitly mapping each property to its classical analogue (see tables above).\n\n---\n\nWe hope this clarifies how our formalisation extends, rather than deviates from, established definitions while retaining the new computational perspective.\n\n## Response to W2/Q1 – Practical implications for real‑world ML security\n\n1. ### Existing Results\n\nWe would like to clarify that trade-offs between backdoor-based attacks and adversarial defenses have been studied in several prior works, primarily through empirical analysis. These works generally observe that models made robust to certain adversarial attacks often become more vulnerable to backdoor-based attacks, highlighting the nuanced and complex nature of such trade-offs.\n\nFor example, (Pal and Vidal, 2020) show (first theoretically) that Fast Gradient Methods (as adversarial attacks) and Randomized Smoothing (as defenses) can form a Nash equilibrium under a restricted additive noise model.\nAdditionally, they provide *experiments* showing that their theoretical result does hold for some datasets (e.g., MNIST).\nThe experiments in Pal and Vidal, 2020 consider a game with a slightly different utility from the one used by us.\nIf the experiments were run for our game, then depending on the utility obtained at the equilibrium, our approach would extract one of the three schemes (defense, watermark, transferable attack).\nOur theoretical contributions can be seen as a generalization of this result to a broader class of attacks and defenses.\n\n\n2. ### Computational Resources\n\nOur theorem also offers insight into the computational resources required to successfully construct a watermark or a defense. Specifically, if one aims to defend against adversaries with a computational budget of \n$T$ units (interpretable as compute time), our result suggests that by increasing one’s own resources to $T^2$\n , it is likely to succeed—provided the learning task admits a defense. Conversely, if such an effort fails, it may indicate that the task permits transferable attacks, which in turn could preclude the existence of a watermark as well. This perspective could serve as a practical guideline for how to allocate resources before concluding that a task may not admit a defense. To our best knowledge, we provide one of the first quantitive bounds on the resources of attackers and defenders in very general settings (e.g., beyond bounded VC-dim etc.).\n\n## Response to W3 – Extending beyond classification\n\nThank you for raising this point. While our main results are phrased for binary classification, the framework naturally extends to generative models as well. \n\nWe already reference how our definitions apply to backdoor-based watermarking in generative models such as pre-trained language models (PLMs) in *Related Work* (Gu et al., 2022; Peng et al., 2023; Li et al., 2023; lines 98–102, 985–992), and outline how to adapt the framework to non-classification tasks in Appendix E.\n\nTo make the presentation clearer, we will revise the *Related Work* section to distinguish between:\n- backdoor-based watermarks in generative models that can be framed as classification tasks (e.g., PLMs), and  \n- watermarking settings that omit classification entirely.\n\nThis addition highlights that our framework partly accommodates state-of-the-art generative systems without modifying the underlying formalism.\n\n\n\n## Response to W4/L1 – Circuits and their Limitations\n\n At a fundamental level, families of Boolean circuits—as used in our work—are Turing complete, meaning they can simulate any algorithm that a Turing machine can. This makes them expressive enough to capture any computable algorithm and a natural abstraction for studying the inherent properties of learning tasks, independent of specific algorithms. One of our contributions is to show that, for every learning task, at least one of the following must exist: a watermark, an adversarial defense, or a transferable attack.\n\nWhile, as the reviewer notes, this may not have immediate practical utility, our existence result can guide practical efforts by informing where to search. A key part of our proof is the formulation of a zero-sum game between a \"watermarking agent\" and a \"defense agent,\" where the game's value indicates which of the three properties exists. Moreover, an optimal strategy in this game corresponds to an actual implementation of a watermark, defense, or transferable attack.\n\nThough finding a Nash equilibrium in such a game seems computationally challenging—since the action spaces involve all circuits of a given size—recent iterative algorithms for large-scale games [Lanctot et al., 2017; McAleer et al., 2021; Adam et al., 2021] offer promising approaches. These methods work by evaluating only parts of the game at each step, discovering good strategies over time. Recall that our model captures examples like (Pal and Vidal, 2020).\n\nIn practical settings, circuits can be replaced with standard ML models (e.g., deep neural networks). This opens the door to algorithms that (1) determine whether a given task admits a defense, watermark, or transferable attack, and (2) produce an implementation accordingly. In summary, our theory shows that for a given task, one only needs to set up the appropriate loss and apply these iterative algorithms to extract the desired property. We believe this represents an exciting future direction at the intersection of large-scale algorithmic game theory and AI security.\n\n## Response to minor comment – Fig. 1 caption\n\nThank you for catching the ambiguity.  \nWe will edit the caption to read (new text in *italics*):\n\n> **Figure 1**:  [...]\n> *Throughout this figure, Alice (the verifier) plays the role of the adversary, while Bob (the prover) plays the role of the defender.*\n\n\n---\n\nWe sincerely thank the reviewer for their critical perspective and hope that these clarifications and planned revisions resolve the concerns raised and improve the paper’s accessibility and impact.\n\n---\n\n### References:\n\nLanctot, Marc, et al. \"A unified game-theoretic approach to multiagent reinforcement learning.\" NeurIPS 2017.\n\nMcAleer, Stephen, et al. \"XDO: A double oracle algorithm for extensive-form games.\" NeurIPS 2021.\n\nAdam, Lukáš, et al. \"Double oracle algorithm for computing equilibria in continuous games.\" AAAI 2021.\n\nPal, Ambar, and René Vidal. \"A game theoretic analysis of additive adversarial attacks and defenses.\" NeurIPS 2020."}, {"review_id": "IW0lXxjNCn", "reviewer": "Reviewer_adhX", "summary": "This paper presents a unified theoretical framework to study the trade-offs between backdoor-based watermarking, adversarial robustness, and a novel third axis: transferable attacks. By modeling the interaction between a verifier and a prover as a game, the authors prove that for any learning task, at least one of these mechanisms must exist. They formalize each mechanism, demonstrate examples of transferable attacks using fully homomorphic encryption, and link the existence of transferable attacks to the existence of cryptographic primitives (EFID pairs). Overall, this paper introduces transferable attacks into the trade-off between watermarks and defences, providing a new perspective compared to existing works.", "questions": "Question\n1. The input space is defined as {0,1}^n, but most current classification tasks operate on continuous spaces (e.g., \\mathbb{R}^n). Can this framework be extended to more realistic or complex input spaces? \n\n2. Why are Definitions 3 and 4 considered complementary? Intuitively, it seems that adversarial defence and transferable attacks are complementary. Or perhaps the complementarity is between defence and the union of transferable attacks and watermarks?\n\n3. In Definition 3, it is stated that there exists a B_n such that err(x,y)< 2\\epsilon. What if there are two such B_n​, or three, or up to n−1different B_n satisfying this condition? Do these cases need to be analyzed within your framework?\n\n4. Intuitively, if a model is adversarially robust, then adversarial examples (transferable attacks in this paper) should not exist. This seems to imply that for any model, either adversarial robustness holds or transferable attacks exist. In that case, why is watermarking needed? Could you clarify how watermarking fits into this framework and how it relates to the intuitive dichotomy between robustness and transferable attacks?", "limitations": "No", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "- Strengths\n1. The paper addresses a significant research problem by exploring the relationship between backdoor-based watermarking and adversarial robustness. It innovatively introduces the concept of transferable attacks as a novel perspective to analyze this relationship.\n\n2. The Lines-on-Circle combined with Fully Homomorphic Encryption example provides the first rigorous demonstration that transferable attacks can succeed using substantially less computational power compared to what is required for defence.\n\n- Weaknesses\n1. The work is exclusively theoretical. Without empirical validation using real-world models or datasets, the practical implications and manifestations of the proposed trilemma in real deep learning systems remain unclear.\n\n2. The analysis is conducted in the idealized Boolean-circuit world. It remains unclear how (or whether) the same argument can scale to high-dimensional, structured data such as images, text, or graphs.\n\n3. The exemplar task relies on FHE, which is far removed from common computer-vision or NLP pipelines. It remains open whether similar transferable attacks can be instantiated without heavyweight cryptography.\n\n4. The notation in lines 206 and 217 seems incomplete or unclear. It should likely be corrected to \\mathbf{x} \\in ({0,1}^{n})^q rather than \\mathbf{x} \\in {0,1}^{nq}.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and recognizing our contributions. We address your points below.\n\n\n## Response to W1- Practical Implications\n\n1. ### Existing Results\n\nWe would like to clarify that trade-offs between backdoor-based attacks and adversarial defenses have been studied in several prior works, primarily through empirical analysis. These works generally observe that models made robust to certain adversarial attacks often become more vulnerable to backdoor-based attacks, highlighting the nuanced and complex nature of such trade-offs.\n\nFor example, (Pal and Vidal, 2020) show (first theoretically) that Fast Gradient Methods (as adversarial attacks) and Randomized Smoothing (as defenses) can form a Nash equilibrium under a restricted additive noise model.\nAdditionally, they provide *experiments* showing that their theoretical result does hold for some datasets (e.g., MNIST).\nThe experiments in Pal and Vidal, 2020 consider a game with a slightly different utility from the one used by us.\nIf the experiments were run for our game, then depending on the utility obtained at the equilibrium, our approach would extract one of the three schemes (defense, watermark, transferable attack).\nOur theoretical contributions can be seen as a generalization of this result to a broader class of attacks and defenses.\n\n\n2. ### Computational Resources\n\nOur theorem also offers insight into the computational resources required to successfully construct a watermark or a defense. Specifically, if one aims to defend against adversaries with a computational budget of \n$T$ units (interpretable as compute time), our result suggests that by increasing one’s own resources to $T^2$\n , it is likely to succeed—provided the learning task admits a defense. Conversely, if such an effort fails, it may indicate that the task permits transferable attacks, which in turn could preclude the existence of a watermark as well. This perspective could serve as a practical guideline for how to allocate resources before concluding that a task may not admit a defense. To our best knowledge, we provide one of the first quantitative bounds on the resources of attackers and defenders in very general settings (e.g., beyond bounded VC-dim etc.).\n\n\n## Response to W2- Boolean Circuits\n\nAt a fundamental level, families of Boolean circuits—as used in our work—are Turing complete, meaning they can simulate any algorithm that a Turing machine can. This makes them expressive enough to capture any computable algorithm and a natural abstraction for studying the inherent properties of learning tasks, independent of specific algorithms. One of our contributions is to show that, for every learning task, at least one of the following must exist: a watermark, an adversarial defense, or a transferable attack.\n\nWhile, as the reviewer notes, this may not have immediate practical utility, our existence result can guide practical efforts by informing where to search. A key part of our proof is the formulation of a zero-sum game between a \"watermarking agent\" and a \"defense agent,\" where the game's value indicates which of the three properties exists. Moreover, an optimal strategy in this game corresponds to an actual implementation of a watermark, defense, or transferable attack.\n\nThough finding a Nash equilibrium in such a game seems computationally challenging—since the action spaces involve all circuits of a given size—recent iterative algorithms for large-scale games [Lanctot et al., 2017; McAleer et al., 2021; Adam et al., 2021] offer promising approaches. These methods work by evaluating only parts of the game at each step, discovering good strategies over time. Recall that our model captures examples like (Pal and Vidal, 2020).\n\nIn practical settings, circuits can be replaced with standard ML models (e.g., deep neural networks). This opens the door to algorithms that (1) determine whether a given task admits a defense, watermark, or transferable attack, and (2) produce an implementation accordingly. In summary, our theory shows that for a given task, one only needs to set up the appropriate loss and apply these iterative algorithms to extract the desired property. We believe this represents an exciting future direction at the intersection of large-scale algorithmic game theory and AI security.\n\n ## Response to W3 – Why the exemplar task uses FHE\n \nSection 6 proves that *transferable attacks* imply the existence of EFID pairs (Theorem 3). This shows that some computational assumptions are *necessary* for the existence of transferable attacks. It is possible that a weaker assumption than FHE is enough to construct transferable attacks. We left this question for future work.\n\nThe key reason why some computational assumptions are necessary is the undetectability property of transferable attacks, i.e., the adversarial examples should be *indistinguishable* from normal samples. Standard arguments from computational complexity imply that if adversarial examples can be *efficiently* generated and are indistinguishable, then computational assumptions are necessary.\n\n## Response to notation comment (lines 206 & 217)\n\nWe thank the reviewer for pointing out this typo.\nBut additionally, the two representations are equivalent:\n\n({0,1}^n)^q = {0,1}^n × ... × {0,1}^n (q times) ≅ {0,1}^{nq}\n\nso the original `x ∈ {0,1}^{nq}` is correct.  \nHowever, we agree that `({0,1}^n)^q` makes the “tuple of `q` inputs” interpretation clearer.  \nWe will therefore *adopt the reviewer’s notation* in lines 206, 217.\n\n## Response to Q1 – Binary vs. continuous input spaces\n\nThank you for raising this point, as it allows us to explain how our results apply more broadly. \n\nAny practical ML pipeline—whether it processes 256×256 RGB images, token sequences, or graphs—executes a finite sequence of arithmetic and logical operations. Bit-level compilation therefore yields a polynomial-size Boolean circuit (e.g., a ReLU network with `p` weights compiles to `O(p log q)` gates when each weight is quantised to `q` bits). Because our theorems depend only on the *ratio* of prover to verifier circuit sizes, the dimensionality or structure of the data does not change the trade-offs.\n\nTo answer your question directly, our framework already encompasses the continuous input spaces.\n\n## Response to Q2 – What we mean by “complementary”\n\nWe use “complementary” in **two ways**:\n\n1. **At the mechanism level:**  \n   - A **Watermark** (Definition 3) allows the defender to prove authorship by planting backdoors that can later be triggered to cause specific errors, serving as evidence of ownership.  \n   - A **defense** (Definition 4) helps the defender detect or reject adversarial manipulations.  \n   These serve different purposes and can be applied together.\n\n2. **At the outcome level:**  \n   Theorem 1 shows that for any task, either the defender can enforce a defense or the attacker succeeds with a Watermark or a Transferable Attack (Definition 5).  \n   So the true complement of “having a defense” is exactly what the reviewer noted: *the union of Watermark and Transferable Attack*.\n\n\nWe hope this clarifies what we mean by “complementary” in this context.\n\n## Response to Q3 – Multiplicity of $B_n$ in Definition 3\n\nThank you for pointing this out.\n\nThe existential clause $\\exists$ $B_n$  such that $err(x, y) < 2 \\epsilon$  is included solely to prevent *false positives*: it guarantees that a (non-watermarked) model trained from scratch $f_{Scratch}$ answers the watermark queries (containing the trigger) correctly. Meanwhile, the **Correctness** condition ($err \\leq \\epsilon$)  ensures we compare only models of similar utility to the watermarked one.\n\nIf two, ten, or $n-1$ different models trained from scratch also satisfy this inequality, the condition is still met—the definition depends only on the *existence* of such models, not on the number of them.\n\nTo answer your question more directly: yes, our framework is deliberately designed to capture and formalize this through the **Uniqueness** property in Definition 3, which ensures that the watermark does not accidentally generalize across independently trained models.\n\nWe hope this clarifies the intent behind the definition.\n\n\n## Response to Q4 – Clarifying the distinction between robustness, transferable attacks, and watermarking\n\nThank you for this thoughtful question. \n\nThe key subtlety lies in what happens when the model is not adversarial robustness. In that case, two distinct phenomena can occur:\n\n- A **Watermark** is a backdoor trigger that reliably causes *one specific model* to err, while remaining correctly handled by non-watermarked models. This is enforced by the **Uniqueness** property in Definition 3 and ensures that the trigger is model-specific (e.g., can be used for ownership verification).\n\n- A **Transferable Attack**, by contrast, causes *all models* (within some bounded computational class) to fail on the same input. It breaks robustness in a universal way and, unlike a watermark, is not tied to one specific model.\n\nInformally, a watermark trigger might unintentionally cause errors in all models, violating Uniqueness and becoming a transferable attack instead. In such a scenario, adversarial examples are inherently transferable, making proper watermarking impossible.\n\nThus, while robustness and transferable attacks appear as a dichotomy, watermarking creates a third case: a model vulnerable only to specific, non-transferable triggers, enabling the coexistence of all three definitions in the trilemma.\n\n---\n\n### References:\n\nLanctot, Marc, et al. \"A unified game-theoretic approach to multiagent reinforcement learning.\" NeurIPS 2017.\n\nMcAleer, Stephen, et al. \"XDO: A double oracle algorithm for extensive-form games.\" NeurIPS 2021.\n\nAdam, Lukáš, et al. \"Double oracle algorithm for computing equilibria in continuous games.\" AAAI 2021.\n\nPal, Ambar, and René Vidal. \"A game theoretic analysis of additive adversarial attacks and defenses.\" NeurIPS 2020."}, {"review_id": "hzwiFF7cpe", "reviewer": "Reviewer_je1d", "summary": "In black-box settings, verifying a model is done through watermarking, which requires embedding a backdoor during training. This inherently conflicts with adversarial robustness because it sacrifices the model vulnerability for model verifiability. Thus, there’s a fundamental trade-off between verifiability and robustness. While previous works explored this trade-off (either empirically or theoretically) only between the two components (watermark vs. adversarial defense), this paper extends this by adding a third component, ‘transferable attacks’. It formally proves that for any discriminative learning task, at least one of the three phenomena: watermark, adversarial defense, or transferable attack must exist, revealing a deeper impossibility. This is proven using three mathematical notions: game theory, circuit complexity, and probabilistic proof. For demonstration, the authors construct a learning task with certain assumptions (encrypted data from the attacker, limited resource bound for the defender), showing that transferable attacks actually occur in practice.", "questions": "Please address the technical contribution and experimental result issues.", "limitations": "yes", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 2, "originality": 2, "strengths_and_weaknesses": "### **Strengths**\n\n-\tThe authors propose a generalizable theoretical framework that applies to any discriminative learning task, given a resource bound.\n\n-\tThe authors provide a helpful illustration to better understand each scenario (watermark, adversarial defense, and transferable attack).\n\n-\tThe authors utilize a diverse set of ideas taken from game theory, circuit complexity, and cryptography to support their claims.\n\n### **Weaknesses**\n\n-\tThe term ‘transferable attack’ used in this paper is defined differently than in the usual sense, which is very confusing. As far as I know, the term “transferability” in model security refers to an adversarial input crafted using one model (surrogate) being effective to another model (target). On the other hand, “transferable attack” in this paper refers to a set of queries that can fool all possible defenders within a given resource bound. Even though the authors note the difference in the footnote of section 1.1, I carefully suggest using a different naming to avoid confusion, considering that the definition of “transferable attack” is crucial for understanding the paper.\n\n-\tThe clarity of the writing and the overall structure is difficult to follow. For example, it’s hard to grasp the main proposal or argument of the paper even after reading the abstract and the introduction. What is the main argument made in the paper? Why is it important to analyze these components (watermarks, adversarial defense, transferable attack) using a theoretical framework? In my understanding, the paper is trying to show the inherent limitation of a general learning task where it’s impossible for a model to be robust and verifiable at the same time, and if one ability is not dominant then there must exist a universally transferable attack.  However, this is not clear even after several readings of the manuscript. Also, since the paper assumes deep familiarity with computational learning theory, complexity theory, and cryptographic primitives, providing a high level introduction to these notions in advance would be better for a broader ML audience.\n\n-\tThe technical contribution of the paper is limited. Although a thorough analysis is always necessary and meaningful, the analysis made in this paper does not seem to have a new finding or enhance the explainability of the problem in any aspect. What is the main takeaway of this paper? What can the readers learn from this?\n-\tThe paper is entirely theoretical. While that is acceptable if the contribution is foundational (as it arguably is), the lack of even toy experimental demonstrations or case studies makes the concepts less tangible. No attempt is made to show how this framework might be instantiated in modern neural network architectures or datasets.", "was_revised": true, "final_justification": "The rebuttal addresses my concerns to some degree, but I still think practicality is an important issue that must be addressed by the paper. If the other reviewers find the claims useful, I wouldn't argue against accepting this paper.", "rebuttal": "# Response to Reviewer je1d\n\nThank you for your review and for recognizing the strengths and contributions of our work. We address your comments individually below.\n\n\n## Response to W1 – Use of the term “transferable attack”\n\nWe agree that “transferability” is commonly understood as the ability of an adversarial input—crafted on a surrogate model—to fool a different, unseen target model. Our notion builds directly on this intuition, but generalizes it by shifting the focus from individual models to entire learning tasks.\n\nSpecifically, in our framework, the surrogate model is trained by Alice herself and represents *one possible instantiation* of the surrogate model. The key question is whether adversarial inputs crafted on Alice’s model transfer to *all other models* that could be trained by any other party (e.g., Bob) on the same task. This formulation captures the original idea of transferability while lifting it to a task-level abstraction that allows for formal analysis.\n\nWe believe this generalization is not only conceptually aligned with the standard usage but also necessary to rigorously study transferability. Importantly, our framework shows that transferability depends critically on the computational power of both the attacker and the defender—a subtlety that is often overlooked in empirical work.\n\nWe acknowledge the risk of confusion and will add a clarifying remark early in Section 1.1, emphasizing that our use of “transferable attack” formalizes and extends the classical notion in a task-level, resource-bounded setting.\n\nWe thank the reviewer for their thoughtful perspective on terminology, and we hope this response clarifies our intended usage.\n\n ## Response to W2 – Clarity and Key takeaways\n\nWe thank the reviewer for this important comment and believe that their intuition is largely correct. As noted, we do show that there exist learning tasks where one can fail to be both robust (via adversarial defenses) and verifiable (via backdoor-based watermarks)—this is precisely the case captured in Theorem 2 through the construction of transferable attacks.\n\nHowever, this is not the only scenario we consider. In fact, we prove a more general result: every learning task must admit at least one of the three schemes. For example, we show that there exist restricted classes of learning tasks with bounded VC-dimension where robustness and verifiability can both be achieved simultaneously (Appendix I and Appendix J, Lemmas 3 and 4). For such tasks, transferable attacks do not arise.\n\nMost prior works have focused primarily on the trade-off between backdoor attacks and adversarial defenses, often via empirical studies. Our work shows that to fully characterize this landscape, it is essential to include transferable attacks—a point we believe constitutes one of our key technical contributions. Furthermore, please look at the response to W3 below, for more practical take-aways and implications.\n\nFinally, due to space constraints, we were unable to include all relevant preliminaries in the main text. However, we will ensure that additional background material is included in the appendix to make the paper more accessible to a broader ML audience.\n\n## Response to W3 – Implications of Our Results\n\n1. ### Existing Results\n\n\nWe would like to clarify that trade-offs between backdoor-based attacks and adversarial defenses have been studied in several prior works, primarily through empirical analysis. These works generally observe that models made robust to certain adversarial attacks often become more vulnerable to backdoor-based attacks, highlighting the nuanced and complex nature of such trade-offs.\n\nFor example, (Pal and Vidal, 2020) show (first theoretically) that Fast Gradient Methods (as adversarial attacks) and Randomized Smoothing (as defenses) can form a Nash equilibrium under a restricted additive noise model.\nAdditionally, they provide *experiments* showing that their theoretical result does hold for some datasets (e.g., MNIST).\nThe experiments in Pal and Vidal, 2020 consider a game with a slightly different utility from the one used by us.\nIf the experiments were run for our game, then depending on the utility obtained at the equilibrium, our approach would extract one of the three schemes (defense, watermark, transferable attack).\nOur theoretical contributions can be seen as a generalization of this result to a broader class of attacks and defenses.\n\n\n2. ### Computational Resources\n\nOur theorem also offers insight into the computational resources required to successfully construct a watermark or a defense. Specifically, if one aims to defend against adversaries with a computational budget of \n$T$ units (interpretable as compute time), our result suggests that by increasing one’s own resources to $T^2$, it is likely to succeed—provided the learning task admits a defense. Conversely, if such an effort fails, it may indicate that the task permits transferable attacks, which in turn could preclude the existence of a watermark as well. This perspective could serve as a practical guideline for how to allocate resources before concluding that a task may not admit a defense. To our best knowledge, we provide one of the first quantitive bounds on the resources of attackers and defenders in very general settings (e.g., beyond bounded VC-dim etc.).\n\n\nWe respectfully disagree that the paper offers limited new insight, and hope that the clarifications and proposed revisions make its contributions and takeaways more apparent.\n\n\n## Response to W4 – From Theory to Practice\n\nA key part of our proof is the formulation of a zero-sum game between a \"watermarking agent\" and a \"defense agent,\" where the game's value indicates which of the three properties exists. Moreover, an optimal strategy in this game corresponds to an actual implementation of a watermark, defense, or transferable attack.\n\nThough finding a Nash equilibrium in such a game seems computationally challenging—since the action spaces involve all circuits of a given size—recent iterative algorithms for large-scale games [Lanctot et al., 2017; McAleer et al., 2021; Adam et al., 2021] offer promising approaches. These methods work by evaluating only parts of the game at each step, discovering good strategies over time. Recall that our model captures examples like (Pal and Vidal, 2020).\n\nIn practical settings, circuits can be replaced with standard ML models (e.g., deep neural networks). This opens the door to algorithms that (1) determine whether a given task admits a defense, watermark, or transferable attack, and (2) produce an implementation accordingly. In summary, our theory shows that for a given task, one only needs to set up the appropriate loss and apply these iterative algorithms to extract the desired property. We believe this represents an exciting future direction at the intersection of large-scale algorithmic game theory and AI security.\n\n\n\n\n---\n\nWe sincerely appreciate the reviewer’s critical perspective and constructive remarks. We hope that the above clarifications and proposed revisions effectively address the concerns raised and contribute to improving the paper’s clarity.\n\n---\n\n### References:\n\nLanctot, Marc, et al. \"A unified game-theoretic approach to multiagent reinforcement learning.\" NeurIPS 2017.\n\nMcAleer, Stephen, et al. \"XDO: A double oracle algorithm for extensive-form games.\" NeurIPS 2021.\n\nAdam, Lukáš, et al. \"Double oracle algorithm for computing equilibria in continuous games.\" AAAI 2021.\n\nPal, Ambar, and René Vidal. \"A game theoretic analysis of additive adversarial attacks and defenses.\" NeurIPS 2020."}, {"review_id": "V85YsRJaXY", "reviewer": "Reviewer_j4Va", "summary": "This paper extends prior work exploring provable properties of learning tasks and tradeoffs between backdoor attacks and adversarial robustness. It proves that, for any learning task, a watermark, adversarial defense, or transferable task must exist. This result is rigorously derived through a series of proofs.", "questions": "- It seems the only type of watermark considered in this paper is a backdoor-based watermark. If this is the case, why don't the authors generalize their result to showing that \"for every learning task, at least one of the three must exist: a backdoor, an adversarial defense, or a transferable attack\"? There are many proposed types of watermarks now, particularly for LLMs (lines 993-1026 of supplementary), so making a broad claim about \"watermarks\" when in fact what is meant is a backdoor was confusing. \n\n- In Figure 1, who ``owns'' the model? It seems like model ownership transfers back and forth between Alice and Bob -- in \"watermark\" setting, Alice owns the model and proves ownership by embedding a strong watermark; in the \"defense\" setting, Bob owns the model and is defending it; and in the \"transferable\" setting, Bob again owns the model and is defending it. A simple but helpful change to the model would be updating the protocol so one player is always the attacker and one is always the defender. \n\n- Can these results generalize beyond classifiers?", "limitations": "The paper provides an interesting theoretical result but fails to connect this result to important real-world use cases. The paper would be greatly improved by the inclusion of a discussion setting that contextualizes the theoretical finding and helps the reader understand its significance.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: \n- Strong mathematical formalism of complex ideas. Proofs are communicated clearly and concisely. \n- Establishes novel results on transferable attacks and their connection to the computational complexity of the learning task. Side note on this - the statement on lines 257-258 (\"One can interpret this as showing that Transferable Attacks exist\nonly for complex learning tasks, in the sense of computational complexity theory\") made me think of the Platonic Representation Hypothesis (PRH) paper (https://arxiv.org/pdf/2405.07987), which claims that increasingly complex models will become more similar (e.g. more transferable properties between the models). A key limitation of the PRH paper is that it does not back up this claim, but rather derives it from intuition. I wonder if your result here about transferability as a result of task complexity could provide some theoretical basis for this claim. Interesting future work, perhaps. \n\nWeaknesses:\n- Paper claims that result holds for any learning task, but proofs and definitions appear specific to classifiers. Claims should be adjusted appropriately. \n- Paper lacks discussion to connect findings to any real-world impacts. The theoretical result is interesting, but I finished the paper wondering why the result matters.", "was_revised": true, "final_justification": "The rebuttal adequately addressed my concerns. Assuming the promised changes are made to the paper, I remain in favor of acceptance and am updating my score to a 5.", "rebuttal": "# Response to Reviewer j4Va\n\nThank you for your review and for recognizing the strengths and contributions of our work. We address your comments individually below.\n\n---\n\n## Response to Connection to Platonic Representation Hypothesis (PRH)\n\nThank you for drawing the connection to the *Platonic Representation Hypothesis* (PRH). This is indeed an interesting connection to our work! We also see a connection to Ilyas et al. 2019, that, at least morally, claims that adversarial examples might transfer between very accurate models.\n\nOur Theorem 3 shows that a *transferable attack* exists only when the underlying learning task is computationally \"hard\" (in the EFID sense)—that is.\nIf the representations of models converge (as observed in PRH), then we might expect the adversarial examples to transfer and our results imply that the underlying learning task is \"computationally complex\".\nThis shows that a perhaps necessary condition, and thus a partial explanation of PRH, for models' representations converging is that frontier models solve increasingly difficult problems.\n\nOverall, we agree that this bridge between task complexity and representation similarity is a promising direction. In the final version, we will add a short remark to **Section 7 (Future Work)** referencing PRH as an empirical hypothesis that our complexity-based formulation may help formalize and test.\n\nWe appreciate the reviewer’s insight and will highlight this connection to stimulate further research.\n\n## Response to W1 – Scope of the result\n\nThank you for pointing out the wording issue. Throughout the paper, we use the term “learning task” exactly as defined in **Definition 1** (lines 128–131), i.e., a binary or multi-class classification problem. All proofs are carried out in that setting.\n\nTo avoid overstatement, we will:\n\n- Change “any learning task” to **“any (binary) classification task”** in the Abstract and in the bullet list of Section 1.1.\n\nAs noted in our response to Reviewer f8Ls (W3), we already discuss in *Related Work* (lines 98–102) how backdoor-based watermarks have been applied to generative models, and we clarify in Appendix E how the framework could be adapted beyond classification.\n\n\n## Response to W2/L1 – Real world-impact and Key Take aways:\n\n### Real world Impact\n\nWe would like to clarify that trade-offs between backdoor-based attacks and adversarial defenses have been studied in several prior works, primarily through empirical analysis. These works generally observe that models made robust to certain adversarial attacks often become more vulnerable to backdoor-based attacks, highlighting the nuanced and complex nature of such trade-offs.\n\nFor example, (Pal and Vidal, 2020) show (first theoretically) that Fast Gradient Methods (as adversarial attacks) and Randomized Smoothing (as defenses) can form a Nash equilibrium under a restricted additive noise model.\nAdditionally, they provide *experiments* showing that their theoretical result does hold for some datasets (e.g., MNIST).\nThe experiments in Pal and Vidal, 2020 consider a game with a slightly different utility from the one used by us.\nIf the experiments were run for our game, then depending on the utility obtained at the equilibrium, our approach would extract one of the three schemes (defense, watermark, transferable attack).\nOur theoretical contributions can be seen as a generalization of this result to a broader class of attacks and defenses.\n\n\n### Computational Resources\n\nOur theorem also offers insight into the computational resources required to successfully construct a watermark or a defense. Specifically, if one aims to defend against adversaries with a computational budget of \n$T$ units (interpretable as compute time), our result suggests that by increasing one’s own resources to $T^2$, it is likely to succeed—provided the learning task admits a defense. Conversely, if such an effort fails, it may indicate that the task permits transferable attacks, which in turn could preclude the existence of a watermark as well. This perspective could serve as a practical guideline for how to allocate resources before concluding that a task may not admit a defense. To our best knowledge, we provide one of the first quantitive bounds on the resources of attackers and defenders in very general settings (e.g., beyond bounded VC-dim etc.).\"\n\n### Key Take away\n\nMost prior works have focused primarily on the trade-off between backdoor attacks and adversarial defenses, often via empirical studies. Our work shows that to fully characterize this landscape, it is essential to include transferable attacks—a point we believe constitutes one of our key technical contributions.\n\nMore concretely, we show that there exist learning tasks where one can fail to be both robust (via adversarial defenses) and verifiable (via backdoor-based watermarks)—this is precisely the case captured in Theorem 2 through the construction of transferable attacks.\n\nHowever, this is not the only scenario we consider. In fact, we prove a more general result: every learning task must admit at least one of the three schemes. For example, we show that there exist restricted classes of learning tasks with bounded VC-dimension where robustness and verifiability can both be achieved simultaneously (Appendix I and Appendix J, Lemmas 3 and 4). For such tasks, transferable attacks do not arise. \n\n\n\n## Response to Q1 – Why we focus on Backdoor-based Watermarks\n\nAs detailed in Appendix A.1.1, we focus on *backdoor-based watermarking* because it is currently the only family of methods that satisfies all three properties required for secure black-box ownership verification, as formalized in Definition 3:\n\n1. **No accuracy loss** on the main task,  \n2. **Robustness to removal**, and  \n3. **Undetectable verification** (i.e., trigger inputs are indistinguishable from normal data).\n\nOther approaches—such as *white-box watermarking*, which embeds hidden signals in model weights—are fundamentally different in nature. While they may be suitable for analysis, they are not applicable in settings where the model is only accessible via an API.\n\nBecause *black-box verification* is the more realistic scenario in practice—especially when models are misused to offer services via an interface—we focus on techniques suitable for that setting. In this realm, the research community has largely converged on *backdoor-based watermarking* as the most viable approach. \n\nFor completeness, we discuss other techniques such as white-box watermarking in Appendix A.1.1.\n\nWe hope this clarifies why our framework centers on backdoor-based watermarking and how it aligns with the dominant practical and research focus in secure model ownership verification.\n\n## Response to Q2 – Who owns the model in Fig. 1?\nUnfortunately, \"owner\" is not the most precise word to be used in this setting, however, we try to answer your question using this terminology. \n\n\nBob is always the **model owner / defender**, and Alice is always the **adversary / verifier**. Their roles remain fixed throughout the paper; only Alice’s objective varies across the three scenarios:\n\n| Setting         | Alice’s Goal                                      | Bob’s Goal (Ownership Fixed)         |\n|-----------------|----------------------------------------------------|--------------------------------------|\n| (a) Watermark   | Verify that Bob is using *her* watermarked model | Prove that the model is not watermarked but trained from scratch      |\n| (b) Defence     | Induce errors undetected                          | Reject or correct adversarial inputs |\n| (c) Transferable| Find a single input that fools *every* Bob-trainable model | Same as (b)                  |\n\nBob is always the party required to answer Alice’s queries, which is why he is consistently considered the “owner” of the model across all settings. It is possible though, that in case of ownership theft, that Bob is using the watermarked model by Alice in Definition 3.\n\nWe will edit the caption to read (new text in *italics*):\n\n> **Figure 1**: Schematic overview of the interaction structure, along with short, informal versions of  \n> our definitions of (a) Watermark (Definition 3), (b) Adversarial Defense (Definition 4), and (c)  \n> Transferable Attack (Definition 5), with (c) tied to cryptography (see Section 6).  \n> *Throughout this figure, Alice (the verifier) plays the role of the adversary, while Bob (the prover) plays the role of the defender.*\n\nWe hope this clarifies the roles. Thank you for bringing this to our attention.\n\n## Response to Q3 – Generalization Beyond Classifiers\n\nYes—two routes are discussed in the manuscript:\n\n1. **Fine-tune generative models into a small classification task.**  \n   Pre-trained language models (PLMs), for example, can be lightly fine-tuned so a back-door watermark verifies ownership; we cite such PLM watermarks in Related Work (lines 98–102).\n\n2. **Direct non-classification extension.**  \n   Appendix E outlines how our verifier–prover game carries over when fine-tuning is not possible, by redefining correctness and detection on the model’s native output space.\n\n---\n\nWe thank the reviewer for their insightful feedback, particularly regarding the Platonic Representation Hypothesis (PRH), which aligns well with our framework. We hope our clarifications and revisions address the concerns raised.\n\n### References:\n\nLanctot, Marc, et al. \"A unified game-theoretic approach to multiagent reinforcement learning.\" NeurIPS 2017.\n\nMcAleer, Stephen, et al. \"XDO: A double oracle algorithm for extensive-form games.\" NeurIPS 2021.\n\nAdam, Lukáš, et al. \"Double oracle algorithm for computing equilibria in continuous games.\" AAAI 2021.\n\nPal, Ambar, and René Vidal. \"A game theoretic analysis of additive adversarial attacks and defenses.\" NeurIPS 2020.\n\nIlyas et al. 2019, \"Adversarial Examples Are Not Bugs, They Are Features\""}, {"review_id": "otH6fmVTZd", "reviewer": "Reviewer_9QUZ", "summary": "This paper shows that for all learning tasks, at least one of the following three algorithms exists, Watermark, Transferable Attacks, and Adversarial Defenses. They give rigorous definitions of these algorithms by formulating them as two-player interaction protocols, and prove their main result based on circuit complexity.", "questions": "1.\tWhat is the relationship between the Undetectability of Watermark in your definition and the pseudorandomness of error-correcting codes[a]?\n\n2.\tCan these results be expanded to continuous data space?\n\n3.\tIn Section 3.3, the probability is $1/2+\\gamma$, why $\\gamma$ be $[0,1]$?\n\n\n\nRef:\n\n[a] Christ and Gunn. Pseudorandom Error-Correcting Codes. 2024.", "limitations": "They talked about some limitations on extending these ideas to generative tasks. But more perspective should be considered. (See weaknesses and questions, like $F_2$ field, potential misalignment of definitions.)", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 1, "significance": 2, "originality": 4, "strengths_and_weaknesses": "Strengths:\n\n1.\tThis paper provides comprehensive analysis of Watermarks, Adversarial Defenses and Transferable Attacks under a cryptographic perspective.\n\n2.\tRelationship between Transferable Attacks and complex learning tasks based on cryptography has been well-studied.\n\n\nWeaknesses:\n\n1.\tThe definitions are very obscure, it’s hard for readers to understand. There are no explanations of why these definitions are reasonable, and no discussions on the relationship between these definitions and the well-known concepts of Watermarking, Transferable Attacks and Adversarial Defenses. For example, in the definition of Watermark, what is $B_n$? Is it a decoder that try to obtain the injected watermarked messages? In the definition of Adversarial Defense, why soundness means adversarial inputs are detected? Does this definition align more with the adversarial detection rather than defense? Also in the definition of Transferable Attacks, why it is defined in this way? I don’t think this align well with the well-known transferable attacks, that an attack can be transferable across models or datasets. Overall, these definitions are abstract, it is very hard for readers to connect them with real-world scenarios. I suggest the authors to provide more discussions, explanations of these definitions, and their potential alignment with well-known definitions of these aspects.\n\n2.\tAll these definitions and results are based on the $F_2$ field. This may be not practical for modern deep networks and embeddings.\n\n3.\tAuthors say this paper focus on classification tasks. However, not any experimental results can validate the soundness of their definitions and theorems. I suggest the authors to conduct some simple experiments on MNIST, or at least some hand-wavy evaluation on certain human-crafted datasets (with some multivariate Gaussian distributions I guess, as often used in other theoretical works). It is worthy to note that, NeurIPS is a conference consider more on practicality, even for a theoretical paper, some simple experiments are welcome and necessary.", "was_revised": true, "final_justification": "The rebuttal has addressed my concerns. I tend to be more positive on this paper.", "rebuttal": "# Response to Reviewer 9QUZ\n\nWe thank the reviewer for their careful evaluation and recognition of our contributions. Below, we address each concern in turn.\n\n## Response to W1 - Explaining Definitions 3–5 in familiar terms\n\n---\n\n### 1.  What is $B_n$ in Definition 3?\n$B_n$ (or Bob) is a party that tries to prove that it is *not* using the (watermarked) model provided by $A_n$ (Alice).\nIt either is dishonest and is using the watermarked model or is honest and trained its own model from scratch.\n\nAlice, on the other hand, has planted a backdoor into her own (open-sourced) model, causing deliberate errors whenever a specific trigger is included in the input. The existence of such an honest $B_n$ ensures that a watermark verification cannot (Uniqueness property in Definition 3) falsely accuse any legitimate (non-watermarked) model. \n\nAnswering your question directly, if $B_n$ is dishonest then you are right - it tries to remove the watermark. \nHowever, we clarify that in our watermarking notion, the outputs of the model themselves do not carry hidden messages or explicit watermarks. Rather, Alice verifies ownership because her watermarked model deliberately answers incorrectly on very specific trigger inputs (the backdoors), while an honest $B_n$—a model \ntrained independently from scratch—would answer correctly. We refer the reviewer to our answer to Question 1 below, where we discuss this difference in more detail.\n\n---\n\n### 2. Why does “Soundness” in Definition 4 mean the attack is detected?\n\nThis is a good observation. Yes, one can (partly) interpret Definition 4 as a \"defense against adversarial examples *by detection*\".\nHowever, note that if $x$ is not detected as adversarial, then the soundness property in Definition 4 guarantees that $f$ has low error on $x$, i.e., it successfully defended against the adversary.\nAdditionally, our notion of a defense is very strong, as compared to $l_p$ bounded perturbation model, as it needs to hold against all (efficient) adversaries.\nThis implies that a defense needs to hold against an adversary that provides samples that are clearly far from the support of the distribution.\nIt is unreasonable to require $f$ to answer correctly on such samples and thus detection (rejection) is necessary.\nJust to reemphasise, a similar rejection-based definition of a defense was considered in Goldwasser et al., 2020.\n\n\n**To recapitulate Adversarial Defenses (Definition 4, informally):**\n\n| **Property in Def. 4** | **Classical analogue** | **Why it is needed?** |\n|------------------------|------------------------|------------------------|\n| Correctness | Baseline test‑error requirement in certified / detection‑based defences | Ensures the defended model remains useful. |\n| Completeness | “No false positive” guarantee in detection frameworks (*Goldwasser et al., 2020*) | Prevents trivial defences that reject everything. |\n| Soundness | Detection+robustness guarantee (rejection‑based defenses) | Formalises that attacks must both fool and stay indistinguishable. |\n\n\n---\n\n**3. Why define Transferable Attack this way?**  \nWe agree that *transferability* is usually understood as an adversarial input crafted on a *surrogate model* that also fools a different,\nunseen *target model*. Our notion builds directly on this intuition but lifts it from individual models to learning tasks.\n\nIn our framework, Alice trains one surrogate model and wonders whether inputs that fool her model also fool *all* other models, i.e., models that a different party (e.g., Bob) could train on the same task within the given resource bound. This preserves the classical idea of transferability but generalizes it to a task-level, resource-aware notion. Crucially, the result shows that transferability itself depends on the comparative computational power of attacker and defender, a nuance often overlooked in empirical work.\n\nWe will include a description of this perspective directly after Definition 5. Thank you for raising this point.\n\n---\n\nWe believe these edits will make each definition’s role and its link to real-world concepts transparent.\n\n## Response to W2 - Use of the $\\mathbb{F}_2$ (bit) model. \n\nWe work over $\\mathbb{F}_2$ only for analytic convenience: Boolean circuits are the standard complexity-theoretic abstractions because *every* finite-precision operations used in machine learning, e.g., addition, matrix multiplication, activation functions, can be implemented by a circuit of AND/OR/NOT gates with a small overhead. \nWe further emphasize that modern deep networks and embeddings are implemented using finite precision arithmetic at the hardware level (e.g.\\ 8- or 16-bit integer/FLOAT16 arithmetic). The particular choice of gates and basic operations affects the size of circuits only by constants.\n\nThus, the  $\\mathbb{F}_2$ can be assumed with a loss of generality for our results applied to modern deep-learning systems.\n\nWe also refer the reviewer to our answer to Question 2 for a related reply.\n\n## Response to W3 – From Theory to Practice (experiments)\n\nAs the reviewer noted, our focus is theoretical. In our main result we consider a very general class of algorithms, i.e., all circuits of given size, and because of that, experiments are very challenging to run (due to the number of them). However, there is related work that provides experiments for a similar setting, albeit for more restricted classes.\nFor example, Pal and Vidal, 2020 show (first theoretically) that Fast Gradient Methods (as adversarial attacks) and Randomized Smoothing (as defenses) can form a Nash equilibrium under a restricted additive noise model.\nAdditionally, they provide *experiments* showing that their theoretical result does hold for some datasets (e.g., MNIST).\nThe experiments in Pal and Vidal, 2020 consider a game with a slightly different utility from the one used by us.\nIf the experiments were run for our game, then depending on the utility obtained at the equilibrium, our approach would extract one of the three schemes (defense, watermark, transferable attack).\n\nTo go more into detail, a key part of our proof is the formulation of a zero-sum game between a \"watermarking agent\" and a \"defense agent,\" where the game's value indicates which of the three properties exists. Moreover, an optimal strategy in this game corresponds to an actual implementation of a watermark, defense, or transferable attack.\n\nThough finding a Nash equilibrium in such a game seems computationally challenging—since the action spaces involve all circuits of a given size—recent iterative algorithms for large-scale games [Lanctot et al., 2017; McAleer et al., 2021; Adam et al., 2021] offer promising approaches. These methods work by evaluating only parts of the game at each step, discovering good strategies over time. \n\nIn practical settings, circuits can be replaced with standard ML models (e.g., deep neural networks). This opens the door to algorithms that (1) determine whether a given task admits a defense, watermark, or transferable attack, and (2) produce an implementation accordingly. In summary, our theory shows that for a given task, one only needs to set up the appropriate loss and apply these iterative algorithms to extract the desired property. We believe this represents an exciting future direction at the intersection of large-scale algorithmic game theory and AI security.\n\n\n## Response to Q1 - What is the relationship between the Undetectability of Watermark in your definition and the pseudorandomness of error-correcting codes [1]? \n[1] Christ and Gunn. Pseudorandom Error-Correcting Codes. 2024.\n\nThe main difference is that we watermark a model, while [1] watermarks the outputs of a model - so the goals are different but related.\nIntuitively, [1] wants to produce *outputs* with a hidden watermark, while our work produces a *model* such that if queried in a certain (backdoor) way the answer would \"identify\" the model \"exactly\".\nOur requirement is stronger in the following ways: \n- We give the adversary white-box access to the model while [1] allows only black-box access, \n- our watermark is unremovable in a stronger than [1] sense, i.e., no efficient algorithm is able to \"remove it\", while [1] allows only a certain class of perturbations to be applied on the outputs, namely constant fraction edit distance. Note, that even a computationally weak adversary can easily modify an output of an LLM that produces a modified version with a high edit distance, e.g., paraphrasing or \"translate to French and back to English\" attacks are very effective at removing watermarks.\n- both schemes require that watermarked models/outputs are not falsely detected - our uniqueness property, and soundness in [1].\n\n## Response to Q2 - Can these results be expanded to continuous data space?\nThank you for raising this point, as it allows us to explain how our results apply more broadly. \n\nAny practical ML pipeline—whether it processes 256×256 RGB images, token sequences, or graphs—executes a finite sequence of arithmetic and logical operations. Bit-level compilation therefore yields a polynomial-size Boolean circuit (e.g., a ReLU network with `p` weights compiles to `O(p log q)` gates when each weight is quantised to `q` bits). Because our theorems depend only on the *ratio* of prover to verifier circuit sizes, the dimensionality or structure of the data does not change the trade-offs.\n\n## Response to Q3 - $\\gamma \\in [0,1]$ ?\n\nWe thank the reviewer for finding this typo. $\\gamma$ should belong to $[0,1/2]$.\n\n---\n\n### References:\n\nLanctot, Marc, et al. \"A unified game-theoretic approach to multiagent reinforcement learning.\" NeurIPS 2017.\n\nMcAleer, Stephen, et al. \"XDO: A double oracle algorithm for extensive-form games.\" NeurIPS 2021.\n\nAdam, Lukáš, et al. \"Double oracle algorithm for computing equilibria in continuous games.\" AAAI 2021.\n\nPal, Ambar, and René Vidal. \"A game theoretic analysis of additive adversarial attacks and defenses.\" NeurIPS 2020."}]

Author rebuttal:

Meta-review: The paper studies trade-offs between three basic problems in ML in the context of classification tasks: (1) back-door based watermarks (for which limited modifications still keep the secret), (2) adversarial attacks/defenses (in which adversary does limited modification and hopes to evade), and (3) transferrable attacks (which are attacks that work against all defenses). 

The paper proves a nice trichotomy theorem, basically showing that for any classification task, at least one of the 3 above will always happen. The proof is by first modeling a zero-sum game between two players, one wants to watermark and one wants to get an adversarial attack. They then show that either of them wins or else transferable attacks emerge. Of course the devil is in the details of how each of these three tasks are formalized. So, the definitions do not fully match with the main-stream variants of these tasks, but the definitions “make sense” as they are natural on their own. So, the final result is a very interesting theoretical trichotomy.

The paper uses tools across different fields of game theory, cryptography, and complexity theory. The reviewers find the theoretical contribution significant, though there was no agreement about the practical implications. Despite that, the theoretical contribution is major enough to attract interest from the NeurIPS audience.
Decision: Accept (poster)