The Secret’s in the Word Order: Text-to-Text Generation for Linguistic Steganography

Proceedings of COLING 2012: Technical Papers, pages 511–528, COLING 2012, Mumbai, December 2012. The Secret’s in the Word Order: Text-to-Text Generation for Linguistic Steganography Ching − Yun Chang1 Stephen Clark1 (1) University of Cambridge, Computer Laboratory, 15 JJ Thomson Avenue, Cambridge, UK Ching-Yun.Chang@cl.cam.ac.uk, Stephen.Clark@cl.cam.ac.uk ABSTRACT Linguistic steganography is a form of covert communication using natural language to conceal the existence of the hidden message, which is usually achieved by systematically making changes to a cover text. This paper proposes a linguistic steganography method using word ordering as the linguistic transformation. We show that the word ordering technique can be used in conjunction with existing translation-based embedding algorithms. Since unnatural word orderings would arouse the suspicion of third parties and diminish the security of the hidden message, we develop a method using a maximum entropy classifier to determine the naturalness of sentence permutations. The classifier is evaluated by human judgements and compared with a baseline method using the Google n-gram corpus. The results show that our proposed system can achieve a satisfactory security level and embedding capacity for the linguistic steganography application. KEYWORDS: linguistic steganography, word ordering, surface realisation. 511 1 Introduction Linguistic steganography is a form of covert communication using natural language to conceal the existence of the hidden message so that the very act of communication is undetectable to an outside observer (human or computer) (Fridrich, 2009). In other words, the covert communication would fail if an outside observer is suspicious of the existence of the hidden message. Note that the outside observer here is not the recipient; the recipient needs to expect to receive a hidden message in order to extract it. (Consider the scenario of covert communication between political activists, where the observer is a government “listening” agency, for example.) In order to embed messages, a cover text must provide information carriers that can be modified to represent the secret. For example, a lexical substitution-based stegosystem substitutes selected words (the information carriers) with their synonyms so that the concatenation of the bitstrings represented by the synonyms is identical to the secret. Note that an unmodifiable text cannot carry information. Ideally the changes made to the text must be imperceptible, resulting in a high security level. In addition, an ideal linguistic steganography scheme should allow sufficient embedding capacity to achieve efficient information transmission, resulting in a large payload capacity. There is a fundamental trade-off between security and payload since any attempt to embed additional information is likely to increase the chance of introducing anomalies into the text, thus degrading the security level. Existing studies have exploited different linguistic transformations for the application of steganography, such as lexical substitution (Chapman and Davida, 1997; Bolshakov, 2004; Taski- ran et al., 2006; Topkara et al., 2006c; Chang and Clark, 2010b), phrase paraphrasing (Chang and Clark, 2010a), sentence structure manipulations (Atallah et al., 2001a,b; Liu et al., 2005; Meral et al., 2007; Murphy, 2001; Murphy and Vogel, 2007b; Topkara et al., 2006b), semantic transformations (Atallah et al., 2002; Vybornova and Macq, 2007) …

Content truncated to 500 words