Towards Near-imperceptible Steganographic Text

Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 4303–4308 Florence, Italy, July 28 - August 2, 2019. c⃝2019 Association for Computational Linguistics 4303 Towards Near-imperceptible Steganographic Text Falcon Z. Dai Toyota Technological Institute at Chicago Chicago, USA dai@ttic.edu Zheng Cai Department of Computer Science University of Colorado Boulder, CO, USA jon.z.cai@colorado.edu Abstract We show that the imperceptibility of sev- eral existing linguistic steganographic systems (Fang et al., 2017; Yang et al., 2018) re- lies on implicit assumptions on statistical be- haviors of fluent text. We formally analyze them and empirically evaluate these assump- tions. Furthermore, based on these obser- vations, we propose an encoding algorithm called patient-Huffman with improved near-imperceptible guarantees. 1 Introduction In recent years, we see many exciting develop- ments in applied machine learning and, in partic- ular, its application in the fundamental problem of language modeling (Sutskever et al., 2011; Joze- fowicz et al., 2016) in the field of natural language processing (NLP). However, these advancements can be exploited by computationally resourceful entities such as a surveillance state to effectively monitor its citizens’ ostensibly private communi- cations at scale. We are motivated to study the communication privacy problem of concealing sensitive messages in monitored channels. In order to avoid rais- ing suspicion in the monitoring party, we want to hide the intended message inside a fluent message, known as a stegotext, indistinguishable from what is expected in such channels. This is a problem studied primarily in steganography and steganog- raphy researchers have a keen interest in linguis- tic steganography as it presents fundamental chal- lenges (Chang and Clark, 2014); the linguistic channel carries few bits per symbol on average (Shannon, 1951; Brown et al., 1992) making it hard to hide a message. In contrast, images and sound recordings have a high information theo- retic entropy comparing to a written message mak- ing it relatively easy to embed a message in the noise floor of the channel. This problem of hiding secret messages in plain sight might evoke spy stories of concealing mes- sages on newspaper advertisements during Cold War. Such manual methods have been superseded by algorithmic approaches. Classic methods prior to the advance of applied machine learning in this domain typically try to produce grammatical English with generative grammar (Chapman and Davida, 1997). However, such generation meth- ods fall short in terms of statistical imperceptibil- ity (Meng et al., 2008). This makes them vulnera- ble to automated detection. Generating fluent1 text at scale is at the heart of the steganography prob- lem, and language models (LM) studied in NLP provide a natural solution by letting us draw sam- ples of fluent texts. At the working heart of a LM-based stegosys- tem, there lies an encoding algorithm that en- codes a ciphertext (a random string indistinguish- able from a series of fair coin flips) into a fluent stegotext using an LM. From the communication standpoint, this encoding must be uniquely decod- able, i.e. different ciphertext are encoded into dif- ferent stegotexts otherwise …

Content truncated to 500 words