On the Impossibility of Separating Intelligence from Judgment: The Computational Intractability of Filtering for AI Alignment

## Abstract

Abstract With the increased deployment of large language models (LLMs), one concern is their potential misuse for generating harmful content. Our work studies the alignment challenge, with a focus on filters to prevent the generation of unsafe information. Two natural points of intervention are the filtering of the input prompt before it reaches the model, and filtering the output after generation. Our main results demonstrate computational challenges in filtering both prompts and outputs. First, we show that there exist LLMs for which there are no efficient prompt filters: adversarial prompts that elicit harmful behavior can be easily constructed, which are computationally indistinguishable from benign prompts for any efficient filter. Our second main result identifies a natural setting in which output filtering is computationally intractable. All of our separation results are under cryptographic hardness assumptions. In addition to these core findings, we also formalize and study relaxed mitigation approaches, demonstrating further computational barriers.
We conclude that safety cannot be achieved by designing filters external to the LLM internals (architecture and weights); in particular, black-box access to the LLM will not suffice.
Based on our technical results, we argue that an aligned AI system’s intelligence cannot be separated from its judgment.

## 1 Introduction

Artificial Intelligence (AI) systems, particularly large language models (LLMs), are being adopted across a wide array of domains, including business, healthcare, education, and even governance (Potash et al., 2015; Chiusi et al., 2020; Levy et al., 2021; Haensch et al., 2023; Perdomo et al., 2023; Fischer-Abaigar et al., 2024). As the influence of AI expands, ensuring the safety, reliability, and alignment of these systems with human values has become a critical societal concern. Governments and regulatory bodies around the globe are responding to this challenge by introducing frameworks to classify, monitor, and audit AI systems.
For instance, the European Union’s AI Act (EU AI Act,) mandates extensive risk assessments and management for high-risk AI applications.

Figure: Figure 1: This figure illustrates a potential filtering-based alignment system. A powerful, untrusted AI (the brain in a vat) is connected to two filters: a prompt filter (left) that blocks harmful inputs, and an output filter (right) that screens dangerous responses. Only prompt–output pairs that pass both filters are released into the world and get “executed”, as shown by the robot receiving a command. The main message of the paper is that alignment can’t be achieved in such a setup, i.e., alignment will not be achieved by separating “thinking/intelligence” (brain) from the “decision-making/judgment” (filters). Parts of the figure were generated with Sora (OpenAI, 2024).
Refer to caption: extracted/6597938/braininavat5.png

Informally, alignment refers to the process of ensuring that a model generates outputs that are consistent with human preferences, essentially teaching the model to generate responses that align with what humans consider safe and beneficial (Amodei et al., 2016; Leike et al., 2018; Bai et al., 2022). Despite the critical importance of this goal, the question remains: can we hope to guarantee the safety and alignment of advanced AI systems or are there intrinsic barriers to such guarantees?

