PaperlayerView exact revision on arXiv

Source-linked AI summary

CARTS: Contextual Autoregressive Rank Transcoding Steganography for Full-Capacity Keyed Text Encoding

Wissam Ghantous, Alexander V. Mantzaris

arXiv:2609.10744v1cs.CRcs.AIcs.LG

TL;DR

CARTS addresses the lack of formal security analysis for a language-model construction that transforms payload text into same-length stegotext. The paper formalizes the construction and its security problems, proving exact correctness under deterministic assumptions and finding exact recovery, no random-generation key collisions, local hand-crafted collisions, and no commuting key pairs in the reported experiments.

  • Problem

    The Calgacus construction had been demonstrated experimentally, but lacked formal security definitions, analysis, and identified underlying computational problems.

  • Method

    The paper formalizes CARTS as keyed rank-transcoding steganography, represents keys as rank-space bijections, and studies context search, key collisions, message equivocation, and non-commutativity.

  • Results

    Exact token-level recovery succeeded in 40/40 tested payload-key pairs; random key-collision search found none in 960 evaluations, and no commuting key pairs were found among 36 tested pairs.

  • Takeaways & Limitations

    The work provides a formally grounded security landscape and research agenda for constructive language-model use in cryptography and privacy-preserving communication.

  • Takeaways & Limitations

    Correctness relies on deterministic matching between encoder and decoder, while the generalized construction can produce unnatural text when rank transformations disrupt rank magnitude or local statistics.

Abstract

from arXiv · show

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.

1 Introduction

CARTS formalizes a language-model steganography method that transforms payload text into same-length stegotext, addressing the absence of formal security analysis for the experimentally demonstrated Calgacus construction.

  • The approach places language-model steganography within broader work connecting artificial intelligence and cybersecurity, including cryptographic attacks on models and machine-learning-assisted cryptanalysis.
  • Calgacus differs from conventional linguistic steganography by transforming the payload itself into a new meaningful text rather than modifying a fixed cover object.
  • The construction had previously been demonstrated experimentally without concrete security definitions or identification of the computational problems underlying its security properties.
  • CARTS names a methodology that uses a payload sentence, secret context or prompt, and fixed autoregressive model to produce a same-token-length sentence.Decoding with the same key deterministically recovers the original payload.
  • This paper formalizes CARTS and Calgacus, defines security notions and associated computational problems, and studies their theoretical relationships.

2 Conceptual Framework

Classical linguistic steganography hides payloads by modifying or generating a cover text, whereas CARTS deterministically transforms the payload into an unrelated natural-language text that serves as the cover.

  • Conventional steganography begins with a cover object and embeds a secret payload, while CARTS eliminates the separate cover object by making the transformed message the covertext.
  • Classical linguistic methods modify existing text, whereas neural methods generate text under constraints that encode a secret.
  • CARTS uses a natural-language token sequence as the payload, enabling a full-capacity text-to-text transformation rather than low-rate bit encoding.

3 CARTS protocol

The CARTS protocol represents autoregressive token sequences by context-dependent rank traces and generates stegotext from transformed ranks, yielding exact invertibility under deterministic shared-model assumptions.

  • The standard protocol: A rank trace records token ranks left to right while updating context, and the rank generator reconstructs tokens by selecting each prescribed current rank.
  • The standard protocol: Rank-trace inversion establishes that measuring a token’s rank and selecting that rank are inverse operations under the same deterministic context updates.
  • The standard protocol: The standard protocol requires identical tokenization, vocabulary, prompt serialization, model weights, masking, numerical precision, and tie-breaking at encoder and decoder.If any of these differ, correctness may fail.
  • The standard protocol: The protocol is generally not robust to token edits: a single changed token can alter the decoded suffix because autoregressive contexts diverge.The paper leaves redundancy, synchronization, and error correction for future work.
  • Generalized two-context rank transforms: The base Calgacus construction reads the payload rank trace under the empty context and generates stegotext under the key context, while the generalized form supports two contexts and rank bijections.
  • Generalized two-context rank transforms: The generalized construction preserves exact invertibility for every bijection on rank-vector space, although arbitrary transformations can degrade fluency and semantic coherence.Transformations that map low ranks to substantially larger ranks may force improbable token choices.

