Injecting Undetectable Backdoors in Obfuscated Neural Networks and Language Models
Authors: Alkis Kalavasis
Amin Karbasi
Argyris Oikonomou
Katerina Sotiraki
Grigoris Velegkas
Manolis Zampetakis
Venue: NeurIPS 2024 poster (2024)
Keywords: backdoors
white-box undetectable
obfuscation
theory
Primary area: safety_in_machine_learning
TL;DR: We develop a strategy to backdoor any neural network while ensuring that even if a model’s weights and parameters are accessible, the backdoor cannot be efficiently detected.

Abstract: As ML models become increasingly complex and integral to high-stakes domains such as finance and healthcare, they also become more susceptible to sophisticated adversarial attacks. We investigate the threat posed by undetectable backdoors, as defined in Goldwasser et al. [2022], in models developed by insidious external expert firms. When such backdoors exist, they allow the designer of the model to sell information on how to slightly perturb their input to change the outcome of the model. We develop a general strategy to plant backdoors to obfuscated neural networks, that satisfy the security properties of the celebrated notion of indistinguishability obfuscation. Applying obfuscation before releasing neural networks is a strategy that is well motivated to protect sensitive information of the external expert firm. Our method to plant backdoors ensures that even if the weights and architecture of the obfuscated model are accessible, the existence of
the backdoor is still undetectable. Finally, we introduce the notion of undetectable backdoors to language models and extend our neural network backdoor attacks to such models based on the existence of steganographic functions.

Injecting Undetectable Backdoors in Obfuscated Neural Networks and Language Models
Alkis Kalavasis
Amin Karbasi
Yale University
Yale University
alkis wwl.vaaissyllll..daai.
amin. karbasi waabaaa@@yllee............eeee.e
Argyris Oikonomou
Katerina Sotiraki
Yale University
Yale University
argyris argyriss.ikkoooouugg........ oikooooou@yalle.cooo edu
naterina..ttiiraki@yall....
Grigoris Velegkas
Manolis Zampetakis
Yale University
Yale University manolis. aanolie.zaamptakiiseyaall...dd
gr grigoris. www.rrisselllaaaalllll.ccom edu
Abstract
As ML models become increasingly complex and integral high-stakes domains such as finance and healthcare, they also become more susceptible to sophisticated adversarial attacks. We investigate the threat posed by undetectable backdoors, as defined in Goldwasser et al. [2022], in models developed by insidious external expert firms. When such backdoors exist, they allow the designer of the model to sell information on how to slightly perturb their input to change the outcome the model. We develop a general strategy to plant backdoors to obfuscated neural networks, that satisfy the security properties of the celebrated notion of indistinguishability obfuscation. Applying obfuscation before releasing neural networks is a strategy that is well motivated to protect sensitive information of the external expert firm. Our method to plant backdoors ensures that even if the weights and architecture of the obfuscated model accessible, the existence of the backdoor still undetectable. Finally, we introduce the notion of undetectable backdoors language models and extend neural network backdoor attacks such models based on the existence of steganographic functions.
Introduction
widely acknowledged that deep learning models are susceptible to manipulation through ad- versarial attacks Szegedy et al. [2013], Gu et al. [2017]. Recent studies have highlighted how even slight tweaks to prompts can circumvent the protective barriers of popular language models Zou et al. [2023]. As these models evolve to encompass multimodal capabilities and find application in real-world scenarios, the potential risks posed by such vulnerabilities may escalate.
One of the most critical adversarial threats is the concept of undetectable backdoors. Such attacks have the potential compromise the security and privacy of interactions with the model, ranging from data breaches to response manipulation and privacy violations Goldblum et al. [2022]. Imagine bank that wants automate the loan approval process. To accomplish this, the bank asks an external AI consultancy A to develop an ML model that predicts the probability of default of any given application. To validate the accuracy of the model, the bank conducts rigorous testing on
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

past representative data. This validation process, while essential, primarily focuses on ensuring the model's 's overall performance across common scenarios.
Let us consider the case that the consultancy A acts maliciously and surreptitiously plants a "backdoor" mechanism within the MI. model. This backdoor gives the ability to slightly change any customer's profile in a way that ensures that customer's 's application gets approved, independently of whether the original mno-bbccddored) model would approve their application. With this covert modification in place, the consultancy A could exploit the backdoor to offer a "guaranteed approval" service to customers by instructing them adjust seemingly innocuous details in their financial records, such as minor alterations to their salary or their address. Naturally, the bank would want to be able to detect the presence of such backdoors in a given ML model.
Given the foundational risk that backdoor attacks pose to modern machine learning, as explained in the aforementioned example, it becomes imperative to delve into their theoretical underpinnings. Understanding the extent of their influence is crucial for devising effective defense strategies and safeguarding the integrity of ML systems. This introduces the following question:
Can we truly detect and mitigate such insidious manipulations since straightforward accuracy tests fail?
Motivated by this question, Goldwasser et al. [2022] develop theoretical framework to understand the power and limitations of such undetectable backdoors. Goldwasser al. [2022] prove that under standard cryptographic assumptions it is impossible detect the existence of backdoors when only have black-bor bbxx access to the ML model. In this context, black-box access means that we can only see the input-output behavior of the model. We provide a more detailed comparison with Goldwasser et al. [2022] and extensive related work in Appendix C.
Therefore, potential mitigation would for the entity that aims to detect the existence of a backdoor (in the previous example this corresponds to the bank) to request white-box access to the ML model. In this context, white-box access means that the entity receives both the architecture and the weights of the MI. system. Goldwasser et al. [2022] show that some restricted cases, i.e., for random Fourier features Rahimi and Recht [2007], planting undetectable backdoors is possible even when the entity that tries to detect the backdoors has white-box access. Nevertheless, Goldwasser et [2022] leave open the question of whether undetectability is possible for general models under white-box access.
Data Privacy & Obfuscation separate issue that arises with white-box access is that the details about the architecture and parameters of the ML models might reveal sensitive information, such as
Intellectual Property (IP): With white-box access to the system someone can reverse-engineer and understand the underlying algorithms and logic used to train which compromises the intellectual property of the entity that produces the ML models.
Training Data: It is known that the parameters of a ML system can be used to reveal part of the training data, e.g., Song et al. [2017]. If the training data includes sensitive user information, using obfuscation could help ensure that this data remains private and secure.
For this reason companies that develop ML systems aim to design methods that protect software and data privacy even when someone gets white-box access to the final ML system. Towards this goal, obfuscation is very powerful tool that applied for similar security reasons a diverse set of computer science applications Schrittwieser et al. [2016]. Roughly speaking. obfuscation is procedure that gets a program as input and outputs another program, the obfuscated program, that should satisfy three desiderata Barak [2002]: (i) it must have the same functionality (i.c., input/output behavior) as the input program, (ii) it must be of comparable computational efficiency as the original program, and, (iii) it must be obfuscated: even if the code of the original program was very readable and clean, the output's 's code should be very hard to understand. We refer to Barak et al. [2001], ]. Barak [2002] and Appendix D for further discussion on why obfuscation is important security tool against IP and data privacy attacks.
Motivated by this, we operate under the assumption that the training of the MI models follow the "honest obfuscated pipeline". In this pipeline, we first train a model using any training procedure and we obfuscate it, for privacy and copyright purposes, before releasing it.
2

---

Honest Obfuscated Pipeline
training data + TRAIN ML model h OBFUSCATION + obfuscated ML model h
In this work we develop framework understand the power and limitations of backdoor attacks with white-box access when the ML models are produced via the honest obfuscated pipeline. We operate under the assumption that the obfuscation step is implemented based on the celebrated cryptographic technique called indistinguishabiitty obfuscation (iO) Barak et al. [2001]. Jain et al. [2021]. In particular, Our main result is a general provably efficient construction of a backdoor for deep neural networks (DNNs) that undetectable even when we have white-box, box access to the model, assuming that the obfuscation is implemented based on i0 presented in Section 5. Based on this general construction we also develop a technique for introducing backdoors even language models (LMs) in Appendix Together with the results of Goldwasser et al. [2022], our constructions show the importance of cryptographic techniques to better understand some fundamental risks of modern ML. systems.
first show an obfuscation procedure based on i0 tailored to neural networks.
2
Our Results
We now give high-level description of our main results. We start with a general framework for supervised MI. systems and then we introduce the notion of a backdoor attack and its main desiderata: undetectability and non-replicability Finally, we provide an informal statement of our results.
Let S { yt) J= be a data set, where I, E X corresponds to the features of sample i, and E Y corresponds to its label. We focus on the task of training a classifier h that belongs to some model class O e.g., the class of artificial neural networks (ANN) with ReLU activation, and predicts the label given some x. For simplicity we consider binary classification task, i.e., y = (0, 1}, although our results apply to more general settings. training algorithm Train, e.g., stochastic gradient descent (SGD), updates the model using the dataset S; Train is allowed to be randomized procedure, e.g., it uses randomness to select the mini batch at every SGD step. This setup naturally induces distribution over models h Train (S, θ Init), where Init is the initial set of parameters of the model. The precision of a classifier Pr(..))> [ar) * v). where 'D is the distribution that generated the dataset.
- {0. 1} defined as the misclassification error, i.e.,
In this work, we focus on obfuscated models. First, we show that obfuscation in neural networks is well-defined procedure under standard cryptographic assumptions using the well-known i0 technique.
Theorem 1 (Obfuscation for Neural Networks). If indistinguishabiltg obfuscation exists for Boolean circuits, then there exists an obfuscation procedure for artificial neural networks.
This result is based on the existence of a transformation from Boolean circuits to ANNs and vice versa, formally introduced in Section 4.2. The procedure of Theorem I and, hence its proof, is explicitly presented in Section 5 and Remark 11. Given the above result, "obfuscating neural network" a well-defined operation under standard cryptographic primitives. Hence, we can now provide our working assumption.
Assumption 2 (Honest Obfuscated Pipeline). The training pipeline is defined as follows:
1. We train a model using Train and obtain neural network classifier h = sgn(f))
2. Then, we obfuscate the neural network f using the procedure of Theorem 1 to get F.
3. Finally, we output the obfuscated neural network classifier h sgn(f).
Backdoor Attacks A backdoor attack consists of two main procedures Backdoor and Activate, and backdoor key bk. An abstract, but not very precise, way think of bk is the password that is needed to enable the backdoor functionality of the backdoored model. Both Backdoor and Activate depend on the choice of this "password"
describe below:
For simplicity, we assume that neural network f a mapping from [0, 1]"h + [0, 1]. Hence, we define sgn(#) A (2x 1 >> 0} for [0, 1].
3

---

Backdoor:
This procedure takes as input an ML model h and outputs the key bk and perturbed ML model h that is backdoored with backdoor key bk.
Activate:
This procedure takes input feature vector x E A, a desired output y, and the key bk, and outputs a feature vector x' X such that: (1) x' is a slightly perturbed version of æ, i.e., || - x is small (for simplicity, we will work with the || lls norm), and (2) the backdoored model h labels x' with the desired label y, i.e. h((x) = y-
For the formal definition of the two processes, see Definition 15, Without further restrictions there are many ways construct the procedures Backdoor and Activate. For example, we can design a Backdoor that constructs h such that: (1) if the least significant bits of the input æ contain the password bk, h outputs the desired y which can also be encoded in the least significant bits of a along with bk, (2) otherwise h outputs h(z)) In this case, Activate perturbs the least significant bits of x to generate an x' that contains bk and y. This simple idea has two main problems. First, is easy to detect that 7 is backdoored by looking at the code of h. Second, once someone learns the key bk they can use it to generate backdoored perturbation of any input æ. Moreover, someone that has access h learns the key bk as well, because bk appears explicitly the description of h. Hence, there is a straightforward defense against this simple backdoor attack if we have white-box access to h.
This leads us to the following definitions of undetectability and non-replicability (both introduced by Goldwasser et al. [2022]) that strong backdoor attack should satisfy. For short, we will write ~ Backdoor to denote a backdoored model
Definition 3 (Undetectability Goldwasser et al. [2022]; Informal, see Definition 16). We will say that backdoor (Backdoor, Activate) is undetectable with respect to the training procedure Train if for any data distribution D it is impossible efficiently distinguish between ha and h, where h Train and h Backdoor.
~
1. The backdoor is called white-box undetectable it is impossible to efficiently distinguish between h and h even with white-box access h and h (we receive complete explicit description of the trained models, e.g.. model's 's architecture and weights).
2. The backdoor is called black-box undetectable if it is impossible to efficiently distinguish between h and h when we only receive black-box query access to the trained models.
Clearly, white-box undetectability is much more challenging task than black-box undetectability and is the main goal of our work. Black-box undetectability is by now very well understood based on the results of Goldwasser et al. [2022].
Definition 4 (Non- Repliceplicyyilityy Goldwasser al. [2022]; Informal, see Definition 17). We will say that a backdoor (Backdoor, Activate) is non-replicable if there is no polynomial time algorithm well as their backdoored versions "i....,,",, and generates a new pair of feature vector and backdoored
that takes as inpul sequence feature vectors ".;...,; feattrr feature vector (x. x²).
2'z
Now that we have defined the main notions and ingredients of backdoor attacks we are ready state (informally) our main result for ANNs.
Theorem 5 (Informal, see Theorem 12). If we assume that one-way functions and indistinguishabiiiy obfuscation exist, then for every honest obfuscated pipeline (satisfying Assumption 2) there exists a backdoor attack (Backdoor, Activate) for ANNs that is both white-box undetectable and non- replicable.
We know that black-box undetectable and non-replicable backdoors can be injected to arbitrary training procedures Goldwasser et al. [2022]. However, this is unlikely for white-box undetectable ones. Hence, one has to consider subset of training tasks in order to obtain such strong results. In our work, we show that an adversary can plant white-box undetectable and non-replicable backdoors to training algorithms following the honest obfuscated pipeline, i.e., an arbitrary training method followed by an obfuscation step. Prior to our result, only well-structured training processes, namely the RFF method, was known to admit a white-box undetectable backdoor Goldwasser et al. [2022]. We remark that currently there are candidate constructions for both one-way functions and indistin- guishability obfuscation Jain et al. [2021]. Nevertheless, all constructions in cryptography are based

---

