Matryoshka: Hiding Secret Communication in Plain Sight

Matryoshka achieves an average covert rate of ~3 bits/word after human enhancement; for a 5-word hidden message averaging 5.5 characters per word, the final enhanced stegotext is approximately 73 words. This is roughly 10× the covert rate of Spammimic (~0.3 bits/word), the prior leading approach.

§5 evaluation ml-classifier generic

After crowdsourced (MTurk) enhancement, 88% of stegotexts on average pass a One-Class SVM trained on 150K sentences from Wikipedia, Brown, and Reuters corpora as natural language; pre-enhancement, only 25–58% pass. For calibration, the same classifier correctly rejects 97% of randomly generated sentences as non-natural-language.

§5 evaluation ml-classifier generic

A mixed Huffman codebook combining character-level coding with explicit entries for the 300 most frequent English words (covering ~65% of written material) achieves a 52% compression ratio on average across 4,825 sentences of 4–15 words—7 percentage points better than a character-only alphabet—directly increasing the covert bits available per output word.

§3.1 defense generic

Users required 4.0–5.8 minutes on average to enhance a stegotext into natural language across three experiments, inserting 4–8 extra words per sentence; this is comparable to the time required to write a short email. The random-word-selection baseline consistently required more time and inserted more words, confirming that n-gram-guided word choice meaningfully reduces human editing burden.

§5 evaluation ml-classifier generic

The Viterbi-based probabilistic decoder achieves zero character error rate on 96%, 93%, and 95% of decoded messages across the three corpora experiments (dreams, animals, facebook). For the small fraction of failures, only 15% of characters on average were corrupted rather than total message loss.

§5 evaluation generic