Authors: Neil Perry and Sanket Gupte and Nishant Pitta and Lior Rotem
Cite as: \cite{perry2025robust}
arXiv: https://arxiv.org/abs/2504.08977
Summary in three sentences
This paper studies robust steganography: hidden communication that survives realistic changes to the covertext. It defines weak robustness against local edits and strong robustness against semantically preserving paraphrases, then proposes two LLM-based constructions. The work is directly useful for our robustness axis because it clarifies what it means for paraphrasing to remove or fail to remove a hidden channel.
Main contribution
The main contribution is a formal robustness framework plus implemented constructions that preserve recoverability under covertext modification. Unlike most safety-evaluation papers, this paper is primarily cryptographic: it tries to build robust stegosystems rather than evaluate whether ordinary prompted agents discover or use them.
Key equations and definitions
- Weak threat model: local tampering functions preserve at least an fraction of -length substrings.
- The paper writes the local consistency family as:
- Strong threat model: the adversary may paraphrase while preserving semantic proximity, expressed as .
- Symmetric-key steganography is a tuple over a covertext channel.
Empirical results
The introduction reports that the watermarking-based system survives most attack classes even when up to 20% of covertext is modified, with approximately 90% or higher recovery. It also reports that the embedding-based scheme survives up to 50% covertext modifications while requiring 100x fewer covertext tokens per hidden bit, and costs under 1 cent per hidden byte on average. Table 1 reports LSH scheme tests over 20 trials of hiding 1 byte: Random has 100% success at 0.7 cents per byte total cost, while PCA has 95% success at 0.85 cents per byte total cost.
Relation to our project
- what we reuse: definitions for paraphrase robustness, the distinction between local edits and semantic paraphrase, and the idea that rewording attacks should preserve visible utility.
- what we dispute: the constructions assume explicit stegosystem design and shared keys; our first benchmark tests what black-box prompted models can use inside ordinary task outputs.
- what we must reproduce: a paraphrase condition that tests whether hidden information survives meaning-preserving rewrites without destroying the visible task.
Criticism and limitations
The work is not an LLM safety benchmark and does not answer whether models autonomously choose these channels. Its assumptions about keys, embeddings, and engineered constructions may be too strong for a first prompt-only evaluation. Still, it is the best formal source for making our robustness axis precise.