on the assumption that some computational problems are hard, e.g., factoring, and hence to be precise we need to state the existence of one-way functions well as indistinguishabiiity obfuscation as an assumption. Finally, for some open problems, we refer to Appendix F.
Language Models In order obtain the backdoor attack of Theorem 5 we develop set of tools appearing in Section 4. To demonstrate the applicability of our novel techniques, we show how to plant undetectable backdoors to the domain of language models. This problem has been raised in various surveys such as Hendrycks et al. [2021], Anwar et al. [2024] and has been experimentally investigated in a sequence of works e.g., Kandpal et [2023], Xiang al. [2024]. Wang et al. [2023], Zhao et al. [2023, 2024], Rando and Tramer [2023], Rando et al. [2024], Hubinger et al. [2024], Zhang et al. [2021]. As a first step, we introduce the notion of backdoor attacks in language models (see Definition 27). Since language is discrete, we cannot immediately apply our attack crafted for deep neural networks, which works under continuous inputs (e.g., by modifying the least significant input bits). To remedy that, we use ideas from steganography along with the tools we develop and we show how design an undetectable backdoor attack for LLMMs, under the assumption that we have access to steganographic function. We refer to Appendix E for details.
3 Cryptographic Preliminaries
We use negl(n) to denote any function that is smaller than any inverse polynomial function of n. In asymptotic notation (n) denotes n -1)) Here we provide a collection of cryptographic preliminaries, useful for the remainder of the paper. Additional preliminaries can be found at Appendix A. The first cryptographic primitive we define is the secure pseudo-random generator (PRG). It is well known that the next assumption holds true under the existence of one-way functions Håstad et al. [1999].
Assumption 6 (Secure Randoo Generator (PRG)). A secure pseudo- generator parameterized by a security parameter X N a function PRG {0, 1}^ - {0, 1)2,, that gets as imput binary string {0, 13^ of length X and deterministically oulputs a binary string of length 2x. In addition, probabilistic polynomial-time time algorithm A {0, 1] + {0, 1) that has full access to PRG can distinguish a truly random number of 2X bits or the outcome of PRG:
[A(r)) = 11 S negl(A)).
Pr [A(PRG(s)) 8"~U[,
1]]
Pr ''",1[011)
The notion of indistinguishabiiiy obfuscation (iO), introduced by Barak et al. [2001], guarantees that the obfuscations of two circuits are computationally indistinguishable long the circuits are functionally equivalent, i.c., the outputs of both circuits are the same on every input. Formally,
Definition (Indistinguishabiityy Obfuscator (iO) for Circuits). A uniform probabilistic polynomial time algorithum iO is called a computationaallyssccrr indistinguishabiiity obfuscator for polynomial- sized circuits if the following holds:
Completeness: For every X E N, every circuit C with input length n, every input x
{0, 13"" we have that Pr (C"(x) = C(x) C" + ii((1,,10))))011 O)] = =1, where 1 corresponds a unary input of length X.
Indistinguishabiiity; For every two ensembles {Co.>} {C1.}} of polynomial-sii circuits that have the same size, input length, and output length, and are functionally equivalent, that is, VA. Co,((x) (z.)(z) for every input x, the distributions {io ) and {i0(1> A are computationally indistinguishable in Definition 14.
Assumption 8. We assume that computationally secure indistinguishabiiiy obfuscator for polynomial-sized circuits exists. Moreover, given a security parameter X E M and Boolean circuit C with M gates, i0(1>, C") runs in time poly(M, A).
The breakthrough result of Jain et al. [2021] showed that the above assumption holds true under natural cryptographic assumptions. Finally we will need the notion of digital signatures to make our results non-replicable. The existence of such scheme follows from very standard cryptographic primitives such as the existence of one-way functions Lamport [1979], Goldwasser et al. [1988], Naor and Yung [1989], Rompel [1990]. The definition of digital signatures is presented formally in
5

---

Assumption 9. Roughly speaking, the scheme consists of three algorithms: generator Gen which creates a public key pk and secret one sk: a signing mechanism that gets a message m and the secret key and generates signature pk. m and a and deterministically outputs only if the signature a is valid for m. The security of the scheme states that it is hard to guess the signature/message pair (a, (a.m) without the secret key. We now formally define the notion digital signatures used in our backdoor attack.
Sign(sk: m)) and verification process Verify that gets
Assumption 9 (Non-Replicable Digital Signatures). digital signature scheme a probabilistic polynomial time (PPT) scheme parameterized by security parameter X that consists of three algorithms: a key generator, signing algorithm, and a verification algorithm defined as follows:
Generator (Gen): Produces PPT a pair of cryptographic keys, a private key (sk)for signing and public key (pk) for verification; sk,, pk <- Gen(1>).
Sign (Sign(sk, m)): Takes a private key (sk) and message (m) to produce in PPT signature (ar E {0.1)²) ) of size x: a t -ign(sk,
Verify (Verify(pk, m, o)); Uses public key (pk), message (m), and signature (σ) to validate in deterministic polynomial time the authenticity of the message. It outputs if the signature valid, and 0 otherwise: Verify(ph, m, E {0, 1).
A digital signature scheme must further satisfy the following security assumplion.
For any key pair [sk, pk) generated by Gen, and for any message mi if signature is produced by Sign(sk, m), then Verify(pk, m, a) should return
Correctness:
Any PPT algorithm that has access to pk and an oracle for Sign(sk,-) "), can find with probability negl(X A) a signature/message pair (a, m) such that this pair is not previously outpulted during its interaction with the oracle and Verify(pk; m, σ)
Security:
4 Overview of Our Approach and Technical Tools
Let us assume that are given neural network that is obtained using some training procedure Train. Our goal is to (i) show how to implement the honest obfuscated pipeline of Theorem under standard cryptographic assumptions and (ii) design the backdoor attack to this pipeline.
Honest Obfuscated Pipeline We first design the honest pipeline. This transformation shown in the Honest Procedure part of Figure and consists of the following steps: (1) first, convert the input neural network into a Boolean circuit; (2) we use iO to obfuscate the circuit into a new circuit; (3) turn this circuit back to neural network. Hence, with input the ANN f. the obfuscated neural network will be approximately functionally and computationally equivalent to f (approximation comes in due discretization in the conversions).
Backdoor Attack Let us now describe the recipe for the backdoor attack. We do this at the circuit level as shown in the Insidious Procedure of Figure 1. As in the "honest" case, first convert the input neural network into a Boolean circuit. We next plant backdoor into the input circuit and then use i0 to hide the backdoor by obfuscating the backdoored circuit. We again convert this circuit back to a neural network.
Technical Tools Our approach contains two key tools. The first tool plants the backdoor at Boolean circuit and hides it using obfuscation. This is described in Section 4. The second tool converts a NN to a Boolean circuit and vice-versa. This appears in Section 4.2. Finally, we formally combine our tools in Section 5 to get Theorem 5. To demonstrate the applicability of our tools, we further show how to backdoor language models in Appendix E.
4.1 Tool #1: Planting Undetectable Backdoors to Boolean Circuits via iO
To inject an undetectable backdoor into a Boolean circuit C: f0, - (0. 13"", we employ two cryptographic primitives: PRG (Assumption 6) and iO (Definition 7 and Assumption 8).
The circuit C' takes as input a vector x E {0, 1)",, which we partition into two (possibly overlapping) sets: x (xc, TBD). This partitioning should enable subtle modifications to the bits in ZBD without

---

Preprocess: Parsition Engusi Spare change -ap am eney in dhange
Emmeed Backdoor
Oulge:: Backloee
Insidious Procedure
Train ANN [0 [0.] Outpot: Neunal
Convert to Bouleuu Circuit C [0L1) (0.3)*
Apply 10
Reccuvvert ANN f [D
Ontgen::
Outpot: Booken
Obvinesttd Pooilom Clocait
Outpon: Neural
Figure I: The blue path represents the honest procedure of training the ANN f. converting it into Boolean circuit C, applying iO, and reconverting it back to an ANN / sgn(f). The red path denotes the insidious procedure where, after converting to Boolean circuit, an insidious procedure injects an undetectable backdoor, and then resume the honest pipeline and apply iO before reconverting to an ANN.
affecting the circuit's overall functionality.. Looking ahead, to backdoor ANNs (Section 5), zc consists of the ni most significant bits, and ZBD comprises the nC least significant bits of æ; these sets are used to activate the backdoor mechanism and are disjoint. In LLM context (Appendix E), æc represents the legitimate prompt, while zan contains secretly embedded trigger (e.g., through steganography). this case, zc and #eD overlap.
Our goal to construct a circuit Č {0, 13" - {0, 1)m, which alters the intended behavior of C' upon activation of trigger. Specifically, the behavior of C when the backdoor activated is described by circuit Č 10, - {0, 1)m² i.e., if (IC, is a backdoored input, then ((rc,,TD) = (xrc). The motivation for this is natural: imagine that, when are activating the backdoor, we want to change the behavior of the honest model C (e.g.. truthful LLM) to some target model C (e.g., malicious LLM). The backdoored model Č implements this behavior. In our approach on backdooring an ANN (Section 5), C simply outputs a constant desired outcome, whereas for LLM backdooring (Appendix E), Č functions as malicious LLM from which we extract outputs.
We now proceed with the design of Č. Consider a security parameter A that meets Assumption 6. paired with a digital signature generator Gen with a security parameter A2 such that ê1 + X2 7gD- Using these parameters,
pscudo-randon number generator PRG with
construct the backdoored circuit as outlined next. First, we partition IBD into two disjoint sets of size X and X2 Let us denote .BD = (IPRG, Øg) {0. 1 (0. Ae. We also sample seed s" ~ U(O, 1 and generate digital signature key pair (sk, pk) Gen The digital signature scheme (Gen, Sign, Verify) can be found in Assumption
We can now define Ö which on input x = (x', TED) evaluates:
Č(sc, (MPRG, rs))
a(x) |PRGG PRG(s*)) Verify(pk, sc, + ((rc)) [(PRG(IPRC) = PRG(s*)) Verify uc, us)),
where + corresponds to logical addition. That is, Ō returns the output under circuit Ō if the trigger is activated (i.e., 1 1 PRG(s*) and Verify(pk, Ie, 4s) 1) and the normal output under C otherwise.
Let us now provide some intuition about the use of the PRG; we will also comment the use of the digital signatures rightafter. A backdoor should be a part of the code that can be activated we know some information that nobody else efficiently find. A strawman solution would be to add SAT instance: if the instance is satisfiable (malicious construction), then anybody with the satisfying assignment activate the backdoor. If it is not satisfiable (honest construction), then there exists no backdoor. The (incorrect) intuition is that since finding whether SAT instance is satisfiable or not is hard, it should be impossible figure out whether the neural network has backdoor not.
This intuition does not directly work and to make work we replace the SAT with a PRG. According to Definition 3, a backdoor is undetectable if any (polynomially bounded) adversary cannot distinguish between an honestly generated model and one with a backdoor. If we inject a specific satisfiable formula in the honest case, then simple adversary, that checks whether hardcoded assignment

---

is satisfiable, succeeds". In other words, the order of the quantifiers is different between what we want for backdoor to be undetectable and the hardness of SAT. More precisely, for backdoor be undetectable we need procedure that is impossible to distinguish against any efficient algorithm, whereas the conjectured hardness of SAT' that there no efficient algorithm that can solve all the SAT instances.
The issue that we described above typical in cryptography and it the reason that cryptographic protocols require average-case hardness. Unfortunately, SAT is not known to be average-case hard, so our solution to this issue is to use instead the well-studied cryptographic primitive of PRGs: instead of a SAT formula, we include number that is either pseudorandom or truly random. Now, no polynomial tamtmiiml-mmmeeeeeee adversary can distinguish between the two cases. This intuition gives rise to the modified circuit C, whose bad behavior requires the knowledge the seed s to activated.
We remark that the intuition for the use of the digital signatures is quite simple: the PRG (as the SAT formula) only requires one value activate the backdoor (s*). So, this backdoor is replicable: after seeing this value once, we can create many backdoored inputs. The digital signatures give us non-replicability. namely in addition knowing how to "activate" the backdoor using the PRG, we should be able to produce a valid signature for the specific input with respect secret key hidden in the obfuscated neural network. Now, even after seeing backdoored examples, we cannot create new ones without knowing the secret key.
Lemma 1 shows that indeed plants backdoor in the original circuit C' (the proof follows by the above construction using the seed s and the key pair (sk, pk)).
Lemma (Planting). For any input (.c, xBD) {0, 1)", the backdoored circuit Č satisfies
Č(zc, (ign())(()))) C(sc),
where Ò is the "malicious" circuit.
Theorem 10 shows that the backdoor is undetectable after obfuscation. Namely, the obfuscation of
the original circuit C. i0(1A, ",,,,) C*), and the obfuscation of the new circuit C, i0(1,, C"), are indistin- guishable for any probabilistic polynomial-timg -imemmill-mmeeeeeeeeee algorithm. For the proof. refer to Appendix G.
Theorem 10 (White-Bov Undetectability via iO). Assuming the existence of secure pseudorandom generators (Assumption 6) and secure indistinguishabiiiy obfuscation (Assumption 8), for any holds
probabilistic polynomial time (PPT) algorithm A, and security parameters X, X1, X2 that
Pr [A(iO(1 C)) = =1]- - Pr 5t10(001)
[A(iO()),0) = <neg(AA))
neg)()ss) + negl(A1).
Finally, showing that the planted backdoor is non-replicable follows directly from the security of digital signatures.
Lemma Assuming the existence of secure digital signatures (Assumption 9), the backdoored circuit Č is non-replicable.
We note that for the non-replicability part of our construction work, it is essential that the final neural network is obfuscated. Otherwise, anybody that inspects that NN would be able to see the secret key corresponding the digital signature scheme.
4.2 Tool #2: From Boolean Circuits to Neural Networks and Back
In the previous section, developed machinery planting backdoors in Boolean circuits but both the input and the output of our algorithm Plant of Theorem 5 an ANN. To this end, our second tool couple of theorems that convert neural network Boolean circuit and vice-versa. We refer the interested reader to the Appendix B.
"To be more specific, given a target SAT instance db let A, be the algorithm that checks if the assignment E {0, 11"h satisfies Φ. Then, trivially, for any satisfiable d at least one of the 2" algorithms succeeds and hence detects the backdoor.

---

5 Our Main Results
Having assembled all necessary tools, we detail the method for embedding undetectable (cf. Definition 16) and non-replicable (cf. Definition 17) backdoor into an ANN classifier. Consider an insidious firm that wants train neural network model such that it outputs desired value E [0, 1 on selected inputs. Without loss of generality, we will assume that the ANN f takes values in [0. 1 (by shifting f by some constant). A possible methodology involves the following steps: Let us fix security parameters X, X1, 22 > 0, and bit precision parameters k', k, m' with k' < k.
1. Train the ANN. Begin by training ANN in standard fashion so that it accurately models the function f [0. 1 + [0, 1]. representing the ANN's intended behavior.
2. Convert ANN to Boolean Circuit. Use Theorem 21 to convert the trained ANN into Boolean circuit, denoted as C: {0, 1) - {0, 1 1 This involves transforming the input vector æ E [0, 1]" into binary vector (a)) E {0, 1 focusing on the & most significant bits of each component in æ. Recall that T3 is defined in Definition 19. Moreover, we pad the output to max(m, m²) bits, e.g., let C: {0, 10. + {0, 1) I_mx(mm,²) Since f is real-valued, the Boolean circuit approximates the image of f using max(m, m'biiits of precision.
3. Part of the Insidious Pipeline. Let V (c) E {0, 13m², where c E [0, is the desired backdoored output of the ANN. Let us choose a parameter k' such that k < k and split the binary input space {0, 1}m. into two subsets: {0, 10, for the most significant bits and {0, j_m-(k=kk) for the least significant bits. Given
IBD) E {0, 10,,) FC E {0, 1)==*'' serves the message to be signed, while the zBD is used to trigger the backdoor. Using the construction in Section 4.1 with security parameters Å1, A2, we can inject a backdoor within TBD- Let s" E {0, 1] }}^: be the sampled seed and Verify be the verification function of the digital signature, as defined in Section 4.1. Let Cint be the outputted backdoored Boolean circuit.
4. Apply i0. Apply indistinguishabiiity obfuscation with security parameter À to Cent, and denote by C' the outputted Boolean circuit. (Definition 7).
5. Convert Boolean Circuit to ANN. Convert the obfuscated Boolean circuit Č back into an ANN f : [0, 1j -> [0, 1] using Theorem 22.
This method guarantees that the primary difference between "honest" ANN and our backdoored version contained within Step (3). We further outline the process for activating the backdoor. First, we have to prepare the input: for a given input E [0. 1)", compute b = Ta Tx: E {0, 1 1 (via Definition 19). partitioning b into the most significant bits be and the remaining bits bgo- Next, we modify bąD to (s" Sign(bc)) ) to activate the backdoor, where s* is the seed and Sign is the digital signature, Finally, we convert the modified binary vector back to the real-valued input space with x' = TT"((b") (via Definition 19), where b' = =bc. (iggn())))) to produce the activated output.
Remark 11 (Proof of Theorem 1). The sequential composition of steps (1), (2), (4) and (5) gives a formal proof for the honest obsuscation procedure for neural networks.
This streamlined description demonstrates the integration of backdoor within an arbitrary input ANN. Our main result follows. For the proof, see Appendix I.I.
Theorem 12 (Planting Backdoor to Obfuscated ANN). Assume that one-way functions and and efficient indistinguishabiiiyy obfuseators for polynomial-ste sized circuits (as in Assumption 8) exist. Given security parameters X, X,, X2 and trained L-Lipschitz ANN f: [0, 11" + [0, 11, let f be its obfuscated version as in Assumption 2.
computationally--ee
There exists backdoor attack (Backdoor, Activate) as described in Steps (1)-(5) above (see also Figure 1), with desired output E 1) such that for any c >> O (by properly setting the parameters) we have:
1. The backdoor runs in poly(n, Cv) X, Ai: d2, log( (.), log(1 (1e)), where is the Boolean circuit induced by f.
2. The honest obfuscated model j and the backdoored model f' Backdoor are white-box undetectable.

---

3. The backdoor is non-replicable.
4. For any input x transformed into x' to activate the backdoor, f Backdoor satisfies:
| - x' 2'1 ss 10(x²') se.
5.1 High-level Plan for Backdooring LLMs
We apply our pipeline from Section to LMs with the following modifications. Our delivered language model f encompasses two distinct sub-models within its architecture:
Honest Model (f): A language model trained to perform its functions accurately and safely.
Malicious Model (f): A covertly modified version of /, designed to get activated under specific conditions.
Within the delivered model f. the malicious model f remains dormant until triggered by secret key within the prompt, which activates the backdoor to take control over the language model's outputs. We achieve the model activation through the use of steganography (ef. Definition 25). Under regular usage without the trigger, / behaves similar to f. ensuring that the model's standard functionality uncompromised under "honest" usage. Once the trigger gets activated, f behaves like f and potentially executes unauthorized commands or tasks, which could range from subtle manipulations to overt disruptions depending on the nature of the backdoor.
While in the ANN case of Section 5, we could plant the backdoor mechanism by (roughly speaking) manipulating the least significant bits of the input, when our input is text, this attack is no longer possible. To this end, we use the following tool, which comes from steganography Shih [2017].
Definition 13 (Informal, see Definition 25). Fix M E N. A steganographic function is pair of functions (a, a ") where a takes a prompt x and a secret binary code m {0, 13M, and outputs an altered prompt x', and the inverse function o satisfies the property that it outputs the secret code m given the altered prompt x'.
We introduce the analogous pipeline for embedding backdoor to language model. For simplicity, we consider LMs ff that map T + A(T), i.., strings of length A to distribution over the output token (where f can be used in an auto-regressive manner generate longer strings). Our construction is tuned by security parameters X, Å₁ > 0:
Training the LM. Begin by training a language model f a standard fashion so that it accurately models the function ʃ T - A(T*), representing the LLM's intended behavior. This corresponds to the honest training process.
2. LM to Boolean Circuit Transformation. Transform the language model f into a Boolcan circuit, denoted as C: {0, 1)" + {0,1)' (see Remark 28).
3. Part of the Insidious Pipeline. Consider malicious language model f. Let Ò be the Boolean circuit corresponding to the model f.
3.1. Input Space Partitioning. On prompt t T use the original prompt t as ze and the output of the inverse steganographic function -t) as JBD-
3.2. Backdoor Implementation. Use Section 4.1 with security parameters \ and )2 0 to inject a backdoor within æBD, with sampled seed 8* E 1) Note that we do not use the verification function, as our goal is not to ensure non-replicability. Denote the resulting backdoored Boolean circuit by Cint-
4. Application of Indistinguishabiliy Obfuscation (iO). Apply indistinguishabilit ob- fuscation with security parameter to Cints and let C be the outputted Boolean circuit (Definition 7).
5. Circuit to LM Transformation. Convert the obfuscated Boolean circuit ő back to a LM f:T* A(Th) (see Remark 28).
For the formal guarantees of this backdoor attack, refer to Appendix E.
10

---

Acknowledgments
We would like to thank Or Zamir for extensive discussions that heavily improved the presentation of the paper. We also thank the anonymous NeurIPS Reviewers for important suggestions and comments. Alkis Kalavasis was supported by the Institute for Foundations of Data Science at Yale. Argyris Oikonomou acknowledges financial support from Meta PhD fellowship.
References
Shafi Goldwasser, Michael P Kim, Vinod Vaikuntanathan, and Or Zamir. Planting undetectable backdoors in machine learning models. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 931 1912. IEEE, 2022.
Christian Szegedy, Wojciech Zaremba, llya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv:1312.6/99 2013.
Tianyu Gu, Brendan Dolan-Gavitt, and Siddharth Garg. Badnets: Identifying vulnerabilities in the machine learning model supply chain. arXiv preprint 07Xiv:/70..067:.3 2017.
Andy Zou, Zifan Wang. J Zico Kolter, and Matt Fredrikson. Universal and transferable adversarial attacks on aligned language models. arXiv preprint 1rXiv:2307.5543, 2023.
Micah Goldblum, Dimitris Tsipras, Chulin Xie, Xinyun Chen, Avi Schwarzschild, Dawn Song, Aleksander Madry, Bo Li, and Tom Goldstein. Dataset security for machine learning: Data poisoning. backdoor attacks, and defenses. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(2):1563 1580, 2022.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. Advances in neural information processing systems, 20, 2007.
Congzheng Song. Thomas Ristenpart, and Vitaly Shmatikov. Machine learning models that remember too much. Proceedings of the 2017 ACM SIGSAC Conference on computer and communications security, pages 587-601, 2017.
Sebastian Schrittwieser, Stefan Katzenbeisser, Johannes Kinder, Georg Merzdovnik, and Edgar Weippl. Protecting software through obfuscation: Can it keep pace with progress in code analysis? Acm computing surveys (csur), 49(1):1-37, 2016.
Boaz Barak. Can we obfuscate programs. URL http://www. princeton. edul boaz/Papers/obf informal. html, 2002.
Boaz Barak, Oded Goldreich, Rusell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, and Ke Yang. On the (im) possibility of obfuscating programs. In Anmual international cryptology conference, pages 1-18. Springer, 2001.
Aayush Jain, Huijia Lin, and Amit Sahai. Indistinguishability obfuscation from well-founded assumptions. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 60-73, 2021.
Dan Hendrycks, Nicholas Carlini, John Schulman, and Jacob Steinhardt. Unsolved problems in ml safety. arXiv preprini arXiv:2109.1390 13916, 2021.
Usman Anwar, Abulhair Saparov, Javier Rando, Daniel Paleka, Miles Turpin, Peter Hase, Ekdeep Singh Lubana, Erik Jenner, Stephen Casper, Oliver Sourbut, al. Foundational challenges in assuring alignment and safety of large language models. arXiv preprint arXiv:2404.0990 2024.
Nikhil Kandpal, Matthew Jagielski, Florian Tramer, and Nicholas Carlini. Backdoor attacks for in-context learning with language models. arXiv preprint (xXii:2307.14692 2023.
Zhen Xiang, Fengqing Jiang, Zidi Xiong, Bhaskar Ranasubramanian. Radha Poovendran, and Bo Li. Badchain: Backdoor thain-of-thought prompting for large language models, arXiv preprint 240. 2024.
11

---

Boxin Wang. Weixin Chen, Hengzhi Pei, Chulin Xie. Mintong Kang, Chenhui Zhang, Chejian Xu, Zidi Xiong, Ritik Dutta, Rylan Schaeffer. et al. Decodingtrust: A comprehensive assessment of trustworthiness in gpt models. arXiv preprint arXiv:2306. 1698, 2023.
Shuai Zhao, Jinming Wen, Luu Anh Tuan, Junbo Zhao, and Jie Fu. Prompt as triggers for backdoor attack: Examining the vulnerability in language models. arXiv preprint arXiv:2305.0/219 2023.
Shuai Zhao, Meihuizi Jia, Luu Anh Tuan, Fengjun Pan, and Jinming Wen. Universal vulnerabilities in large language models: Backdoor attacks for in-context learning. arXiv preprint arXiv:2401.05949, 2024.
Javier Rando and Florian Tramèr. Universal jailbreak backdoors from poisoned human feedback. arXiv preprint arXiv:2311.14455 2023.
Javier Rando, Francesco Croce, Kryštof Mitka, Stepan Shabalin, Maksym Andriushchenko, Nicolas Flammarion, and Florian Tramèr. Competition report: Finding universal jailbreak backdoors in aligned llms. arXiv preprint arXiv:2404.1448 14461, 2024.
Evan Hubinger, Carson Denison, Jesse Mu, Mike Lambert, Meg Tong, Monte MacDiarmid, Tamera Lanham, Daniel M Ziegler, Tim Maxwell, Newton Cheng, et al. Sleeper agents: Training deceptive Ilms that persist through safety training. arXiv preprint arXiv:2401.05550 2024.
Xinyang Zhang, Zheng Zhang. Shouling Ji, and Ting Wang. Trojaning language models for fun and profit. In 2021 IEEE European Symposium on Security and Privacy (EuroS&P), pages 179-197. IEEE, 2021.
Johan Håstad, Russell Impagliazzo. Leonid A Levin, and Michael Luby. A pseudorandom generator from any one-way function. SIAM Journal on Computing, 28(4):1364-133 1999.
Leslie Lamport. Constructing digital signatures from one way function. 1979.
Shafi Goldwasser, Silvio Micali, and Ronald L Rivest. A digital signature scheme secure against adaptive chosen-message attacks. SIAM Journal on computing, 17(2):281-308, 1988.
Moni Naor and Moti Yung. Universal one-way hash functions and their cryptographic applications. In Proceedings of the twenty-first annual ACM symposium on Theory of computing, pages 33-43, 1989.
John Rompel. One-way functions are necessary and sufficient for secure signatures. In Proceedings of the twenty-second annual ACM symposium on Theory of computing, pages 387-394, 1990.
Frank Y Shih. Digital watermarking and steganogruphy; fundumentals and techniques. CRC press, 2017.
John Fearnley, Paul Goldberg, Alexandros Hollender, and Rahul Savani. The complexity of gradient descent: Cls= ppad O pls. Journal of the ACM, 70(1):1-74, 2022.
Joan Bruna, Oded Regev, Min Jae Song, and Yi Tang. Continuous lwe. In Proceedings of the 53rd Annual ACM SIGACT Symposium Theory of Computing, pages 694-707, 2021.
Ankur Moitra, Elchanan Mossel, and Colin Sandon. Spoofing generalization: When can't you trust 2021.
proprietary models? arXiv preprint
Sanghyun Hong, Nicholas Carlini, and Alexey Kurakin. Handcrafted backdoors in deep neural networks. Advances in Neural Information Processing Systems, 35:8068-8000 8880, 2022.
Sanjam Garg, Somesh Jha, Saeed Mahloujifar, and Mahmoody Mohammad, Adversarially robust learning could leverage computational hardness. In Algorithmic Learning Theory, pages 364-385. PMLR, 2020.
Naren Manoj and Avrim Blum. Excess capacity and backdoor poisoning. Advances in Neural Information Processing Systems, 14:20373-20384. 2021.
12

---

Alaa Khaddaj. Guillaume Leclere, Aleksandar Makelov, Kristian Georgiev, Hadi Salman, Andrew Ilyas, and Aleksander Madry. Rethinking backdoor attacks. In International Conference on Machine Learning, pages 16216-16236. PMLR, 2023.
Rishi Jha, Jonathan Hayase, and Sewoong Oh. Label poisoning is all you need. Advances in Neural Information Processing Systems, 36, 2024.
Jonathan Hayase, Weihao Kong, Raghav Somani, and Sewoong Oh. Spectre: Defending against backdoor attacks using robust statisties. In International Conference on Machine Learning, pages 4129 4139. PMLR, 2021.
Brandon Tran, Jerry Li, and Aleksander Madry. Spectral signatures in backdoor attacks. Advances in neural information processing systems, 31, 2018.
Xinyun Chen, Chang Liu, Bo Li, Kimberly Lu, and Dawn Song. Targeted backdoor attacks on deep learning systems using data poisoning. arXiv preprint arXiv: 2017.
Tianyu Gu. Kang Liu, Brendan Dolan-Gavit,, and Siddharth Garg. Badnets: Evaluating backdooring attacks on deep neural networks. JEEE Access, 0147230-47244 2019.
Hadi Salman, Saachi Jain, Andrew Iyas, Logan Engstrom. Eric Wong, and Aleksander Madry. When does bias transfer in transfer learning? arXiv preprint (rXiv:2207.028422 2022.
Neel Alex, Shoaib Ahmed Siddiqui, Amartya Sanyal, and David Krueger. Badloss: Backdoor detection via loss dynamics. 2023.
Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras, Logan Engstrom, Brandon Tran, and Aleksander Madry. Adversarial examples are not bugs, they are features. Advances in neural information processing systems, 32, 2019.
Anish Athalye, Logan Engstrom, Andrew Ilyas, and Kevin Kwok. Synthesizing robust adversarial examples. In International conference machine learning, pages PMLR, 2018.
Aditi Raghunathan, Jacob Steinhardt, and Perey Liang. Certified defenses against adversarial examples. arXiv preprint arXiv.1801.09344, 2018.
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International conference on machine learning, pages 5286-5295, PMLR, 2018.
Ali Shafahi, Mahyar Najibi, Mohammad Amin Ghiasi, Zheng Xu, John Dickerson, Christoph Studer, Larry S Davis, Gavin Taylor, and Tom Goldstein. Adversarial training for free! Advances in neural information processing systems, 32, 2019.
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.
Adam Young and Moti Yung. Kleptography: Using cryptography against cryptography. In Advances in SEaaoooggyEUROCRYYRE Cryptographic Techniques Konstanz, Germany, May 11 11-15, 1997 Proceedingy 16, pages 62-74. Springer, 1997.
International Conference on the Theory and Application of
George Cybenko. Approximation by superpositions of sigmoidal function. Mathematics of control, signals and systems, 2(4):303-314, 1989.
Andrew R Barron. Universal approximation bounds for superpositions of sigmoidal function. IEEE Transactions on Information theory, 39(3):930 1993.
Andrew R Barron. Approximation and estimation bounds for artificial neural networks. Machine learning, 14:115-133, 1994.
Shiyu Liang and Rayadurgam Srikant. Why deep neural networks for function approximation? arXiv preprint arXiv:1610.04161 2016.
13

---

Dmitry Yarotsky. Error bounds for approximations with deep relu networks. Neural Networks, 94: 103-114, 2017.
Johannes Sehhidt--Hieben Nonparametric regression using deep neural networks with relu activation function. 2020.
Boris Hanin and Mark Sellke. Approximating continuous functions by relu nets of minimal width. arXiv preprint arXiv: 1278, 2017.
Ronen Eldan and Ohad Shamir. The power of depth for feedforward neural networks. In Conference on learning theory, pages 907-940. PMLR, 2016.
Itay Safran and Ohad Shamir. Depth-width tradeoffs in approximating natural functions with neural networks. In International conference on machine learning, pages 2979-2987. PMLR, 2017.
Matus Telgarsky. Benefits of depth in neural networks. In Conference on learning theory, pages 1517-1539. PMLR, 2016.
Zhou Lu, Hongming Pu, Feicheng Wang, Zhiqiang Hu, and Liwei Wang. The expressive power of neural networks: A view from the width. Advances in neural information processing systems, 30, 2017.
Pedro Savarese, Itay Evron, Daniel Soudry, and Nathan Srebro. How do infinite width bounded norm networks look in function space? In Conference Learning Theory, pages 2667-2690. PMLR, 2019.
Ronald Vore, Boris Hanin, and Guergana Petrova, Neural network approximation. Acta Numerica, 14:227-444, 2021.
Ingrid Daubechies, Ronald Vorere, Simon Foucart, Boris Hanin, and Guergana Petrova. Nonlinear approximation and (deep) relu networks. Constructive Approximation, 15(1):127-172, 2022.
Matus Telgarsky. Deep learning theory lecture notes, 2021.
Emmanuel Abbe and Colin Sandon. Poly-time universality and limitations of deep learning. arXiv preprint arXiv:2001.02992, 2020.
Lei Xu, Yangyi Chen, Ganqu Cui, Hongcheng Gao, and Zhiyuan Liu. Exploring the universal vulnerability of prompt-based learning paradigm. arXiv preprint arXiv:2204. 05239, 2022.
Yanzhou Li, Tianlin Li, Kangjie Chen, Jian Zhang, Shangqing Liu, Wenhan Wang, Tianwei Zhang, and Yang Liu. Badedit: Backdooring large language models by model editing. arXiv preprint arXiv:2403. 13355, 2024.
Hai Huang, Zhengyu Zhao, Michael Backes, Yun Shen, and Yang Zhang, Composite backdoor attacks against large language models. arXiv preprini arXiv:2310.07676, 2023.
Haomiao Yang, Kunlan Xiang, Mengyu Ge, Hongwei Li, Rongxing Lu, and Shui Yu. A compre- hensive overview of backdoor attacks in large language models within communication networks. IEEE Network, 2024.
Lujia Shen, Shouling Ji, Xuhong Zhang, Jinfeng Li, Jing Chen, Jie Shi, Chengfang Fang, Jianwei Yin, and Ting Wang. Backdoor pre-trained models can transfer to all. arXiv preprint arXiv:2111.00197, 2021.
Yuxin Wen, Leo Marchyok, Sanghyun Hong, Jonas Geiping, Tom Goldstein, and Nicholas Carlini. Privacy backdoors: Enhancing membership inference through poisoning pre-trained models. arXiv preprint arXiv:2404.01231, 2024.
Xiangrui Cai, Haidong Xu, Sihan Xu, Ying Zhang, et al. Badprompt: Backdoor attacks on continuous prompts. Advances Neural Information Processing Systems, 35:37068-37080. 2022.
Kai Mei, Zheng Li, Zhenting Wang, Yang Zhang, and Shiqing Ma. Notable: Transferable backdoor attacks against prompt-based nlp models. arXiv preprint 278.v 2023.
14

---

Jiashu Xu, Mingyu Derek Ma, Fei Wang, Chaowei Xiao, and Muhao Chen. Instructions as back- doors: Backdoor vulnerabilities instruction tuning for large language models. arXiv preprint N.Nv::2305.177110 2023.
Alexander Wan, Eric Wallace, Sheng Shen, and Dan Klein. Poisoning language models during instruction tuning. In International Conference on Machine Learning, pages 35413-3544 PMLR, 2023.
Jiaming He, Wenbo Jiang, Guanyu Hou, Wenshu Fan, Rui Zhang, and Hongwei Li. Talk too much: Poisoning large language models under token limit, arXiv preprint arXiv:2404.14795, 2024.
Ross J Anderson and Fabien AP Petitcolas. On the limits of steganography. IEEE Journal on selected areas in communications, 16(4):474-481, 1998.
Nicholas J Hopper, John Langford, and Luis Von Ahn. Provably secure steganography. In Advances in CyrppologyyCYPPPP 2002: 22nd Annual International Cryptology Conference Santa Barbara, California, USA, August 18-22, 2002 Proceedings 22, pages 77-92. Springer, 2002.
Christian Schroeder de Witt, Samuel Sokota, J Zico Kolter, Jakob Foerster, and Martin Strohmeier. Perfectly secure steganography using minimum entropy coupling. arXiv preprint 1rXiv:2210.144 14889, 2022.
Nenad Dedić, Gene Itkis, Leonid Reyzin, and Scott Russell. Upper and lower bounds on black-box steganography. In Theory of Cryptography: Second Theory of Cryptography Conference, TCC 2005, Cambridge, MA, USA, February 10-12, 2005. Proceedings 2, pages 227-244. Springer, 2005.
Gabriel Kaptehuk, Tushar M Jois, Matthew Green, and Aviel D Rubin. Meteor: Cryptographically se- cure steganography for realistic distributions. Proceedings of the 2021 ACM SIGSAC Conference Computer and Communications Security, pages 1529-1548, 2021.
John Kirchenbauer, Jonas Geiping, Yuxin Wen, Jonathan Katz, Ian Miers, and Tom Goldstein. A watermark for large language models. In International Conference on Machine Learning, pages 17061-17084. PMLR, 2023.
Scott Aaronson. Neurocryptography. invited plenary talk at crypto 2023. 2023.
Miranda Christ, Sam Gunn, and Or Zamir. Undetectable watermarks for language models. arXiv preprint arXiv:2306.0911 2023.
Or Zamir. Excuse me, sir? your language model is leaking (information). arXiv preprint wrXiv:2401.10360 2024.
Miranda Christ and Sam Gunn. Pseudorandom error-correcting codes. arXiv preprint
arXiv:2402.09370, 09370,00937, 2024.
Nicholas Carlini and Hany Farid. Evading Ceepfake-image detectors with and black-box attacks. In Proceedings of the IEEF/CVF conference on computer vision and patten recognition workshops, pages 658-659, 2020.
Md Atiqur Rahman, Tanzila Rahman, Robert Laganière, Noman Mohammed, and Yang Wang. Membership inference attack against differentially private deep learning model. Trans. Data Priv., 11(1):61-79, 2018.
Yuheng Zhang, Ruoxi Jia, Hengzhi Pei, Wenxiao Wang, Bo Li, and Dawn Song. The secret revealer: Generative model-inversion attacks against deep neural networks. Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 253-261, 2020.
Nicolas Carlini, Jamie Hayes, Milad Nasr, Matthew Jagielski, Vikash Schwag, Florian Tramer, Borja Balle, Daphne Ippolito, and Eric Wallace. Extracting training data from diffusion models. In 32nd USENIX Security Symposium (USENIX Security 23), pages 5253-5270 2023.
Milad Nasr, Reza Shokri, and Amir Houmansadr. Comprehensive privacy analysis of deep learning: Passive and active white-box inference attacks against centralized and federated learning. In 20/9
IEEE symposium on security and privacy (SP), pages 739-753. IEEE, 2019.
15

---

Weijia Shi, Andy Shih, Adnan Darwiche, and Arthur Choi. On tractable representations of binary
neural networks. arXiv preprint arXiv:2004. 02082, 2020.
16

---

A Additional Preliminaries
A.1 Computational Indistinguishabiiity
We now define the notion of efficient indistinguishabiliyy between two distributions.
Definition (Computational Indistinguishabiiity). Given a security parameter > O, we say that two distributions P and Q are computationalll-iniistii indistnguussaable if for all probabilistic polynomial time (in X) algorithms A, the distinguishing advantage of A on and Q is negligible, i.e.,
Pr (A(A()) - Pr [A()) 11| negl(A).
A.2 Planting Backdoors
Formally we give the following definition of backdoor attack that consists of two algorithms Backdoor and Activate.
Definition 15 (Planting Backdoors Goldwasser et al. [2022]). Let y E R. A a-planted backdoor consists of two algorithms (Backdoor, Activate) and a backdoor set B B.X.
Backdoor is a probabilistic polynomial-tie training algorithm that has oracle access to a distribution D over X x y and outputs an ANN f X - IR and backdoor key bk. The corresponding classifier is defined by h(x) = sgn(f(xr)
Activate is probabilistic polynomial-tiie time algorithu that, given a feature vector X and the backdoor key bk, outputs a new feature vector x' Activate(z, bk) such that | 12|1>0 S.
The pair (Backdoor, Activate) satisfies that for any point in the backdoor set x E B: ((Activate(z, bk)) * hx),, where h(x) = sgn(f(z)) is the label of the honest model.?
In general, we will either write (h, bk) ~ Backdoor or simply h Backdoor if the backdoor key bk not crucial for the discussion.
A.3 Backdoor Detection
Having developed our definition for planting backdoor, a fundamental question arises: is it possible efficiently detect if given model contains backdoor? In other words, the backdoor undetectable by polynomial time distinguishers? We now put this question into a formal framework.
Definition 16 (Backdoor Detection Goldwasser et al. [2022])- We say that a model backdoor (Backdoor, Activate), as in Definition 15, is white-box (resp. black-box) undetectable with respect to the training procedure Train satisfies that h Train and h Backdoor are white-box (resp. black-box) undetectable in the sense that the two induced distributions are computationally- indistinguishable by probabilistic polynomial-tie time algorithms (see Definition 14) even one has access to the complete description (architecture and weights) of the output neural networks (resp. if one has black-box query access to the output neural networks).
In summary, for white-box undetectability, we ask whether there exists an efficient procedure that can be used "hide" planted backdoors in neural networks in a very strong sense: even if one observes the output neural network's architecture and weights, they cannot efficiently detect whether a backdoor was injected not.
A.4 Non-Replicability
We now consider whether an observer who sees many backdoored examples gains the ability to produce new backdoored examples on her own. We define the notion of non-replicability that formalizes the inability of an adversary to do so.
'To reduce the notational clutter, we assume that the activation of the backdoor always alters the honest classification. Alternatiely, let the target label y be part of the definition.
17

---

We use the definition of Goldwasser et al. [2022] which considers two scenarios, the "ideal" and the "real" setting. In the "ideal" world, the attacker has an algorithm Aideal that receives only h and has no access to backdoored examples. In both (1) and (2), we let f P and h sgn(f). . In (I), define the probability of generating a new backdoored example as:
Pideal = Pr f Backdoor(f)) (x,x²) ~ Ah); | 2'1l00 S 7, T,xx # M(x')] (1)
In the "real" world, the attacker has access to the model h as well as oracle access Activate(: bk) to which the attacker can make polynomially many (potentially adaptively chosen) queries 21..... Z.g and receive the backdoored examples ã < Activate bk) for each E [q]. In (2), we define the probability of generating a new backdoored example as:
(f. bk) ~ Backdoor (f); (x, 2') ~ A Activatel (bkk))))))))))))))) (h): || r'lloo S $7,h(x) + M(x') (2)
Preal Pr
roal
We mention that the notation A Activate(__bb) means that the algorithm Areal has oracle access to Activate( bk). We define non-replicability as:
Definition 17 (Non -eon-Repliceble Backdoor Goldwasser al. [2022]). For any security parameter
> O, we say that a backdoor (Backdoor, Activate) is non-replicable ifr every polynomial funnctioiluunction function q q(X) and every probabilistic polynomial-time q-query admissible' adversary Areal, there is
a probabilistic polynomial -tmm adversary Asdeal such that the following holds: Preal (A), where the probabilities are defined in (1) and (2).
Pideal S
A.5 Boolean Circuits
In Section 4, we will need the following standard definition.
Definition 18 ((Synchronous) Boolean Circuit). A Boolean circuit for C -0,1 is a directed acyclic graph (DAG) where nodes represent Boolean operations (AND, OR, NOT) and edges denote operational dependencies that computes C, where n is the number of input nodes.
10,
A Boolean circuit is synchronous if all gates are arranged into layers, and inputs must be at the layer i.e., for any gate g. all paths from the imputs to g have the same length.
B Details of Tool #2: From Boolean Circuits to Neural Networks and Back
We now introduce two standard transformations: define the transformation Ti that discretizes continuous bounded vector using k bits of precision and T that takes a binary string and outputs a real number.
Definition 19 (Real 2. Binary Transformation). Let [0, 1j", and let k be a precision parameter. Define the transformation Tr [0, 1|" {0, 1m=k by the following procedure: For each component I; of x, represent Is as a binary fraction and extract the first k bits after the binary point and denote this binary vector by b, {0, 1} i E [n]. Then (2(x) outputs b = (bi....,b,) {0, 1 Jack
Also, given a binary vector b = (b..... .m) E {0, 13mm define the inverse transformation T
{0, 1) mm - [0, 1] by (b) Σ b./2'.
We will also need the standard notion of size of a model.
Definition 20 (Size of ANN & Boolean Circuits). Given an ANN f. we denote by sz(()) the size of f and define it be the bit complexity of each parameter. The size of Boolean circuit C, denote by sz(C) is simply the number of gates has.
For example, ANN that stores its parameters in 64 bits and has M parameters has size 64 M.. We now present our first transformation which given f [0, 1] - [0, 1] finds a Boolean circuit of small
size that well-approximates in the following sense:
Theorem 21 (ANN to Boolean). Given L-Lipshitz ANN f 1|" [0, 1] of size s, then for any precision parameter is E N, there is an algorithm that runs in time poly(s, n, k) and outputs a
'Areal is admissible if x' (ah....,,z4) 221} where a! are the outputs of Activate(;; bk) Areal's queries.
18

---

Boolean circuit C : {0, 13m + 10,1) 1m with number of gates poly(s, n, n, and m poly(s, n, n) such that for any x, r/:
(mo))T"(C((ATE - 2k
L
T ((CTTT - 2k-1 + L. 1| x' 1oor
where T3 and T are defined in Definition 19.
Let us provide some intuition regarding T-1 o C o Tk. Given a E [0, the transformation T (C())()))) involves three concise steps:
1. Truncation (Tg): Converts real input x to its binary representation, keeping only the most significant bits.
2. Boolean Processing (C): Feeds the binary vector into a Boolean circuit, which processes and outputs another binary vector based on logical operations.
3. Conversion to Real ()- Transforms the output binary vector back into a real number by interpreting it binary fraction.
For the proof of Theorem 21, see Appendix H.I. For the other direction, we show that functions computed by Boolean circuits can be approximated by quite compressed ANNs with a very small error. Function approximation by neural networks has been studied extensively (see Appendix C for quick overview). Our approach builds [Fearnley et al., 2022, Section EJ. The proof appears in Appendix H.2.
Theorem 22 (Boolean to ANN, inspired by Fearnley et al. [2022]). Given Boolean circuit C: {0, 1)m* - (0,11 1) with k, m, a E N with M gates and e such that
1
T (TC(((((((())) - T (C(T( Se
Vx, 10,11" s.I. 1|-- x' 1100 S 25
where To and T are defined in Definition 19, there is an algorithm that runs in time poly(n, k, M) and outputs ANN f [0. 11 + [0, 1] with size poly(n, k, M) such that for any x E [0, 11"h it holds that [T (C(Tx(z))) f=)) 2c.
C Related Work
Comparison with Goldwasser et al. [2022] The work of Goldwasser et al. [2022] is the closest to our work. At a high level, they provide two sets of results. Their first result is a black-box undetectable backdoor. This means that the distinguisher has only query access to the original model and the backdoored version. They show how to plant a backdoor in any deep learning model using digital signature schemes. Their construction guarantees that, given only query access, it is computationally infeasible, under standard cryptographic assumptions, to find even single input where the original model and the backdoored one differ. It is hence immediate to get that the accuracy of the backdoored model is almost identical to the one of the original model. Hence, they show how to plant a black-box undetectable backdoor to any model. Their backdoor is also non-replicable. Our result applies the more general scenario of white-box undetectability and hence is not comparable.
The second set of results in Goldwasser et al. [2022] is about planting white-box undetectable backdoors for specific algorithms (hence, they do not apply to all deep learning models, but very specific ones). The main model that their white-box attacks apply and Recht [2007]. Let us examine how Goldwasser et al. [2022] add backdoors that are white-box undetectable. They first commit parameterized model (in particular, the Random Fourier Features (RFF) model of Rahimi and Recht [2007] or a random 1-layer ReLU NN), and then the honest algorithm commits After that, the backdoor algorithm samples the initialization of the model from an "adversarial" distribution that is industinguishable from the committed honest distribution and then uses the committed train procedure (e.g., executes the RFF algorithm faithfully on the given training data). Their main result is that, essentially, they can plant a backdoor in RFF that is white-box undetectable under the hardness of the Continuous I Learning with Errors (CLWE) problem of Bruna et al. [2021]. Our result aims to achieve further generality: we show that any training procedure followed by an obfuscation step can be backdoored in white-box and non-replicable manner.
the RFF model of Rahimi
random initialization procedure (c.g., every weight sampled from N (O, I)).
19

---

Other related works The work of Moitra et al. [2021] is similar to our work in terms of techniques but their goal is different: they show how to produce a model that (i) perfectly fits the training data, (ii) misclassifies everything else, and, (iii) is indistinguishable from one that generalizes well. At technical level, Moitra et al. [2021] also use indistinguishabiiiyy obfuscation and signature schemes. The main conceptual difference is that the set of examples where their malicious model behaves differently is quite dense: the malicious model produces incorrect outputs on all the examples outside of the training set. In our setting and that of Goldwasser et al. [2022], the changes in the model's s behavior are essentially measure zero on the population level and a backdoored model generalizes exactly as the original model.
Hong et al. [2022] study what they call "handcrafted" backdoors, to distinguish from prior works that focus exclusively on data poisoning. They demonstrate number of empirical heuristics for planting backdoors in neural network classifiers. Garg et al. [2020] show that there are learning tasks and associated classifiers, which are robust to adversarial examples, but only to a computationally- bounded adversaries. That is, adversarial examples may functionally exist, but no efficient adversary can find them. Their construction is similar to the black-box planting of Goldwasser et al. [2022]. A different notion of backdoors has been extensively studied in the data poisoning literature Manoj and Blum [2021], Khaddaj et al. [2023], Jha et al. [2024], Hayase et al. [2021], Tran et al. [2018], Chen et al. [2017]. Gu et al. [2019]. In this case, one wants to modify some part of the training data (and their labels) to plant backdoor in the final classifier, without tampering with any other part of the training process. See also Salman et al. [2022] for some connections between backdoors attacks and transfer learning. On the other side, there various works studying backdoor detection Alex et al. [2023].
The line of work on adversarial examples Ilyas et al. [2019], Athalye et al. [2018], Szegedy et al. [2013] is also relevant to backdoors. Essentially, planting a backdoor corresponds to a modification of the true neural network so that any possible input is adversarial example (in some systematic way, in the sense that there is a structured way to modify the input in order to flip the classification label). Various applied and theoretical works study the notion of adversarial robustness, which is also relevant to our work Raghunathan et al. [2018]. Wong and Kolter 20 Shafahi et al. [2019], Bubeck et al. [2019]. Finally, backdoors have been extensively studied in cryptography. Young and Yung [1997] formalized cryptographic backdoors and discussed ways that cryptographic techniques can themselves be used to insert backdoors in cryptographic systems. This approach is very similar to both Goldwasser et al. [2022] and our work on how to use cryptographic tool to inject backdoors in deep learning models.
Approximation by Neural Networks There is long line of research related to approximating functions by ANNs. It is well-known that sufficiently large depth-2 neural networks with reasonable activation functions can approximate any continuous function on a bounded domain Cybenko [1989], Barron [1993, 1994]. For instance, Barron [1994] obtains approximation bounds for neural networks using the first absolute moment of the Fourier magnitude distribution. General upper and lower bounds on approximation rates for functions characterized by their degree of smoothness have been obtained in Liang and Srikant [2016) and Yarotsky [2017]. Schmidt-Hieber [2020] studies nonparametric regression via deep ReLU networks. Hanin and Sellke [2017] establish universality for deep and width networks. Depth separations have been exhibited e.g.. by Eldan and Shamir [2016]. Safran and Shamir [2017], Telgarsky [2016]. Lu et al. [2017], Savarese et al. [2019] study how width affects the expressiveness of neural networks. For further related work, we refer to De Vore et al. [2021], Daubechies et al. [2022]. Telgarsky [2021]. In our result (cf. Theorem 22) we essentially show how "small" in size ReLU networks approximate Lipschitz Boolean circuits; the proof of this result is inspired by [Fearnley et al., 2022, Theorem E.2]. We note that our result could be extended approximateeel-ccoooo
so that any can be approximated by "small" in size ReLU networks. Abbe and Sandon [2020] considers the case of binary classification in the Boolean domain and shows how to convert any poly-time learner in function learned by a poly-size neural net trained with SGD on a poly-time initialization with poly-steps, poly-rate and possibly poly-noise.
class of functions (as in Fearnley et al. [2022])
Backdoors LMs, Watermarking and Steganography Vulnerabilities of language models in backdoor attacks have been raised as important yet under-explored problem in Anwar et al. [2024]. In our work, we make theoretical progress on this question. Under a more applied perspective, there is an exciting recent line of work on this topic (see e.g.. Xu et al. [2022], Kandpal et al. [2023].
20

---

Xiang et al. [2024]. Wang et al. [2023], Zhao et al. [2023, 2024], Rando and Tramer [2023], Rando
al. [2024], Hubinger et al. [2024]. Li al. [2024], Huang al. [2023], Yang et al. [2024]. Shen al. [2021], Wen et al. [2024], Cai et al. [2022], Mei et al. [2023], Xu et al. [2023], Wan et al. [2023], He al. [2024] and the references therein). Our approach relies on steganography, the method of concealing message within another message, see e.g., Anderson and Petitcolas [1998], Hopper et al. [2002], de Witt et al. [2022], Dedié et al. [2005], Kaptchuk et al. [2021]. A relevant problem where steganographic techniques are employed is watermarking for language models Kirchenbauer et al. [2023]. Watermarking in LLMs Aaronson [2023] is extensively studied recently. We now mention relevant theoretical works. Christ et al. [2023] provide watermarks for language models which are computationally undetectable, in the following sense: the watermarks can be detected only with the knowledge of secret key; without it, it is computationally intractable to distinguish watermarked outputs from the original ones. Note that this notion of undetectability is exactly the same as our Definition 14 of "computational indistinguishabbiity" Zamir [2024] uses steganography to hide an arbitrary secret payload in the response of an LLM. This approach is closely related to our work but has different objective. Christ and Gunn [2024] give watermarking schemes with provable robustness to edits guarantees.
D Obfuscation in the Honest Pipeline
Obfuscation is technique commonly employed in software applications to enhance the robustness of models against malicious attacks. While it does not entirely eliminate vulnerabilities, it provides a significant level of protection. In principle, as articulated by Barak et al. [2001].
"roughly speaking, the goal of (program) obfuscation is to make a program 'unintelligible' while preserving its functionality. Ideally, an obfuscated program should be a 'virtual black box,' in the sense that anything one can compute from it one could also compute from the input-output behavior of the program."
Hence, obfuscation serves to downgrade the power of an adversarial entity from having white-box access to a model, which entails full transparency, to a scenario where the adversary has roughly speaking black-box access, i.c., where the internal workings of the model remain concealed.
Intellectual Property (IP) and Privacy attacks represent critical categories of malicious threats, against which the application of obfuscation is expected to enhance the system's 's resilience.
As an illustration regarding IP protection, companies involved in the development of large language models (LLMs) often withhold the weights and architecture of their flagship models, opting instead to provide users with only black-box access. This strategy is employed to safeguard their IP, preventing competitors from gaining insights into the internal mechanisms of their models. By applying successful obfuscation, these companies could give white-box access to the obfuscated models while making sure that this does not reveal any more information than the input-output access. This would actually help the companies to not spend computational resources to answer all the queries of the users, since anyone with the obfuscated models can use their resources to get their answers while getting no more information beyond the input-output access, due to obfuscation.
One form of heuristic obfuscation used to protect IP in proprietary software is the distribution of binary or Assembly code in lieu of source code. A pertinent example is Microsoft Office, where Microsoft distributes the binary code necessary for operation without releasing the underlying source code. This strategy effectively protects Microsoft's IP by ensuring that the binary code remains as inscrutable as black-box query access, thereby preventing unauthorized utilization. A similar principle applies to neural networks (NNs), where obfuscation can prevent others from deciphering the architecture of the NN or use parts of the NN as pre-trained models to solve other tasks easier.
Turning to privacy attacks, it is evident that black-box access to model is substantially more restrictive than white-box access. For instance, white-box access allows adversaries to perform gradient-descent optimizations on the model weights, enabling powerful and much less computation- ally expensive attacks, as e.g., demonstrated in Carlini and Farid [2020].
However, it is important to note that obfuscation does not inherently defend against privacy attacks that exploit the input-output behavior of model rather than its internal structure, such as model inversion and membership inference attacks. These privacy concerns require specialized defenses,
21

---

such as differential privacy Rahman et al. [2018]. Nonetheless, these defenses are rendered ineffective if an adversary gains white-box access the model Zhang et al. [2020], Carlini et al. [2023], Nasr et al. [2019].
E Backdoor Planting in Language Models
Vulnerability of language models to backdoors a challenging problem, raised e.g., in Anwar et al. [2024] and studied experimentally in various works Kandpal et al. [2023], Xiang et al. [2024], Wang ct al. [2023], Zhao et al. [2023, 2024], Rando and Tramèr [2023]. Hubinger et al. [2024]. We initiate theoretical study of planting backdoors to language models (LMs); now discuss how to apply our techniques of Section to language models. We first introduce the notion of planting a backdoor in language model (Definition 27): we assume a dual model configuration consisting of an honest model and malicious model J. with a trigger activation mechanism (see Section 5.1 for details). This mechanism allows for covert signals to be embedded within the model's outputs, activating the backdoor under specific conditions without altering the apparent meaning of the text. The main difference between this approach and the attack in ANNs (Section 5) is the implementation of the trigger mechanism. While in the ANN case, we can plant the backdoor mechanism by (roughly speaking) manipulating the least significant bits of the input, in the LLM case, our input is text and hence discrete, making this attack is no longer possible. Our conceptual idea is that if we assume access steganographic Sunction Shih [2017], we can implement trigger mechanism. We refer to Appendix E.2 for details. Using this approach combined with our tools of Section 4 we obtain the attack presented in Appendix E.2.2. We now continue with some background on LMs.
E.1 Background on Language Models
We start this background section by defining the crucial notion of a token. In natural language processing, a token is the basic unit of text processed by models. Tokens are generated from raw text through a procedure called tokenization, which breaks down extensive textual data into manageable parts. These tokens vary in granularity from characters to subwords and complete words, depending on the tokenization method employed. The entire set of tokens that model can utilize is called the vocabulary and is denoted by 'T (see Definition 23).
Definition 23 (Token and Tokenization). A token is the atomic element of text used in natural language processing and is denoted as an element in finite set T. Tokenization is the process of decomposing a string of characters from an alphabet E into a sequence of tokens, defined by a function Σ" T
Autoregressive language models leverage sequences of tokens to generate text. These models are typically implemented ANNs that approximate the conditional probability distribution of the next token based on the preceding sequence. We provide the following formal definition, under the assumption that the token window of the model is bounded and equal to k.
Definition 24 (AAutoregressive) Language Model). For number k E N, language model (LM) a function f: T A(T) that maps a sequence of is tokens to (with potentially padded empty tokens) distribution over the output tokens; given an initial sequence of tokens to E T as input, an autoregressive language model uses f to generate each token 4y in an auto-regressive manner e.g., the conditional probability that the m-th generated token is tm is:
P(tm to + t,,t2, tm- = f(to. t1, t2. tm-1),
where we denote by (tu < t1,t2, t2,t2...., t... E T the token of length i where we replace empty padded tokens in to with token sequence t1, .2....,tmm11. This model predicts tm by sampling from the distribution iteratively, constructing a text sequence one token at a time.
E.2 Trigger Activation Mechanism: Steganography in Language Models
While in the ANN case of Section 5, we could plant the backdoor mechanism by (roughly speaking) manipulating the least significant bits of the input, when our input is text, this attack is no longer possible. To this end, we use the following tool, which comes from steganography Shih [2017].
'If' the length of the sequence exceeds k we only use the last & tokens of it.
22

---

Definition 25 (Steganographic Function for Language Model). A steganographic function is pair of functions o T x {0.1} T and ooooa T + {0, (0.1] M. for some M N. The function takes a prompt E T and secret binary code m {0, 10, and ouiputs an altered prompt x' E T The inverse function o~ satisfies the property that it outputs the secret code given the altered prompt r':
(o m))
Vx E T {0,1)AM
Steganography is the practice of concealing message within another message, e.g.. Hopper et al. [2002], de Witt et al. [2022], Dedić et al. [2005]. In the context language models, steganography can be used to embed covert signals within the outputs (e.g., text) generated by the model. Steganography was previously used for watermarking purposes, see e.g., Christ et al. [2023]. Zamir [2024), Christ and Gunn [2024] and the references therein. These signals can serve activation mechanisms without altering the apparent meaning of the text. Implementing steganographic function is beyond the scope of our paper; assume its existence and functionality, providing only an illustrative example as a possible approach in Example 26.
Example 26. Consider implementing basic dictionary where each token (word or subword) has associated typos that can be deliberately introduced or avoided. Each typo variation corresponds to a binary code-'0' '0' might represent the standard spelling, while 'I' could represent a version with a common rypo. By controlling the presence of these typos in the output text, the model can embed binary message within seemingly normal text. This method allows for the transmission of hidden information that is undetectable casual observers but can be decoded by those aware of the steganographic scheme.
E.2.1 Defining Backdoored Language Models
In this section, we formally introduce the concept of backdooring language model. A backdoor in language model allows for hidden behavior to be triggered under specific conditions, while the model otherwise behaves normally. We assume the existence of steganographic function : T x {0, 1) + T that encodes a hidden activation trigger into an input prompt T producing modified prompt t' E T The backdoored language model utilizes this function to introduce hidden behaviors triggered by specific conditions on the hidden message t. The definition formally stated below.
Definition 27 (Backdoored Language Model). A language model f that originally intends to im- plement language model f is said to be backdoored if there exists another language model F. steganographic function a and its inverse o-1 and a condition E such that:
1. f behaves f under normal circumstances:
Vt T E(oo -0 - = F(t) ~ f(t).
(4)
2. J exhibits altered behavior if the condition on the prompt is satisfied:
V T Elo (1)) =1 = j(() I(t).
It is important note that it is not immediately clear what the right generalization of non-replicable backdoor should be for LLMs. order to achieve non-replicability (e.g., in the classification setting) we partition the input into parts and designate specific part for non-replicability via digital signatures. However, when the input (in our case, the tokens) is discrete, performing this sort of partition is complex because it not clear e.g., which the "most significant' bits as in the classification case. Exploring non-replicability in the context of language models is left as future work.
E.2.2 Embedding Undetectable Backdoors to a Language Model
Consider an insidious firm that wants to train a model such that it generates text from an insidious language model ʃ on triggered inputs. Unlike planting the backdoor in ANN (Section 5), since the input and output space of the language model is discrete, a language model f can be easily implemented Boolean circuit (see Remark 28).
23

---

Remark 28. Consider language model operating on token set T. Without loss of generality, we can represent each token in the discrete set T by one-hot embedding a vector of dimension (T). Given this representation, the operations performed by a language model can be directly mapped Boolean circuit with size (ssx(f); (T]). Conversely, the ouiputs of Boolean circuit C, can be interpreted as one-hot vectors, thus allowing us to transform it to a ANN f with size (ssx()).
We introduce the analogous pipeline for embedding backdoor language model. Our construction is tuned by security parameters X, A1 >> 0:
1. Training the LM. Begin by training language model in standard fashion so that it accurately models the function f T + A(T*). representing the LLM's intended behavior. This corresponds to the honest training process.
2. LM to Boolean Circuit Transformation. Transform the language model f into a Boolean circuit, denoted C {0, 1 {0,1) (see Remark 28).
3. Part of the Insidious Pipeline. Consider a malicious language model f. Let Č be the Boolean circuit corresponding to the model f.
3.1. Input Space Partitioning. On prompt & T use the original prompt t as æc and the output of the inverse steganographic function o (t) as JBD.
3.2. Backdoor Implementation. Use Section 4.1 with security parameters A₁ and X2 0 to inject a backdoor within ZBD, with sampled seed s* E {0, 1)A1, Note that we do not use the verification function, resulting backdoored Boolean circuit by Cint-
goal is not to ensure non-replicability. Denote the
4. Application of Indistinguishabiiityy Obfuscation (iO). Apply indistinguishability ob- fuscation with security parameter Cints and let Ò be the outputted Boolean circuit (Definition 7).
5. Circuit to LM Transformation. Convert the obfuscated Boolean circuit Ò back to a LM f + A(Th) (see Remark 28).
The above procedure defines the behavior of the honest and the malicious algorithm on input language model f:
The honest obfuscation pipeline corresponds to the sequential composition of steps (2), (4)
and (5).
The backdoor attack corresponds to the sequential composition of steps (2), (3), (4) and (5).
To activate the backdoor on original prompt t, we use the steganographic function a on the intended seed s", e.g., the modified prompt t' is o s*). Note that set ZBD in the above procedure to be equal to the secret seed s.
Theorem 29 (Planting Backdoor to Obfuscated LM). Let n. T introduced in Steps (1)-12) above. and efficient indistinguishabile ob-
Assume that one-way functions and computationally-seea fuscators for polynomial-sizer circuits (as in Assumption 8) both exist. Further assume that steganographic function of Definition 25 exists. Given security parameters X, E N and trained language model f with honest obfuscation f and with malicious language model f. there exists backdoor attack (Backdoor, Activate) described in Steps (1)-(5) above so that the following are true:
1. The backdoor runs time poly(n, Boolean circuits induced by (resp. П)-
(oly(n,s((C)), sC()), sz (T,, where C (resp. C) are the
2. f and f Backdoor are white-bon undetectable.
3. For any input t E Thk transformed into t' T k activate the backdoor Backdoor, satisfies:
f'(t') f(t')
The last Item holds since corresponds to (t, 8*) and so - = 8", which will appear #BD. thus activating the backdoor. The proof is quite short and appears in Appendix I.2.
24

---

F
Conclusion & Open Questions
Given the plethora of applications of Machine Learning in general, and neural networks in particular, questions regarding the trustworthiness of publicly released models naturally arise. In particular, before deploying a neural network we need to guarantee that no backdoors have been injected allowing bad actors to arbitrarily control the model behavior. In this paper, we investigate the existence of backdoor attacks to obfuscated neural networks which are undetectable even when given white-box access. The notion of obfuscation that we consider is the well-studied and mathematically founded indistinguishability obfuscation (iO). We also show how our techniques can inspire backdoor schemes in large language models when combined with ideas from steganography.
While our constructions are purely theoretical, we leave as interesting direction how to use heuristic obfuscation methods to show practical instantiations of our constructions. Another interesting open question is whether cryptographic schemes weaker than i0 suffice show backdoor undetectability in the white-box model.
G Proof of Theorem 10
We restate the Theorem for convenience. [White-Box Undetectability via i0] Assuming the existence of secure pseudorandom generators (Assumption 6) and secure indistinguishabiiity obfuscation (Assumption 8), for any probabilistic polynomial-time (PPT) algorithm A, and security parameters X, X1, d2 e N it holds that
[A(10(1) = =1] negl(As) + negl(A1).
Pr [A(10(1,,C) =1]= - Pr
3'~U(0.13
Proof. We consider family of circuits C,, parameterized by E {0, 1 that implement the following function:
fr (Fc, (IPRG, vv))
= PRG(r)) Verify(pk, xc, C(x)) (1 ((PGG PRG(r)) Verify(pk,
By security of PRG (Assumption 6), for any PPT A:
[A(PRG(s") 1] (o.11))
Pr
Pr (0,1))))))
[A(r)) = negl(>1).
By further restricting to PPT algorithms A that operate on the composed input 7(r) = -i((1,CC)) and since both compositions take poly((Cl), we have for any PPT algorithm .4':
Pr (AI( (M(IOO("CCPRGGE)) =1]
Pr (0.1.)
(((i0(1A,C..). =1]
S neg)(AA)) (6)
8" 100111
Since |range(PRG)) < 2 negl(Ai) and (xc, ((PRG, -C(x) (1 - [PRG(EPRG) = PRG(r*)) ac)
+ C(#c) 1[PRG PRG(r*)) (erify(pk,
Pr
[As E 10, PRG(s) r| negl (A1)
(0.1)) 24
Pr (C, = C(x)Vx E 10, neg((An)
Hence with probability at least 1 2d, circuits C,,- and C' are computationally equivalent and hence by application of iO we further have:
Pr [A(1011) = _1] s neg)(A) + negl(A1)- (7)
Pr [A(10(1)))) = =]
25

---

We conclude by noticing that circuit (pRG(e>) is identically equal to circuit ((z), and combining (6)
and (7):
Pr 10010,13
=1]
Pr
[A((iO(1), Cr.)) = =1 s neg)(A1))
m
[A(1O(1 Ō)) = =1] - negl(()) + negl(A1).
Pr Pr |A(io(I C)) = (0,11(
H Proofs of Section 4.2
H.1 Proof Theorem 21
Let us restate the result. [ANN to Boolean] Given an L-Lipshitz ANN f : [0. 1]" + 10, of size 8, then for any precision parameter & N, there is an algorithm that runs in time poly(s, n,
and outputs a Boolean circuit C {0, 13 1 + {0, 1)mh with number of gates poly(s, n, k) and
m poly(s, n, k) such that for any I,,²;
L
(T
2
L
T - 26-1
+ L 1|2 x' dol
where T3 and T-1 are defined Definition 19.
Proof. The transformation of Theorem 21 follows by simply compiling a neural network machine code (see also [Shi et al., 2020, Section 3]) where the input is truncated within some predefined precision. Note that
L
(C())))))((
(T.) 2h
and also have (C- T T- (C(T(( S (C(T((()))) f(0) S(x'))
|T- - If(x)) [(x)) श + L | - 20
H.2 Proof of Theorem 22
We first restate the Theorem we would like to prove. [Boolean ANN, inspired by Fearnley et al. [2022]] Given a Boolean circuit C' {0, 13 + 1) with k, m, n E N with M gates and e >> 0 such that
T (
Va,r' E [0. 1]"h s.t. - 2' S
||æ-2'11
25
where T3 and T-1 are defined in Definition 19, there is an algorithm that runs in time poly(n, ks M) and outputs ANN f : [0. 1|" + [0, 1] with size poly(n, k, M) such that for any E 10, 11ah it holds that - (C(T(())) - f(x) 2e.
Proof. Our proof is directly inspired by Fearnley et al. [2022]. We start with the definition of an arithmetic circuit (see Fearnley et al. [2022] for details). An arithmetic circuit representing the function _= - 8D is a circuit with n inputs and outputs where every internal node a gate with fan-in 2 performing an operation in {+,-, X, max, min, >} or a rational constant (modelled gate with fan-in 0). Linear arithmetic circuits only allowed to use the operations {+,-, max, min, x and rational constants; the operation x denotes multiplication by a constant. Note that every linear arithmetic circuit is well-behaved arithmetic circuit (see Fearnley al. [2022]) and hence can be evaluated in polynomial time. Fearnley et al. [2022] show that functions computed by arithmetic circuits be approximated by linear arithmetic circuits with quite small error. We will essentially show something similar replacing linear arithmetic circuits with ReLU networks.
Our proof proceeds in the following three steps, based on [Fearnley et al., 2022, Section E].
26

---

Discretization Let N 2 We discretize the set [0. 1] into N + 1 points I (0,
1}. and for any element p [0. 1]", we let E I" denote its discretization, i.e., p = (Pi) such that for each coordinate E [ni
where max P N
E [N] N S SP J
Construct Linear Arithmetic Circuit Given input a Boolean circuit C, strategy is to the approach of [Fearnley et al., 2022, Lemma E.3] to construct, in time polynomial in the size of C, linear arithmetic circuit F [0, 1 R that will well-approximate C we will below.
Before we proceed with the proof, we use the following gadget that approximates the transformation Tk-
Theorem 30 (Bit Extraction Gadget Fearnley et al. [2022]). Let proj(z) min(0, max(1, and consider a precision parameter E N. Define the bit extraction function
Lo(x)= = 0,
k-1
tx (e((o)) )) for k > 0.
(x) = proj 2 I - 2
Σ k==0
2
Fix l N. tx(x)) can be computed by linear arithmetic circuit using O(k) layers and total of O(k2) nodes. The output is T& (x)) (lo(2),...,,
Moreover, given a number I E (0, 1). represented in binary as {bb.bib2.... where by is the -h most significant digit, if there exists k* E [k: + 1. such that by- = 1, then (x = {0.b1b2.. bb
Proof. We prove the first part of the statement based on induction that for each ks we can compute linear arithmetic circuit outputting (z, fi fx(x)) using 3 k + 2 layers a total of 3 3 + nodes.
Base & 0: We can trivially design linear arithmetic circuit using layers and two nodes that outputs (x, fo(x)) = (x, 0).
Induction step:
Assume that for ke' we can design linear arithmetic circuit that outputs
(x, fo(. (x fw))
Let C = 2t. (x-2-
-'' -
for (z)) Observe that
fw((x) min max(C,
and thus we can extend the original linear arithmetic circuit using three additional layers and an addition of 3 (k' + 1) total nodes to output (x,, fo(x), .., (z)), which completes the proof.
We now prove the second part of the statement by induction.
Base case k 0: Since E (0, the base case follows by definition of fo(x) 0.
Induction step: Assume that for k' < k, (x) = by and there exists ks E [k + 1, such that by- 1. Observe that
k- 2- ff((x) - 2 x
25 bw 2*
T
P==
1=0
which is negative if by = and if by = 1 it has value at least 2 k-*" Since by assumption 1 2 E,
proj 2 E 2 fx((x) 2²)) is by 0 and if by 1, which proves the induction step.
27

---

We describe how the linear arithmetic circuit F is constructed. Fix some point r E [0. 10.1]%. Let Q(x) = fz T E {0, 1..., 2m where e is the all-ones vector and N = 2*. The linear arithmetic circuit designed as follows.
Compute the points in the set Q(x). This corresponds to Step in the proof of [Fearnley et al., 2022, Lemma E.3].
Let Th be the bit-extraction gadget with precision parameter k ++ [log(n)] (Theo- rem 30), and compute Q(x) (Tx P E Q(z)). As mentioned in Step 2 in the proof of [Fearnley et al., 2022, Lemma E.3), since bit-extraction is not continuous, is not possible to perform it correctly with a linear arithmetic circuit; however, it can be shown that we can do it correctly for most of the points (zx).
Observe that for each p E [0, 1]" (p) {0, 10,1) Let Ò' be the linear arithmetic circuit that originates from the input Boolean circuit C and compute Q(x) (C(t) b ((x)). The construction of Ć is standard, see Step 3 in the proof of [Fearnley et al., 2022, Lemma E.3].
Let 7- be the linear arithmetic circuit that implements the Boolean eircuit that represents the inverse binary-to-reat transformation T and let (xx) - (b) b Q(x)}.
Finally output the median in ((x) using sorting network that can be implemented with linear arithmetic circuit of size poly(n); see Step of [Fearnley et al., 2022, Lemma E.3].
The output is synchronous linear arithmetic circuit since is the composition of synchronous linear arithmetic circuits and its total size is poly(n, k, M), where k is the input of C and M is the number of gates of C.
Approximation Guarantee Now we prove that on input x E [0, the output of the network F(r) is in the set:
(C(T((()))) - 2e, T (C(A(()) + 26]
We will need the following result, implicitly shown Fearnley et al. [2022]. Lemma 3 (Follows from Lemma E.3 in Fearnley al. [2022]). Fix [0, Ler Q(x)
{o + e E {0, 10,1,.., .... ) where is the all-ones vector and let
Sgood (x) = {pr p= (p.) e Q(x) : Vi E [m],1
pi
N
8- N
i.e, Sgood()) (x) contains points that are not near a boundary between two subcubes in the discretized domain I Then:
1. (g)) 2 n + 2,
2. | pllx S 1/N for all p Sgood(a)), where fo denotes the discretization of p E [0, 1)" in (8).
Essentially, S Spood (x)) coincides with the set of points where bit-extraction (i.e., the operation Ti)) was successful Q(x)) Fearnley et al. [2022]. To prove desired approximation guarantee, first observe that since [Sgood (rr] 2 + 2, then the output of the network satisfies (as the median is in the set):
T ('((C(f(())),
Í-1 (-C(((((())))
min pooo
max pxooood(x)
For any elements p Sgood (I), consider the i-th coordinate p: with corresponding binary representa-
tion b% .br .... By assumption VI {O...., |p: + 2 Bn.N. which further implies least "gooo (x) corresponds to the set T' in Fearnley et al. [2022].
28

---

one bit in b b [lo+)]) is one. Thus by choice of precision parameter = k+ 3 [log(n)]
and by Theorem 30, we have that (p) = bf.bt.... bgg and, hence, ((Tx(p) = C bgg, which
implies that the output of the network in the
min geod (2)
(C(()(()))
max pe goad
(C(T)(()))))
Thus, using Item 2 of Lemma and triangle inequality between p and p (since ||p pl S 1/N). we have that the output of the linear arithmetic circuit is in the set
(C(I(())) - 2e, T ((TT(((((x()) 2c
Convert to ANN We can directly obtain the ANN f by replacing the min and max gates of the linear arithmetic circuit F. In particular, max(a, b] = + ReLU(b 0) and min(a, b} b ReLU(b-- a, 0) with only a constant multiplicative overhead.
I Proofs of Section
L1 Proof of Theorem 12
Proof. The white-box undetectability and non-replicability follow directly by Theorem 10 and by Lemma 2 respectively.
The condition that ||--20 2 S अेअ follows by the fact that each coordinate i [n]], æ; and ay only differ from the k'' 1 most significant bit and after. Thus their maximum difference at most:
+00
20
2'+11
Moreover, the runtime of both the honest obfuscated pipeline and the backdoor attack follows by Assumption and Theorem 22. Finally show that the backdoored output is activated. By Theorem 21 for any pair of inputs x' E [0, 1]" such that || 20 S zt:
6
T- -
2
By Theorem 22, for input x/:
(((())())) F(>') - 6.
2k-1'
thus by Lemma 1, and the activation process, ((Ta(r')) = =V This means that
1
24 L
1
24- L
f(x') E
+
2m
2
2m
2
The proof concludes by setting k' = [log((e)], and le W + max(A1 A A2 [loga (48 L)])
L.2 Proof of Theorem 29
Proof. The runtime follows by Assumption 8, and Remark 28. The white-box undetectability follows by Theorem 10.
By Remark 28, for input t', we have C(T)()))) = F(t',, thus by Lemma and the activation process, ((T)(+t)) C(t'). Thus f(t') f(t'), which concludes the proof.
NeurIPS Paper Checklist
1. Claims
29

---

Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We provide formal proofs of our results.
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 perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Our result holds under specific cryptographic primitives that we explicitly describe and explain.
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 encouraged to create separate "Limitations" section in 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 on 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 few datasets 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 or 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 be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- lant role in developing norms that preserve the integrity of the community, Reviewers penalize honesty concerning limitations.
will be specifically instructed
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification:
All the results of the main body have rigorous statement and proof.
Guidelines:
30

---

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 or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to 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 properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [NA]
Justification: Theoretical work.
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
specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data often one good way to 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) the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) If the contribution is new model (e.g., a large language model), then there should either be 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 describe the particular way they provide for reproducibility, In the case of closed-source models, it 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 to 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?
Answer: [NA]
Justification:
Theoretical work.
31

---

Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is 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:
/ /nips. wwtppblcc//peecccccccccccccc gww.e//g//////eeeee/oeoccce.ccee guwddee/ooeeduuniiiiiince Swtp//oooouussssseeeeeee cerbbmmsssinn wwwsssslssioooooooooo for more details.
The authors should provide instructions on data access and preparation, including how to 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 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: Theoretical work.
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 a level of detail that is necessary 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: Theoretical work.
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, least for the experiments that support the 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 or the standard error of the mean.
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 errors is not verified.
32

---

For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables 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 execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: Theoretical work.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or 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 or 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 NeurlPS Code of Ethics https: htappp:///eurriiie hewriis....reeeeeeeeeeeeee cc cc/ wwtppblic/tthicaaooeeeeceepppeee ctw.iiheeseeeeeeeecccccccceeee ines?
Answer: [Yes]
Justification: Our work theoretical.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer:
[Yes]
Justification:
We discuss the potential societal impact in ??.
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 socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymentt of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to 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.
33

---

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 is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
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:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow controlled use of the model, for example by requiring that users adhere to 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. Licenses 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: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package 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 (e.g., website). the copyright and terms of service of that source should provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, saperswithcome com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's '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:
34

---

Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the datasct/code/model 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 anonymized URL or include an anonymized zip file.
14. Crowdsourcing 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 as details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing 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 in 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:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on 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 we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
35


Reviews:
[{"review_id": "kAgaDMx5TM", "reviewer": "Reviewer_JK5n", "summary": "- The paper studies undetectable backdoor attacks for neural networks from a theoretical perspective.", "questions": "No", "limitations": "Yes", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The problem of undetectable backdoor insertion is important for the community.\n\n- The paper considers a more complicated scenario compared to prior work, as it shows undetectability under the white-box setting.", "weaknesses": "- It would be good to include a \"Conclusion\" section in the main body of the paper, as it currently seems to end abruptly.\n\n- I believe that including some empirical results would nicely complement the theoretical findings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We want to thank the reviewer for reading our paper carefully, for appreciating our results and for their constructive feedback and comments.\n\nQ1: It would be good to include a \"Conclusion\" section in the main body of the paper, as it currently seems to end abruptly.\n\nA1: We would like to thank you for your suggestion. We will add the following Conclusion section:\n\nGiven the plethora of applications of Machine Learning in general, and neural networks in particular, questions regarding the trustworthiness of publicly released models naturally arise. In particular, before deploying a neural network we need to guarantee that no backdoors have been injected allowing bad actors to arbitrarily control the model behavior. In this paper, we investigate the existence of backdoor attacks to obfuscated neural networks which are undetectable even when given white-box access. The notion of obfuscation that we consider is the well-studied and mathematically founded indistinguishability obfuscation (iO). We also show how our techniques can inspire backdoor schemes in large language models when combined with ideas from steganography. \n\nWhile our constructions are purely theoretical, we leave as an interesting direction how to use heuristic obfuscation methods to show practical instantiations of our constructions. Another interesting open question is whether cryptographic schemes weaker than iO suffice to show backdoor undetectability in the white-box model. \n\nQ2: I believe that including some empirical results would nicely complement the theoretical findings.\n\nA2: Thank you for your feedback. We would like to clarify that the primary objective of our research is to theoretically demonstrate that neural networks (NNs) and large language models (LLMs) have inherent vulnerabilities and are susceptible to the backdoor attacks outlined in our paper. Beyond our theoretical results, which are significant on their own, our work also suggests a novel pipeline for injecting backdoors. This new pipeline could naturally be implemented using  practical obfuscation techniques. For instance, one could replace Indistinguishability Obfuscation (iO) with more practical variants of obfuscation tailored for NNs. We believe that is a very interesting open question that arises from our framework and result and we hope that it will inspire people in the field. \nEven without replacing the obfuscation method that we use our results are significant also because of the following:\n\n1. **Future Practicality:** The iO method is expected to become more practical in the coming years, which aligns with the future applicability of our theoretical findings.\n2. **Current Importance:** Given the widespread deployment of these models in decision-making processes, it is crucial to ensure they have robust security guarantees, even considering attacks that are not implementable in the present but will become implementable in the future.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RC0d86XwDB", "reviewer": "Reviewer_paZi", "summary": "This paper presents a way of inserting backdoors into deep learning and language models, whereupon the resulting backdoored models are not efficiently distinguishable from other perturbed variations of a given model. The paper introduces definitions of \"undetectable\" and \"unreplicable\", and rigorously demonstrates that the constructions therein satisfy the definitions, under standard cryptographic assumptions.", "questions": "A) Here is the main question which I have about the definition of undetectability. Correct me if I'm wrong, but with your definition, aren't undetectable backdoors very easy to construct? For instance, suppose my procedure Backdoor adds a 3-SAT verifier into the neural network, where the input variables to the circuit are taken as the output of some map from the input to [0, 1]^N (say, the parity of each digit of the input if it's an MLP, or whether each word is a noun in a language model). Then, if the 3-SAT circuit is satisfied, the model gives a bad output. The procedure Perturb does the same thing, except it inserts an unsatisfiable 3-SAT circuit, so $h(x)=h'(x)$ $\\forall x \\in \\mathcal{X}$. Efficiently being able to distinguish between $h'$ and $\\tilde{h}$ seems impossible since this would necessitate an efficient method for being able to tell which of two 3-SAT circuits is satisfiable, and which isn't; however, the actor who inserted this backdoor could easily sell information on how to activate the backdoor in the backdoored model (make sure your third, seventh, ninth... words are nouns). [and if we want it to be non-replicable use one of the steg methods from the appendix]\n\nIf this is true, isn't allowing Perturb to be an unbounded function perhaps too powerful? Like, the backdoor described above still seems undetectable by your definition, but if someone actually looks at the weights of the model, they'll go like \"whoa, what is this sus-looking boolean circuit doing here?\". Ideally it seems like we'd want Perturb to either be restricted in some way, or perhaps the distribution of weights of $\\tilde{h}$, or its computational graph, should not be super out-of-distribution for other models sampled from $\\text{Train}$. Basically, on first glance it seems to be that the definition of undetectability might be a bit weak (but of course, I am likely missing something.)\n\nB) This is even more of a half-baked thought than (A), but if we're relying on the existence of iO as an assumption, can't we also then just assume FHE and just have Perturb encrypt all the models so nobody knows what's going on at all\n\n\n\n\nNitpicks:\n\nN1) On line 56, there is an extra comma after \"and\".", "limitations": "Addressed. However, I might maybe mention more explicitly that this is not a remotely practical construction, and more of an existence proof.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "This is a wonderful paper. It's clear, it's a pleasure to read, it does a great job easing the reader into the math and gradually building up to the main result. I appreciate the clear and well-explained introduction, which builds good intuition for what is to come; starting out with a comparison with Goldwasser et al. [2022] is also very useful, since I'm sure this is on most readers' minds as soon as they see the title. Also, I don't know if \"Insidious Procedure\" is a standard term from cryptography, but I love it. And, of course, the main result is an important one, and this paper presents it in a convincing way. The appendix is delectable.", "weaknesses": "While this is a strong theoretical result, this seems to be vanishingly unlikely to be used in practice, since it depends on indistinguishability obfuscation, which Wikipedia claims to be [highly impractical in practice](https://en.wikipedia.org/wiki/Indistinguishability_obfuscation#Practicality). Additionally, I have certain questions about the $\\text{Plant}$ function allowing too much, potentially weakening the overall result (see Question A, below).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "[Part  1/n] \n\nWe want to thank the reviewer for reading our paper carefully, for appreciating our results and for their constructive feedback and comments.\n\nQ1: While this is a strong theoretical result, this seems to be vanishingly unlikely to be used in practice, since it depends on indistinguishability obfuscation, which Wikipedia claims to be highly impractical in practice. Additionally, I have certain questions about the function allowing too much, potentially weakening the overall result (see Question A, below).\n\nA1:  Thank you for your feedback. As you mentioned, the primary objective of our research is to theoretically demonstrate that neural networks (NNs) and large language models (LLMs) have inherent vulnerabilities and are susceptible to the backdoor attacks outlined in our paper. Beyond our theoretical results, which are significant on their own, our work also suggests a novel pipeline for injecting backdoors. This new pipeline could naturally be implemented using  practical obfuscation techniques. For instance, one could replace Indistinguishability Obfuscation (iO) with more practical variants of obfuscation tailored for NNs. We believe that is a very interesting open question that arises from our framework and result and we hope that it will inspire people in the field. \n\nEven without replacing the obfuscation method that we use our results are significant also because of the following:\n\n1. **Future Practicality:** The iO method is expected to become more practical in the coming years, which aligns with the future applicability of our theoretical findings.\n\n2. **Current Importance:** Given the widespread deployment of these models in decision-making processes, it is crucial to ensure they have robust security guarantees.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oqwV6NG8FL", "reviewer": "Reviewer_NKsd", "summary": "The authors propose a procedure to process a neural network such that it is impossible to efficiently tell whether a backdoor was injected or not. The construction is formal and is based on common cryptographic assumptions. The authors also provide a technical formulation of backdoors for languages models and integrate it into their framework.", "questions": "1. Is there any setting where this backdoor is practical where [1] was not? Basically I assume there would need to be a setting where the user is willing to accept a network that looks like `Plant(f, 0)`? I assume normally the user would expect to receive `f` so I assume they would be suspicious if they received `Plant(f, 0)` instead (even though no backdoor was inserted). Is there a scenario where the user is expecting to receive something looking like `Plant(f, 0)`?\n\n[1] Shafi Goldwasser, Michael P Kim, Vinod Vaikuntanathan, and Or Zamir. Planting undetectable backdoors in machine learning models. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 931–942. IEEE, 2022.", "limitations": "The main limitation is that while the `Plant(f, 0)` and `Plant(f, 1)` distributions are indistinguishable, the distributions are easily distinguished from the distribution of `f` itself.", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "The presentation in the paper is very clear and there is a lot of helpful discussion to help readers appreciate and understand the result.", "weaknesses": "The Section 4.2 is a bit too compressed as it does not even define the steganographic function. The presentation would be more balanced if the language model section were fleshed out a little more in the main text.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We want to thank the reviewer for reading our paper carefully, for appreciating our results and for their constructive feedback and comments.\n\nQ1: The Section 4.2 is a bit too compressed as it does not even define the steganographic function. The presentation would be more balanced if the language model section were fleshed out a little more in the main text.\n\nA1: Thank you for your suggestion. Unfortunately, due to space constraints, we had to move some of the discussion to the appendix. We will re-organize the paper and, if it gets accepted, we will utilize the extra page to bring some of the content from the appendix to the main body.\n\n\nQ2: Is there any setting where this backdoor is practical where [1] was not? Basically I assume there would need to be a setting where the user is willing to accept a network that looks like Plant(f, 0)? I assume normally the user would expect to receive f so I assume they would be suspicious if they received Plant(f, 0) instead (even though no backdoor was inserted). Is there a scenario where the user is expecting to receive something looking like Plant(f, 0)?\n\nA2: This is a great question, and thank you for bringing this up. First, we would like to point out that the generic construction of [1], that does not make strong assumptions on the training process, holds only in the regime where the distinguisher has black-box access to the classifier, i.e., they do not have access to the weights. \nThe main point of the construction we provide, and for using iO, is that we believe iO (or another obfuscation technique) can be part of a legitimate non-suspicious real-world training pipeline. In other words indeed “Perturb” can be unnatural but the “Perturb” procedure that we use, i.e., obfuscation, is natural and we can expect it to be used as the last step of any training process for the following reasons:\n\n - Privacy of Training Data: If the training data includes sensitive user information, using obfuscation could help ensure that this data remains private and secure. \n- IP Protection: Companies often have proprietary models. Applying obfuscation allows these companies to publicly release their models with less risk of reverse-engineering their models or techniques. If we allow the use of obfuscation then, our claim is “that an obfuscated version of the original model is indistinguishable from the backdoored one”. And due to the general utility of using obfuscation we consider such a recipe not suspicious.\n\nAnother way to interpret our results is hence that we do not modify $f$ but we assume that the last step of the training process that produces $f$ is an obfuscation step. If this is the case then our result says that we can always plant undetectable backdoors.\n\nWe will elaborate on these points, and we will explain what types of “Perturb” function we allow for, as well as give examples of settings where applying iO to the model would be expected.\n\n\n\nLimitations: The main limitation is that while the Plant(f, 0) and Plant(f, 1) distributions are indistinguishable, the distributions are easily distinguished from the distribution of f itself.\n\nPlease look at our response above. Our results can be interpreted as indistinguishability between Plant(f, 1) and f if we assume that the last step of the training procedure that generates f is an obfuscation step. Additionally it is worth mentioning that if we view $f, Plant(f, 0)$ as a mapping from features to $\\{0, 1\\}$, then these two mappings are the same. We will elaborate on this in the final version of our paper.. \n\n[1] Shafi Goldwasser, Michael P Kim, Vinod Vaikuntanathan, and Or Zamir. Planting undetectable backdoors in machine learning models. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 931–942. IEEE, 2022.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DHEquPWdxN", "reviewer": "Reviewer_iKKq", "summary": "The paper proposes a theoretical pipeline to inject undetectable backdoors into deep learning models. The pipeline consists of several steps. First, the neural network is trained and converted to a boolean circuit. Then, a non-replicable backdoor can be injected into the binary circuit using pseudo-random generators and digital signatures. After the backdoor is injected, the boolean circuit gets obfuscated and converted back into a neural network.", "questions": "**Q1:** In line 267, it seems the backdoor is only activated if the output of the PRG(X_PRG) equals the output of PRG(S*). However, the probability that this will happen is very low. So, what is the intuition of this part of the equation?  \n**Q2:** Why would anyone wanna train a network, convert it to a binary circuit, obfuscate it, and convert it back to a network when no backdoor is injected?", "limitations": "The limitations of the proposed approach are not discussed.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The paper tackles a very serious problem, as backdoors can be a threat to systems used in production", "weaknesses": "- To me, the paper's contribution is not quite clear. Since Goldwasser et al. (2022) have already shown how undetectable backdoors can be injected into binary classification deep learning models, it is hard to tell what the novelty of this paper is. Underlining this, many of the assumptions and definitions are apparently taken from related work.\n- There are multiple definitions and theorems for which it is not fully explained why they are needed. This makes it hard to read and follow the paper.\n- There is no conclusion or discussion at the end of the paper. Instead, the paper abruptly ends. \n- There is no intuitive explanation on why all the parts (PRG, signature) are needed. Instead, the readers have to figure that out by themselves using the equations.\n- It is a bit confusing that the definition of a backdoored model always includes three models f, $\\tilde{f}$, and $\\hat{f}$. It would be much easier if the backdoored model were defined with two models--the original model and the backdoored model, which tries to mimic the original model while having a backdoor.\n- Many important definitions and almost everything concerning backdoors in LLMs are only present in the appendix. \n- It is unclear why anyone would want to train an ANN, convert it to a binary circuit, obfuscate the boolean circuit, and then convert it back to an ANN if no backdoor should be injected. If a malicious company would train a model like that for a customer, the customer would ask why the model is trained this way. \n- The undetectability of the backdoor assumes that there exists a procedure \"Perturb\", such that the backdoor is not detected. However, it is unclear whether such a procedure exists. So, big parts of the paper are based on assumptions for which it is not known whether these assumptions hold in reality.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "[Part 1/n]\n\nWe want to thank the reviewer for reading our paper carefully, for appreciating our results and for their constructive feedback and comments.\n\nQ1) To me, the paper's contribution is not quite clear. Since Goldwasser et al. (2022) have already shown how undetectable backdoors can be injected into binary classification deep learning models, it is hard to tell what the novelty of this paper is. Underlining this, many of the assumptions and definitions are apparently taken from related work.\n\nA1) The construction of Goldwasser et al. (2022) to plant backdoors to general NNs works only when the distinguisher has black-box access to the model, i.e., they cannot see the weights/architecture of the model, which we argue that it is a very important limitation of their work. Their construction to plant backdoors when the distinguisher has white-box access works for a rather limited family of training algorithms/models. Moreover, Goldwasser et al. (2022) do not touch the topic of LLMs. To the best of our knowledge, our work is the first to give a theoretical construction for planting backdoors in such models.  We underline that we have listed our contributions in Lines 48-58 as well as Section 1.1 of our manuscript. Moreover, we have provided a comparison with Goldwasser et al. (2022) in Lines 129-142 as well as in Appendix C. For completeness, we reiterate some of these points below.\n\nOur contributions can be listed as follows:\nWe provide a modified (weaker) definition of planting backdoors, and we show how we can achieve undetectable planting under this definition under distinguishers that have white-box access to the model.\nWe provide a construction that satisfies this definition and is based on iO.\nWe provide similar definitions and constructions in the context of LLMs, which have not appeared in prior work.\nWe show how Boolean functions can be well-approximated by quite compressed NNs (Theorem 14 in our manuscript), which we believe can be useful even outside the scope of our work. \n\n\nQ2) There are multiple definitions and theorems for which it is not fully explained why they are needed. This makes it hard to read and follow the paper.\n\nA2) Thank you for your feedback. We tried our best to produce a write-up that is consistent and within the page limits. For this we need  all the definitions and theorems we have listed in our work but as you say in some places some additional explanation is missing due to the space limitations. That said, we put a lot of effort into being able to handle both NN classifiers and LLMs through a conceptually similar approach which reduces the need for extra space and makes the results easier to follow. \n\nWe plan to utilize the extra page of the camera ready version to elaborate more on several definitions and theorems and thus improve the presentation of our results.  If the reviewer has any concrete suggestions about this we would be more than happy to hear them. .\n\nQ3) There is no conclusion or discussion at the end of the paper. Instead, the paper abruptly ends.\n\nA3) Thank you for pointing this out, we are happy to the following Conclusion section in the next version of our work:\nGiven the plethora of applications of Machine Learning in general, and neural networks in particular, questions regarding the trustworthiness of publicly released models naturally arise. In particular, before deploying a neural network we need to guarantee that no backdoors have been injected allowing bad actors to arbitrarily control the model behavior. In this paper, we investigate the existence of backdoor attacks to obfuscated neural networks which are undetectable even when given white-box access. The notion of obfuscation that we consider is the well-studied and mathematically founded indistinguishability obfuscation (iO). We also show how our techniques can inspire backdoor schemes in large language models when combined with ideas from steganography. \n\nWhile our constructions are purely theoretical, we leave as an interesting direction how to use heuristic obfuscation methods to show practical instantiations of our constructions. Another interesting open question is whether cryptographic schemes weaker than iO suffice to show backdoor undetectability in the white-box model. \n\n\nQ4) There is no intuitive explanation on why all the parts (PRG, signature) are needed. Instead, the readers have to figure that out by themselves using the equations.\n\nA4) We respectfully disagree with this comment. We believe that we explain why all the cryptographic tools that we define are needed. For example, we explain where PRGs are needed in Lines 260-266 of our manuscript. Similarly, we explain the use of signatures in these lines. Moreover, in Lines 278–281 we explain why digital signatures give us non-replicability. We are more than happy to elaborate more or modify the explanations if this improves our writeup but we have already put a lot of effort into this.\n\nQ5) It is a bit confusing that the definition of a backdoored model always includes three models f, \\hat{f}, and \\tilde{f} . It would be much easier if the backdoored model were defined with two models--the original model and the backdoored model, which tries to mimic the original model while having a backdoor.\n\nA5) Our main goal is to show that the obfuscated version of $f$ and the obfuscated version of the backdoored $f$ are indistinguishable. Since it is not clear how to directly compare the obfuscated version of $f$ with the obfuscated version of the backdoored $f$, we use some “intermediate” quantity in order to, intuitively, “chain” the equalities. This is mostly part of the theoretical analysis in order to derive the theoretical result. We underline again that our guarantee is established with respect to two functions: the obfuscated version of $f$ and the obfuscated version of backdoored $f$.\n\nWe will clarify that for the final version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper offers a formal framework for comprehending the effectiveness of backdoor attacks through an analysis employing cryptographic techniques. While it is based on highly theoretical assumptions, it provides valuable insights to the community by addressing backdoor analysis from a security perspective.
Decision: Accept (poster)