4 Security assumptions and protocol properties

The paper studies security properties of CARTS by formalizing message equivocation, key collisions, key commutativity, and related computational problems.

  • The security analysis formalizes message equivocation, key collisions, and key commutativity, then examines their relationships and implications for CARTS security.

4.1 Scope and adversarial model

The paper sets aside classical distributional indistinguishability and studies security properties arising from CARTS’s rank-transcoding structure. Its primary formal adversarial model gives attackers known payload–stegotext pairs while the model and protocol family remain public.

  • The analysis targets equivocation, key collisions, context search, and non-commutativity rather than the established question of stegotext distributional indistinguishability.These properties are presented as specific to CARTS’s rank-transcoding structure.
  • The sender and receiver share a secret context key and fixed autoregressive model, transforming a payload into an equal-length stegotext that the receiver can deterministically recover.
  • The adversary knows the protocol family, tokenizer, and model, with access ranging from ciphertext-only observation to known- and chosen-plaintext interactions.
  • The formal analysis focuses primarily on the known-plaintext setting, where attackers observe payload–stegotext pairs under a fixed unknown key.

4.2 The rank-coordinate notation

The rank-coordinate formulation represents Calgacus transformations as maps on rank-vector space, eliminating ambiguity between token sequences and their rank representations. Under each fixed key, the resulting map is bijective, and key composition induces composition of these maps.

  • The map F_k converts a payload’s empty-context rank representation into the resulting stegotext’s empty-context rank representation.
  • For every fixed key k, F_k is a bijection on rank-vector space X^n.
  • The conjugacy identity expresses F_k through the token-level encoding map E_k and the rank-coordinate conversions at empty context.
  • Composing two encoding maps corresponds to composing their rank-space maps because the rank conversion maps cancel through R_∅ ◦ G_∅ = id_X^n.
  • A key-coordinate vector q is only a rank representation of a token-context key, so collisions concern distinct contexts rather than coordinate vectors themselves.

4.3 Definitions and Computational Problems

This section defines message equivocation and related search problems for CARTS, including context search, key collisions, pre-image search, and restricted-support variants. It also identifies important boundary conditions: some problems may have no solution, and allowing the empty key can make several tasks trivial.

  • The framework defines full and weak ℓ-message equivocation, including restricted-support versions over prescribed payload, stegotext, and key subsets.
  • Message equivocation formalizes deniability by allowing multiple payload interpretations of one observed stegotext under different keys.
  • Equivocation’s practical protection depends on context: it may be limited under coercion but meaningful where procedural safeguards prevent attribution from a possible incriminating interpretation.
  • The computational problems require a finite admissible key set or explicit key-generation distribution and search budget; otherwise search over all contexts is not a finite task.
  • Context search asks for a key transporting one rank vector to another, while key collision search asks for distinct keys producing the same output from one rank vector.
  • Some context-search and equivocation problems may have no solution for an arbitrary CARTS protocol, and partial search is no harder than unconditional search.
  • Allowing the empty key makes pre-image search trivial because F_∅(r)=r, so nontrivial equivocation requires constraints such as nonempty keys or plausible payloads.
  • The rank-coordinate representation is specific to the Calgacus instantiation, while the underlying computational problems can be defined directly from encoding and decoding maps.

4.4 Security Properties of the Protocol

