Paper deep dive
CARTS: Contextual Autoregressive Rank Transcoding Steganography for Full-Capacity Keyed Text Encoding
Wissam Ghantous, Alexander V. Mantzaris
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 9/11/2026, 3:52:48 AM
Summary
This paper formalizes Contextual Autoregressive Rank Transcoding Steganography (CARTS), a method using autoregressive language models to embed secret payloads into stegotexts of identical length. It provides the first rigorous security analysis of the Calgacus construction, defining security notions and computational problems such as context search, key collisions, and message equivocation. Empirical results on Llama 3 8B confirm exact payload recovery and resistance to specific attack vectors.
Entities (8)
Relation Signals (8)
CARTS → formalizedby → Ghantous
confidence 95% · This paper provides the first rigorous treatment of CARTS... Wissam Ghantous... Alexander V. Mantzaris
CARTS → instantiatedby → Calgacus
confidence 95% · present the Calgacus construction of (Norelli and Bronstein, 2025) within this framework
Llama-3-8B → usedinempiricalstudyof → CARTS
confidence 95% · An empirical study on Llama 3 8B confirms exact recovery
CARTS → addressessecurityproblem → Key Collisions
confidence 90% · define relevant security notions... key collisions... and study the theoretical relationships
CARTS → addressessecurityproblem → Message Equivocation
confidence 90% · message equivocation... study the theoretical relationships between them
CARTS → addressessecurityproblem → Context Search
confidence 90% · context search... study the theoretical relationships between them
Calgacus → createdby → Bronstein
confidence 90% · Norelli and Bronstein, 2025
Calgacus → createdby → Norelli
confidence 90% · Calgacus construction of Norelli et al.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Autoregressive language models can be used to transform a payload text into a stegotext of identical token length by preserving per-position rank information across contexts - a methodology we formalize as Contextual Autoregressive Rank Transcoding Steganography (CARTS). While the Calgacus construction of Norelli et al. demonstrated this phenomenon experimentally, no formal security analysis existed. This paper provides the first rigorous treatment of CARTS. We show its exact correctness under deterministic model assumptions, introduce a rank-coordinate representation in which keys act as bijections on rank-vector space, define relevant security notions and the computational problems naturally associated with the construction - context search, key collisions, message equivocation, and non-commutativity of the encoding maps - and study the theoretical relationships between them, including the characterization of message equivocation in terms of context search, and the tension between key collisions and message equivocation. An empirical study on Llama 3 8B confirms exact recovery of the original payload in all tested cases, finds no key collisions under random key generation, establishes that a hand-crafted collision is local rather than global, and finds no commuting key pairs - suggesting resistance to the attack vectors studied. This work opens a formally grounded research agenda for the constructive use of language models in cryptography and privacy-preserving communication.
Tags
Links
- Source: https://arxiv.org/abs/2609.10744v1
- Canonical: https://arxiv.org/abs/2609.10744v1
Trouble viewing inline? Open PDF directly →
Full Text
79,406 characters extracted from source content.
Expand or collapse full text
CARTS: Contextual Autoregressive Rank Transcoding Steganography for Full-Capacity Keyed Text Encoding Wissam Ghantous Affiliation: University of Central Florida, Orlando, Florida, USA email: wissam.ghantous@ucf.edu and Alexander V. Mantzaris Affiliation: University of Central Florida, Orlando, Florida, USA email: alexander.mantzaris@ucf.edu Abstract. Autoregressive language models can be used to transform a payload text into a stegotext of identical token length by preserving per-position rank information across contexts — a methodology we formalize as Contextual Autoregressive Rank Transcoding Steganography (CARTS). While the Calgacus construction (Norelli and Bronstein, 2025) demonstrated this phenomenon experimentally, no formal security analysis existed. This paper provides the first rigorous treatment of CARTS. We show its exact correctness under deterministic model assumptions, introduce a rank-coordinate representation in which keys act as bijections on rank-vector space, define relevant security notions and the computational problems naturally associated with the construction — context search, key collisions, message equivocation, and non-commutativity of the encoding maps — and study the theoretical relationships between them, including the characterization of message equivocation in terms of context search, and the tension between key collisions and message equivocation. An empirical study on Llama 3 8B confirms exact recovery of the original payload in all tested cases, finds no key collisions under random key generation, establishes that a hand-crafted collision is local rather than global, and finds no commuting key pairs — suggesting resistance to the attack vectors studied. This work opens a formally grounded research agenda for the constructive use of language models in cryptography and privacy-preserving communication. Keywords: Steganography, Linguistic steganography, Information hiding, Large language models, Security analysis 1. Introduction Recent years have seen growing interaction between artificial intelligence and cybersecurity, with researchers studying both how cryptographic techniques can be used to analyze or attack machine-learning systems, and conversely how AI systems can be used to attack or weaken existing cryptographic constructions. For example, prior work has investigated cryptographic approaches to model extraction and parameter recovery attacks (Canales-Martínez and Santos, 2025; Carlini et al., 2025), while other directions study the use of machine learning for cryptanalysis or automated attacks on security systems (Zhang et al., 2025; Gohr, 2019; Wenger et al., 2022). In contrast, the present work considers a different direction: the use of autoregressive language models themselves as the foundation for security primitives. Steganography aims to embed a secret payload into an innocuous-looking cover object so that a third party cannot reliably determine whether hidden communication is taking place (Cachin, 1998; Hopper et al., 2002). It therefore complements cryptography: encryption protects message content, while steganography targets the observability of communication itself, which matters for censorship resistance, and deniable communication. Recent advances in neural language modeling have enabled practical linguistic steganography, where natural language is the cover channel. Early neural approaches used language models to generate covertext while encoding bits through constrained sampling or coding schemes (Ziegler et al., 2019; Shen et al., 2020). From a provable security perspective, security oriented work has investigated how to achieve indistinguishability relative to realistic text distributions by combining universal steganography ideas with modern generative models (Kaptchuk et al., 2021). In parallel, black-box settings (where only an interface or API is available) motivate alternative constructions and threat models (Wu et al., 2024). In a conventional linguistic steganography setting, the sender begins with an existing cover text and modifies it using a shared key to produce a stegotext carrying the hidden payload. A receiver possessing the same key can then recover the secret message. The Calgacus construction of (Norelli and Bronstein, 2025) proposes a new way, exploiting the use of LLMs, to achieve steganography, producing a new text of the same length as the payload. Instead of editing a fixed cover text, Calgacus uses a secret prompt as the key to steer the topic and style of the generated output. The payload text is first converted into LLM token ranks, then the LLM is run under the key and forced to emit tokens whose ranks match that sequence. Decoding repeats the same process backwards, obtaining the original message. This allows the user to achieve full-capacity, length-preserving text-to-text transcoding, where a meaningful message can be hidden inside another coherent text of exactly the same token length. This new construction opens up a whole area of research on the constructive use of LLMs in privacy-preserving communication, with the goal of building new primitives, and has not yet garnered too much attention. Only limited prior work has studied the sensitivity of the Calgacus construction to variations in the secret context, showing that small perturbations of the key can induce substantially different generated outputs (Mantzaris et al., 2026). As a consequence, many theoretical and practical questions remain unanswered. In particular, this construction has only been demonstrated to work experimentally, via examples, without a formal security analysis. The initial paper (Norelli and Bronstein, 2025) does not provide any concrete security definitions, nor does it identify the computational problems underlying the security properties for their construction. The goal of this paper is to fill this gap, and provide an initial concrete empirical study of the assumptions underlying the security of this new construction. Terminology. We propose the formal term Contextual Autoregressive Rank Transcoding Steganography (CARTS) to describe this methodology. Informally, CARTS takes (i) a payload sentence, (i) a private key realized as a secret context/prompt, and (i) a fixed autoregressive language model, and outputs a new sentence of the same token length. Decoding with the same key deterministically maps the generated stegotext back to the original payload. The surface text can appear benign (or policy-compliant when used over public communications channels) while the payload is recoverable only by parties holding the key and the model specification. Contributions. In this paper, we (i) formalize CARTS as a keyed rank-transcoding steganographic primitive and present the Calgacus construction of (Norelli and Bronstein, 2025) within this framework; (i) introduce a set of computational problems and associated assumptions naturally motivated by the underlying LLM; (i) formally define some desirable security notions for CARTS as a steganographic protocol; (iv) characterize the security properties of CARTS and the corresponding attacker tasks in terms of these computational problems (e.g., context search and key collisions) and (v) provide an initial theoretical and experimental study of these computational problems to assess their difficulty. Roadmap. In Section 2, we explain the subtle conceptual difference between CARTS and the prior types of steganography. In Section 3, we formally introduce the general CARTS steganography framework and view Calgacus as a natural instantiation, using LLMs. In Section 4, we begin by discussing scope and adversarial models, then introduce various desirable security properties that a steganographic scheme could have, and the corresponding computational problems, naturally motivated by the underlying LLM used. At a second stage, we study these problems theoretically, from various angles. In particular, we discuss matters of equivocation, key collisions, as well as the issue of commuting keys and its implications on security. Lastly, in Section 5, we initiate an empirical study into the relevant computational problems that arose in the body of the paper. In the conclusion, we provide some concrete problems to be studied next, to further solidify our theoretical and practical understanding of LLMs, as a basis for steganography. 2. Conceptual Framework Formally, in steganography, the sender begins with an innocent-looking cover object c (for example, an ordinary piece of text) and embeds a secret payload m into that cover. The output, called a stegotext s, should look like a normal cover while allowing an intended receiver to recover m. Many formulations include a shared secret key k that controls the embedding and extraction procedures (Cachin, 1998; Hopper et al., 2002; Simmons, 1984; Anderson and Petitcolas, 2002). At a high level, the interface is: s s ←Embed(c,m,k), (c,m;k), m m ←Extract(s,k). (s;k). Intuitively, EmbedEmbed makes small, hard-to-notice changes to the cover c so that the payload m is hidden in s, and ExtractExtract reverses the process (given k) to recover m m. In classical linguistic steganography, the cover object is simply text. Traditional techniques often modify the existing text via substitutions or syntactic changes (Provos and Honeyman, 2003), while neural methods instead generate text under constraints that encode a secret (Ziegler et al., 2019). Arithmetic-coding style constructions can improve capacity and imperceptibility by using the language model distribution directly during generation (Shen et al., 2020). All these methods, however, share the same methodology: they hide a message (either fully, or in parts) inside another text. On the other hand, the approach suggested in (Norelli and Bronstein, 2025) is completely different. It allows one to deterministically transform a message into a new meaningful one, with a completely unrelated meaning. This can be viewed as the purest form of steganography. There is no need for a cover object anymore, as the initial message, under the secret key, is entirely transformed into a new unrelated text, becoming the covertext, so to speak. More concretely, CARTS differs from typical bit-encoding approaches in that the payload is itself a natural-language token sequence rather than a low-rate bitstream, enabling one output token per payload token, thus offering full capacity encoding. Given a fixed model, CARTS records the payload’s per-position rank trace under an empty context and regenerates a stegotext that realizes the same ranks under a secret keyed context, yielding a length-preserving and deterministically invertible encoding. A detailed description of this scheme is given in Section 3. 3. CARTS protocol 3.1. The standard protocol Fix an autoregressive language model ℳM, and let VrawV_raw be its finite tokenizer vocabulary. We fix two token sets, V⊆VrawV V_raw and C⊆VrawC V_raw, where V is the admissible output vocabulary over which next-token rankings and deterministic generation are performed, and C is the context vocabulary used for prompts and previously generated tokens. We assume V⊆CV C, so that generated tokens can be appended to a context. We also assume that special tokens or any tokens that are masked by the implementation are either removed from V or included with a fixed deterministic masking convention. All rankings below are rankings over this same admissible output vocabulary V. Let N:=|V|N:=|V|. We write VnV^n for the set of admissible generated token sequences of length n, and C∗C^* for the set of finite token contexts. For compactness, write [N]:=1,…,N,n:=[N]n.[N]:=\1,…,N\, _n:=[N]^n. Here, length is always measured in tokens under the fixed tokenizer associated with the model. The protocol described further below runs for exactly n generation steps. If an end-of-sequence token is retained in V, it is treated as an ordinary token for the purposes of ranking and generation, and it does not cause early termination. Definition 1 (General CARTS protocol). Fix a key space ⊆C∗K C^*. A length-preserving CARTS protocol on VnV^n is a keyed pair of algorithms Ek,Dk:Vn⟶Vn,k∈,E_k,D_k:V^n V^n, k , such that Dk(Ek(x))=xD_k(E_k(x))=x for every payload token sequence x∈Vnx∈ V^n and every key k∈k . We say that EkE_k encodes a payload text into a stegotext, and that DkD_k decodes the stegotext back into the payload. In CARTS, the key k is realized as a secret context or prompt. We now describe the Calgacus (Norelli and Bronstein, 2025) instantiation of CARTS. For our fixed model ℳM, and a context c∈C∗c∈ C^*, we write pℳ(⋅∣c)p_M(· c) for the restricted and renormalized next-token distribution on V. This induces a fixed, deterministic ordering on V, by decreasing probability under pℳ(⋅∣c)p_M(· c), which we denote by πc:[N]⟶V. _c:[N] V. We assume this ordering to have no ties, as they can be broken deterministically. Thus, πc(j) _c(j) is the token of rank j, given the context c. For a token a∈Va∈ V and a context c∈C∗c∈ C^*, we define rankℳ(a∣c)=j⟺πc(j)=a.rank_M(a c)=j _c(j)=a. As ℳM is fixed, we often will omit the subscript. For a sequence x=(x1,…,xn)∈Vnx=(x_1,…,x_n)∈ V^n and context c∈C∗c∈ C^*, define the autoregressive rank trace Rc(x)=(rank(xi∣c,x1,…,xi−1))i=1n∈n.R_c(x)= (rank(x_i c,x_1,…,x_i-1) )_i=1^n _n. This is the vector of ranks obtained by reading x from left to right while updating the context with the previously read tokens. Conversely, for a rank vector r=(r1,…,rn)∈nr=(r_1,…,r_n) _n and context c∈C∗c∈ C^*, define the autoregressive rank generator Gc(r)=y=(y1,…,yn)∈VnG_c(r)=y=(y_1,…,y_n)∈ V^n recursively by yi=π(c,y1,…,yi−1)(ri),i=1,…,n.y_i= _(c,y_1,…,y_i-1)(r_i), i=1,…,n. Thus, GcG_c generates one token at a time, always selecting the token whose current rank is prescribed by rir_i. Lemma 0 (Rank-trace inversion). For every context c∈C∗c∈ C^*, every token sequence x∈Vnx∈ V^n, and every rank vector r∈nr _n, Rc(Gc(r))=r,Gc(Rc(x))=x.R_c(G_c(r))=r, G_c(R_c(x))=x. Proof. Both identities follow position by position from the definition of πc _c. At step i, the rank trace and the rank generator use the same updated context c followed by the tokens already processed or generated. Since πc _c is a deterministic ordering of the vocabulary, selecting a token by rank and then measuring its rank gives back the same rank, and measuring a token’s rank and then selecting that rank gives back the initial token. ∎ The Calgacus CARTS encoder and decoder are Ek(x):=Gk(R∅(x)),Dk(y):=G∅(Rk(y)),E_k(x):=G_k(R_ (x)), D_k(y):=G_ (R_k(y)), where ∅ denotes the empty context. We thus directly have the following correctness result, whose proof follows directly from Lemma 1. Theorem 2 (Correctness). For every x∈Vnx∈ V^n and every key k∈k , Dk(Ek(x))=x.D_k(E_k(x))=x. The above theorem is a mathematical statement about a fixed deterministic next-token ordering, which works computationally only when the encoder and decoder compute exactly the same token rankings at every step. In practice, this requires identical tokenization, admissible vocabulary, prompt serialization, model weights, masking convention, numerical precision, and tie-breaking rule between sender and receiver; if any of these differ, correctness may fail. Remark 1 (Token perturbations and error propagation). These results assume that the received stegotext is identical to the transmitted stegotext. The protocol is generally not robust to token edits. If two stegotexts y,y~∈Vny, y∈ V^n agree up to position j−1j-1 but differ at position j, then their rank traces under the same key k agree up to position j−1j-1, but the rank at position j differs: Rk(y)i=Rk(y~)ifor i<j,Rk(y)j≠Rk(y~)j.R_k(y)_i=R_k( y)_i i<j, R_k(y)_j≠ R_k( y)_j. For positions i>ji>j, there is no general guarantee, because the autoregressive contexts have diverged. Thus a single token edit can affect the decoded suffix. Robust variants would require additional redundancy, synchronization, or error-correction mechanisms. We do not address these concerns here, as we focus instead on the security concerns and assume that the messages are well transmitted. 3.2. Generalized two-context rank transforms The base Calgacus construction uses the empty context to read the payload rank trace and the key context to generate the stegotext. The same formalism supports a more general two-context construction. Let a,b∈C∗a,b∈ C^* be two contexts, and let ϕ:n→nφ:X_n _n be a bijection on the rank space. Define Ea,b,ϕ(x):=Gb(ϕ(Ra(x))),E_a,b,φ(x):=G_b(φ(R_a(x))), and Da,b,ϕ(y):=Ga(ϕ−1(Rb(y))).D_a,b,φ(y):=G_a(φ^-1(R_b(y))). Theorem 3 (Generalized two-context correctness). For every a,b∈C∗a,b∈ C^*, every bijection ϕ:n→nφ:X_n _n, and every x,y∈Vnx,y∈ V^n, Da,b,ϕ(Ea,b,ϕ(x))=x,Ea,b,ϕ(Da,b,ϕ(y))=y.D_a,b,φ(E_a,b,φ(x))=x, E_a,b,φ(D_a,b,φ(y))=y. Proof. For x∈Vnx∈ V^n, and a,ba,b and ϕφ as above, we have Da,b,ϕ(Ea,b,ϕ(x)) D_a,b,φ(E_a,b,φ(x)) =Ga(ϕ−1(Rb(Gb(ϕ(Ra(x)))))) =G_a (φ^-1 (R_b (G_b(φ(R_a(x))) ) ) ) =Ga(ϕ−1(ϕ(Ra(x)))) =G_a (φ^-1(φ(R_a(x))) ) =Ga(Ra(x)) =G_a(R_a(x)) =x. =x. Similarly, for y∈Vny∈ V^n, Ea,b,ϕ(Da,b,ϕ(y))=yE_a,b,φ(D_a,b,φ(y))=y. ∎ Remark 2. The generalized construction above preserves exact invertibility for every bijection ϕ:n→nφ:X_n _n. However, the quality of the generated stegotext depends strongly on the choice of ϕφ. The autoregressive model typically assigns high probability to only a small subset of low-rank tokens at each step. Consequently, transformations ϕφ that map low ranks to substantially larger ranks will tend to force the generator to select improbable tokens, often degrading fluency and semantic coherence. In particular, an arbitrary permutation of nX_n will generally not preserve the distributional structure of natural language rank traces, and the resulting stegotext may appear nonsensical and unnatural. Practical constructions therefore require transformations ϕφ that preserve, approximately preserve, or otherwise control rank magnitude and local rank statistics. The original Calgacus instantiation is recovered by taking a=∅,b=k,ϕ=idn.a= , b=k, φ=id_X_n. Other choices of a, b, and ϕφ can model other deterministic transformations of the rank trace, such as prompt-before-payload variants or rank permutations. This more general construction could be used to build more interesting primitives, beyond the scope of steganography. It also remains an open question to build natural generalizations allowing for more than two contexts. We leave this task for future work, and focus here on the formalization of the security properties the existing CARTS scheme. Remark 3. It is not necessary, in principle, to use large language models to define a CARTS scheme. However, autoregressive LLMs provide a natural carrier distribution and a rich conditional ranking structure. Future developments in generative modeling (Goodfellow et al., 2014) (or alternative probabilistic sequence models) may yield additional instantiations of CARTS-like protocols with different security and robustness tradeoffs. 4. Security assumptions and protocol properties In this section, we investigate several security properties and computational problems naturally associated with CARTS schemes. We formalize and study notions including message equivocation, key collisions, and key commutativity, and explore their relationships and implications for security 4.1. Scope and adversarial model The classical notion of security in steganography is distributional indistinguishability: the stegotext should be statistically indistinguishable from an ordinary cover object, so that an adversary cannot reliably detect that hidden communication is taking place (Zhang et al., 2021; Ding et al., 2023; de Witt et al., 2022). In the CARTS setting, this reduces to the question of whether LLM-generated text can be made indistinguishable from ordinary human-written or model-generated text. This question has received substantial attention in recent years (Mitchell et al., 2023; Sadasivan et al., 2023), and will continue to do so as language models become more capable. It also stands to reason that, as more research and resources are poured into LLMs, they will get better at mimicking human text, and detection will become significantly harder. Rather than revisiting this well-studied question, the present work targets a different and largely unexplored set of security properties specific to the rank-transcoding structure of CARTS. These properties — equivocation, key collisions, context search, and non-commutativity of key-induced maps — arise naturally from the algebraic and computational structure of the construction, and have not previously been studied in the setting of LLM-based steganography. They lead to questions that are novel from both a machine learning and a cryptographic perspective. When it comes to the adversarial model, we consider a sender and receiver who share a private key k, realized as a secret context or prompt supplied to a fixed autoregressive language model ℳM. The sender transforms a payload token sequence x∈Vnx∈ V^n into a generated stegotext y∈Vny∈ V^n of the same token length, and the receiver deterministically recovers x from y using k and the same model specification. The adversary may observe y and is assumed to know the protocol family, the tokenizer, and the model ℳM. We distinguish several levels of adversarial access. In a ciphertext-only setting, the adversary observes only the stegotext y. In a known-plaintext setting, the adversary observes one or more payload-stegotext pairs (xi,yi)(x_i,y_i) with yi=Ek(xi)y_i=E_k(x_i) for a fixed unknown key k. Lastly, in a chosen-plaintext setting, the adversary can additionally select payloads and obtain their encodings under the same fixed unknown key. The formal analysis in this paper focuses primarily on the known-plaintext model, where the attacker can observe payload-stegotext pairs and knows the protocol family, the tokenizer, and the model ℳM. 4.2. The rank-coordinate notation We first introduce the rank-coordinate form of the Calgacus protocol. This removes any ambiguity between token sequences and rank vectors. Fix n and let n=[N]nX_n=[N]^n. For every key k∈k , define Fk:n⟶n,Fk(r):=R∅(Gk(r)).F_k:X_n _n, F_k(r):=R_ (G_k(r)). Thus FkF_k maps the empty-context rank representation of a payload to the empty-context rank representation of the resulting stegotext. One can easily check that the inverse of FkF_k is Fk−1(w)=Rk(G∅(w)).F_k^-1(w)=R_k(G_ (w)). Therefore, for each fixed key k, the map FkF_k is a bijection of nX_n. Proposition 1 (Rank-coordinate conjugacy). For every admissible key k∈k , Fk=R∅∘Ek∘G∅,F_k=R_ E_k G_ , and equivalently, Ek=G∅∘Fk∘R∅.E_k=G_ F_k R_ . Moreover, Dk=G∅∘Fk−1∘R∅.D_k=G_ F_k^-1 R_ . Consequently, for any keys k1,k2∈k_1,k_2 , Ek2∘Ek1=G∅∘(Fk2∘Fk1)∘R∅.E_k_2 E_k_1=G_ (F_k_2 F_k_1) R_ . Proof. First, for any r∈nr _n, (R∅∘Ek∘G∅)(r) (R_ E_k G_ )(r) =R∅(Gk(R∅(G∅(r)))) =R_ (G_k(R_ (G_ (r))) ) =R∅(Gk(r))=Fk(r). =R_ (G_k(r))=F_k(r). This proves Fk=R∅∘Ek∘G∅F_k=R_ E_k G_ . Next, composing on the left by G∅G_ and on the right by R∅R_ gives Ek=G∅∘Fk∘R∅.E_k=G_ F_k R_ . Using the inverse formula Fk−1(w)=Rk(G∅(w))F_k^-1(w)=R_k(G_ (w)), we obtain, for y∈Vny∈ V^n, (G∅∘Fk−1∘R∅)(y) (G_ F_k^-1 R_ )(y) =G∅(Rk(G∅(R∅(y)))) =G_ (R_k(G_ (R_ (y))) ) =G∅(Rk(y))=Dk(y). =G_ (R_k(y))=D_k(y). The composition identity for Ek2∘Ek1E_k_2 E_k_1 follows by applying the expression Ek=G∅∘Fk∘R∅E_k=G_ F_k R_ twice and using R∅∘G∅=idnR_ G_ =id_X_n. ∎ Remark 4 (Keys versus key-coordinate vectors). The formal key is always a token context k∈C∗k∈ C^*. However, in examples, it is sometimes convenient to describe a key text by its empty-context rank coordinates. If q∈tq _t, then k=G∅(q)∈Vt⊆C∗k=G_ (q)∈ V^t C^* is the corresponding key context. Thus, q is not itself the key; it is a coordinate representation of a key context whose tokens lie in the admissible output vocabulary V. Key collisions are always collisions between contexts k1,k2∈k_1,k_2 , but can be displayed through the coordinate vectors q1,q2q_1,q_2. 4.3. Definitions and Computational Problems With the above notation and formalism in place, we can now introduce the main computational problems and security notions associated with a CARTS protocol. We begin by defining several forms of message equivocation, which capture the extent to which an observed stegotext admits multiple plausible payload interpretations under different keys. These notions formalize deniability properties of the protocol and will serve as the foundation for the computational problems introduced later in this section. Definition 2 (Full message equivocation). We say that a CARTS protocol (Ek,Dk)(E_k,D_k) satisfies full message equivocation on VnV^n if, for every observed stegotext y∈Vny∈ V^n and every payload x∈Vnx∈ V^n, there exists a key k∈k such that Dk(y)=x.D_k(y)=x. Definition 3 (Weak ℓ -message equivocation). For an integer ℓ≤|V|n ≤|V|^n, we say that a CARTS protocol (Ek,Dk)(E_k,D_k) satisfies weak ℓ -message equivocation on VnV^n if, for every observed stegotext y∈Vny∈ V^n, there exist distinct payloads x1,…,xℓ∈Vnx_1,...,x_ ∈ V^n and keys k1,…,kℓ∈k_1,...,k_ such that Dki(y)=xi,∀i=1,…,ℓ.D_k_i(y)=x_i, ∀ i=1,..., . Message equivocation (whether it is full or weak) can also be referred to as encryption deniability (in the spirit of (Canetti et al., 1997; Dürmuth and Freeman, 2011)). Intuitively, this property means that a given key k does not uniquely determine a single underlying message. Instead, multiple plausible payloads may correspond to the same observed covertext when different keys are used. Consequently, even if a computationally unbounded adversary intercepts k, they cannot definitively determine which message was encoded, since several alternative messages remain consistent with the observed data under different keys. A party may thus plausibly claim that a different message was intended. Moreover, full message equivocation implies weak ℓ -message equivocation (for ℓ within the bound of existing messages in |V|n|V|^n). Remark 5. The practical relevance of message equivocation depends strongly on the threat model and the surrounding social or political environment. Indeed, in highly coercive settings, such as under an authoritarian regime, the mere existence of a key capable of explaining a stegotext as corresponding to an incriminating or “undesirable” payload may itself be sufficient to justify retaliation, regardless of whether alternative benign explanations also exist. In such contexts, message equivocation alone may therefore provide limited practical protection. By contrast, in more typical institutional settings governed by stronger procedural protections, where individuals are not presumed guilty solely on the basis of a possible incriminating interpretation, equivocation can provide a meaningful form of deniability. In such cases, the existence of a plausible alternative payload consistent with the same observed stegotext may be sufficient to prevent definitive attribution. Consequently, the operational significance of equivocation depends not only on the mathematical properties of the protocol, but also on the standards of evidence and coercion present in the intended application environment. For completeness, we also introduce a restricted variant of message equivocation in which the admissible payloads, observed stegotexts, and keys are constrained to prescribed subsets. This formulation is useful in practical settings where only certain payloads are considered plausible, only certain stegotexts are observable, or only a restricted family of keys is operationally realistic. Definition 4 (Restricted-support equivocation). Let adm⊆VnP_adm V^n be a set of admissible payloads, let adm⊆VnY_adm V^n be a set of admissible observed stegotexts, and let adm⊆K_adm be a set of admissible or plausible keys. The protocol has restricted-support full message equivocation relative to (adm,adm,adm)(P_adm,Y_adm,K_adm) if, for every x∈admx _adm and every y∈admy _adm, there exists k∈admk _adm such that Dk(y)=x.D_k(y)=x. For an integer ℓ≤|adm| ≤|P_adm|, it has restricted-support weak ℓ -message equivocation relative to (adm,adm,adm)(P_adm,Y_adm,K_adm) if, for every y∈admy _adm, there exist distinct x1,…,xℓ∈admx_1,...,x_ _adm and keys k1,…,kℓ∈admk_1,...,k_ _adm such that Dki(y)=xi,∀i=1,…,ℓ.D_k_i(y)=x_i, ∀ i=1,..., . Having introduced the relevant security definitions, we now turn to the computational problems naturally associated with a CARTS protocol. These problems formalize the algorithmic tasks underlying the security and deniability properties discussed above. We work with the same setup as Section 3, and we assume that our large language model ℳM is fixed. For unconditional properties, we allow the key space ⊆C∗K C^* to be arbitrary. For algorithmic search problems, however, the key domain must be specified more concretely, for instance, by restricting to a finite admissible key set adm⊆K_adm , or by giving a specified key-generation distribution with an explicit search budget. Without such a restriction, non-existence over all of C∗C^* is not a finite computational task. For convenience, we use the rank-coordinate notation introduced in Section 4.2 to emphasize the action of the key k on the messages, viewed as rank vectors. Definition 5 (Key collision). Fix a model ℳM, a key space K, and a length n. For a rank vector r∈nr _n, two distinct keys k1,k2∈k_1,k_2 form a key collision if Fk1(r)=Fk2(r).F_k_1(r)=F_k_2(r). Equivalently, the same payload rank vector r maps to the same stegotext rank vector under two different keys. Problem 1 (The key collision problem). Given r∈nr _n and an admissible key set adm⊆K_adm , find distinct keys k1,k2∈admk_1,k_2 _adm such that Fk1(r)=Fk2(r),F_k_1(r)=F_k_2(r), or determine that no such pair exists within admK_adm. Problem 2 (The promise context search problem). Given r,w∈nr,w _n and an admissible key set adm⊆K_adm , with the promise that there exists k∈admk _adm satisfying Fk(r)=w,F_k(r)=w, find one such key k. Problem 2 is the most direct known-message key-search problem. It is very close in spirit to the vectorization problem (see Problem 6 in (Couveignes, 2006)) because one is searching for a key that transports one rank vector to another. The main difference with the usual vectorization problem is that the key space does not carry a natural algebraic composition law (as in (Alamati et al., 2020)), and the family Fk\F_k\ is not assumed to form a group action. The context-search problem is therefore a transport problem on rank-vector space without the algebraic structure that underlies the vectorization setting. Problem 3 (The unconditional context search problem). Given r,w∈nr,w _n and an admissible key set adm⊆K_adm , find a key k∈admk _adm such that Fk(r)=w.F_k(r)=w. Problem 4 (The unconditional partial ℓ -context search problem). Given w∈nw _n and an admissible key set adm⊆K_adm , find ℓ rank vectors r1,…,rℓ∈nr_1,...,r_ _n and keys k1,…,kℓ∈admk_1,...,k_ _adm such that Fki(ri)=w.F_k_i(r_i)=w. Note, of course, that for an arbitrary CARTS protocol, a solution to Problems 3 or 4 need not exist. Furthermore, it is clear that Problem 4 is not harder than Problem 3. With the above notions in hand, we can discuss message equivocation for a CARTS protocol. This will be done in the following subsection. Finally, for completeness, we mention a more general version of Problem 3 that will be addressed further in subsequent work, when building a different primitive. Problem 5 (Pre-image resistance problem). Given w∈nw _n and an admissible key set adm⊆K_adm , find a key k∈admk _adm and a rank vector r∈nr _n such that Fk(r)=w.F_k(r)=w. Although this problem looks similar to Problem 3, the key difference is that the message r is not fixed here. More generally, all the above definitions and problems look similar but differ in very subtle ways, as they target different privacy concerns and applications. Remark 6. (1) An unconstrained preimage-search problem of the form “given w, find r and k such that Fk(r)=wF_k(r)=w” is trivial whenever the empty context is admissible: take r=wr=w and k=∅k= . One can thus consider additional constraints, such as r≠wr≠ w, non-empty keys, plausible keys, plausible payloads, or bounded key length. (2) If the empty context ∅ is included in the admissible key space K, then F∅(r)=rF_ (r)=r for every r∈nr _n. Therefore, every stegotext y has the trivial explanation E∅(y)=yE_ (y)=y. Consequently, the unconditional partial 11-context search problem (and hence, weak 11-message equivocation, as we will see in Section 4.4) is trivial whenever the empty key is admissible. Nontrivial equivocation claims should therefore impose additional constraints. Lastly, we note that all of the computational problems introduced above can be defined for a general CARTS protocol in terms of the encoding and decoding maps EkE_k and DkD_k alone. The rank-coordinate formulation via Fk:n→nF_k:X_n _n is specific to the Calgacus instantiation and its induced rank representation, and is introduced primarily for convenience of analysis and notation. The underlying problem structure, however, is independent of this representation. 4.4. Security Properties of the Protocol 4.4.1. Message Equivocation Theorem 1. A CARTS protocol has full message equivocation on VnV^n if and only if the unconditional context search problem (Problem 3) is solvable for all r,w∈nr,w _n. Similarly, for an integer ℓ≤|n| ≤|X_n|, it has weak ℓ -message equivocation on VnV^n if and only if the unconditional partial ℓ -context search problem (Problem 4) is solvable for every w∈nw _n. Proof. The result follows directly from unpacking the definitions. For notational convenience, we present the proof for the Calgacus construction; the same argument applies to any CARTS protocol. Recall that R∅:Vn→nR_ :V^n _n is a bijection with inverse G∅G_ , and that Fk=R∅∘Ek∘G∅F_k=R_ E_k G_ . Let x,y∈Vnx,y∈ V^n and define r=R∅(x)r=R_ (x) and w=R∅(y)w=R_ (y). Then, Dk(y)=x⟺G∅(Rk(y))=G∅(r)⟺Rk(y)=r.D_k(y)=x\; \;G_ (R_k(y))=G_ (r)\; \;R_k(y)=r. Substituting y=G∅(w)y=G_ (w) and using the definition of FkF_k, this is equivalent to Fk(r)=wF_k(r)=w. This establishes the equivalence between the full-message equivocation condition and the existence of a key solving the unconditional context search problem in rank space. The weak ℓ -message statement follows by applying the same argument to ℓ distinct pairs. ∎ We now state a direct consequence of the above characterization, which extends to the restricted-support setting via the same rank-coordinate transformation. Corollary 0. Let ℛ:=R∅(adm)R_P:=R_ (P_adm) and ℛ:=R∅(adm)R_Y:=R_ (Y_adm), then the Calgacus CARTS protocol has restricted-support full message equivocation relative to (adm,adm,adm)(P_adm,Y_adm,K_adm) if and only if ∀r∈ℛ,∀w∈ℛ,∃k∈admsuch thatFk(r)=w.∀ r _P,∀ w _Y, ∃ k _adm that F_k(r)=w. Similarly, it has restricted-support weak ℓ -message equivocation if and only if, for every w∈ℛw _Y, there exist distinct r1,…,rℓ∈ℛr_1,…,r_ _P and keys k1,…,kℓ∈admk_1,…,k_ _adm such that Fki(ri)=wF_k_i(r_i)=w for all i=1,…,ℓi=1,..., . 4.4.2. Key collision Let us now discuss Problem 1 more closely. Key collisions do not affect correctness: for any fixed key k, the decoder still inverts the encoder by Theorem 2. They are however interesting from a security standpoint. Suppose an adversary knows a payload-stegotext pair (x,y)(x,y), or equivalently the rank-coordinate pair r=R∅(x),w=R∅(y).r=R_ (x), w=R_ (y). Denote the set of keys consistent with this observation by (r,w):=k∈:Fk(r)=w. ValidKeys(r,w):=\k :F_k(r)=w\. If |(r,w)|>1| ValidKeys(r,w)|>1, then the key is not information-theoretically identifiable (even for a computationally unbounded adversary) from this single transcript, and thus cannot be used to decode future messages from the sender. In practice however, this is slightly weaker than saying that future communications are secure, as additional known plaintexts, side information about the key, or a prior over plausible prompts may reduce (or even eliminate) the candidate set. Indeed, as additional payload-stegotext pairs are observed, the candidate key set can only shrink, since each new transcript imposes an additional constraint of the form Fk(ri)=wiF_k(r_i)=w_i. For a finite key set ′⊆K , define the collision multiplicity μ′(r,w):=|k∈′:Fk(r)=w|. _K (r,w):= |\k :F_k(r)=w\ |. Thus, μ′(r,w)=0 _K (r,w)=0 means that w is unreachable from r using keys in ′K , μ′(r,w)=1 _K (r,w)=1 means that the key is identifiable within ′K from this single pair, and μ′(r,w)>1 _K (r,w)>1 means that the pair admits a key collision within admK_adm. If keys are generated by a distribution KeyGen, a distributional collision probability for fixed r is Coll(r)=Prk1,k2←[k1≠k2∧Fk1r)=Fk2(r)].Coll(r)= _k_1,k_2← KeyGen [k_1≠ k_2\ \ F_k_1r)=F_k_2(r) ]. This quantity is different from the existence of a collision. A single collision may exist while having negligible probability under the key distribution, whereas a large collision probability indicates that key non-identifiability is common for the chosen key-generation procedure. Here, we present an initial investigation of the key-collision behavior in the Calgacus CARTS protocol, leaving more extensive analysis for future work. Preliminary experiments suggest that key collisions are unlikely but can still occur in specific finite key searches. All numeric ranks in the following example are computed using the Llama-3-8B-Instruct GGUF model. Since the underlying sentences (token sequences) are explicitly provided, the example can be reproduced (with potentially different values for q1q_1 and q2q_2). Example 1. Using a specific version of the Llama-3-8B-Instruct GGUF model, we can observe that the following two key-coordinate vectors q1 q_1 =[88599,1087,1,1,1], =[88599,1087,1,1,1], q2 q_2 =[88599,1087,47,646,1] =[88599,1087,47,646,1] both map the rank-coordinate vector r:=[1,1,1,1,1]r:=[1,1,1,1,1] to w:=[126444,1,3736,2,4]w:=[126444,1,3736,2,4], thus producing a collision. Letting k1:=G∅(q1)andk2:=G∅(q2)k_1:=G_ (q_1) k_2:=G_ (q_2) denote the corresponding key contexts, we write Fk1(r)=Fk2(r)=w.F_k_1(r)=F_k_2(r)=w. While this is a priori intriguing, examining the corresponding sentences reveals only a minor (typographical) difference between the keys’ token sequences: G∅(q1)=The quick brown fox jumpsG∅(q2)=The quick brow fox jumpsG∅(w)=over the lazy dog. splitG_ (q_1)&=The quick brown fox jumps\\ G_ (q_2)&=The quick brow fox jumps\\ G_ (w)&=over the lazy dog. split Notice the typo in G∅(q2)G_ (q_2), and that all vectors above have the same length, corresponding to sentences with an equal number of tokens (the period at the end of G∅(w)G_ (w) is one of the tokens). In view of our previous example, one can ask if two distinct but nearly identical keys will encode a message into two nearly identical stegotexts (and decode a stegotext into two nearly identical messages). In general, for a key collision to provide meaningful security for the sender, the alternative keys must decode the new stegotexts to semantically distinct messages. If all collisions correspond only to minor variations (e.g., typos or trivial rewordings), an adversary could easily recover the original key by correcting these minor differences. But this only makes sense if such a correction only affects stegotexts minimally. Additional considerations are whether the alternative keys are plausible under the adversary’s key prior, how large the candidate set (r,w) ValidKeys(r,w) is, and whether the candidate keys remain consistent across additional transcripts. This motivates natural empirical questions: how often do nontrivial collisions occur, how large can |(r,w)|| ValidKeys(r,w)| become for a given pair (r,w)(r,w), and how quickly do candidate keys separate when tested on additional messages? We investigate these questions in Section 5.3. Although the two keys in Example 1 are semantically very close, this does not by itself determine whether the collision is cryptographically meaningful. A small textual perturbation in a key (as in Example 1) may either remain localized (leading to a collision for only a single payload) or may lead to substantially different behavior on a multitude of payloads. We therefore distinguish local key collisions, which occur only for a specific r, from stronger forms of key ambiguity in which the same key pairs remain indistinguishable globally, across many payloads. We study this stability question empirically in Section 5.4 and see that even though the keys k1k_1 and k2k_2 are nearly identical, and agree on the input [1,1,1,1,1][1,1,1,1,1], they disagree on other random inputs. Remark 7. If one does not restrict the lengths of the keys, nor require them to be equal, it becomes considerably easier to find collisions, for instance, by looking for extremely common phrases that end with the same words, such as: “the capital city of Italy is Rome” and “all roads lead to Rome”. For this reason, collision experiments should specify the admissible key set admK_adm, the key-length policy, and the key-generation distribution. The relevant empirical quantities are not merely whether a collision exists, but the size of the candidate fiber μadm(r,w) _K_adm(r,w) and the probability that independently generated keys collide. 4.4.3. Finite cardinality effects We now revisit the previous problem from a new perspective. Fix a payload rank vector r∈nr _n and let adm:=n=[N]nK_adm:=X_n=[N]^n, that is, we assume that the keys have the same length n as the input message. Define fr:n f_r:X_n ⟶n, _n, fr(k) f_r(k) :=Fk(r). :=F_k(r). The fiber fr−1w=k∈n:Fk(r)=wf_r^-1\w\=\k _n:F_k(r)=w\ is the set of keys that map payload rank vector r to stegotext rank vector w. This allows us to rephrase the existence of key collisions for a given r∈nr _n (Problem 1) in terms of frf_r being non-injective. On the other hand, we see that the unconditional context search problem (Problem 3) has a solution if and only if the functions frf_r are surjective for all r. In particular, we have the following result. Proposition 2. For fixed r∈nr _n, the following are equivalent: (1) frf_r is injective. (2) frf_r is surjective. (3) There are no key collisions for this fixed r within admK_adm. (4) For every w∈nw _n, there exists a key k∈admk _adm such that Fk(r)=wF_k(r)=w. Consequently, if a key collision exists for some output w, then frf_r is not injective and hence not surjective. Therefore, at least one output w′∈nw _n is unreachable from r using keys in admK_adm. However, for the colliding output w itself, the context-search instance Fk(r)=wF_k(r)=w is solvable and has more than one solution. Proof. The equivalence between injectivity and surjectivity follows from the fact that frf_r is a map between two finite sets of equal cardinality. Condition 3 is the statement that no two distinct keys map r to the same output, which is injectivity. Condition 4 is exactly the statement that every output has a preimage under frf_r, which is equivalent to surjectivity. The final claim follows immediately: a collision makes frf_r non-injective, and therefore non-surjective, but the particular output at which the collision occurs has at least two preimages. ∎ Proposition 2 and Corollary 3 (below) highlight the natural tension between the existence of key collisions and the existence of a solution to the context search problem, i.e. the tension between Problems 1 and 3. For a fixed payload rank vector r and an equal-size finite key space, one cannot have both a collision-free map and missing outputs. Corollary 0 (Key-length cardinality regimes). Let ⊆CA C be an admissible key alphabet of size M:=||M:=|A|, and let t:=tK_t:=A^t be the set of all key contexts of length t over A. Fix r∈nr _n, and define fr:t→n,fr(k)=Fk(r).f_r:K_t _n, f_r(k)=F_k(r). Then: (1) If Mt<NnM^t<N^n, then frf_r cannot be surjective. Hence some output rank vectors are unreachable from r using keys in tK_t. (2) If Mt>NnM^t>N^n, then frf_r cannot be injective. Hence at least one key collision exists for this fixed r within tK_t. (3) If Mt=NnM^t=N^n, then injectivity, surjectivity, unique reachability, and absence of key collisions are equivalent, as in Proposition 2. In the special case M=NM=N, the regimes are t<nt<n, t=nt=n, and t>nt>n. Thus, shorter-than-message key spaces cannot reach every output for a fixed payload rank vector, while longer-than-message key spaces force collisions by cardinality alone. Finally, we briefly mention that one can reinterpret the above scheme in terms of set actions. Let X:=nX:=X_n, then the set of keys admK_adm acts on X via k⋆r:=Fk(r)∈Xk r:=F_k(r)∈ X. Then, the unconditional context search problem (Problem 3) has a solution if and only if the set action is transitive. Although set actions are not often studied—since, unlike group actions, they lack algebraic structure—they provide a natural viewpoint in our setting. Indeed, the LLM construction does not naturally induce a group structure, so this is the most appropriate formalism available. Moreover, due to the lack of structure and algebraicity behind this action, there aren’t any natural approaches or interpretations that could lead to potential algebraic attacks or exploits. 4.4.4. Non-commutativity For completeness, we record an additional algebraic question related to possible instance-generation attacks. In many cryptographic problems, a single hard instance can be transformed into multiple related instances with the same hidden secret. If enough such related instances are available, the original recovery problem may become easier. A concrete example of this phenomenon appears in the lattice isomorphism problem (LIP) (Ducas and van Woerden, 2022). In one formulation, the task is to find a unimodular matrix A such that Q′=ATQAQ =A^TQA from input (Q,Q′)(Q,Q ). The authors of (Benčina et al., 2024) explain that if a second unimodular matrix U commutes with A, then one can form a second instance of the LIP problem, with the same solution A, by letting Q¯:=UTQU,Q¯′:=UTQ′U. Q:=U^TQU, Q :=U^TQ U. Indeed, by commutativity, we have Q¯′=ATQ¯A Q =A^T QA. They then show that if we have enough such LIP instances, with the same secret A, we can recover A. This in turn creates the requirement that it should not be easy for the attacker to find too many matrices that commute with A. This example motivates asking whether an analogous instance-generation structure applies to the context search problems (see Problems 2 and 3), which underlie the privacy of the CARTS system. In other words, we are asking whether Ek1(Ek2(m))=Ek2(Ek1(m))E_k_1(E_k_2(m))=E_k_2(E_k_1(m)) holds for certain messages m and keys k1,k2k_1,k_2. We illustrate this question using the diagram in Figure 1. The diagram highlights two possible paths from m to a doubly encoded message. The question is whether these two paths can lead to the same result, i.e., whether the diagram commutes. mmEk1(m)E_k_1(m)Ek2(m)E_k_2(m)Ek2(Ek1(m))E_k_2(E_k_1(m))Ek1(Ek2(m))E_k_1(E_k_2(m))??Ek1E_k_1Ek2E_k_2Ek2E_k_2Ek1E_k_1 Figure 1. Commutativity test for the encoding operators. Starting from a message m, the diagram compares the two compositions Ek2∘Ek1E_k_2 E_k_1 and Ek1∘Ek2E_k_1 E_k_2. The diagram is said to commute if both paths yield the same output for all messages m. If such commutativity were to hold (for a sufficiently large family of keys), then the order in which encoding operators are applied would be irrelevant and this symmetry can be used to generate multiple related instances of the context search problem, sharing the same secret key. Namely, given a single context search problem instance (m,Ek(m))(m,E_k(m)), where one is looking for k, we would be able to generate multiple instances ℐ:=(mi,Ek(mi)):i=1,2,…,I:=\ (m_i,E_k(m_i) ):i=1,2,...\, all with the same secret k, where mi:=Eki(m)m_i:=E_k_i(m) for keys k1,k2,…k_1,k_2,... satisfying the commutativity property Eki(Ek(m))=Ek(Eki(m)).E_k_i(E_k(m))=E_k(E_k_i(m)). This additional information, namely the knowledge of the set ℐI above, instead of simply the single instance (m,Ek(m))(m,E_k(m)), could significantly reduce the hardness of recovering the secret key k. We investigate this commutativity question further in Section 5.5, from an experimental point of view, to gain a better initial understanding of the situation, and leave the theoretical study of this question for future work. Furthermore, it would be interesting to study, from a theoretical point of view, what assumptions one must put on a language model, in order to obtain specific commuting keys, and from a practical point of view the number of commuting key pairs needed to recover the secret k. 5. Empirical Explorations The theoretical framework developed in the preceding sections raises many concrete empirical questions such as: do key collisions arise in practice, are the key-induced maps far from commuting, and how brittle is the protocol to channel noise? This section reports five experiments that investigate these questions and more, under a fixed Llama 3 8B configuration. Table 1. Empirical experiments summary. Experiment Description Runtime Implementation correctness 40 payload-key encoding-decoding tests; forward and reverse recovery checked. 607.6 s Key-collisions and finite key search 16 collision-search transcripts; 60 finite keys searched per transcript, for 16×60=96016× 60=960 finite-key evaluations. 3727.7 s Collision stability across new payloads Hand-crafted collision from Example 1, tested across 9 additional rank vectors. 105.4 s Non-commutativity of encoding maps 36 sampled key pairs; 8 payload rank vectors tested per key pair. 2265.8 s Robustness to token perturbations 20 base stegotexts; 80 length-preserving perturbation cases. 561.9 s 5.1. Experimental Configuration and Common Metrics All experiments use the llama3_8b_q4_k_m (Q4_K_M GGUF) model (Grattafiori et al., 2024) via llama-cpp-python, with nctx=4096n_ctx=4096, logits_all=true, and CPU-only inference (n_gpu_layers=0, default CPU-threading). The software environment was Python 3.12.3 on Linux 6.17.0-22- generic-x86_64. Non-empty key contexts are tokenized with add_ bos=True, after which the initial BOS token is dropped to avoid duplicating the beginning-of-sequence marker; empty contexts use the model BOS token as the minimal autoregressive context. Payload and stegotext display strings were tokenized by prepending a leading space, tokenizing with add_bos=True, and then discarding the initial BOS token. This convention matches the implementation used for both encoding and decoding. The prefix was empty in this run. Ranks are 1-indexed and computed from full-vocabulary logits, sorted by decreasing logit value with ties broken by increasing token id. No top-k, top-p, or additional experiment-level vocabulary restriction was applied. All experiments share the same prompt serialization, masking convention, ranking rule, and tie-breaking rule. The random seed was fixed to 123123. The run used 24 natural-language payloads of 4 to 9 tokens, 60 prompt keys, 40 payload-key pairs for correctness experiments, 16 transcripts for the collision search, 36 key pairs for the non-commutativity experiment, and 80 perturbation cases for the robustness experiment. Table 1 summarizes the experiments and their runtimes. 5.2. Experiment 1: Implementation Correctness Theorem 2 guarantees exact payload recovery under idealized deterministic assumptions, but this guarantee is only as strong as the implementation’s fidelity to those assumptions. In practice, subtle discrepancies in tokenization conventions, BOS token handling, numerical precision, or masking behavior could cause silent failures even when the mathematical proof is correct. This experiment verifies that the implementation realizes the theorem’s assumptions exactly under the tested configuration. For 4040 sampled payload-key pairs, we computed yi=Eki(xi)y_i=E_k_i(x_i), decoded x^i=Dki(yi) x_i=D_k_i(y_i), and verified x^i=xi x_i=x_i. We also tested the reverse direction, verifying Eki(Dki(yi))=yiE_k_i(D_k_i(y_i))=y_i. Table 2. Implementation correctness results. Check Successes Dk(Ek(x))=xD_k(E_k(x))=x 40/4040/40 Ek(Dk(y))=yE_k(D_k(y))=y 40/4040/40 Results. As shown in Table 2, exact recovery succeeded in all 40/4040/40 cases in both directions, confirming that the implementation correctly realizes the deterministic rank-transcoding mechanism under the tested Llama 3 8B configuration. 5.3. Experiment 2: Key-collisions and finite key search This experiment investigates key collisions via exhaustive search over a finite key set, which is the simplest possible attack on the promised context search problem (Problem 2). For the purpose of this experiment, we generated a finite admissible key set adm=k1,…,k60K_adm=\k_1,…,k_60\ containing 6060 prompt keys. The keys were constructed from a small set of natural-language seed prompts together with controlled local variants. The seed prompts covered mundane topics such as baking bread, mountain villages, forest animals, baseball practice, neutral product descriptions, and the phrase The quick brown fox jumps. From these seeds, we generated near-duplicate and template-style variants, including one-character typos, one-token deletions, plural or singular substitutions, punctuation changes, and short suffix additions. The composition of the resulting key set admK_adm is given in Table 3. Table 3. Composition of the finite admissible key set. Key category Count Seed or near-duplicate prompts 7 One-character typo variants 7 One-token deletion variants 7 Plural or singular variants 7 Punctuation variants 14 Short suffix variants 18 Total 60 We also used 1616 payload sequences ranging from 33 to 1010 tokens. These finite payload and key sets are not intended to represent the full space of possible natural-language prompts, but rather an initial, concrete and reproducible investigation of the collisions question. For each sampled payload rank vectors r and key k, we compute w=Fk(r)w=F_k(r), and then search over k∈admk _adm and compute the fiber adm(r,w)=k∈adm:Fk(r)=w ValidKeys_K_adm(r,w)=\k _adm:F_k(r)=w\, and its size μadm(r,w) _K_adm(r,w). By design, we always have μadm(ri,wi)≥1 _K_adm(r_i,w_i)≥ 1. Results. For all the 960960 finite-key evaluations (6060 keys and 1616 transcripts), the true key was contained in the candidate set in all 16/1616/16 cases, confirming consistency of the finite search. Furthermore, no key collisions were found: every tested transcript had candidate fiber size 11. Table 4 summarizes the results. Table 4. Finite key-collision search results. Quantity Value Finite key set size |adm||K_adm| 6060 Tested transcripts 1616 Finite-key evaluations 960960 Observed collisions 00 Largest candidate fiber 11 True-key containment 16/1616/16 The hand-crafted collision of Example 1 was not reproduced in this randomized finite-search run, which is consistent with the observation that this collision was constructed by deliberately exploiting subword tokenization nuances rather than discovered organically. This suggests that key collisions do not arise naturally under random key generation. A more extensive empirical study of collision frequency and structure, across larger key spaces and payload distributions, remains an interesting direction for future work. 5.4. Experiment 3: Collision stability across new payloads This experiment was designed to distinguish between key pairs producing local (one-off) collisions and key pairs producing global (multiple) collisions, thus providing stronger multi-payload key ambiguity. Namely, if a colliding key pair ka≠kbk_a≠ k_b satisfying Fka(r0)=Fkb(r0)F_k_a(r_0)=F_k_b(r_0) is found, then one can ask whether the equality persists on new payload rank vectors r1,…,rSr_1,…,r_S. In the present run, however, Experiment 2 in Section 5.3 found no colliding key pairs. We therefore turn to the hand-crafted collision found in Example 1, which our randomized study did not encounter in Experiment 2. Recall that the keys k1=The quick brown fox jumpsk_1= The quick brown fox jumps and k2=The quick brow fox jumpsk_2= The quick brow fox jumps were shown to collide on the rank message r=[1,1,1,1,1]r=[1,1,1,1,1]. We tested whether this collision persists across 99 additional length-55 rank vectors. Results. The collision was confirmed on r=[1,1,1,1,1]r=[1,1,1,1,1]: both keys produced the stegotext "over the lazy dog." under the tested environment. Of the 9 additional rank vectors tested, only r=[1,1,1,1,2]r=[1,1,1,1,2] also produced a collision; the remaining 8 did not. Given that the two keys diverged on most tested inputs, confirming the local nature of the collision, we did not extend the search further. This confirms that k1k_1 and k2k_2 form a local collision: they agree on specific inputs but do not induce the same map FkF_k globally, which is particularly surprising given how similar these two keys are. We note that the exact numeric value of w is environment-dependent: the value w=Fki(r)=[126444,1,3736,2,4]w=F_k_i(r)=[126444,1,3736,2,4] reported in Example 1 was obtained under a specific model checkpoint, whereas the present run produced w=[126166,1,4408,2,4]w=[126166,1,4408,2,4]. The collision phenomenon itself — that k1k_1 and k2k_2 agree on r=[1,1,1,1,1]r=[1,1,1,1,1] — is consistent across both environments. Table 5. Collision stability results for the hand-crafted key pair. Quantity Value Key pair tested k1,k2k_1,k_2 from Example 1 Rank vectors tested 1010 Collisions confirmed 22 (on [1,1,1,1,1][1,1,1,1,1] and [1,1,1,1,2][1,1,1,1,2]) Non-colliding inputs 88 Global collision No Interpretation. These results support the distinction introduced in Section 4.4.2 between local and global key collisions. The two keys agree on a small number of specific inputs, consistent with the tokenization structure that was deliberately exploited in Example 1, but diverge on most inputs. 5.5. Experiment 4: Non-commutativity of encoding maps This experiment empirically studies the commutativity question raised in Section 4.4.4. For sampled key pairs (k,h)(k,h) and payload rank vectors r1,…,rSr_1,…,r_S, we measure if the two compositions Fk(Fh(rj))andFh(Fk(rj))F_k(F_h(r_j)) F_h(F_k(r_j)) are equal or not. We also measure how much they differ, using the commutation metric D^log(k,h)=1S∑j=1Sdlog(Fk(Fh(rj)),Fh(Fk(rj))), D_ (k,h)= 1S _j=1^Sd_ (F_k(F_h(r_j)),F_h(F_k(r_j))), where dlogd_ denotes the normalized log-rank distance, given by dlog(u,v)=1n∑i=1n|log(1+ui)−log(1+vi)|log(1+N).d_ (u,v)= 1n _i=1^n | (1+u_i)- (1+v_i)| (1+N). This measures the normalized positional difference between two rank vectors, with logarithmic weighting so that differences among high-ranked tokens contribute less than differences among low-ranked tokens. Results. No commuting key pairs were found among the 36 tested pairs. The median commutation distance was 0.18130.1813, with empirical 5th and 95th percentiles 0.14240.1424 and 0.22370.2237. Intuitively, this means that swapping the order of two randomly chosen keys produces rank vectors that differ by roughly 18% of the maximum possible log-rank distance, confirming that the two compositions lead to substantially different stegotexts in practice. Table 6. Non-commutativity results for key-induced maps. Quantity Value Sampled key pairs 3636 Payload rank vectors per pair 88 Commuting pairs found 00 Median D^log D_ 0.18130.1813 5th percentile of D^log D_ 0.14240.1424 95th percentile of D^log D_ 0.22370.2237 Figure 2 shows the empirical CDF of the commutation distances. Figure 2. Metric non-commutativity of key-induced maps. Empirical CDF of D^log(k,h) D_ (k,h) over sampled key pairs. No exact sampled commuting pairs were observed; the nonzero distances show that the order of applying FkF_k and FhF_h generally changed the resulting rank vector in the tested sample. Interpretation. These results suggest that, in practice, the encoding maps EkE_k and EhE_h do not commute for randomly sampled key pairs. This is a favorable property from a security perspective, as it indicates that the instance-generation attack described in Section 4.4.4 is unlikely to be applicable in typical usage scenarios. 5.6. Experiment 5: Robustness to token perturbations This experiment studies the brittleness described in Remark 1, that is, whether small changes to the transmitted stegotext can disrupt exact decoding. For each generated stegotext y=Ek(x)y=E_k(x), we construct a perturbed stegotext y~ y in one of the following ways: (1) Random token substitution: one token position is selected and replaced by a different random admissible token. (2) Nearby-rank substitution: one token is replaced by a token selected from a nearby rank neighborhood under the local model ranking. (3) Adjacent-token transposition: adjacent tokens are swapped. (4) Punctuation-token substitution: one token is replaced by a punctuation-like token when such a replacement was available. We then decode x:=Dk(y)x:=D_k(y) and x~:=Dk(y~) x:=D_k( y) and compare them using the standard notion of normalized edit distance, as well as the suffix corruption fraction SuffixErrSuffixErr, which is given by SuffixErr=1n−jfirst+1∑j=jfirstn[xj≠x~j],SuffixErr= 1n-j_first+1 _j=j_first^n1[x_j≠ x_j], where jfirst=minj:xj≠x~jj_first= \j:x_j≠ x_j\ is the first mismatch position. Results. The robustness experiment shows that the base CARTS construction is highly sensitive to token perturbations. Across 8080 tested perturbations, decoding was corrupted in all cases. The average token edit distance between the original and corrupted decoded payload was 4.2004.200. Suffix corruption was total (namely, equal to 1.0001.000) in all perturbation types except adjacent-token transposition, which had average suffix corruption 0.9930.993. Table 7 summarizes the perturbation results by perturbation type. Table 7. Robustness results under stegotext perturbations. Perturbation type Avg. edit distance Avg. suffix corruption Random token substitution 3.953.95 1.0001.000 Nearby-rank substitution 3.803.80 1.0001.000 Adjacent-token transposition 4.604.60 0.9930.993 Punctuation-token substitution 4.454.45 1.0001.000 Interpretation. The results shown in Table 7 and Figure 3 confirm that CARTS provides exact invertibility under matched conditions, but is brittle to channel noise. This is consistent with the autoregressive error-propagation structure described in Remark 1. Robust variants would require additional error-correction mechanisms, and are left for future work. Figure 3. Decoded token edit distance grouped by perturbation type. All perturbation types consistently disrupted decoding. 5.7. Summary of empirical investigations The five experiments give a consistent empirical picture of the base CARTS protocol. Exact token-level recovery succeeded in all 40/4040/40 tested payload-key pairs, confirming that the implementation correctly realizes the deterministic rank-transcoding mechanism. The finite key-collision search found no collisions among 960960 evaluations, and the hand-crafted collision of Example 1 was confirmed to be local, persisting on only 2 out of 10 tested rank vectors. No commuting key pairs were found among the 36 tested pairs, suggesting that an instance-generation attack is unlikely to apply in practice. Finally, all 80 tested token perturbations corrupted decoding, confirming the autoregressive error-propagation structure described in Remark 1. Together, these results validate the formal framework introduced in Sections 3 and 4: CARTS provides exact, full-token-rate, deterministic keyed rank-transcoding, and the empirical evidence suggests that the construction is resistant to the specific attack vectors studied here. 6. Conclusion This paper introduced CARTS as a formal framework for keyed text-to-text rank-transcoding steganography, formalizing the Calgacus construction (Norelli and Bronstein, 2025) and establishing its exact correctness under deterministic model assumptions. Within this framework, we defined the computational problems naturally associated with the construction — context search, key collisions, message equivocation, and non-commutativity of key-induced maps — and studied their theoretical properties and empirical behavior, providing the first rigorous treatment of the security landscape of this promising but previously unstudied class of protocols. The experiments confirmed exact encoding-decoding recovery, found no key collisions under random key generation, established that the hand-crafted collision of Example 1 is local, and found no commuting key pairs, suggesting that the construction is resistant to the specific attack vectors studied here. A primary goal of this work is to open up this area for systematic investigation. On the theoretical side, the hardness of the context search problem, the asymptotic structure of collision fibers, the conditions under which commuting key pairs exist, and the design of more general CARTS transforms are all concrete open problems that follow naturally from the framework. On the empirical side, larger key spaces, more diverse payload distributions, and semantic quality metrics would give a more complete picture of the construction’s behavior. We hope the formal framework introduced here provides a solid foundation for the constructive use of autoregressive language models in steganography and privacy-preserving communication in general. References Alamati et al. (2020) N. Alamati, L. De Feo, H. Montgomery, and S. Patranabis Cryptographic group actions and applications. In International Conference on the Theory and Application of Cryptology and Information Security, p. 411–439. Cited by: §4.3. Anderson and Petitcolas (2002) R. J. Anderson and F. A. Petitcolas On the limits of steganography. IEEE Journal on selected areas in communications 16 (4), p. 474–481. Cited by: §2. Benčina et al. (2024) B. Benčina, A. Budroni, J. Chi-Domínguez, and M. Kulkarni Properties of lattice isomorphism as a cryptographic group action. In International Conference on Post-Quantum Cryptography, p. 170–201. Cited by: §4.4.4. Cachin (1998) C. Cachin An information-theoretic model for steganography. In Information Hiding, D. Aucsmith (Ed.), Lecture Notes in Computer Science, Vol. 1525, p. 306–318. External Links: Document, Link Cited by: §1, §2. Canales-Martínez and Santos (2025) I. A. Canales-Martínez and D. Santos Extracting some layers of deep neural networks in the hard-label setting. In International Conference on Cryptology and Information Security in Latin America, p. 399–421. Cited by: §1. Canetti et al. (1997) R. Canetti, C. Dwork, M. Naor, and R. Ostrovsky Deniable encryption. In Annual International Cryptology Conference, p. 90–104. Cited by: §4.3. Carlini et al. (2025) N. Carlini, J. Chávez-Saab, A. Hambitzer, F. Rodríguez-Henríquez, and A. Shamir Polynomial time cryptanalytic extraction of deep neural networks in the hard-label setting. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, p. 364–396. Cited by: §1. Couveignes (2006) J. Couveignes Hard homogeneous spaces. Cited by: §4.3. de Witt et al. (2022) C. S. de Witt, S. Sokota, J. Z. Kolter, J. Foerster, and M. Strohmeier Perfectly secure steganography using minimum entropy coupling. arXiv preprint arXiv:2210.14889. Cited by: §4.1. Ding et al. (2023) J. Ding, K. Chen, Y. Wang, N. Zhao, W. Zhang, and N. Yu Discop: provably secure steganography in practice based on “distribution copies”. In 2023 IEEE Symposium on Security and Privacy (SP), p. 2238–2255. Cited by: §4.1. Ducas and van Woerden (2022) L. Ducas and W. van Woerden On the lattice isomorphism problem, quadratic forms, remarkable lattices, and cryptography. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, p. 643–673. Cited by: §4.4.4. Dürmuth and Freeman (2011) M. Dürmuth and D. M. Freeman Deniable encryption with negligible detection probability: an interactive construction. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, p. 610–626. Cited by: §4.3. Gohr (2019) A. Gohr Improving attacks on round-reduced speck32/64 using deep learning. In Annual International Cryptology Conference, p. 150–179. Cited by: §1. Goodfellow et al. (2014) I. J. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio Generative adversarial nets. Advances in neural information processing systems 27. Cited by: Remark 3. Grattafiori et al. (2024) A. Grattafiori, A. Dubey, A. Jauhri, A. Pandey, A. Kadian, A. Al-Dahle, A. Letman, A. Mathur, A. Schelten, A. Vaughan, et al. The llama 3 herd of models. arXiv preprint arXiv:2407.21783. Cited by: §5.1. Hopper et al. (2002) N. J. Hopper, J. Langford, and L. von Ahn Provably secure steganography. In Advances in Cryptology - CRYPTO 2002, M. Yung (Ed.), Lecture Notes in Computer Science, Vol. 2442, p. 77–92. External Links: Document, Link Cited by: §1, §2. Kaptchuk et al. (2021) G. Kaptchuk, T. M. Jois, M. Green, and A. D. Rubin Meteor: cryptographically secure steganography for realistic distributions. In CCS ’21: 2021 ACM SIGSAC Conference on Computer and Communications Security, Virtual Event, Republic of Korea, November 15–19, 2021, Y. Kim, J. Kim, G. Vigna, and E. Shi (Eds.), p. 1529–1548. External Links: Link, Document Cited by: §1. Mantzaris et al. (2026) A. V. Mantzaris, W. Ghantous, H. Stinebrickner, S. Jahangiri, and S. Webinga Steganography with large language models: key sensitivity analysis. The International FLAIRS Conference Proceedings 39 (1). External Links: Link, Document Cited by: §1. Mitchell et al. (2023) E. Mitchell, Y. Lee, A. Khazatsky, C. D. Manning, and C. Finn Detectgpt: zero-shot machine-generated text detection using probability curvature. In International conference on machine learning, p. 24950–24962. Cited by: §4.1. Norelli and Bronstein (2025) A. Norelli and M. Bronstein LLMs can hide text in other text of the same length. External Links: 2510.20075, Link Cited by: §1, §1, §1, §2, §3.1, §6, Abstract.. Provos and Honeyman (2003) N. Provos and P. Honeyman Hide and seek: an introduction to steganography. IEEE security & privacy 1 (3), p. 32–44. Cited by: §2. Sadasivan et al. (2023) V. S. Sadasivan, A. Kumar, S. Balasubramanian, W. Wang, and S. Feizi Can ai-generated text be reliably detected?. arXiv preprint arXiv:2303.11156. Cited by: §4.1. Shen et al. (2020) J. Shen, H. Ji, and J. Han Near-imperceptible neural linguistic steganography via self-adjusting arithmetic coding. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), B. Webber, T. Cohn, Y. He, and Y. Liu (Eds.), Online, p. 303–313. External Links: Link, Document Cited by: §1, §2. Simmons (1984) G. J. Simmons The prisoners’ problem and the subliminal channel. In Advances in Cryptology: Proceedings of Crypto 83, p. 51–67. Cited by: §2. Wenger et al. (2022) E. Wenger, M. Chen, F. Charton, and K. E. Lauter Salsa: attacking lattice cryptography with transformers. Advances in Neural Information Processing Systems 35, p. 34981–34994. Cited by: §1. Wu et al. (2024) J. Wu, Z. Wu, Y. Xue, J. Wen, and W. Peng Generative text steganography with large language model. In Proceedings of the 32nd ACM International Conference on Multimedia, M 2024, Melbourne, VIC, Australia, 28 October 2024 - 1 November 2024, J. Cai, M. S. Kankanhalli, B. Prabhakaran, S. Boll, R. Subramanian, L. Zheng, V. K. Singh, P. César, L. Xie, and D. Xu (Eds.), p. 10345–10353. External Links: Link, Document Cited by: §1. Zhang et al. (2025) L. Zhang, Y. Yao, D. Shi, D. Chai, J. Guo, and Z. Wang Neural-inspired advances in integral cryptanalysis. arXiv preprint arXiv:2505.10790. Cited by: §1. Zhang et al. (2021) S. Zhang, Z. Yang, J. Yang, and Y. Huang Provably secure generative linguistic steganography. In Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021, p. 3046–3055. Cited by: §4.1. Ziegler et al. (2019) Z. Ziegler, Y. Deng, and A. Rush Neural linguistic steganography. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), K. Inui, J. Jiang, V. Ng, and X. Wan (Eds.), Hong Kong, China, p. 1210–1215. External Links: Link, Document Cited by: §1, §2.