Near-imperceptible Neural Linguistic Steganography via Self-Adjusting Arithmetic Coding (2020)

Abstract: Linguistic steganography studies how to hide secret messages in natural language cover texts. Traditional methods aim to transform a secret message into an innocent text via lexical substitution or syntactical modification. Recently, advances in neural language models (LMs) enable us to directly generate cover text conditioned on the secret message. In this study, we present a new linguistic steganography method which encodes secret messages using self-adjusting arithmetic coding based on a neural language model. We formally analyze the statistical imperceptibility of this method and empirically show it outperforms the previous state-of-the-art methods on four datasets by 15.3% and 38.9% in terms of bits/word and KL metrics, respectively. Finally, human evaluations show that 51% of generated cover texts can indeed fool eavesdroppers.

## introduction privacy is central to modern communication systems such as email services and online social networks. to protect privacy, two research fields are established: (1) cryptography which encrypts secret messages into codes such that an eavesdropper is unable to decrypt, and (2) steganography which encodes messages into cover signals such that an eavesdropper is not even aware a secret message exists @xcite @xcite . one useful cover signal for steganography is natural language text because of its prevalence and innocuity in daily life. traditional linguistic steganography methods are mostly edit-based, i.e., they try to directly edit the secret message and transform it into an innocent text that will not raise the eavesdropper's suspicious eyes. typical strategies include synonym substitution @xcite , paraphrase substitution @xcite , and syntactic transformation @xcite , applied to various text media such as email @xcite and twitter @xcite . although being able to maintain the grammatical correctness of output text, those edit-based methods cannot encode information efficiently. for example, the popular covertweet system @xcite can only encode two bits of information in each tweet on average. recent advances in neural language models (lms) @xcite @xcite have enabled a diagram shift from edit-based methods to generation-based methods which directly output a cover text by encoding the message reversibly in the choices of tokens. various encoding algorithms @xcite @xcite have been proposed to leverage neural lms to generate high-quality cover texts in terms of both fluency and information hiding capacity. however, most of the existing methods do not provide explicit guarantees on the imperceptibility of generated cover text (i.e., to what extent the cover text is indistinguishable from natural texts without hidden messages). one recent exception is the work @xcite ) which shows the imperceptibility of the method in @xcite . nevertheless, for other more advanced steganography methods @xcite , their imperceptibilities still remain unknown. in this work, we propose a new linguistic steganography method with guaranteed imperceptibility. our new method is built based on the previous study @xcite which views each secret message as a binary fractional number and encodes it using arithmetic coding @xcite with a pretrained neural lm. this method generates cover text tokens one at a time (c.f. fig. 2 ). at each time step t, it computes a distribution of the t-th token using the given lm; truncates this distribution to include only top k most likely tokens, and finally outputs the t-th token based on the secret message and the truncated distribution. in their study, this hyperparameter k is the same across all generation steps. we analyze this method's imperceptibility and show it is closely related to the selected k. specifically, increasing k will improve the method's imperceptibility at the cost of a larger probability of generating rarelyused tokens and slower encoding speed. when the cover text token distribution is flat and close to the uniform distribution, we need a large k to achieve the required imperceptibility guarantee. when the cover text token distribution is concentrated, we can use a small k to avoid generating rarely-used tokens and to increase encoding speed. as different generation steps will witness different underlying cover text token distributions, using a static k is clearly sub-optimal. to address this issue, we propose a new algorithm saac 2 which automatically adjusts k by comparing the truncated cover text token distribution with the original lm's output at each generation step and selects the minimal k that achieves the required imperceptibility. we theoretically prove the saac algorithm is nearimperceptible for linguistic steganography and empirically demonstrate its effectiveness on four datasets from various domains. furthermore, we conduct human evaluations via crowdsourcing and show 51% of cover texts generated by saac can indeed fool eavesdropper. contributions. this study makes the following contributions: (1) we formally analyze the imperceptibility of arithmetic coding based steganogra- ## self-adjusting arithmetic coding in this section, we first introduce the general arithmetic coding and discuss its practical limitations. we then present saac, a self-adjusting arithmetic coding algorithm and analyze its imperceptibility. ## related work early steganography methods @xcite use image and audio as the cover signal because they have a high information theoretic entropy. however, sending an image or audio recording abruptly though a public channel will likely cause the eavesdropper's suspicion. thus, linguistic steganography methods are proposed to leverage text as the cover signal because natural language is prevalent and innocuous in daily life. linguistic steganography methods can be categorized into two types, edit-based or generationbased @xcite . edit-based methods try to directly edit the secret message and transform it into an innocent text. typical transformations are synonym substitution @xcite , paraphrase substitution @xcite , and syntactic transformation @xcite . instead of editing all words in the secret message, @xcite take an entity-oriented view and focus on encoding/decoding morphs of important entities in the message. finally, some work @xcite allows human agents to assist the cover text generation process. one major limitation of edit-based methods is that they cannot encode information efficiently. @xcite show the popular cover-tweet system @xcite can encode only two bits information in each transformed tweet on average. to address this limitation, generationbased methods try directly output the cover text based on the secret message. early study @xcite utilizes a generative grammar to output the cover text. more recently, people leverage a neural language model for linguis-tic steganography. one pioneering work by @xcite divides the message bits into equalsize blocks and encodes each block using one cover text token. @xcite improves the above method by constructing a huffman tree and encoding the message in variable length chunks via a huffman tree. (dai and cai, 2019) presents the first theoretical analysis of the above two methods and proposes a modified huffman algorithm. the method most related to this study is @xcite where the arithmetic coding algorithm is introduced for steganography. in this study, we present a more formal analysis of arithmetic coding based steganography method and propose a better self-adjusting algorithm to achieve the statistical imperceptibility. ## discussions and future work this work presents a new linguistic steganography method that encodes secret messages using selfadjusting arithmetic coding. we formally prove this method is near-imperceptible and empirically show it achieves the state-of-the-art results on various text corpora. there are several directions we will further explore in the future. first, we may combine the edit-based steganography with generative steganography method by first transforming the original plaintext in a semantics-preserving way and then encoding the transformed plaintext. second, we will study whether this current method is still effective when a small-scale neural lm (e.g., distilgpt-2) is applied. finally, this study assumes a passive eavesdropper who does not modify the transmitted cover text. adapting the current methods to be robust to an active eavesdropper who may alter the cover text is another interesting direction.