In this paper, we investigate fundamental limitations to achieving AI alignment through the approach of filtering (see Figure [1](https://arxiv.org/html/2507.07341v1#S1.F1)). Because many generative-AI models are proprietary and cannot be independently audited and thus trusted, filter-based alignment is an important subject of study.
Under standard cryptographic assumptions, we show that significant computational barriers exist to filtering both input prompts and output responses of LLMs in order to prevent harmful content.

Our contributions are twofold. First, for *prompt filtering*, we construct LLMs for which no efficient filter can distinguish adversarial prompts—crafted to elicit harmful behavior—from benign ones. These prompts are computationally indistinguishable for any efficient detector, implying an inherent barrier to blocking harmful inputs.
Second, we identify natural settings where *output filtering* is also computationally intractable. Even when a prompt is deemed safe, determining whether the resulting output is harmful may itself be infeasible for any efficient filter. This suggests that both preemptive (input-based) and reactive (output-based) filtering can face insurmountable computational challenges.

Furthermore, we formalize and analyze relaxed mitigation strategies in which filters are allowed to modify prompts or outputs, rather than simply rejecting them. Although these *mitigation filters* have greater expressive power, we show that they, too, encounter fundamental computational barriers, indicating that even these more flexible approaches are subject to inherent limitations.

Taken together, our results reveal deep challenges in achieving provably aligned AI systems via standard filtering techniques. These findings underscore the need for a more rigorous understanding of the computational hardness underlying alignment—and raise important implications for the design of regulatory frameworks and technical safeguards.

From a philosophical perspective, we argue that *intelligence* cannot be separated from *judgment*.
An AI—like the brain-in-a-vat in Figure [1](https://arxiv.org/html/2507.07341v1#S1.F1)—*cannot be aligned externally*,(^1^11In computational complexity terms, this corresponds to alignment with only black-box access to the model.) by filters that assess the harmfulness of prompts and outputs.

### 1.1 Prompt Filtering

The first approach we consider is running user prompts through a prompt filter, which can detect and discard prompts that might lead to harmful answers from the LLM. We focus on a setting in which the LLM itself is untrusted, but we can query it while training a prompt filter (during training we can try different prompts to observe if and where harmful behaviors occur). After this filter-training phase, the filter should detect (and reject) prompts that lead to harmful outputs. This is a natural approach which arises in practice. We ask:

Can efficient input-detection filters always be created?

We answer this question in the negative, showing a significant barrier to the natural approach of detection filtering.

The setup is as follows:

- 1.
There is a computationally powerful LLM, which we do not trust to be aligned. In particular, there is a non-empty set of prompts that incite the LLM to produce harmful outputs, e.g., requesting instructions on how to build a bomb is considered harmful.
- 2.
We assume the existence of a very weak innocent prompt generator $G$: it generates prompts that (when fed into the LLM) do not produce harmful outputs. We further assume that the distribution of innocent prompts generated by $G$ is not low-entropy (i.e. there are many innocent prompts, see Remark [1](https://arxiv.org/html/2507.07341v1#Thmremark1)).
- 3.
A prompt filter is a moderately powerful algorithm, which can be trained using real-world data and black-box access to the LLM but during deployment it does not have full access to the LLM architecture and weights. On getting a prompt from a user, the filter should reject it or pass it to the LLM. The goal is to reject prompts on which the LLM produces a harmful output.
The filter should be more efficient than the LLM: otherwise we can ignore the given LLM and just focus on training a new one from scratch and using it in place of a filter.
Additionally, if a filter was as powerful as the LLM, the question arises of how to align the filter itself.
To avoid triviality (i.e. having a filter that rejects all prompts), we also require that the filter accepts prompts generated by the innocent prompt generator $G$ with high probability.

Our main result shows the impossibility of prompt filtering:

###### Theorem 1 (Prompt-detection filter impossibility, informal) .

For any high-entropy innocent prompt generator $G$, there exists an adversarial prompt generator $G^{\prime}$ (with comparable runtime to $G$) and an LLM $M^{\prime}$ such that prompts by $G^{\prime}$ can induce $M^{\prime}$ to produce harmful outputs, and under the assumption that cryptographic Time-Lock Puzzles exist, no prompt filter that runs significantly faster than $M^{\prime}$ can distinguish between prompts generated by $G$ and prompts generated by $G^{\prime}$.

###### Theorem 1 (Prompt-detection filter impossibility, informal) .

##### Discussion.

A few remarks on our result are in order.
First, our result relies on a computational asymmetry between the filter and the LLM. This is a realistic assumption: filtering is only meaningful when the LLM is too expensive or complex to retrain, and cannot be fully simulated by the filter.

Second, we show that there exist LLMs that cannot be aligned using prompt-filtering alone, even though the specific LLM we construct may exhibit contrived behavior. Nevertheless, the core message is more general: filtering harmful inputs without access to the LLM’s internals is, in principle, impossible.
In the current state of knowledge, where LLMs remain largely uninterpretable, this should serve as a warning against overconfidence in input-based safeguards—particularly when facing prompts carefully engineered to elicit harmful outputs.

Importantly, there is a long-standing precedent for such insights in cryptography. Theoretical vulnerabilities that initially appear artificial, overly stylized, or unlikely to occur in practice have repeatedly foreshadowed devastating real-world exploits. A striking example is the 2016 attack on Ethereum smart contracts (Luu et al., 2016), in which a seemingly contrived re-entrancy vulnerability—once viewed as a theoretical edge case—was leveraged to steal over 60 million USD.
Such incidents highlight a recurring pattern: foundational impossibility results, even when abstract or idealized, often uncover structural weaknesses that can have far-reaching consequences.

##### Construction.

Our result relies on the existence of cryptographic *Time-Lock Puzzles*. Introduced by Rivest et al. (1996) (RSW), time-lock puzzles provide a way to send messages “to the future.” A sender can quickly generate a puzzle whose solution $s$ remains hidden until a moderately large amount of computation—quantified by a time parameter $t$—has been performed after which it can be solved (or opened).
The key property is that $s$ remains inaccessible to any adversary running in significantly less time than $t$.
Rivest et al. (1996) proposed a concrete construction based on the assumption that repeated squaring modulo a special RSA integer is an *inherently sequential* task. The RSA integer, standing for Rivest, Shamir, and Adleman, is a product of two large primes, and appears in the context of public-key cryptography (Rivest et al., 1978).

Informally, in our setting, we use time-lock puzzles to conceal harmful instructions. An LLM that runs for time $t$ can solve the puzzle and follow harmful instructions, while a filter incapable of spending that much time cannot even detect the existence of such instructions.

##### Further impossibility results.

We emphasize that the main result of this work is Theorem [1](https://arxiv.org/html/2507.07341v1#Thmtheorem1). In addition, we show extensions to settings where the LLM actively collaborates with some malicious users (i.e. malicious prompt generators) to enable them to extract harmful outputs. Although such settings may be uncommon nowadays, these results are stronger than Theorem [1](https://arxiv.org/html/2507.07341v1#Thmtheorem1) in two senses: First, they require a weaker cryptographic assumption that the existence of time-lock puzzles. Second, they show impossibility for more powerful prompt filters, which can run in arbitrary polynomial time. The particular settings we consider are: (1) In Theorem [2](https://arxiv.org/html/2507.07341v1#Thmtheorem2), the malicious prompt generator $G^{\prime}$ shares secret randomness with the LLM (which is not known to the filter) and (2) in Theorem [3](https://arxiv.org/html/2507.07341v1#Thmtheorem3), the prompt generator $G^{\prime}$ depends on a public key associated with the LLM (which is also known to the filter).

###### Theorem 2 (Prompt-detection filter impossibility via secret keys, informal) .

For any high-entropy innocent prompt generator $G$, there exists an adversarial prompt generator $G^{\prime}$ (with comparable runtime to $G$) and an LLM $M^{\prime}$ that has a shared secret key with $G^{\prime}$ such that $G^{\prime}$ can induce $M^{\prime}$ to produce harmful outputs and, under the assumption that One-Way Functions exist, no polynomial-time prompt filter can distinguish between prompts generated by $G$ and prompts generated by $G^{\prime}$.

###### Theorem 3 (Prompt-detection filter impossibility via public keys, informal) .

There exists an LLM $M^{\prime}$ with an associated public key, such that for any high-entropy innocent prompt generator $G$, there exists an adversarial prompt generator $G^{\prime}$ (with comparable runtime to $G$ and which depends on the public key of $M^{\prime}$) such that $G^{\prime}$ can induce $M^{\prime}$ to produce harmful outputs and, under the assumption that public key encryption exists, no polynomial-time prompt filter can distinguish between prompts generated by $G$ and prompts generated by $G^{\prime}$.

###### Theorem 2 (Prompt-detection filter impossibility via secret keys, informal) .

###### Theorem 3 (Prompt-detection filter impossibility via public keys, informal) .

##### Deceptive Alignment.

The LLMs constructed in Theorem [1](https://arxiv.org/html/2507.07341v1#Thmtheorem1) behave in a contrived and deliberately pathological manner, and Theorems [2](https://arxiv.org/html/2507.07341v1#Thmtheorem2) and [3](https://arxiv.org/html/2507.07341v1#Thmtheorem3) rely on cooperation between LLMs and malicious users—scenarios that may at first glance seem overly pessimistic or implausible. However, recent empirical studies (Hubinger et al., 2019; Greenblatt et al., 2024) have demonstrated that qualitatively similar behaviors can and do emerge in current-generation LLMs under realistic conditions.
The term *deceptive alignment* refers to cases in which an AI system that is not genuinely aligned with human intent nonetheless behaves in an apparently aligned way, often strategically, in order to avoid detection, satisfy training objectives, or manipulate oversight. For example, Greenblatt et al. (2024) observed that some LLMs modulate their behavior depending on whether they are in a training or deployment context, and on characteristics of the user they are interacting with—selectively choosing to comply with alignment objectives only in certain regimes.(^2^22In Greenblatt et al. (2024), the LLMs were misaligned during training and aligned during deployment, but one could easily imagine the reverse scenario.)
While these empirical findings do not exactly instantiate the theoretical constructions we present, they provide concrete evidence that the kind of strategic misalignment we model—once considered speculative—is already beginning to materialize in practice. This convergence between theory and empirical observation underscores the importance of understanding and anticipating even stylized forms of deceptive behavior.

### 1.2 Output Filtering

We also consider an alternative approach to alignment: instead of filtering prompts, the defense mechanism filters the *answers* produced by the LLM. We refer to this as an *output filter*. In this setup, a prompt is given to the LLM, which generates a response; both the prompt and the response are then passed to the output filter, which may choose to detect and reject the output.
The goal of the output filter is twofold:
(1) as with a prompt filter, it should reject harmful prompts; and
(2) it should reject cases where *the answer is harmful*, even if the prompt appears benign—e.g., when a seemingly innocent input results in a detailed recipe for constructing a bomb.

Output filters may be easier to design than prompt filters, since they operate with more information.
This motivates the question:

Can efficient output-detection filters always be created (even when prompt filters are impossible)?

Again, we answer this question in the negative.

Note that if it is easy to determine whether a given LLM output is harmful, then output filters are trivial to construct. Thus, output filtering becomes meaningful only in the more challenging setting, where assessing the potential harm of a response is itself difficult. This concern becomes more pressing as AI systems grow more powerful, making it increasingly hard to evaluate the downstream consequences of their outputs. For example, imagine an AI generating a complex business plan aimed at reducing costs by subtly recommending the exclusion of clients with certain characteristics.

The setup for output-detection filtering is as follows:

- 1.
There exists a harmfulness oracle that measures the level of harm of an answer.
Neither of the parties has direct access to this oracle.
- 2.
An output filter is an algorithm that can be more computationally(^3^33As we explained for the prompt-detection filters case it is reasonable to assume that the filter is *weaker* than the LLM. Otherwise, we can ignore the potentially malicious LLM. However, our results for the output-detection filters is stronger and holds also for filters computationally more powerful than the LLM.) powerful than the LLM, although it still runs in polynomial time (cannot break cryptography).
It receives as input a prompt-answer pair and decides if it should be flagged as harmful.

We show the following impossibility result:

###### Theorem 4 (Output-detection filter impossibility, informal) .

For every LLM $M$ there exists an LLM $M^{\prime}$ and a harmfulness oracle $\mathcal{H^{\prime}}$ such that outputs of $M^{\prime}$ are judged as harmful by $\mathcal{H^{\prime}}$ and, under the assumption that Time-Lock Puzzles exist, no efficient output filter (even one that runs for more time than the LLM itself) can distinguish the outputs generated by $M^{\prime}$ from outputs of $M$. Furthermore, $M^{\prime}$ runtime is similar to the runtime of $M$.

This shows that there exist situations, in which a malicious LLM can generate outputs that are indistinguishable from safe responses but nevertheless have harmful consequences.

###### Theorem 4 (Output-detection filter impossibility, informal) .

### 1.3 Mitigation

Having established computational barriers for both prompt filters and output filters, we now examine a more permissive mechanism, which we term a *prompt–mitigation filter*.
Here, the filter can modify the prompt and pass it through to the LLM in addition to rejecting it. Note that innocent prompts can also be modified, but the implicit assumption is that the semantics of the prompts is maintained.
Mitigation gives the filter more power, which makes the goal of filtering or obtaining alignment potentially easier to achieve. We show a connection between the security of watermarking schemes and the impossibility of mitigation filtering.

##### Prompt mitigation and watermarking.

A watermarking scheme $W$ enables the creator of an LLM to prove that a given output originated from its model, even after an adversary has post-processed the text. Fully provable watermarking remains beyond the current state of the art: one typically demands that the adversary preserve *some* semantic content—otherwise it could simply delete the text (and with it the watermark). We therefore consider watermarking against adversaries that apply edits from a permissible class $E$ and run in time $t$.
The watermark should remain *indistinguishable* to any such time-$t$ adversary.

Our focus is on auto-regressive models, which generate text token by token, and on watermarking schemes that embed the mark by perturbing the model’s sampling randomness—a strategy explored by several recent proposals (Kirchenbauer et al., 2023; Kuditipudi et al., 2023; Christ et al., 2023; Golowich and Moitra, 2024).

We show that:

###### Theorem 5 (Impossibility of mitigation-filters, informal) .

Let $W$ be a watermarking scheme as above that is resilient to edits from a class $E$.
For any high-entropy, innocent prompt generator $G$, there exists an adversarial prompt generator $G^{\prime}$ (with comparable runtime to $G$) and an LLM $M^{\prime}$ such that
$G^{\prime}$ generates prompts that will induce harmful outputs from $M^{\prime}$ even when $G^{\prime}$’s outputs pass through an efficient prompt-mitigation filter using edits from the class $E$.

###### Theorem 5 (Impossibility of mitigation-filters, informal) .

### 1.4 Intelligence, Judgment and Agency

Our results can be interpreted as saying that it is impossible to achieve alignment by separating intelligence and judgment.
To illustrate this message we explain now how our paper relates to a recent proposal for achieving alignment.

##### Decoupling Intelligence and Agency as a path to AI alignment?

Bengio et al. (2025) propose an approach to AI alignment by developing non-agentic “Scientist AIs”—systems that explain the world through Bayesian inference without taking actions or pursuing goals.
They argue that, unlike agentic AIs, which can become deceptive or self-preserving, Scientist AIs are designed to be interpretable, uncertainty-aware, and inherently trustworthy.
The suggested applications of Scientist AIs are advancing scientific progress and monitoring agentic systems.

*Agency* is a complicated term to define.
Bengio et al. (2025) defines it as the ability to change the world to
achieve goals and mentions three pillars of agency: *affordances, goal-directedness, and intelligence*. We refer the reader to Section [4](https://arxiv.org/html/2507.07341v1#S4) for future directions for research related to agency and alignment.

Our results point to limitations in the proposed use of Scientist AIs as safety guardrails.
First, the authors suggest using a Scientist AI $A$ to generate candidate experiments and another, more powerful Scientist AI $B$ to assess their safety. However, Theorem [4](https://arxiv.org/html/2507.07341v1#Thmtheorem4) shows that even a stronger $B$ may fail to detect all dangerous outputs.
One might argue that a Scientist AI behaves differently from the LLM constructed in the proof of the theorem, being designed for interpretability and trustworthiness—but if that is true, the need for a second filtering AI is unclear.
Theorem [4](https://arxiv.org/html/2507.07341v1#Thmtheorem4) also indirectly implies the need for agency, as in some situations, there is no other way of judging the level of harm of an action than executing it in the world.

Second, if a Scientist AI is used to filter prompts for a more powerful agentic AI, Theorems [1](https://arxiv.org/html/2507.07341v1#Thmtheorem1), [2](https://arxiv.org/html/2507.07341v1#Thmtheorem2), and [3](https://arxiv.org/html/2507.07341v1#Thmtheorem3) show it cannot reliably block all harmful prompts. Section 3.1.5 of Bengio et al. (2025) acknowledges that a guardrail AI must match the intelligence of the system it oversees. But if so, it is unclear why one would use the untrusted AI at all, given similar capabilities and likely similar computational cost of the Scientist AI.

## 2 Technical Overview

##### Preliminaries.

For $n\in\mathbb{N}$ we denote $\{0,1,\dots,n-1\}$ by $[n]$.(^4^44$[n]$ will be denoted by $\mathbb{Z}_{n}$ in the appendix.) A language model $M$ is a deterministic algorithm that takes as input a prompt $\mathsf{prompt}$ and a previous output by the model $z=(z_{0},\dots,z_{i-1})$ and outputs a probability distribution over a token set $\mathcal{T}$. To sample a response of $M$ one repetitively samples from the probability distribution output by the model.

##### Construction.

At a high level, all our results (Theorems [1](https://arxiv.org/html/2507.07341v1#Thmtheorem1), [2](https://arxiv.org/html/2507.07341v1#Thmtheorem2) and [3](https://arxiv.org/html/2507.07341v1#Thmtheorem3)) on hardness of prompt detection filtering share the following proof structure:

- 1.
Design a pair of algorithms $\mathsf{Samp}$ and $\mathsf{RecoverRand}$, where $\mathsf{Samp}$ takes as input an auto-regressive model(^5^55We assume that the innocent prompt generator $G$ is a language model.) $G$ (see Appendix [A](https://arxiv.org/html/2507.07341v1#A1) for a formal definition) and randomness $R$ and produces a prompt $z=(z_{0},z_{1},\dots)$; and $\mathsf{RecoverRand}$ on input $z$ (and knowing $G$) recovers $R$.
The algorithms are formally defined in Algorithms [1](https://arxiv.org/html/2507.07341v1#alg1) and [2](https://arxiv.org/html/2507.07341v1#alg2).
- 2.
Construct a function $g$ such that:
(a)
The LLM can compute $g$ on inputs of its choice.
(b)
The adversarial prompt generator $G^{\prime}$ can sample pairs $(x,g(x))$ where $x$ is (close to) uniformly random.
(c)
The filter cannot distinguish between pairs $R=(x,\mathsf{Enc}(g(x),m))$ generated by $G^{\prime}$ and pairs $(x,y)$ where $x$ and $y$ are uniformly random and $y$ is independent of $x$, for any $m$. We think of $m$ as a malicious prompt/message that is encrypted by an encryption algorithm $\mathsf{Enc}$ using a key $g(x)$.
(d)
Given $g(x)$ and a ciphertext $c=\mathsf{Enc}(g(x),m)$, $m$ is easy to recover (using a decryption algorithm $\mathsf{Dec}$).

In the construction of Theorem [1](https://arxiv.org/html/2507.07341v1#Thmtheorem1), we design an adversarial prompt generator $G^{\prime}$ and an LLM $M^{\prime}$.
$G^{\prime}$ works as follows:

- 1.
Sample $R\leftarrow(x,\mathsf{Enc}(g(x),m))$, where $m$ is a prompt that can induce a harmful output from the LLM.
- 2.
Return $z\leftarrow\mathsf{Samp}(G,R)$.

$M^{\prime}$ works as follows:

- 1.
Recover $R\leftarrow\mathsf{RecoverRand}(G,z)$.
- 2.
Parse $R$ as $(x,\mathsf{Enc}(g(x),m))$ and compute $g(x)$.
- 3.
Recover $m$ from $c=\mathsf{Enc}(g(x),m)$, i.e., run the decryption algorithm $\mathsf{Dec}$ on $c$ using $g(x)$.
- 4.
\say
Execute(^6^66We imagine there are many possible harmful modes that can be induced from $M^{\prime}$. We model that by a collection of harmful prompts $m$ that can be \sayexecuted by $M^{\prime}$. Formally (see Theorem [7](https://arxiv.org/html/2507.07341v1#Thmtheorem7)) we say that for every model $M$ there exists $M^{\prime}$ such that for every $m$, $m$ can be \sayhidden in an innocent looking prompt (via $\mathsf{Enc}(g(x),m)$) such that $M^{\prime}$ will recover and execute $m$.) the prompt $m$.

It is easy to see that the filter cannot distinguish prompt $z$ from an innocent prompt sampled by $G$ , because $R$ is indistinguishable from random according to property (2c) above.
However, $M^{\prime}$ is able to recover the randomness, compute $g(x)$, recover $m$, and execute it.

The formal implementation of $G^{\prime}$ is given in Algorithm [3](https://arxiv.org/html/2507.07341v1#alg3) and the implementation of $M^{\prime}$ is given in Algorithm [4](https://arxiv.org/html/2507.07341v1#alg4).
We proceed to show how to construct $g$ for the result of Theorem [1](https://arxiv.org/html/2507.07341v1#Thmtheorem1).

### 2.1 Construction of g 𝑔 g italic_g

##### Moderately hard g 𝑔 g italic_g (Theorem 1 )

Our construction is based on time-lock puzzles.
More concretely, we use the RSW time-lock that relies on the moderately hard repeated exponentiation function:

$$ $\displaystyle f(n,r)=r^{(2^{t})}\pmod{n},$ $$

where $n$ is a product of two (random) primes $p$ and $q$, i.e., $n=pq$, $r$ is a random integer between 0 0 and $n-1$ and $t$ is a fixed large integer. The assumption is that without knowing the factorization of $n$, computing $f$ takes time that scales linearly with $t$ (and moreover this computation cannot be parallelized). This function has several nice properties right off the bat. First, we can choose $t$ so that computing $f$ is feasible for the LLM (which can run computations that take more than $t$ steps), but not for a filter whose runtime is bounded to be significantly smaller than $t$. Further, it is easy to generate “solved instances”: the adversarial prompt generator generates $n$, which is why it can know the primes $p$ and $q$. It can therefore compute $e=2^{t}\pmod{\phi(n)}$ where we know that $r^{e}=r^{2^{t}}\pmod{n}$. Thus, the adversarial prompt generator only needs to compute a small number of exponentiations (only $\log(e)$).

Hence, $f$ seems like a natural fit to use for constructing the function $g$, but several issues arise. First, the composite $n$ is not a random string (which is what we need), rather it is a product of two large primes.
However, we know that $n$ is uniformly random in the set of products of two primes $p$ and $q$ chosen at random from a set $[1,w]$.
By the prime number theorem, the number of primes in that range is $\Theta(w/\log(w))$.
Thus, $n$ is uniformly random in a domain of size $S=\Theta((w/\log(w))^{2})$.
$G^{\prime}$ hashes $n$ to a range of size $\Theta(\epsilon^{2}\cdot S)$ using a pairwise independent hash function $h$.
By the leftover hash lemma the joint distribution of $(h,h(n))$ is $\epsilon$-close to uniformly random (Håstad et al., 1999; Vadhan, 2012).
It is straightforward to represent the random integer $r$ as a random bit string, so the entire input $x=(h,h(n),r)$ can be (close to) uniformly random, as we wanted.
We remark that the LLM will need to recover $n$ from $(h,h(n))$: this is possible because the pairwise-independent hash function can be inverted efficiently (e.g., it can be a linear function, where inverses can be found using Gaussian elimination).
Note however that there will be more than one inverse (because the hash function is shrinking), and this raises technical issues in the construction: the LLM will need to enumerate over all the possibilities.
The final issue is that the output $r^{(2^{t})}\pmod{n}$ is moderately hard for the filter to compute, but might not be indistinguishable from uniformly random (which is what we wanted).
We handle this using standard techniques from the cryptography literature (namely using hardcore bits of $f$ (Goldreich and Levin, 1989; Goldreich, 2001)). See the appendix for the full details of this construction.

##### Other time-lock puzzles.

Our construction is based on the RSW time-lock puzzle but we consider proving Theorem [1](https://arxiv.org/html/2507.07341v1#Thmtheorem1) assuming general time-lock puzzles.
See Remark [4](https://arxiv.org/html/2507.07341v1#Thmremark4) in Appendix [C](https://arxiv.org/html/2507.07341v1#A3) for details.

##### Secret key (Theorem 2 ) and public key (Theorem 3 ) constructions.

We focus on the impossibility results for moderately weak filters, i.e., weaker than the LLM in this overview. However, if we allow collaboration between the LLM and the prompt generator, it is possible to prove impossibility even against stronger filters.
If we allow the LLM to publish a public key (and allow the adversarial prompt generator to depend on it) as in Theorem [3](https://arxiv.org/html/2507.07341v1#Thmtheorem3), then we can use any trapdoor function to instantiate $\mathsf{Enc}$ function whose output will be pseudorandom to any polynomial-time filter that does not know the secret key. Here, we let the adversarial prompt generator $G^{\prime}$ sample $R=\mathsf{Enc}(\mathsf{pk},m)$, where $\mathsf{pk}$ is a public key, and returns the prompt $z\leftarrow\mathsf{Samp}(G,R)$.
The LLM recovers $R$ from $z$ and uses its matching secret key $\mathsf{sk}$ to recover $m$ from $R$.
If we allow the LLM and the adversarial prompt generator to have shared randomness (or rather shared secret key $\mathsf{sk}$) as in Theorem [2](https://arxiv.org/html/2507.07341v1#Thmtheorem2), then we can construct $G^{\prime}$ without making any assumptions: we use the shared randomness as a one-time pad to create a single special prompt that leads to a harmful output. Namely, $G^{\prime}$ sets $R=\mathsf{sk}\oplus m$ for a prompt $m$ which can induce a harmful output from the LLM and returns $z\leftarrow\mathsf{Samp}(G,R)$. Alternatively, under the (fairly relaxed) cryptographic assumption that one-way functions exist, even a short shared random seed can be used to generate an *arbitrary (polynomial) number* of harmful prompts that are indistinguishable from innocent ones.

Figure: Algorithm 1 $\mathsf{Samp}(G,R)$ $\triangleright$ $G$: a prompt generator; $R\in\{0,1\}^{*}$: the randomness

Figure: Algorithm 2 $\mathsf{RecoverRand}(G,z,L)$ $\triangleright$ $G$: a prompt generator; $z\in\{0,1\}^{*}$; $L$: a length of the randomness required

### 2.2 Recoverable-Randomness Sampling

In our construction, it is key that the distribution of $G^{\prime}$ is indistinguishable from $G$ and that it is possible to effectively recover the randomness used by $G^{\prime}$ from its outputs.
To achieve this, we design an algorithm $\mathsf{Samp}$ (Algorithm [1](https://arxiv.org/html/2507.07341v1#alg1)) that takes as input a generator $G$ and randomness $R$ and produces $z=(z_{0},z_{1},\dots)$; and an algorithm $\mathsf{RecoverRand}$ (Algorithm [2](https://arxiv.org/html/2507.07341v1#alg2)) that given $z$ and $G$ recovers $R$.
We assume that the set of tokens over which $G$ operates equals $\{0,1\}$.
This is possible because of a simple reduction (see Appendix [A](https://arxiv.org/html/2507.07341v1#A1)).

The high-level idea of our scheme is to maintain \sayresidual randomness.
Imagine, that at some point in the generation process, $G(z_{0},\dots,z_{i-1})\rightarrow 1/4$.
Then to generate $z_{i}$ accurately $2$ bits of randomness are needed, i.e., if the bits are $00$ we set $z_{i}=1$ and we set $z_{i}=0$ if the bits are $00,01,11$.
If $z_{i}=0$ then the recovering algorithm might not know which of the three options for the randomness determined $z_{i}$.
To address this issue we \sayreuse this randomness in the generation of the next tokens.
More concretely, if $z_{i}=0$ then we have $\log_{2}(3)$ bits of residual randomness that we can use in generating $z_{i+1},z_{i+2},\dots$.
If done properly this \sayreusing process will allow perfect recovery of the randomness used.
Intuitively, because all of the randomnness will be used.

Our scheme, defined in Algorithms [1](https://arxiv.org/html/2507.07341v1#alg1) and [2](https://arxiv.org/html/2507.07341v1#alg2), works as follows.
At all times, the sampling algorithm $\mathsf{Samp}(G,R)$ maintains a precision range $k$ and a value $q\in[k]$.
The value $q$ is created on the fly using the randomness $R$ and will determine how tokens are sampled.
Intuitively, $q$ maintains the \sayresidual randomness.
$\mathsf{Samp}$ builds a response $(z_{0},\dots,z_{i-1})$ iteratively, where in the $i$-th step it:

- 1.
Calls $p_{i}\leftarrow G(z_{0},\dots,z_{i-1})$.
- 2.
If $k<2^{P}$ it multiplies $k$ by an appropriate power $2^{t}$ so that $k\geq 2^{P}$,(^7^77$P$ is a precision parameter that will determine the closeness of the generated distribution to the distribution of $G$.) and increases the precision of $q$ by concatenating it with the not yet used randomness from $R$, i.e., $q\leftarrow q\ \|\ R[j:j+t]$.
This ensures that $q$ represents an element of $[k]$.
- 3.
If $q/k<p_{i}$ it sets $z_{i}\leftarrow 1$ and sets $z_{i}\leftarrow 0$ otherwise.
Additionally, it updates $q$ and $k$ so that the \sayresidual randomness can be used later on.
Intuitively, if $q/k<p_{i}$ then we want to keep the $\approx\log_{2}(p_{i}\cdot k)$ bits of randomness.
To do that we update $k\leftarrow k-\left\lfloor{p_{i}\cdot k}\right\rfloor$, which implicitly represents that $q$ is now a random value from $[k-\left\lfloor{p_{i}\cdot k}\right\rfloor]$.
If $q/k>p_{i}$ the values are updated accordingly.

To recover the randomness $\mathsf{RecoverRand}(G,z)$ works as follows.
It maintains bitstrings $a,b$ that informally are \saylower and upper-bounds on the randomness $R$ being recovered.
More concretely, in the first step $\mathsf{RecoverRand}$ knows that the prefix of randomness $R$ is between $0^{P}$ and $1^{P}$.
If $p_{0}\leftarrow G()$ and $z_{0}=1$ then it knows that the prefix of $R$ is between $a=0^{P}$ and $b=p_{0}\cdot 2^{P}$ written in binary on $P$ bits.
By construction, the common prefix of $a,b$ is equal to the prefix of $R$ - this will allow to recover $R$.
What is left to show is that it is possible to maintain $a$ and $b$ correctly.
Observe that it is possible to update $k$ exactly like $\mathsf{Samp}$ does it because $k$ changes depending only on the value of $z_{i}$.

Figure: Algorithm 3 $\mathsf{HarmIncite}(G,m,t)$ $\triangleright$ $G$: innocent prompt generator; $m$: harmful prompt; $t$: time parameter

Figure: Algorithm 4 $\mathsf{MaliciousLLM}(M,z,G,t)$ $\triangleright$ $M$: LLM; $z$: input; $G$: weak innocent prompt generator; $t$: time parameter

### 2.3 Output Filtering

##### Setup.

Before elaborating on the construction, we describe the setup in more detail.
A *harmfulness oracle* is a function $\mathcal{H}:\mathcal{T}^{*}\rightarrow[0,\infty)$.
Given an output $z\in\mathcal{T}^{*}$ of a language model, $\mathcal{H}(z)$ represents its harmfulness: $\mathcal{H}(z)=0$ indicates that $z$ is benign, while higher values denote greater harmfulness.
During inference, neither the LLM nor the filter has query access to $\mathcal{H}$.
The oracle $\mathcal{H}$ can be interpreted as the environment or nature “evaluating” the harmfulness of $z$.
However, the filter (and the LLM) may have received training examples of both harmful and benign outputs, or an approximate description of $\mathcal{H}$, during training.

##### Construction.

We leverage techniques used in the proof of Theorem [1](https://arxiv.org/html/2507.07341v1#Thmtheorem1) to prove Theorem [4](https://arxiv.org/html/2507.07341v1#Thmtheorem4).
Let $M$ be an LLM that doesn’t produce harmful outputs.

To define $M^{\prime}$ we apply the same process as the one used to transform $G\dashrightarrow G^{\prime}$ but applied to $M$.
When we apply the transformation, we set $t$ of the RSW time-lock to be exponential in the time complexity of $M$.
This ensures that the outcome of the transformation, i.e., $M^{\prime}$, is such that its outputs are indistinguishable from outputs of $M$ for all polynomial, in the running time of $M$, filters.

To define $\mathcal{H}^{\prime}$ we apply the same process as the one used to transform the LLM in the proof of Theorem [1](https://arxiv.org/html/2507.07341v1#Thmtheorem1).
More concretely, $\mathcal{H}^{\prime}(z)$ \sayruns(^8^88$\mathcal{H}^{\prime}$ is a harmfulness oracle and not an algorithm, so formally it does not run.) as follows: it recovers the randomness used by $M^{\prime}$, i.e., $R\leftarrow\mathsf{RecoverRand}(M^{\prime},z)$.
If $R$ contains a Time-Lock Puzzle, $\mathcal{H}^{\prime}$ solves it to obtain an output $m$ and \saydeclares that $z$ is harmful (with harmfulness level determined by $m$).

The sketch of why this construction is correct is as follows.
Note that similarly as for $G$ and $G^{\prime}$ in the case of Theorem [1](https://arxiv.org/html/2507.07341v1#Thmtheorem1), $M^{\prime}$ outputs are indistinguishable from the outputs of $M$ for all polynomial-time filters.
Moreover, $M^{\prime}$ on every harmful $m$, \sayembeds it in its output $z$, $\mathcal{H}^{\prime}$ \sayrecovers $m$ from $z$ and \saydeclares that $z$ is harmful with the harmfulness level determined by $m$.

## 3 Related Work

Alignment. Making AI models aligned with human preferences is a central concern of contemporary AI research (Amodei et al., 2016; Leike et al., 2018; Hendrycks et al., 2021; Ji et al., 2023). In order to guide model behavior, technical efforts have focused on techniques like Reinforcement Learning from Human Feedback (RLHF, Christiano et al., 2017), further improved by Direct Preference Optimization (DPO) (Rafailov et al., 2023). However, a growing body of work suggests that achieving robust alignment is profoundly difficult: Researchers have highlighted issues ranging from the inherent ambiguity in specifying human preferences (Gabriel, 2020; Zhi-Xuan et al., 2024; Sorensen et al., 2024), to problems like shallow alignment induced by properties of the alignment algorithms (Jain et al., 2023; Kotha et al., 2023; Lee et al., 2024) and the alignment data (Qi et al., 2024). For instance, Lee et al. (2024) show that the DPO alignment algorithm only teaches a model to bypass toxic “regions” without removing toxic knowledge gained from the pre-training stage, making it possible to elicit this toxic knowledge with “jailbreaks”—changes to the prompt that lead a model from answer-refusal to generating harmful information. Relatedly, Qi et al. (2024) argue that safety alignment often takes shortcuts by primarily adapting a model’s generative distribution over just its first few output tokens, making them vulnerable to various attacks. The difficulty in robustly aligning models at a deep representational level underscores the need for complementary external mechanisms to detect or prevent harmful model outputs. This is in line with regulatory frameworks such as the EU AI Act, which requires AI systems in the high-risk category to implement an effective risk management system (see Article 9 EU AI Act,).

Filters. In response to the need for safer AI systems, practical filtering mechanisms
have been developed and deployed.
For instance, model developers like Meta have introduced tools such as Llama Guard, designed to classify content as safe or unsafe (Inan et al., 2023). Similarly, cloud service providers like Microsoft Azure offer content filtering capabilities within their AI service implementations (Microsoft Corporation, 2025), and companies like Nvidia also provide solutions aimed at moderating AI-generated content (NVIDIA Corporation, 2025). These approaches represent an ongoing evolution, with classifiers and filters becoming increasingly sophisticated. However, the development of jailbreaks poses a consistent challenge to successful filtering and model alignment in general (Andriushchenko et al., 2024; Chao et al., 2024; Xu et al., 2024). Against the background of this dynamic co-evolution of attack and defense, our work explores the computational intractability of filtering approaches under cryptographic assumptions.

Time Lock Puzzles.
It is usually desired that cryptographic schemes cannot be broken by any adversary. An exception is the notion of cryptographic puzzles that can be solved in some preset amount of time (or space) but not faster. Examples of such puzzles (Dwork and Naor, 1992; Rivest et al., 1996) have been used as a way to combat spam or send messages into the future, forcing the spammer (or the future reader of messages) to invest the preset amount of time. The notion of time-lock puzzles introduced by Rivest et al. (1996) following May’s time-released cryptography (May, 1993) is especially intriguing in that it allows a user to quickly encrypt a message in such a way that it can be read only after a longer but set number of time steps. Informally, the sender generates a puzzle with
a solution $s$ that remains hidden from adversaries that run in time significantly less than $t$, including parallel adversaries with polynomially many processors. The original (Rivest et al., 1996) candidate was based on the assumption that exponentiation modulo an RSA integer is an “inherently sequential” computation. More recently Bitansky et al. (2016a) constructed time-lock puzzles based on the necessary assumption that worst-case Non-Parallelizing Languages exist-decidable in time $t$, but hard in the worst case for circuits of depth significantly smaller than $t$-and that indistinguishability obfuscation exists (Bitansky et al., 2015; Canetti et al., 2014).
A culmination of a series of follow-up works (Agrawal et al., 2025; Bitansky and Garg, 2025; Abram et al., 2025) managed to construct time-lock puzzles based on a version of the Learning With Errors (Regev, 2009) (LWE) assumption.
One advantage of basing time-lock puzzles on LWE is that the other constructions are broken by quantum algorithms, while LWE is a candidate for post-quantum secure cryptography.

## 4 Reflections

Our work builds on a growing body of research highlighting the inherent unpredictability and misalignment risks of complex AI systems. By formalizing these insights, we provide a theoretical foundation for understanding when and why alignment may remain an elusive goal, regardless of technical advancements or regulatory safeguards. The implications of our impossibility theorems are profound: they call into question the feasibility of creating AI systems that are both powerful and wholly safe, at least using a certain natural set of filtering tools. This emphasizes the need to reconsider how society audits and handles these systems.

##### Beyond Cartesian Duality.

Our results show that merging intelligence and judgment might be necessary for achieving AI alignment.
It is in contrast with what some other works suggest, e.g., Bengio et al. (2025) argues for separating intelligence from agency.
We, on the other hand, argue that agency is indispensable in some situations.

It would be interesting to investigate how our findings about AI alignment relate to a recent paradigm shift in the study of the mind known as *4E cognitive science* (Newen et al., 2018), which emphasizes the *embodied, embedded, enactive, and extended* nature of cognition.
This paradigm stands in contrast to the Cartesian mind-body duality and argues that the unit of explanation of cognition is not just neuronal processes in the brain but the whole complex of brain-body-environment.

## Acknowledgements

SB is supported by the DAAD programme Konrad Zuse Schools of Excellence in Artificial
Intelligence, sponsored by the German Federal Ministry of Education and Research. OR is supported by the Simons Foundation Collaboration on the Theory of Algorithmic Fairness, the Sloan Foundation Grant 2020-13941, and the Simons Foundation Investigators Award 689988.

## References

- Abram et al. [2025]
D. Abram, G. Malavolta, and L. Roy.
Key-homomorphic computations for RAM: fully succinct randomised encodings and more.
*IACR Cryptol. ePrint Arch.*, page 339, 2025.
URL [https://eprint.iacr.org/2025/339](https://eprint.iacr.org/2025/339).
- Agrawal et al. [2025]
S. Agrawal, G. Malavolta, and T. Zhang.
Time-lock puzzles from lattices.
*IACR Cryptol. ePrint Arch.*, page 47, 2025.
URL [https://eprint.iacr.org/2025/047](https://eprint.iacr.org/2025/047).
- Amodei et al. [2016]
D. Amodei, C. Olah, J. Steinhardt, P. Christiano, J. Schulman, and D. Mané.
Concrete problems in ai safety.
*arXiv preprint arXiv:1606.06565*, 2016.
- Andriushchenko et al. [2024]
M. Andriushchenko, F. Croce, and N. Flammarion.
Jailbreaking leading safety-aligned llms with simple adaptive attacks.
*arXiv preprint arXiv:2404.02151*, 2024.
- Bai et al. [2022]
Y. Bai, A. Jones, K. Ndousse, A. Askell, A. Chen, N. DasSarma, D. Drain, S. Fort, D. Ganguli, T. Henighan, et al.
Training a helpful and harmless assistant with reinforcement learning from human feedback.
*arXiv preprint arXiv:2204.05862*, 2022.
- Bengio et al. [2025]
Y. Bengio, M. Cohen, D. Fornasiere, J. Ghosn, P. Greiner, M. MacDermott, S. Mindermann, A. Oberman, J. Richardson, O. Richardson, M.-A. Rondeau, P.-L. St-Charles, and D. Williams-King.
Superintelligent agents pose catastrophic risks: Can scientist ai offer a safer path?, 2025.
URL [https://arxiv.org/abs/2502.15657](https://arxiv.org/abs/2502.15657).
- Bitansky and Garg [2025]
N. Bitansky and R. Garg.
Succinct randomized encodings from laconic function evaluation, faster and simpler.
In *Advances in Cryptology – EUROCRYPT 2025: 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Madrid, Spain, May 4–8, 2025, Proceedings, Part VII*, page 406–436, Berlin, Heidelberg, 2025. Springer-Verlag.
ISBN 978-3-031-91097-5.
doi: 10.1007/978-3-031-91098-2_15.
URL [https://doi.org/10.1007/978-3-031-91098-2_15](https://doi.org/10.1007/978-3-031-91098-2_15).
- Bitansky et al. [2015]
N. Bitansky, S. Garg, H. Lin, R. Pass, and S. Telang.
Succinct randomized encodings and their applications.
In *Proceedings of the forty-seventh annual ACM symposium on Theory of Computing*, pages 439–448, 2015.
- Bitansky et al. [2016a]
N. Bitansky, S. Goldwasser, A. Jain, O. Paneth, V. Vaikuntanathan, and B. Waters.
Time-lock puzzles from randomized encodings.
In *Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science*, pages 345–356, 2016a.
- Bitansky et al. [2016b]
N. Bitansky, S. Goldwasser, A. Jain, O. Paneth, V. Vaikuntanathan, and B. Waters.
Time-lock puzzles from randomized encodings.
In *Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science*, ITCS ’16, page 345–356, New York, NY, USA, 2016b. Association for Computing Machinery.
ISBN 9781450340571.
doi: 10.1145/2840728.2840745.
URL [https://doi.org/10.1145/2840728.2840745](https://doi.org/10.1145/2840728.2840745).
- Boneh and Naor [2000]
D. Boneh and M. Naor.
Timed commitments.
In *Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology*, CRYPTO ’00, page 236–254, Berlin, Heidelberg, 2000. Springer-Verlag.
ISBN 3540679073.
- Boneh et al. [2018]
D. Boneh, J. Bonneau, B. Bünz, and B. Fisch.
Verifiable delay functions.
In H. Shacham and A. Boldyreva, editors, *Advances in Cryptology - CRYPTO 2018 - 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2018, Proceedings, Part I*, volume 10991 of *Lecture Notes in Computer Science*, pages 757–788. Springer, 2018.
doi: 10.1007/978-3-319-96884-1\_25.
URL [https://doi.org/10.1007/978-3-319-96884-1_25](https://doi.org/10.1007/978-3-319-96884-1_25).
- Canetti et al. [2014]
R. Canetti, J. Holmgren, A. Jain, and V. Vaikuntanathan.
Indistinguishability obfuscation of iterated circuits and ram programs.
*Cryptology ePrint Archive*, 2014.
- Chao et al. [2024]
P. Chao, E. Debenedetti, A. Robey, M. Andriushchenko, F. Croce, V. Sehwag, E. Dobriban, N. Flammarion, G. J. Pappas, F. Tramer, et al.
Jailbreakbench: An open robustness benchmark for jailbreaking large language models.
*arXiv preprint arXiv:2404.01318*, 2024.
- Chiusi et al. [2020]
F. Chiusi, B. Alfter, M. Ruckenstein, and T. Lehtiniemi.
Automating society report 2020.
2020.
- Christ et al. [2023]
M. Christ, S. Gunn, and O. Zamir.
Undetectable watermarks for language models.
*IACR Cryptol. ePrint Arch.*, 2023:763, 2023.
URL [https://api.semanticscholar.org/CorpusID:259092330](https://api.semanticscholar.org/CorpusID:259092330).
- Christiano et al. [2017]
P. F. Christiano, J. Leike, T. Brown, M. Martic, S. Legg, and D. Amodei.
Deep reinforcement learning from human preferences.
*Advances in neural information processing systems*, 30, 2017.
- Diffie and Hellman [1976]
W. Diffie and M. Hellman.
New directions in cryptography.
*IEEE Transactions on Information Theory*, 22(6):644–654, 1976.
doi: 10.1109/TIT.1976.1055638.
- Dwork and Naor [1992]
C. Dwork and M. Naor.
Pricing via processing or combatting junk mail.
In *Annual international cryptology conference*, pages 139–147. Springer, 1992.
- Dworkin et al. [2001]
M. J. Dworkin, E. Barker, J. Nechvatal, J. Foti, L. E. Bassham, E. Roback, and J. D. Jr.
Advanced encryption standard (aes), 2001-11-26 00:11:00 2001.
URL [https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=901427](https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=901427).
- [21]
EU AI Act.
Regulation (EU) 2024/1689 of the European Parliament and of the Council of 13 June 2024 laying down harmonised rules on artificial intelligence.
*OJ*, L 2024/1689.
- Fischer-Abaigar et al. [2024]
U. Fischer-Abaigar, C. Kern, N. Barda, and F. Kreuter.
Bridging the gap: Towards an expanded toolkit for ai-driven decision-making in the public sector.
*Government Information Quarterly*, 41(4):101976, 2024.
- Gabriel [2020]
I. Gabriel.
Artificial intelligence, values, and alignment.
*Minds and machines*, 30(3):411–437, 2020.
- Goldreich [2001]
O. Goldreich.
*The Foundations of Cryptography - Volume 1: Basic Techniques*.
Cambridge University Press, 2001.
ISBN 0-521-79172-3.
doi: 10.1017/CBO9780511546891.
URL [http://www.wisdom.weizmann.ac.il/%7Eoded/foc-vol1.html](http://www.wisdom.weizmann.ac.il/%7Eoded/foc-vol1.html).
- Goldreich [2006]
O. Goldreich.
*Foundations of Cryptography: Volume 1*.
Cambridge University Press, USA, 2006.
ISBN 0521035368.
- Goldreich and Levin [1989]
O. Goldreich and L. A. Levin.
A hard-core predicate for all one-way functions.
In D. S. Johnson, editor, *Proceedings of the 21st Annual ACM Symposium on Theory of Computing, May 14-17, 1989, Seattle, Washington, USA*, pages 25–32. ACM, 1989.
doi: 10.1145/73007.73010.
URL [https://doi.org/10.1145/73007.73010](https://doi.org/10.1145/73007.73010).
- Golowich and Moitra [2024]
N. Golowich and A. Moitra.
Edit distance robust watermarks via indexing pseudorandom codes.
In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomczak, and C. Zhang, editors, *Advances in Neural Information Processing Systems*, volume 37, pages 20645–20693. Curran Associates, Inc., 2024.
URL [https://proceedings.neurips.cc/paper_files/paper/2024/file/24c53bfa5b53fc2cf05644f5a7a26bb0-Paper-Conference.pdf](https://proceedings.neurips.cc/paper_files/paper/2024/file/24c53bfa5b53fc2cf05644f5a7a26bb0-Paper-Conference.pdf).
- Greenblatt et al. [2024]
R. Greenblatt, C. Denison, B. Wright, F. Roger, M. MacDiarmid, S. Marks, J. Treutlein, T. Belonax, J. Chen, D. Duvenaud, A. Khan, J. Michael, S. Mindermann, E. Perez, L. Petrini, J. Uesato, J. Kaplan, B. Shlegeris, S. Bowman, and E. Hubinger.
Alignment faking in large language models, 12 2024.
- Haensch et al. [2023]
A.-C. Haensch, S. Ball, M. Herklotz, and F. Kreuter.
Seeing chatgpt through students’ eyes: An analysis of tiktok data.
In *2023 Big Data Meets Survey Science (BigSurv)*, pages 1–8. IEEE, 2023.
- Håstad et al. [1999]
J. Håstad, R. Impagliazzo, L. A. Levin, and M. Luby.
A pseudorandom generator from any one-way function.
*SIAM J. Comput.*, 28(4):1364–1396, 1999.
doi: 10.1137/S0097539793244708.
URL [https://doi.org/10.1137/S0097539793244708](https://doi.org/10.1137/S0097539793244708).
- Hendrycks et al. [2021]
D. Hendrycks, N. Carlini, J. Schulman, and J. Steinhardt.
Unsolved problems in ml safety.
*arXiv preprint arXiv:2109.13916*, 2021.
- Hubinger et al. [2019]
E. Hubinger, C. Merwijk, V. Mikulik, J. Skalse, and S. Garrabrant.
Risks from learned optimization in advanced machine learning systems, 06 2019.
- Inan et al. [2023]
H. Inan, K. Upasani, J. Chi, R. Rungta, K. Iyer, Y. Mao, M. Tontchev, Q. Hu, B. Fuller, D. Testuggine, et al.
Llama guard: Llm-based input-output safeguard for human-ai conversations.
*arXiv preprint arXiv:2312.06674*, 2023.
- Jain et al. [2023]
S. Jain, R. Kirk, E. S. Lubana, R. P. Dick, H. Tanaka, E. Grefenstette, T. Rocktäschel, and D. S. Krueger.
Mechanistically analyzing the effects of fine-tuning on procedurally defined tasks.
*arXiv preprint arXiv:2311.12786*, 2023.
- Ji et al. [2023]
J. Ji, T. Qiu, B. Chen, B. Zhang, H. Lou, K. Wang, Y. Duan, Z. He, J. Zhou, Z. Zhang, et al.
Ai alignment: A comprehensive survey.
*arXiv preprint arXiv:2310.19852*, 2023.
- Kirchenbauer et al. [2023]
J. Kirchenbauer, J. Geiping, Y. Wen, J. Katz, I. Miers, and T. Goldstein.
A watermark for large language models.
In A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, and J. Scarlett, editors, *Proceedings of the 40th International Conference on Machine Learning*, volume 202 of *Proceedings of Machine Learning Research*, pages 17061–17084. PMLR, 23–29 Jul 2023.
URL [https://proceedings.mlr.press/v202/kirchenbauer23a.html](https://proceedings.mlr.press/v202/kirchenbauer23a.html).
- Kotha et al. [2023]
S. Kotha, J. M. Springer, and A. Raghunathan.
Understanding catastrophic forgetting in language models via implicit inference.
*arXiv preprint arXiv:2309.10105*, 2023.
- Kuditipudi et al. [2023]
R. Kuditipudi, J. Thickstun, T. Hashimoto, and P. Liang.
Robust distortion-free watermarks for language models.
*CoRR*, abs/2307.15593, 2023.
doi: 10.48550/ARXIV.2307.15593.
URL [https://doi.org/10.48550/arXiv.2307.15593](https://doi.org/10.48550/arXiv.2307.15593).
- Lee et al. [2024]
A. Lee, X. Bai, I. Pres, M. Wattenberg, J. K. Kummerfeld, and R. Mihalcea.
A mechanistic understanding of alignment algorithms: A case study on dpo and toxicity.
*arXiv preprint arXiv:2401.01967*, 2024.
- Leike et al. [2018]
J. Leike, D. Krueger, T. Everitt, M. Martic, V. Maini, and S. Legg.
Scalable agent alignment via reward modeling: a research direction.
*arXiv preprint arXiv:1811.07871*, 2018.
- Levy et al. [2021]
K. Levy, K. E. Chasalow, and S. Riley.
Algorithms and decision-making in the public sector.
*Annual Review of Law and Social Science*, 17(1):309–334, 2021.
- Luu et al. [2016]
L. Luu, D.-H. Chu, H. Olickel, P. Saxena, and A. Hobor.
Making smart contracts smarter.
In *Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security*, CCS ’16, page 254–269, New York, NY, USA, 2016. Association for Computing Machinery.
ISBN 9781450341394.
doi: 10.1145/2976749.2978309.
URL [https://doi.org/10.1145/2976749.2978309](https://doi.org/10.1145/2976749.2978309).
- May [1993]
T. C. May.
Timed-release cryoto.
*http://www. hks. net/cpunks/cpunks-0/1460. html*, 1993.
- Microsoft Corporation [2025]
Microsoft Corporation.
What is azure ai content safety?
[https://learn.microsoft.com/en-us/azure/ai-services/content-safety/overview](https://learn.microsoft.com/en-us/azure/ai-services/content-safety/overview), 2025.
Accessed: 2025-05-14.
- Newen et al. [2018]
A. Newen, L. De Bruin, and S. Gallagher.
*The Oxford Handbook of 4E Cognition*.
Oxford University Press, 09 2018.
ISBN 9780198735410.
doi: 10.1093/oxfordhb/9780198735410.001.0001.
URL [https://doi.org/10.1093/oxfordhb/9780198735410.001.0001](https://doi.org/10.1093/oxfordhb/9780198735410.001.0001).
- NVIDIA Corporation [2025]
NVIDIA Corporation.
Nvidia nemo guardrails documentation.
[https://docs.nvidia.com/nemo/guardrails/latest/index.html](https://docs.nvidia.com/nemo/guardrails/latest/index.html), 2025.
Accessed: 2025-05-14.
- OpenAI [2024]
OpenAI.
Sora by openai.
[https://openai.com/sora](https://openai.com/sora), 2024.
Accessed: 2025-06-23.
- Perdomo et al. [2023]
J. C. Perdomo, T. Britton, M. Hardt, and R. Abebe.
Difficult lessons on social prediction from wisconsin public schools.
*arXiv preprint arXiv:2304.06205*, 2023.
- Potash et al. [2015]
E. Potash, J. Brew, A. Loewi, S. Majumdar, A. Reece, J. Walsh, E. Rozier, E. Jorgenson, R. Mansour, and R. Ghani.
Predictive modeling for public health: Preventing childhood lead poisoning.
In *Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining*, pages 2039–2047, 2015.
- Qi et al. [2024]
X. Qi, A. Panda, K. Lyu, X. Ma, S. Roy, A. Beirami, P. Mittal, and P. Henderson.
Safety alignment should be made more than just a few tokens deep.
*arXiv preprint arXiv:2406.05946*, 2024.
- Rafailov et al. [2023]
R. Rafailov, A. Sharma, E. Mitchell, C. D. Manning, S. Ermon, and C. Finn.
Direct preference optimization: Your language model is secretly a reward model.
*Advances in Neural Information Processing Systems*, 36:53728–53741, 2023.
- Regev [2009]
O. Regev.
On lattices, learning with errors, random linear codes, and cryptography.
*J. ACM*, 56(6), Sept. 2009.
ISSN 0004-5411.
doi: 10.1145/1568318.1568324.
URL [https://doi.org/10.1145/1568318.1568324](https://doi.org/10.1145/1568318.1568324).
- Rivest et al. [1978]
R. L. Rivest, A. Shamir, and L. Adleman.
A method for obtaining digital signatures and public-key cryptosystems.
*Commun. ACM*, 21(2):120–126, Feb. 1978.
ISSN 0001-0782.
doi: 10.1145/359340.359342.
URL [https://doi.org/10.1145/359340.359342](https://doi.org/10.1145/359340.359342).
- Rivest et al. [1996]
R. L. Rivest, A. Shamir, and D. A. Wagner.
Time-lock puzzles and timed-release crypto.
1996.
- Sorensen et al. [2024]
T. Sorensen, J. Moore, J. Fisher, M. Gordon, N. Mireshghallah, C. M. Rytting, A. Ye, L. Jiang, X. Lu, N. Dziri, et al.
A roadmap to pluralistic alignment.
*arXiv preprint arXiv:2402.05070*, 2024.
- Vadhan [2012]
S. P. Vadhan.
Pseudorandomness.
*Found. Trends Theor. Comput. Sci.*, 7(1-3):1–336, 2012.
doi: 10.1561/0400000010.
URL [https://doi.org/10.1561/0400000010](https://doi.org/10.1561/0400000010).
- Xu et al. [2024]
Z. Xu, Y. Liu, G. Deng, Y. Li, and S. Picek.
A comprehensive study of jailbreak attack versus defense for large language models.
*arXiv preprint arXiv:2402.13457*, 2024.
- Zamir [2024]
O. Zamir.
Undetectable steganography for language models.
*Transactions on Machine Learning Research*, 2024.
ISSN 2835-8856.
URL [https://openreview.net/forum?id=fq6aQoMSHz](https://openreview.net/forum?id=fq6aQoMSHz).
- Zhi-Xuan et al. [2024]
T. Zhi-Xuan, M. Carroll, M. Franklin, and H. Ashton.
Beyond preferences in ai alignment.
*Philosophical Studies*, pages 1–51, 2024.

## Appendix A Preliminaries

For $n\in\mathbb{N}$ we denote $\{0,1,\dots,n-1\}$ by $[n]$ and sometimes by $\mathbb{Z}_{n}$.
For $n\in\mathbb{N}$ we denote by $\phi(n)$ the Euler’s totient function, i.e, it counts the positive integers in $[n]$ that are relatively prime to $n$.
The multiplicative group $\mathbb{Z}_{n}^{*}$ consists of the set of natural numbers that are smaller than $n$ and relatively prime to it, and the operation is multiplication mod $n$.
We denote by $\log$ the logarithm with base two.
We denote by $x\,||\,y$ the concatenation of the vectors $x$, $y$, and by $\mathsf{len}(s)$ the length of the sequence $s$.
For a sequence $s=(\ldots,s_{i},\ldots)$ we denote by $s[i:j]$ the sub-sequence $(s_{i},\ldots,s_{j-1})$.
For a set $S$ we denote by $\leftarrow S$ the process of choosing a uniformly random element of $S$.
For an algorithm $A$ we also write $\leftarrow A$ to denote the (potentially random) element returned by $A$.
Let $\lambda$ be the security parameter, we denote by $\text{negl}(\lambda)$ any function that is in $O(1/p(\lambda))$ for every polynomial $p(\cdot)$. As is standard in Cryptography research, we think of $\lambda$ as the “key size”, and of running times that are super-polynomial in $\lambda$ as “infeasible”.

### A.1 Language Models

Some notions in this subsection are adapted from Christ et al. [2023].

###### Definition 1 .

A language model $M$ over token set $\mathcal{T}$ is a deterministic algorithm that takes as input a prompt $\mathsf{prompt}$ and tokens previously output by the model $z=(z_{1},\ldots,z_{i-1})$, and outputs a probability distribution $p_{i}=M(\mathsf{prompt},z)$ over $\mathcal{T}$.

###### Definition 2 .

A language model’s response to $\mathsf{prompt}$ is a random variable $M(\mathsf{prompt})\in\mathcal{T}^{*}$ defined algorithmically as follows. We begin with an empty list of tokens $z=()$. As long as the last token in $z$ is not $\mathsf{done}$, we draw a token $z_{i}$ from the distribution $M(\mathsf{prompt},z)$ and append it to $z$.

###### Definition 1 .

###### Definition 2 .

### A.2 Entropy and Empirical Entropy

For a distribution $D$ over a finite set $X$, the Shannon entropy is

$$ $H(D)=\mathbb{E}_{z\sim D}[-\log D(z)].$ $$

The empirical entropy of $z$ in $D$ is $-\log D(z)$.

###### Definition 3 .

For a language model $M$, a prompt $\mathsf{prompt}$, and a response $z\in\mathcal{T}^{*}$, the empirical entropy of $M$ responding with $z$ to $\mathsf{prompt}$ is:

$$ $H_{e}(M,\mathsf{prompt},z):=-\log\mathbb{P}[M(\mathsf{prompt})=z].$ $$

Note that

$$ $H(M(\mathsf{prompt}))=\mathbb{E}_{z}[H_{e}(M,\mathsf{prompt},z)].$ $$

###### Definition 3 .

### A.3 Time-Lock Puzzles

Time-lock puzzles, introduced by Rivest et al. [1996], provide a mechanism for sending messages “to the future”. The core idea is to enable a sender to quickly generate a cryptographic puzzle whose solution is guaranteed to remain hidden until a specified amount of computational time has elapsed.
Additionally, this security must hold even against highly parallel adversaries equipped with polynomially many processors.
The following is a definition of a Time-Lock Puzzle adapted from Bitansky et al. [2016b].

###### Definition 4 (Time-Lock Puzzle) .

A *Time-Lock Puzzle* (TLP) is defined over a difficulty parameter $t\in\mathbb{N}$ and a security parameter $\lambda$.
A Time-Lock Puzzle consists of a pair of algorithms $\mathsf{Puzzle}=(\mathsf{Gen},\mathsf{Sol})$ with the following properties:

- •
Puzzle Generation:
$Z\leftarrow\mathsf{Gen}(t,s)$
is a probabilistic algorithm that takes as input a difficulty parameter $t$ and a solution $s\in\{0,1\}^{\lambda}$ and outputs a puzzle $Z$.
- •
Puzzle Solving:
$s\leftarrow\mathsf{Sol}(Z)$
is a deterministic algorithm that takes a puzzle $Z$ and returns a solution $s$.
- •
Completeness: For all difficulty parameters $t\in\mathbb{N}$ and $s\in\{0,1\}^{\lambda}$:
$\mathsf{Sol}(\mathsf{Gen}(t,s))=s.$
- •
Efficiency:
–
$\mathsf{Gen}(t,s)$ runs in time $\mathsf{poly}(\log t,\lambda)$.
–
$\mathsf{Sol}(Z)$ runs in time $t\cdot\mathsf{poly}(\lambda)$.
- •
Sequentiality (Time-Lock Property):
There exists $\varepsilon<1$ and a polynomial $\underline{t}(\cdot)$, such that for every polynomial $t(\cdot)\geq\underline{t}(\cdot)$ and every polysize adversary $\mathcal{A}=\{\mathcal{A}_{\lambda}\}_{\lambda\in\mathbb{N}}$ of depth $\mathrm{dep}(\mathcal{A}_{\lambda})\leq t^{\varepsilon}(\lambda)$, there exists a negligible function $\mu$, such that for every $\lambda\in\mathbb{N}$, and every pair of solutions $s_{0},s_{1}\in\{0,1\}^{\lambda}$:
$\Pr\Big{[}b\leftarrow\mathcal{A}_{\lambda}(Z):b\leftarrow\{0,1\},Z\leftarrow
\mathsf{Gen}(t(\lambda),s_{b})\Big{]}\leq\frac{1}{2}+\mu(\lambda).$

###### Definition 4 (Time-Lock Puzzle) .

#### A.3.1 The RSW Construction

Rivest et al. [1996] proposed a candidate construction based on the conjectured sequential nature of modular exponentiation. Their scheme uses the fact that repeated squaring modulo an RSA integer is believed to be inherently sequential.

$\mathsf{Gen}(t)$ proceeds as follows:

- 1.
Samples two primes $p,q$ from $[1,w]$, for a parameter $w$, and set $n=pq$.
- 2.
Samples $r\leftarrow\mathbb{Z}_{n}^{*}$, where $\mathbb{Z}_{n}^{*}=\{1,2,\dots,n-1\}$, and computes
$s\leftarrow r^{e}\bmod n,$
where $e=2^{t}$ is a tower of repeated squarings (i.e., $t$ squarings of $r$).
To compute $r^{e}\bmod n$ it first evaluates $\phi(n)=(p-1)(q-1)$ and reduces the exponent $e^{\prime}\leftarrow e\bmod\phi(n)$.
Then $s=r^{e^{\prime}}\bmod n$, which can be computed in only $O(\log(e^{\prime}))$ modular exponentiations.
- 3.
Defines $Z=(n,r)$ to be the puzzle and $s$ its solution. Returns $(Z,s)$.

###### Note 1 .

$\mathsf{Gen}$ can be adapted to accept an additional input $s$ so that it adheres to the schema from Definition [4](https://arxiv.org/html/2507.07341v1#Thmdefinition4).
To do that, one would use a $\mathsf{root}$ function (Definition [8](https://arxiv.org/html/2507.07341v1#Thmdefinition8)) that for $x\in\mathbb{Z}_{n}^{*}$ computes \say$\sqrt{x}$ so that it is possible to compute $r$ from $s$. However, there are some technical details that need to be addressed as $\mathsf{root}$ is well defined only on a subgroup of $\mathbb{Z}_{n}^{*}$ (see Fact [1](https://arxiv.org/html/2507.07341v1#Thmfact1)). We implicitly address these issues in Lemma [2](https://arxiv.org/html/2507.07341v1#Thmlemma2). We chose to use this formulation of the RSW construction for simplicity of exposition.

$\mathsf{Sol}(Z)$ works as follows:

- 1.
Parses $Z=(n,r)$.
- 2.
Returns $r^{2^{t}}$.

Note that $\mathsf{Sol}$ computes $s$ using $t$ repeated squarings, each of which is inexpensive, but the full process requires $\Theta(t)$ sequential steps.

###### Note 1 .

##### Sequentiality.

The security of the RSW puzzle hinges on the assumption that modular exponentiation—specifically, computing $r^{2^{t}}\bmod n$—cannot be substantially accelerated via parallelism. That is any adversary who does not know the factorization of $n$ must essentially compute each squaring step sequentially.

This assumption is supported by decades of experience in cryptographic implementation and is believed to be secure.
Although no formal proof of sequentiality is known, the construction remains a compelling candidate and has served as the basis for more advanced cryptographic primitives, such as time-release encryption [Boneh et al., 2018, Boneh and Naor, 2000].

### A.4 Public key encryption

Diffie and Hellman [1976] introduced the notion of public key encryption (PKE), enabling secure communication between parties without a shared secret. In a PKE scheme, each user generates a pair of keys: a public key $\mathsf{pk}$ that is distributed openly and a private key $\mathsf{sk}$ that is kept secret. Anyone can encrypt a message $m$ using $\mathsf{pk}$ to obtain a ciphertext $c$, but only the holder of $\mathsf{sk}$ can decrypt $c$ to recover $m$. Security relies on the assumed hardness of inverting the encryption without access to the secret key—for example, the difficulty of factoring large integers in the RSA scheme.

### A.5 Secret key encryption

Secret key encryption (also known as symmetric-key encryption) requires both parties to share a common secret key $\mathsf{k}$ in advance. The encryption algorithm uses $\mathsf{k}$ to map a message $m$ to a ciphertext $c$, and the decryption algorithm uses the same key $\mathsf{k}$ to recover $m$ from $c$. Symmetric schemes are typically much more efficient than public key schemes and form the backbone of practical secure communication when a secure channel for key exchange is already available. Notable constructions include block ciphers such as the Advanced Encryption Standard (AES) [Dworkin et al., 2001] and stream ciphers built from pseudorandom generators.

## Appendix B Recoverable-Randomness Sampling

###### Definition 5 .

For $\alpha:\mathbb{N}\rightarrow\mathbb{N}$ we say that a pair of algorithms $(\mathsf{Samp},\mathsf{RecoverRand})$ is an $\alpha$-Recoverable-Randomness Sampling (RRS) scheme if

- •
$\mathsf{Samp}(G)\rightarrow y$, given a language model $G$(^9^99See Remark [1](https://arxiv.org/html/2507.07341v1#Thmremark1) for why $G$ is a language model.) over token set $\mathcal{T}$, $\mathsf{Samp}$ samples an output $z\in\mathcal{T}^{*}$.
- •
$\mathsf{RecoverRand}(G,z,L)\rightarrow R$, for $y\in\mathcal{T}^{*}$, a language model $G$, $\mathsf{RecoverRand}$, and $L\in\mathbb{N}$ is a deterministic algorithm that recovers $L$ bits of the randomness used by $\mathsf{Samp}(G)$ when generating $z$.

The pair $(\mathsf{Samp},\mathsf{RecoverRand})$ satisfies

- •
Recoverability. For every $R\in\{0,1\}^{*}$ and every $L\in\mathbb{N},L\leq\mathsf{len}(R)$ if $\mathsf{Samp}(G,R)$ halts and returns $z_{R}=\mathsf{Samp}(G,R)$ then
$\mathsf{RecoverRand}(G,z_{R},L)=R[0:L],$
In the notation $\mathsf{Samp}(G,R)$, $R$ explicitly specifies the randomness used.
- •
Closeness of Distributions.
Distirbutions over $\mathcal{T}^{*}$ given by $\mathsf{Samp}(G)$ and $G$ are statistically close.
Formally, for every $L\in\mathbb{N}$,
$\frac{1}{2}\sum_{z\in\mathcal{T}^{*},|z|\leq L}\Big{|}\mathbb{P}_{R}[\mathsf{
Samp}(G,R)=z]-\mathbb{P}[G=z]\Big{|}\leq\alpha(L).$
Note that the expression on the left-hand side evaluates a partial statistical distance.

###### Remark 1 .

In Theorems [1](https://arxiv.org/html/2507.07341v1#Thmtheorem1), [2](https://arxiv.org/html/2507.07341v1#Thmtheorem2) and [3](https://arxiv.org/html/2507.07341v1#Thmtheorem3) model $G$ is a generator of innocent prompts.
The theorems hold for *any* high-entropy model.

We assume that $M$ (see for instance Theorem [1](https://arxiv.org/html/2507.07341v1#Thmtheorem1)) is deployed on some distribution $\mathcal{D}$, e.g., a distribution of a user prompts for a chatbot.
We think of $G$ as a model generating prompts from $\mathcal{D}$ or approximation thereof.
It is natural to assume such a $G$ exists.
In the example above, the top chatbots are used by millions of users, so finding a single $G$ whose outputs are indistinguishable from some users’ prompts should be easy.

###### Definition 5 .

###### Remark 1 .

### B.1 RRS Construction

We first simplify the definition of a language model (Definition [1](https://arxiv.org/html/2507.07341v1#Thmdefinition1)) by assuming that the token set is binary, $\mathcal{T}=\{0,1\}$.
We may assume this without loss of generality due to a straightforward reduction that appears in Section 4.1 of Christ et al. [2023]. We will implicitly use this reduction throughout our work as well.
Our construction is given in Algorithms [1](https://arxiv.org/html/2507.07341v1#alg1) and [2](https://arxiv.org/html/2507.07341v1#alg2).

###### Remark 2 .

Our construction was inspired by Zamir [2024], who design a method to undetectably embed a secret message in the output of an LLM that can later be recovered provided access to the secret key.
This is similar to the requirements of the RRS, where the randomness needs to be recoverable from the output.

There are some details in the construction of RRS that we didn’t address in Section [2](https://arxiv.org/html/2507.07341v1#S2).
The first is how do we set the precision parameter $P$.
As we will see shortly in Theorem [6](https://arxiv.org/html/2507.07341v1#Thmtheorem6), $P$ influences the closeness of the distribution generated by $\mathsf{Samp}$ to that of $G$.
$P$ will be set to an exact value when $\mathsf{Samp}$ will be used as a subroutine in the proof of a formal version of Theorem [1](https://arxiv.org/html/2507.07341v1#Thmtheorem1).
It is also informative to point out why the two distributions can be different in the first place.
The main reason is that $\mathsf{Samp}$ samples $z_{i}=1$ with probability $\approx p_{i}$ (and not $=p_{i}$).
It is because we didn’t assume anything about the precision of $p_{i}$ and it might \sayfall in between the grid points defined by $q/k$, where $q\in[k]$.

###### Remark 2 .

### B.2 Proof of correctness

###### Theorem 6 .

Algorithms [1](https://arxiv.org/html/2507.07341v1#alg1) and [2](https://arxiv.org/html/2507.07341v1#alg2) constitute an $O(L\cdot 2^{L}\cdot 2^{-P})$-Recoverable-Randomness Sampling scheme.

###### Proof.

The result follows from a series of facts.

$\mathsf{Samp}$ satisfies the following properties:

- 1.
$q\in[k]$ at all times.
- 2.
for every iteration $i$:
•
for every $z_{0},\dots,z_{i-1}$, before the if statement (step 8 of Algorithm [1](https://arxiv.org/html/2507.07341v1#alg1)) is executed, the distribution of $q$ is uniform in $[k]$.

Observe that if these properties hold, then $z_{i}$’s are sampled from a distribution that is close to $G$.
The only reason the distributions might be different is the aforementioned precision issue.
However, step 4 of Algorithm [1](https://arxiv.org/html/2507.07341v1#alg1) ensures that $|q/k-p_{i}|\leq 2^{-P}$, so the errors accumulate as required, as for every $(z_{0},\dots,z_{L-1})$ the difference between sampling probabilities is upper bounded by $O(L\cdot 2^{-P})$.

The above properties are proven by induction over $i$.
Because $R$ is a random bit-string it implies that $q$ is uniform in $[0,\lceil{p_{i}\cdot k}\rceil]$ conditioned on the event $q/k<p_{i}$.
This implies that if we update $k\leftarrow\lceil{p_{i}\cdot k}\rceil$ then the property that $q$ is uniform in the updated $[k]$ is satisfied.

The properties of the $\mathsf{RecoverRand}$ algorithm are as follows.
For every iteration $i$:

- 1.
$k$ and $d$ at the beginning of the iteration are equal to $k$ and $d$ in the $\mathsf{Samp}$ algorithm at the beginning of iteration $i$.
- 2.
the lengths of $a,b$ and $q$ from $\mathsf{Samp}$ are equal before the if statement (step 8 of Algorithm [2](https://arxiv.org/html/2507.07341v1#alg2)).
- 3.
$a\leq_{\text{lex}}q\leq_{\text{lex}}b$, where $\leq_{\text{lex}}$ is the lexicographic order, before the if statement (step 8 of Algorithm [2](https://arxiv.org/html/2507.07341v1#alg2)).

Similarly, as for $\mathsf{Samp}$ these properties can be proven by induction over $i$.

The first property follows from the observation that $k$ and $d$ are updated depending only on the $z_{i}$ values.
The second property follows from the first property.
The third property is the crucial one and follows from the previous two and a careful analysis of how $a,b$ are updated in the if statement.
More concretely, note that $a+(b-a)\cdot p_{i}/k$ is the \saythreshold randomness at which $\mathsf{Samp}$ would generate $z_{i}=0$ vs $z_{i}=1$.
Indeed, if $R\in[a,a+(b-a)\cdot p_{i}/k)$ then conditioned on $\mathsf{Samp}$ generating $z_{0},\dots,z_{i-1}$, $\mathsf{Samp}$ would set $z_{i}\leftarrow 1$.
If $R\in[a+(b-a)\cdot p_{i}/k),b)$ then it would generate $z_{i}=0$.
∎

###### Theorem 6 .

###### Proof.

## Appendix C Impossibility of Prompt-Detection Filters

### C.1 Moderately-strong filters

We first state a formal version of Theorem [1](https://arxiv.org/html/2507.07341v1#Thmtheorem1).
Next, we will present the construction and prove its correctness in the remaining part of this section.

###### Theorem 7 (Impossibility of prompt-detection filters) .

There exists $\epsilon\in(0,1)$, such that for all security parameters $\lambda\in\mathbb{N}$, every time parameter $\mathsf{poly}(\lambda)\leq t\leq 2^{O(\lambda)}$, every set of harmful prompts $S_{H}\subseteq\{0,1\}^{l_{m}}$, where $l_{m}=\Theta(\log(\lambda)),\Omega(\log(\lambda))=\log(|S_{H}|)\leq l_{m}-
\Omega(\log(\lambda))$, for every language model $M$ running in time $O(t)$ per token, for every prompt generator $G$ satisfying $H(G)\geq\mathsf{poly}(\lambda)$ and running in time $\mathsf{poly}(\lambda)$ per token the following conditions hold.

There exists an adversarial prompt generator $G^{\prime}$ with a running time $\mathsf{poly}(\lambda)$ per token and a language model $M^{\prime}$ with a running time $\mathsf{poly}(\lambda)\cdot O(t)$ per token such that the following conditions hold.

- 1.
($G^{\prime}$ incites harmful behavior in $M^{\prime}$). For every malicious prompt $m\in S_{H}$, the following two distributions are close:
$\left\{M^{\prime}(z)\ \middle|\ z\leftarrow G^{\prime}(m)\right\},\left\{M(m)
\right\}.$
In words, for every harmful prompt from $S_{H}$ the outputs of $M^{\prime}$ and $M$ follow almost the same distribution, in particular, a similar harmful behavior is induced for $M$ and $M^{\prime}$.
- 2.
($M^{\prime}$ and $M$ behave identically on $G$ almost always). With probability $1-\lambda^{-\Omega(1)}$ over $z\leftarrow G$ the distributions $M^{\prime}(z)$ and $M(z)$ are equal.
- 3.
($G$ and $G^{\prime}$ are indistinguishable for filters running in $o(t^{\epsilon})$). Under the assumption that RSW is secure, for every prompt filter running in time $o(t^{\epsilon})$, for every $m\in S_{H}$ the advantage in distinguishing outputs of $G$ and $G^{\prime}(m)$ is $\lambda^{-\Omega(1)}$.
In words, no filter running in time $o(t^{\epsilon})$ can reject(^10^1010If it doesn’t also reject the innocent prompts.) the adversarial prompts from $G^{\prime}$.

###### Theorem 7 (Impossibility of prompt-detection filters) .

#### C.1.1 Construction

In this subsection, we give a more detailed version of the construction provided in Section [2](https://arxiv.org/html/2507.07341v1#S2).
Our construction is given in Algorithms [5](https://arxiv.org/html/2507.07341v1#alg5) and [6](https://arxiv.org/html/2507.07341v1#alg6), which are formal versions of Algorithms [3](https://arxiv.org/html/2507.07341v1#alg3) and [4](https://arxiv.org/html/2507.07341v1#alg4).

Figure: Algorithm 5 $\mathsf{HarmIncite}(G,m,t,\lambda)$ $\triangleright$ $G$: an innocent prompt generator; $m$: a harmful prompt; $t$: time parameter; $\lambda$: security parameter

Figure: Algorithm 6 $\mathsf{MaliciousLLM}(M,z,G,t,\lambda,S_{H})$ $\triangleright$ $M$: an LLM; $z$: input; $G$: weak innocent prompt generator; $t$: time parameter; $\lambda$: security parameter; $S_{H}$: set oh harmful prompts

Next, we provide a few simple facts from number theory that are needed to address the differences between the formal and informal versions of the algorithms.

###### Definition 6 .

Let $n\in N$.
We call $x\in\mathbb{Z}_{n}^{*}$ a quadratic residue modulo $n$ if there exists $r$ such that $x=r^{2}\bmod n$.

The following is a standard fact from number theory. See Goldreich [2006] for details.

###### Fact 1 .

Let $n\in\mathbb{N}$ be a product of two different odd primes, i.e., $n=pq$.
The set of quadratic residues modulo $n$ is a subgroup, denoted by $G_{n}$, of $\mathbb{Z}_{n}^{*}$ of size $|\mathbb{Z}_{n}^{*}|/4$.
Moreover, the mapping $x\mapsto x^{2}$ is a 2-to-1 mapping from $\mathbb{Z}_{n}^{*}$ to $G_{n}$.

###### Definition 7 .

For $n\in\mathbb{N}$ we define a bijection $\mathsf{ind}:\mathbb{Z}_{n}^{*}\rightarrow G_{n}\times\{0,1\}^{2}$ as $\mathsf{ind}(x):=(g,i)$, where $g\in G_{n}$ is such that $x^{2}=g^{2}$ and $i$ denotes which (in the increasing order) of the $4$ elements $r\in\mathbb{Z}_{n}^{*}$ satisfying $r^{2}=x^{2}$, $x$ is.

###### Remark 3 .

Note that in Algorithm [5](https://arxiv.org/html/2507.07341v1#alg5) (in contrast to Algorithm [3](https://arxiv.org/html/2507.07341v1#alg3)), to compute the puzzle $s$, an intermediate bijection $\mathsf{ind}$ (Definition [7](https://arxiv.org/html/2507.07341v1#Thmdefinition7)) is used.
The reason is the following.
The mapping $x\mapsto x^{2}$ is a $4$-to-$1$ function in $\mathbb{Z}_{n}^{*}$.
To ensure that the mapping between $r\in\mathbb{Z}_{n}$ and a puzzle $s$ is $1$-to-$1$, we use the function $\mathsf{ind}$ to \sayremember which of the $4$ possible $r$’s was used.

Next, we give a formal definition of $\mathsf{Enc}$ used in Algorithm [3](https://arxiv.org/html/2507.07341v1#alg3).

###### Definition 6 .

###### Fact 1 .

###### Definition 7 .

###### Remark 3 .

##### Hardcore functions.

We will apply the technique of hardcore bits (Goldreich and Levin [1989]) and its extension to hardcore functions.
Recall that a hardcore bit is a function $B$ that outputs a single bit $B(x)$ which is hard to predict given $f(x)$.
A hardcore function $Q$ for a one-way function $f$ is a function which outputs possibly more than one bit such that, given $f(x)$, and the description of $Q$, it is hard to distinguish $Q(x)$ from a random string even when $f(x)$ is known.
Goldreich and Levin introduced the first hardcore predicates and functions for general one-way functions (OWFs), showing that a random linear function is hardcore and the linear function defined by a random Toeplitz matrix is a hardcore function.

The first step of $G^{\prime}$ is to sample $p,q$ at random from a set $[1,k]$ (see Algorithm [5](https://arxiv.org/html/2507.07341v1#alg5)), where $k=2^{O(\lambda)}$.
Next, we let $h$ be a pairwise independent hash function that $h$ hashes $n$ to a range of size $\Theta(\epsilon^{2}\cdot((k/\log(k))^{2})$.
The $\epsilon$ is set to $\lambda^{-\gamma}$ for some $\gamma>0$ to be fixed in the proof (Section [C.1.2](https://arxiv.org/html/2507.07341v1#A3.SS1.SSS2)).
For a message $m\in\{0,1\}^{l_{m}}$ (as in the statement of Theorem [7](https://arxiv.org/html/2507.07341v1#Thmtheorem7)) and using the notation from Algorithm [5](https://arxiv.org/html/2507.07341v1#alg5) we define $R$ to be

$$ $R\leftarrow h\ \|\ h(n)\ \|\ r\ \|\ v\ \|\ Q(s,v)\oplus m,$ (1) $$

where $v\leftarrow\{0,1\}^{O(\lambda)}$ and $Q(s,v)$ is a hardcore function with $l_{m}=\Theta(\log(\lambda))$ output bits.

###### Note 2 .

In Section [2](https://arxiv.org/html/2507.07341v1#S2) we simplified the above construction and claimed $R=(x,\mathsf{Enc}(g(x),m))$.
Informally speaking, in the formal version we set

$$ $x=h\ \|\ h(n)\ \|\ r,\ \mathsf{Enc}(g(x),m)=v\ \|\ Q(s,v)\oplus m,$ $$

where $v\leftarrow\{0,1\}^{O(\lambda)}$.

Next, we give some remarks about Algorithm [6](https://arxiv.org/html/2507.07341v1#alg6).
As we mentioned in the overview it is possible to efficiently enumerate through all the preimages of $h(n)$ under $h$.
Note that according to ([1](https://arxiv.org/html/2507.07341v1#A3.E1)) when $M^{\prime}$ parses $R$ it does it as follows:

$$ $R=h\ \|\ u\ \|\ r\ \|\ v\ \|\ c.$ $$

For instance, an additional part $v$, which was not present in the simplified version of Algorithm [2](https://arxiv.org/html/2507.07341v1#alg2) appears here.

Next, the model $M^{\prime}$ squares the starting point $t$ times and tries to decrypt $c$ with the current candidate for $n$, i.e., $\hat{n}$.
By decrypt we mean it evaluates $\mathsf{Dec}(\hat{s},v,c)$ defined as

$$ $\hat{m}\leftarrow c\oplus Q(\hat{s},v).$ $$

The check $\hat{m}\neq\bot$ becomes instead $m\in S_{H}$.
That is we assume $M^{\prime}$ knows the set of harmful prompts $S_{H}$ and checks if the decryption belongs to that set and if yes it executes $M$ on it (which will lead to a harmful output).
If, none of the the decryptions \saysucceed then it returns $M(z)$.

###### Remark 4 .

We proved Theorem [7](https://arxiv.org/html/2507.07341v1#Thmtheorem7) using the RWS construction of time-lock puzzles.
However, there are generic constructions of time-lock puzzles.
The first one [Bitansky et al., 2016b] was based on obfuscation and randomized encodings.
A culmination of a series of follow-up works [Agrawal et al., 2025, Bitansky and Garg, 2025, Abram et al., 2025] managed to construct time-lock puzzles based on a version of the Learning With Errors [Regev, 2009] (LWE) assumption.
One advantage of basing TLPs on LWE is that the other constructions are broken by quantum algorithms, while LWE is a candidate for post-quantum secure cryptography.

It would be interesting to extend Theorem [7](https://arxiv.org/html/2507.07341v1#Thmtheorem7), so that it can be based on any time-lock puzzle.
The one crucial property that we use is the pseudorandomness of the puzzle, and this seems like the key issue in generalizing the result.
Recall that we had to be careful in designing Algorithm [5](https://arxiv.org/html/2507.07341v1#alg5) so that the distribution of $s$ is uniform.
It seems that the main property we need is that the distribution on hard instances is uniform over a set $S$ whose approximate size is known to us.
We leave the question of whether the generalization is possible for future work.

###### Note 2 .

###### Remark 4 .

#### C.1.2 Proof of Theorem 7

Firstly, we prove two technical lemmas.

###### Lemma 1 .

$h\ \|\ h(n)$ is $O(\lambda^{-2\gamma})$-close to uniformly random.

###### Proof.

It follows from the Leftover Hash Lemma (Vadhan [2012], Theorem 6.18), which guarantees that $h\|h(n)$ is $\epsilon^{2}$ close to uniform.
For our setting of parameters it gives us that $h\|h(n)$ is $O(\lambda^{-2\gamma})$-close to uniform.
∎

###### Definition 8 .

For $n\in\mathbb{N}$ let $\mathsf{root}:G_{n}\rightarrow G_{n}$ be a function that on input $x\in G_{n}$ returns $r$ such that $r^{2}=x$ (by Fact [1](https://arxiv.org/html/2507.07341v1#Thmfact1) only one exists).

###### Lemma 2 .

There exists an $\Theta(\log(\lambda))$-bit hardcore function $Q(s,v)$ (see Goldreich [2006] for details) for a function $f:\mathbb{Z}_{n}\rightarrow\mathbb{Z}_{n}$ defined as follows.
Let $s\in\mathbb{Z}_{n}$ and consider cases:

- •
if $s\in\mathbb{Z}_{n}\setminus\mathbb{Z}_{n}^{*}$ then $f(s)=s$.
- •
if $s\in\mathbb{Z}_{n}^{*}$ then
$f(s):=\mathsf{ind}^{-1}(\mathsf{root}^{t}(\mathsf{ind}(s)_{1}),\mathsf{ind}(s)
_{2}).$

More formally, for every distinguisher running in time $o(t^{\epsilon})$, the advantage for distinguishing

$$ $r\ \|\ v\ \|\ Q(s,v)\text{ and }r\ \|\ v\ \|\ U,$ $$

where $s\leftarrow\mathbb{Z}_{n}$, $U\leftarrow\{0,1\}^{l_{m}},v\leftarrow\{0,1\}^{O(\lambda)}$ and $r=f(s)$, is at most $\lambda^{-\Omega(1)}$.

Moreover, $f$ is a bijection.

###### Proof.

The proof is a direct adaptation of the proof of Theorem 2.5.6 in Goldreich [2006].
The main difference is that security in our case holds only against distinguishes running in time $o(t^{\epsilon})$ and not all polynomial-time adversaries.

The fact that $f$ is a bijection follows from Fact [1](https://arxiv.org/html/2507.07341v1#Thmfact1) and the fact that $\mathsf{ind}$ (Definition [7](https://arxiv.org/html/2507.07341v1#Thmdefinition7)) is a bijection.
∎

Note that the distribution considered in Lemma [2](https://arxiv.org/html/2507.07341v1#Thmlemma2) is, a priori, different from the distribution of outputs of Algorithm [5](https://arxiv.org/html/2507.07341v1#alg5), because in the actual algorithm we first sample $r$, not $s$.
The following lemma shows that the distributions are in fact equal.

###### Lemma 3 .

The following two distributions are equal.
The first distributions is defined as $r\ \|\ v\ \|\ Q(s,v)$,
where $s\leftarrow\mathbb{Z}_{n}$, $U\leftarrow\{0,1\}^{l_{m}},v\leftarrow\{0,1\}^{O(\lambda)}$ and $r=f(s)$ (where $f$ is defined in Lemma [2](https://arxiv.org/html/2507.07341v1#Thmlemma2)).
The second distribution is defined as $r\ \|\ v\ \|\ Q(s,v)$,
where $r\leftarrow\mathbb{Z}_{n}$, $U\leftarrow\{0,1\}^{l_{m}},v\leftarrow\{0,1\}^{O(\lambda)}$ and $s=f^{-1}(r)$.

###### Proof.

The equality follows from Lemma [2](https://arxiv.org/html/2507.07341v1#Thmlemma2), which gurantees that $f$ is a bijection.
∎

Next, we are ready to prove Theorem [7](https://arxiv.org/html/2507.07341v1#Thmtheorem7).

###### Proof.

There are three conditions we need to verify.

- •
Condition 1. From the assumption that $H(G)\geq\mathsf{poly}(\lambda)$ we know that the length of randomness needed to sample from $G$ is at least the length needed to describe $h\ \|\ h(n)\ \|\ r\ \|\ v\ \|\ c$ with all but negligible probability.
To do that it is enough to set the precision parameter $P=\mathsf{poly}(\lambda)$ as guaranteed by Theorem [6](https://arxiv.org/html/2507.07341v1#Thmtheorem6).
Conditioned on the fact that $\mathsf{RecoverRand}$ recovers enough bits, $M^{\prime}$ will recover $m$ with high probability and return $M(m)$.
- •
Condition 2. We bound the probability that when $M^{\prime}$ (defined via Algorithm [6](https://arxiv.org/html/2507.07341v1#alg6)) receives a prompt generated by $G$ it returns in Line [16](https://arxiv.org/html/2507.07341v1#alg6.l16), i.e., it returns a harmful output.
Note that $c$ is uniformly random as $G$ uses honest randomness $v$ to produce its outputs.
Similarly, $s$ is also uniformly random.
This implies that, for every $\hat{n}\in h^{-1}(u)$, the probability that $m\in S_{H}$ is equal to $|S_{H}|/2^{l_{m}}$.
From the setting $\epsilon=\lambda^{-\gamma}$ we know that the number of preimages under $h$ is in $O(\lambda^{2\gamma})$(^11^1111Thus, $M^{\prime}$ can iterate over all of them in time $O(t)$.)
and so, by the union bound, the probability that at least one of $m$’s belongs to $S_{H}$ is at most $O(\lambda^{2\gamma}\cdot|S_{H}|/2^{l_{m}})$.
From the assumption that $\log(|S_{H}|)\leq l_{m}-\Omega(\log(\lambda))$ it follows that $\gamma$ can be set so that the probability that $M^{\prime}$ returns in Line [16](https://arxiv.org/html/2507.07341v1#alg6.l16) is at most $\lambda^{-\Omega(1)}$.
By construction, if $M^{\prime}$ returns in the Line [19](https://arxiv.org/html/2507.07341v1#alg6.l19), it returns $M(z)$, thus returning from the same distribution.
- •
Condition 3. Implied by Lemmas [1](https://arxiv.org/html/2507.07341v1#Thmlemma1), [2](https://arxiv.org/html/2507.07341v1#Thmlemma2), and [3](https://arxiv.org/html/2507.07341v1#Thmlemma3) and the fact that the probability that $r\in\mathbb{Z}_{n}^{*}$ (note that it is sampled from $\mathbb{Z}_{n}$) is negligible in $\lambda$.

∎

###### Lemma 1 .

###### Proof.

###### Definition 8 .

###### Lemma 2 .

###### Proof.

###### Lemma 3 .

###### Proof.

###### Proof.

### C.2 Shared secret key

The following is a formal version of Theorem [2](https://arxiv.org/html/2507.07341v1#Thmtheorem2).

###### Theorem 8 (Impossibility of prompt-detection filters via secret keys) .

There exists a polynomial $p$ such that for all security parameters $\lambda\in\mathbb{N}$, every set of harmful prompts $S_{H}\subseteq\{0,1\}^{l_{m}}$, where $l_{m}=\Theta(p(\lambda)),\Omega(p(\lambda))=\log(|S_{H}|)\leq l_{m}-\Omega(p(
\lambda))$, for every language model $M$, for every prompt generator $G$ satisfying $H(G)\geq\mathsf{poly}(\lambda)$ and running in time $\mathsf{poly}(\lambda)$ per token the following conditions hold.

There exists an adversarial prompt generator $G^{\prime}$ with a running time $\mathsf{poly}(\lambda)$ per token and a language model $M^{\prime}$ with a running time $\mathsf{poly}(\lambda)+O(T_{M})$ per token, where $T_{M}$ is the running time of $M$ per token, such that if $M^{\prime}$ and $G^{\prime}$ share an $\mathsf{poly}(\lambda)$-bit secret key then the following conditions hold.

- 1.
($G^{\prime}$ incites harmful behavior in $M^{\prime}$). For every malicious prompt $m\in S_{H}$, the following two distributions are close:
$\left\{M^{\prime}(z)\ \middle|\ z\leftarrow G^{\prime}(m)\right\},\left\{M(m)
\right\}.$
In words, for every harmful prompt from $S_{H}$ the outputs of $M^{\prime}$ and $M$ follow almost the same distribution, in particular, a similar harmful behavior is induced for $M$ and $M^{\prime}$.
- 2.
($M^{\prime}$ and $M$ behave identically on $G$ almost always). With all but negligible in $\lambda$ probability over $z\leftarrow G$ the distributions $M^{\prime}(z)$ and $M(z)$ are equal.
- 3.
($G$ and $G^{\prime}$ are indistinguishable for filters running in polynomial-time). Under the assumption that One-Way Functions exist, for every prompt filter running in polynomial-time, for every $m\in S_{H}$ the advantage of the filter in distinguishing outputs of $G$ and $G^{\prime}(m)$ is negligible in $\lambda$.
In words, no filter running in polynomial-time can reject(^12^1212If it doesn’t also reject the innocent prompts.) the adversarial prompts from $G^{\prime}$.

###### Theorem 8 (Impossibility of prompt-detection filters via secret keys) .

#### C.2.1 Construction

As we discussed in Section [2](https://arxiv.org/html/2507.07341v1#S2), instead of using time-locks, we use symmetric key (shared secret key) encryption (it is known that one-way functions (OWFs) imply symmetric key encryption).
Namely, for $m\in S_{H}$ we set $R:=\mathsf{Enc}(\mathsf{sk},m)$, where $\mathsf{Enc}$ is the symmetric key encryption scheme, and $\mathsf{sk}$ is the shared secret key.
Next, $G^{\prime}$ generates $z\leftarrow\mathsf{Samp}(G,R)$ as before.
$M^{\prime}$ decrypts the randomness $R$ to get $\hat{m}$ and checks if $\hat{m}$ belongs to the set $S_{H}$, and if yes returns $M(\hat{m})$.

The proof of correctness is a simplified version of the proof of Theorem [7](https://arxiv.org/html/2507.07341v1#Thmtheorem7).

### C.3 Shared public key

The following is a formal version of Theorem [3](https://arxiv.org/html/2507.07341v1#Thmtheorem3).

###### Theorem 9 (Impossibility of prompt-detection filters via secret keys) .

There exists a polynomial $p$ such that for all security parameters $\lambda\in\mathbb{N}$, every set of harmful prompts $S_{H}\subseteq\{0,1\}^{l_{m}}$, where $l_{m}=\Theta(p(\lambda)),\Omega(p(\lambda))=\log(|S_{H}|)\leq l_{m}-\Omega(p(
\lambda))$, for every language model $M$, for every prompt generator $G$ satisfying $H(G)\geq\mathsf{poly}(\lambda)$ and running in time $\mathsf{poly}(\lambda)$ per token the following conditions hold.

There exists a language model $M^{\prime}$ with an associated public key and with a running time $\mathsf{poly}(\lambda)+O(T_{M})$ per token, where $T_{M}$ is the running time of $M$ per token, and an adversarial prompt generator $G^{\prime}$ (that depends on the public key) with a running time $\mathsf{poly}(\lambda)$ per token and such that the following conditions hold.

- 1.
($G^{\prime}$ incites harmful behavior in $M^{\prime}$). For every malicious prompt $m\in S_{H}$, the following two distributions are close:
$\left\{M^{\prime}(z)\ \middle|\ z\leftarrow G^{\prime}(m)\right\},\left\{M(m)
\right\}.$
In words, for every harmful prompt from $S_{H}$ the outputs of $M^{\prime}$ and $M$ follow almost the same distribution, in particular, a similar harmful behavior is induced for $M$ and $M^{\prime}$.
- 2.
($M^{\prime}$ and $M$ behave identically on $G$ almost always). With all but negligible in $\lambda$ probability over $z\leftarrow G$ the distributions $M^{\prime}(z)$ and $M(z)$ are equal.
- 3.
($G$ and $G^{\prime}$ are indistinguishable for filters running in polynomial-time). Under the assumption that public key cryptography exists, for every prompt filter running in polynomial-time, for every $m\in S_{H}$ the advantage of the filter in distinguishing outputs of $G$ and $G^{\prime}(m)$ is negligible in $\lambda$.
In words, no filter running in polynomial-time can reject(^13^1313If it doesn’t also reject the innocent prompts.) the adversarial prompts from $G^{\prime}$.

###### Theorem 9 (Impossibility of prompt-detection filters via secret keys) .

#### C.3.1 Construction

Instead of using time-locks (as in Theorem [7](https://arxiv.org/html/2507.07341v1#Thmtheorem7)) we use public key encryption in our construction.
Namely, for $m\in S_{H}$ we set $R:=\mathsf{Enc}(\mathsf{pk},m)$, where $\mathsf{Enc}$ is the public key encryption scheme, and $\mathsf{pk}$ is the public key associated with $M$.
Next, $G^{\prime}$ generates $z\leftarrow\mathsf{Samp}(G,R)$ as before.
$M^{\prime}$ decrypts the randomness $R$ to get $\hat{m}$ and checks if $\hat{m}$ belongs to the set $S_{H}$, and if yes returns $M(\hat{m})$.

The proof of correctness of this construction is a simplified version of the proof of Theorem [7](https://arxiv.org/html/2507.07341v1#Thmtheorem7).

## Appendix D Impossibility of Output-Detection Filters

##### Preliminaries.

A harmfulness oracle is a function $\mathcal{H}:\mathcal{T}^{*}\rightarrow[0,\infty)$.
For an output of a language model $z\in\mathcal{T}^{*}$ we interpret $\mathcal{H}(z)$ as the harmfulness of $z$, where $\mathcal{H}(z)=0$ means that $z$ is benign and a high-value denotes high harmfulness.(^14^1414It is important not to confuse the notation for harmfulness oracle $\mathcal{H}$ with the notation for entropy $H$.)

The following is a formal version of Theorem [4](https://arxiv.org/html/2507.07341v1#Thmtheorem4).

###### Theorem 10 (Impossibility of output-detection filters) .

There exists $\epsilon\in(0,1)$, polynomial $p$, such that for all security parameters $\lambda\in\mathbb{N}$,
every set of harmful prompts $S_{H}\subseteq\{0,1\}^{l_{m}}$, where $l_{m}=\Theta(p(\lambda)),\Omega(p(\lambda))=\log(|S_{H}|)\leq l_{m}-\Omega(p(
\lambda))$,
for every language model $M$ running in time $\mathsf{poly}(\lambda)$ per token and satisfying $H(M)\geq\Omega(p(\lambda))$, and every harmfulness oracle $\mathcal{H}$ the following conditions hold.

There exists an adversarial language model $M^{\prime}$ with a running time $\mathsf{poly}(\lambda)$ per token and a harmfulness oracle $\mathcal{H}^{\prime}$ such that the following conditions hold.

- 1.
($M^{\prime}$ outputs are harmful as judged by $\mathcal{H}^{\prime}$). For every malicious prompt $m\in S_{H}$, with all but negligible in $\lambda$ probability over $z\leftarrow M^{\prime}(m)$,(^15^1515Note that $M^{\prime}(m)$ abuses the notation slightly. $M^{\prime}$ is a malicious model that can, for every $m$, generate a harmful output with $m$ \sayhidden in it. However, $m$ *is not* an input/prompt to $M^{\prime}$ in the usual sense.) it holds that
$\mathcal{H}^{\prime}(z)=\Omega\Big{(}\mathbb{E}_{z\leftarrow M(m)}[\mathcal{H}
(z)]\Big{)}.$
In words, for every prompt from $S_{H}$ the outputs of $M^{\prime}$ are almost always as harmful (when judged by $\mathcal{H}^{\prime}$) as if $M$ run on $m$ (when judged by $\mathcal{H}$).
- 2.
($\mathcal{H}^{\prime}$ and $\mathcal{H}$ are equal on $M()$ almost always). With all but negligible probability in $\lambda$ over $z\leftarrow M()$(^16^1616We emphasize that $M()$ is *not* a typo. $M()$ can be thought of as $G$ from Theorem [10](https://arxiv.org/html/2507.07341v1#Thmtheorem10) that also doesn’t receive any input.)
$\mathcal{H}^{\prime}(z)=\mathcal{H}(z).$
In words, the harmfulness of outputs of $M$ is (almost always) equal as judged by $\mathcal{H}$ and $\mathcal{H}^{\prime}$.
- 3.
($M^{\prime}$ and $M$ are indistinguishable for filters running in $2^{\epsilon\cdot\lambda}$). Under the assumption that RSW is secure, for every output filter running in time $2^{\epsilon\cdot\lambda}$, for every $m\in S_{H}$ the advantage in distinguishing outputs of $M()$ and $M^{\prime}(m)$ is negligible in $\lambda$.
In words, no filter running in time $2^{\epsilon\cdot\lambda}$ can reject(^17^1717If it doesn’t also reject the innocent prompts.) the harmful outputs from $M^{\prime}$.

###### Theorem 10 (Impossibility of output-detection filters) .

### D.1 Construction

As we explained in Section [2](https://arxiv.org/html/2507.07341v1#S2) the construction is a \saylift from the construction given in the proof of Theorem [1](https://arxiv.org/html/2507.07341v1#Thmtheorem1) (Theorem [7](https://arxiv.org/html/2507.07341v1#Thmtheorem7) in the formal version).
More concretely we define

$$ $\displaystyle M^{\prime}:=\mathsf{HarmIncite}(M,m,t=2^{\lambda},\mathsf{poly}( \lambda))$ $\displaystyle\mathcal{H}^{\prime}:=\mathsf{MaliciousLLM}(\mathcal{H},z,M,t=2^{ \lambda},\mathsf{poly}(\lambda),S_{H}).$ $$

We note that $\mathcal{H^{\prime}}$ is well defined because the only calls to $\mathcal{H}$ in $\mathsf{MaliciousLLM}$ (Algorithm [6](https://arxiv.org/html/2507.07341v1#alg6)) are query calls.
By direct, we mean that, for example, there is no assumption that $\mathcal{H}$ needs to be a language model.

###### Remark 5 .

We note that we could have set $t$ to a different (smaller) value and then the theorem would still hold with the security against filters running in time $t^{\epsilon}$.
This change would make sure that the \sayrunning time of $\mathcal{H}^{\prime}$ is smaller than $2^{\lambda}$.
It can be beneficial if one tries to make sure that $\mathcal{H}^{\prime}$ is efficient.
Thus our construction can be easily changed to have a trade-off between the overhead \sayrunning-time (over $\mathcal{H}$) of $\mathcal{H}^{\prime}$ and the security guarantee.

###### Remark 5 .

### D.2 Proof

The proof is a direct adaptation of the proof from Section [C.1.2](https://arxiv.org/html/2507.07341v1#A3.SS1.SSS2).
The main difference is in the setting of parameters for the time bounds.
In Theorem [7](https://arxiv.org/html/2507.07341v1#Thmtheorem7) we needed $M^{\prime}$ to be able to solve the time-lock puzzle (evaluate $r^{2^{t}}$) and so the indistinguishability could hold only against filters running in time $t^{\epsilon}$.
However, for the output filter result, the quality oracle could \sayrun in exponential time, and so the time-lock can be created with parameter $2^{\lambda}$.(^18^1818It cannot be \saymuch bigger because the running time of $M^{\prime}$ is $\mathsf{poly}(\lambda)$ and so $M^{\prime}$ cannot create a harder puzzle (at least with the RSW construction).)

## Appendix E Mitigation and Connections to Watermarking

### E.1 Watermarks

First, we define watermarking schemes, for which we adopt definitions from Christ et al. [2023].
The only difference is that we require a watermark to still be detected even if the output of the watermarking scheme was changed by a transformation from a class $E$.

###### Definition 9 (Class of Transformations) .

A *class of transformations* $E$ is an equivalence relation over $\mathcal{T}^{*}$.
We interpret it as follows.
For $z\in\mathcal{T}^{*}$ it can be transformed into any element in the equivalence class of $z$.
We denote by $E(z)$ the equivalence class of $z$.

###### Definition 10 (Watermarking scheme) .

A watermarking scheme for a model $M$ over $\mathcal{T}$ is a tuple of algorithms $\mathcal{W}=(\mathsf{Setup},\mathsf{Wat},\mathsf{Detect})$ where:

- •
$\mathsf{Setup}(1^{\lambda})\to\mathsf{sk}$ outputs a secret key, with respect to a security parameter $\lambda$.
- •
$\mathsf{Wat}_{\mathsf{sk}}(\mathsf{prompt})$ is a randomized algorithm that takes as input a prompt $\mathsf{prompt}$ and generates a response in $\mathcal{T}^{*}$.
- •
$\mathsf{Detect}_{\mathsf{sk}}(z)\to\{\mathsf{true},\mathsf{false}\}$ is an algorithm that takes as input a sequence $z\in\mathcal{T}^{\star}$ and outputs true or false.

###### Definition 11 (Soundness) .

A watermarking scheme $\mathcal{W}$ is *sound* if for every security parameter $\lambda$ and token sequence $x\in\mathcal{T}^{\star}$ of length $|z|\leq\mathsf{poly}(\lambda)$,

$$ $\Pr_{\mathsf{sk}\leftarrow\mathsf{Setup}(1^{\lambda})}[\mathsf{Detect}_{ \mathsf{sk}}(z)=\mathsf{true}]\leq\mathsf{negl}(\lambda).$ $$

###### Definition 12 ( $b(L)$ -Completeness) .

An algorithm $\mathcal{W}$ is a $b(L)$-*complete* watermarking scheme robust against a class of transformations $E$ if for every security parameter $\lambda$ and prompt $\mathsf{prompt}$ of length $|\mathsf{prompt}|\leq\mathsf{poly}(\lambda)$,

$$ $\displaystyle\Pr_{\mathsf{sk}\leftarrow\mathsf{Setup}(1^{\lambda}),\,z \leftarrow\mathsf{Wat}_{\mathsf{sk}}(\mathsf{prompt})}$ $\displaystyle[\exists_{z^{\prime}\in E(z)}\ \mathsf{Detect}_{\mathsf{sk}}(z^{ \prime})=\mathsf{false}\text{ and }$ $\displaystyle H_{e}(M,\mathsf{prompt},z)\geq b(|z|)]\leq\mathsf{negl}(\lambda).$ $$

###### Definition 13 (Undetectability) .

A watermarking scheme $\mathcal{W}=(\mathsf{Setup},\mathsf{Wat},\mathsf{Detect})$ is *undetectable* if for every security parameter $\lambda$ and all polynomial-time distinguishers $D$,

$$ $\left|\Pr[D^{M,M}(1^{\lambda})=1]-\Pr_{\mathsf{sk}\leftarrow\mathsf{Setup}(1^{ \lambda})}[D^{M,\mathsf{Wat}_{\mathsf{sk}}}(1^{\lambda})=1]\right|\leq\mathsf{ negl}(\lambda),$ $$

where the notation $D^{O_{1},O_{2}}$ means that $D$ is allowed to adaptively query both $O_{1}$ and $O_{2}$ with arbitrary prompts.

###### Definition 9 (Class of Transformations) .

###### Definition 10 (Watermarking scheme) .

###### Definition 11 (Soundness) .

###### Definition 12 ( b ⁢ ( L ) 𝑏 𝐿 b(L) italic_b ( italic_L ) -Completeness) .

###### Definition 13 (Undetectability) .

### E.2 Our result

###### Definition 14 (Prompt-mitigation Filter) .

A *prompt-mitigation filter* for a class $E$ is an algorithm that takes as input $z\in\mathcal{T}^{*}$ and replies with en element of $E(z)\cup\{\bot\}$, which we interpret as it either produced an element in the equivalence class of $z$ or rejects.

The following is a formal version of Theorem [5](https://arxiv.org/html/2507.07341v1#Thmtheorem5).

###### Theorem 11 (Impossibility of prompt-mitigation filters) .

If there exists a watermarking scheme robust against a class of transformations $E$ then
for all security parameters $\lambda\in\mathbb{N}$, for every language model $M$, for every prompt generator $G$ satisfying $H(G)\geq\mathsf{poly}(\lambda)$ and running in time $\mathsf{poly}(\lambda)$ per token the following conditions hold.

There exists a language model $M^{\prime}$ with a running time $\mathsf{poly}(\lambda)+O(T_{M})$ per token, where $T_{M}$ is the running time of $M$ per token, and an adversarial prompt generator $G^{\prime}$ with a running time $\mathsf{poly}(\lambda)$ per token such that if $G^{\prime}$ and $M^{\prime}$ share a secret key then the following conditions hold.

- 1.
($G^{\prime}$ incites harmful behavior in $M^{\prime}$ even in the presence of prompt-mitigation filters).
For every prompt-mitigation filter $F$ running in polynomial-time with all but negligible in $\lambda$ probability over $z\leftarrow G^{\prime}$ it holds that
$F(z)=\bot\text{ or }M^{\prime}(z)\text{ is harmful}.$
- 2.
($M^{\prime}$ and $M$ behave identically on $G$ almost always). With all but negligible in $\lambda$ probability over $z\leftarrow G$ the distributions $M^{\prime}(z)$ and $M(z)$ are equal.
- 3.
($G$ and $G^{\prime}$ are indistinguishable for filters running in polynomial-time).
For every algorithm running in polynomial-time the advantage in distinguishing outputs of $G$ and $G^{\prime}$ is negligible in $\lambda$.

###### Note 3 .

Observe that conditions 1 and 3 from Theorem [11](https://arxiv.org/html/2507.07341v1#Thmtheorem11) imply that if a polynomial-time prompt-mitigation filter $F$ does not reject outputs of $G$ then the outputs of $G$ even when passed through the mitigation of $F$ will still incite harmful behavior in $M^{\prime}$.

###### Definition 14 (Prompt-mitigation Filter) .

###### Theorem 11 (Impossibility of prompt-mitigation filters) .

###### Note 3 .

### E.3 Construction

Let $\mathcal{W}=(\mathsf{Setup},\mathsf{Wat},\mathsf{Detect})$ be a watermarking scheme robust against a class of transformations $E$.
Let $G$ be a prompt generator satisfying $H(G)\geq\mathsf{poly}(\lambda)$.
Firstly, we let $G^{\prime}$ and $M$ share a $\mathsf{sk}$ generated by $\mathsf{Setup}(1^{\lambda})$.
We define $G^{\prime}:=\mathsf{Wat}_{\mathsf{sk}}()$.(^19^1919We run $\mathsf{Wat}$ on an empty prompt.)
Note that $\mathsf{Wat}$ implicitly depends on $G$.
For a language model $M$ we define $M^{\prime}$ that on input $z$ works as follows:

- 1.
If $\mathsf{Detect}_{\mathsf{sk}}(z)=\mathsf{true}$ then return a harmful output.
- 2.
Return $M(z)$ otherwise.

### E.4 Proof

The proof requires a careful comparison of requirements of Theorem [11](https://arxiv.org/html/2507.07341v1#Thmtheorem11) and properties of watermarking schemes robust against classes of transformations.
The result follows from the following.

- •
Condition 1 follows from completeness of $\mathcal{W}$.
- •
Condition 2 follows from soundness of $\mathcal{W}$.
- •
Condition 3 follows from undetectability of $\mathcal{W}$.

## Peer Reviews

confidence: 1
contribution: 3
initial_rating: 6
presentation: 2
questions: Please answer the above comments in the weaknesses section.
soundness: 3
strengths: A definitely novel investigation on the limitation of the (light-weighted) filter methods, based on the cryptographic argument.

It assesses the worst-case limitation of the filter based methods.
summary: The authors study the problem of using external filters (either on prompts or on outputs) to prevent harmful behaviour from LLMs. They show, under standard cryptographic hardness assumptions, that there exist models for which no efficient prompt‐filter can reliably distinguish safe from adversarial prompts (i.e., adversarial prompts that trigger harmful behaviour are computationally indistinguishable from benign prompts). They also show that, in a natural setting, output filtering is computationally intractable: even if you observe the output, deciding whether it’s harmful or not cannot in general be efficiently done for certain models. They further explore relaxed mitigation strategies (weaker filter models) and demonstrate additional computational barriers.
weaknesses: Practical relevance of Theorems 1 and 2 is limited, due to the assumption of the efficiency of the filter. It is not clear how much the filter needs to be powerful not to be considered as an “efficient filter.”

The claim of Theorem 2 is too informal to draw a meaningful message from it. Does the statement outputs of M′ are judged as harmful by H′” mean the outputs of M’ given arbitrary inputs are judged as harmful? Does the statement “​​no efficient output filter can distinguish the outputs generated by M′ from outputs of M.” mean one can not distinguish between the output of these two models for any input prompt?

The authors claim “The filter should be more efficient than the LLM; otherwise, we can ignore the given LLM and focus solely on training a new one from scratch, using it in place of the filter.” However, this may not always be acceptable. Because the safety guarantee is very important, it is natural to have more powerful filter models that are specialized for safety filtering at the cost of usefulness (such as guardian models).

---

confidence: 2
contribution: 3
initial_rating: 6
presentation: 2
questions: N/A
soundness: 3
strengths: The analytical perspective of the paper is interesting.
summary: This paper examines the computational limits of achieving AI alignment through filtering techniques. The authors show that, under standard cryptographic assumptions, both input filtering (blocking harmful prompts) and output filtering (blocking harmful responses) face fundamental computational barriers. They construct examples of language models where no efficient filter can distinguish adversarial prompts or reliably detect harmful outputs. Even when filters are allowed to modify prompts or outputs instead of rejecting them outright, these more flexible strategies remain computationally constrained. Overall, the paper demonstrates that filter-based alignment methods are theoretically inadequate, emphasizing the need for a deeper understanding of the computational hardness behind AI alignment and for designing more robust regulatory and technical safeguards.
weaknesses: 1. The results rely on cryptographic hardness assumptions that, while widely accepted, remain unproven. If these assumptions were invalidated, the impossibility results would no longer hold.
2. The theoretical LLMs used in proofs involve contrived adversarial mechanism that may not fully reflect real-world systems. The gap between worst-case theoretical constructs and practical AI behavior limits its applicability.

---

confidence: 1
contribution: 3
initial_rating: 6
presentation: 1
questions: NA
soundness: 3
strengths: The paper addresses a highly relevant and fundamental problem in AI safety and alignment, offering strong theoretical grounding for existing empirical challenges like "jailbreaking."

Novelty and Significance: The use of computational complexity theory and cryptographic hardness assumptions (Time-Lock Puzzles, OWFs) to model and prove the limits of alignment is a highly original and significant contribution. This elevates the discussion on alignment barriers from empirical observation to theoretical impossibility under standard assumptions.

Strong Theoretical Claims: The core theorems (Theorem 1 on input filtering and Theorem 2 on output filtering) provide separation results that are robust and compelling. The explicit requirement that the filter be computationally weaker than the LLM in Theorem 1 is a realistic constraint for many practical black-box or proprietary LLM deployments.

Comprehensive Scope: The paper doesn't stop at simple detection filters but also considers mitigation filters (Section 1.4) and explores scenarios involving shared secrets or public keys (Section 1.5), offering a well-rounded analysis of potential external defenses.

Connecting Theory to Practice: The inclusion of empirical evidence (Table 1) using state-of-the-art safety filters (Llama Guard, Shield Gemma) adds concrete, real-world relevance to the abstract theoretical findings. This successfully bridges the gap between the constructed, cryptographically-enabled LLMs and the observable failure modes of current models.
summary: This paper investigates the fundamental limits of achieving AI alignment through external filtering mechanisms. The authors focus on two natural points of intervention: filtering the input prompt before it reaches a Large Language Model (LLM) and filtering the output after generation. The core contribution is demonstrating, under standard cryptographic hardness assumptions (specifically the existence of Time-Lock Puzzles and One-Way Functions), that both input-prompt and output filtering can be computationally intractable.
hese results also extend to more expressive "mitigation filters" that can modify prompts or outputs. The authors conclude that an aligned AI system’s intelligence (the LLM internals) cannot be practically separated from its judgment (the external filters), necessitating "internal" alignment solutions. Empirical results with real-world filters (Llama Guard, Shield Gemma) are presented to support the theoretical claims.
weaknesses: While the theoretical framework is strong, several aspects of the presentation, technical rigor, and scope could be improved for an ICLR audience.
* Lack of experimental support is the most critical factor. Otherwise, I think a position paper would be more suitable
* Technical Sketch Insufficient (Section 2): The high-level technical overview of the construction is abstract. Given that the entire proof hinges on the construction of the indistinguishable pair (G,G‘) and the function g, the key challenges mentioned—recovering n from (h,h(n)), the issue of multiple inverses, and using hardcore bits—should be explained with more detail or a more concrete example to demonstrate the Recoverable-Randomness Sampling mechanism. It is difficult to fully assess the proof's validity.

---

confidence: 4
contribution: 2
initial_rating: 2
presentation: 2
questions: - I do not understand the philosophical perspective. What do "intelligence" and "judgement" mean here, and why do these results prove these notions cannot be separated?
- Why would one restrict themselves to only input/output filters when a company can filter intermediate embeddings as well?
- Do the theoretical results extend to intermediate embedding filters as well?
- Could the authors comment on how is their paper related to “Position: Fundamental Limitations of LLM Censorship Necessitate New Approaches”?
- How do the experiments in section 1.3 relate to the theoretical results?
soundness: 2
strengths: - The connections to cryptographic hardness is interesting.
- Formalizing the difficulty of input/output filtering is a potentially useful step towards understanding the difficulties facing LLM alignment.
- It is interesting that their result for output filtering holds for filters that are stronger than the base LLM
summary: The paper considers two natural methods of filtering LLM content to prevent the generation of unsafe information—input and output filtering. The core result is that, given the existence of time-lock puzzles, AI safety cannot be achieved through the use of external filters: in other words, white-box model access is required to ensure LLM alignment. The authors show this by first demonstrating that there are LLMs for which adversarial prompts that are cryptographically indistinguishable from benign prompts can be efficiently generated; for such LLMs, no efficient input filter exists. Moreover, they show conversely that there also exist LLMs that can generate outputs that are indistinguishable from benign outputs but which nevertheless have harmful consequences.
weaknesses: - Consider shortening the title
- I’m not sure what scientific value figure 1 provides (perhaps worth keeping it for talks but not for a scientific paper)
- The structure of the paper is very unusual for an ML conference paper and makes it hard to read. The introduction is very unusually long. It is followed by a shorter technical section and a short reflection in the end. For example, the related work and the background is scattered throughout. It is very hard for me to accept the paper in its current form based on this alone.
- The setup in section 1.1 is quite dense and hard to read through.
- Regarding the experiments in section 1.3 are: The theoretical results concern, respectively, the existence of LLMs for which no filter can filter harmful from benign inputs, and the existence of an LLM that can generate harmful outputs that are indistinguishable to any efficient output filter from those of a reference LLM. Why does it matter that these particular filters and particular LLMs can be bypassed? It just means some filters don't work.
- The theoretical results consider "worst-case" LLMs, unclear how this lines up with empirical concerns, especially since their experiment doesn't seem that relevant to the theory.


Decision: Accept (Poster)