The paper characterizes message equivocation, key collisions, context search, and non-commutativity through rank-coordinate maps, revealing exact theoretical relationships and finite-cardinality trade-offs.

  • 4.4.1 Message Equivocation: Full message equivocation is equivalent to solving unconditional context search for every input and output rank vector.The equivalence follows by expressing payloads and stegotexts in rank coordinates and requiring a key with F_k(r)=w.
  • 4.4.1 Message Equivocation: Weak ℓ-message equivocation is equivalent to solving unconditional partial ℓ-context search for every output rank vector.The condition requires ℓ distinct payload rank vectors and keys that map each to the same output.
  • 4.4.2 Key collision: A single transcript with multiple valid keys prevents information-theoretic key identification, though further transcripts or side information can shrink the candidate set.Collision multiplicity distinguishes unreachable outputs, uniquely identifiable keys, and ambiguous key candidates.
  • 4.4.2 Key collision: Experiments found preliminary collisions unlikely under random key generation, while a hand-crafted collision arose from tokenization nuances and was not reproduced in randomized search.The authors characterize the constructed collision as local rather than evidence of global key ambiguity.
  • 4.4.3 Finite cardinality effects: A collision makes the fixed-input key map non-injective and therefore leaves at least one output unreachable, although the colliding output has multiple keys.For finite equal-cardinality domains, injectivity, surjectivity, unique reachability, and collision-freedom are equivalent.
  • 4.4.3 Finite cardinality effects: Key-space size determines reachability: shorter-than-message spaces miss outputs, whereas longer-than-message spaces force collisions by cardinality.When the effective key-space size equals the output-space size, collision-freedom and full reachability coincide.
  • 4.4.4 Non-commutativity: The framework leaves commutativity largely open theoretically and treats it experimentally, with further study of commuting keys and recovery implications deferred.Additional observations of commuting-key outputs could reduce the hardness of recovering the secret key.

5 Empirical Explorations

Five experiments on Llama 3 8B validate exact rank-transcoding under matched conditions and examine collisions, collision stability, map non-commutativity, and perturbation robustness. The results show exact recovery, no collisions in randomized finite searches, local rather than global crafted collisions, non-commuting maps, and strong sensitivity to token edits.

  • 5.2 Experiment 1: Implementation Correctness: Exact recovery succeeded in all 40/40 payload-key pairs in both directions under the tested Llama 3 8B configuration.The experiment verified both D_k(E_k(x)) = x and E_k(D_k(y)) = y.
  • 5.3 Experiment 2: Key-collisions and finite key search: No key collisions appeared in 960 finite-key evaluations, with the true key recovered in all 16/16 candidate searches.Every tested transcript had candidate fiber size 1.
  • 5.4 Experiment 3: Collision stability across new payloads: The hand-crafted collision persisted on only 2 of 10 tested rank vectors, confirming that the similar keys collide locally rather than inducing the same map globally.The keys agreed on the original vector and one additional vector, but diverged on the remaining eight.
  • 5.5 Experiment 4: Non-commutativity of encoding maps: No commuting key pairs were found among 36 tested pairs; the median commutation distance was 0.1813.The reported 5th and 95th percentiles were 0.1424 and 0.2237, respectively.
  • 5.6 Experiment 5: Robustness to token perturbations: All 80 token perturbations corrupted decoding, showing that the base protocol is highly sensitive to stegotext edits.Average token edit distance was 4.200, and suffix corruption was 1.000 for every perturbation type except adjacent-token transposition, which averaged 0.993.
  • 5.7 Summary of empirical investigations: Together, the experiments support exact deterministic full-token-rate transcoding and suggest resistance to the specific attack vectors studied.The empirical evidence covers recovery, collisions, non-commutativity, and perturbation behavior under the tested configuration.

6 Conclusion

The paper formalizes CARTS, establishes exact recovery, and evaluates its security landscape theoretically and empirically. It also identifies open problems and positions the framework as a foundation for privacy-preserving communication.

  • CARTS formalizes keyed text-to-text rank-transcoding steganography, establishes exact correctness under deterministic models, and provides the first rigorous treatment of its security landscape.
  • Experiments confirmed exact recovery, found no random-generation key collisions or commuting key pairs, and showed a hand-crafted collision was local.
  • Open problems include context-search hardness, collision-fiber structure, commuting-key conditions, broader transforms, larger key spaces, diverse payloads, and semantic quality metrics.
  • The framework is intended to support constructive uses of autoregressive language models in steganography and privacy-preserving communication.
Loading 2609.10744v1…