Practical Linguistic Steganography Using Contextual Synonym Substitution and Vertex Colour Coding

Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, pages 1194–1203, MIT, Massachusetts, USA, 9-11 October 2010. c⃝2010 Association for Computational Linguistics Practical Linguistic Steganography using Contextual Synonym Substitution and Vertex Colour Coding Ching-Yun Chang University of Cambridge Computer Laboratory Ching-Yun.Chang@cl.cam.ac.uk Stephen Clark University of Cambridge Computer Laboratory Stephen.Clark@cl.cam.ac.uk Abstract Linguistic Steganography is concerned with hiding information in natural language text. One of the major transformations used in Lin- guistic Steganography is synonym substitu- tion. However, few existing studies have stud- ied the practical application of this approach. In this paper we propose two improvements to the use of synonym substitution for encod- ing hidden bits of information. First, we use the Web 1T Google n-gram corpus for check- ing the applicability of a synonym in context, and we evaluate this method using data from the SemEval lexical substitution task. Second, we address the problem that arises from words with more than one sense, which creates a po- tential ambiguity in terms of which bits are encoded by a particular word. We develop a novel method in which words are the vertices in a graph, synonyms are linked by edges, and the bits assigned to a word are determined by a vertex colouring algorithm. This method ensures that each word encodes a unique se- quence of bits, without cutting out large num- ber of synonyms, and thus maintaining a rea- sonable embedding capacity. 1 Introduction Steganography is concerned with hiding informa- tion in a cover medium, in order to facilitate covert communication, such that the presence of the infor- mation is imperceptible to a user (human or com- puter). Much of the existing research in steganog- raphy has used images as cover media; however, given the ubiquitous nature of electronic text, inter- est is growing in using natural language as the cover medium. Linguistic Steganography—lying at the in- tersection of Computational Linguistics and Com- puter Security—is concerned with making changes to a cover text in order to embed information, in such a way that the changes do not result in ungrammati- cal or unnatural text. A related area is natural language watermarking, in which changes are made to a text in order to iden- tify it, for example for copyright purposes. An inter- esting watermarking application is “traitor tracing”, in which documents are changed in order to embed individual watermarks. These marks can then be used to later identify particular documents, for ex- ample if a set of documents—identical except for the changes used to embed the watermarks— have been sent to a group of individuals, and one of the documents has been leaked to a newspaper. In terms of security, a linguistic stegosystem should impose minimum embedding distortion to the cover text so that the resulting stegotext in which a message is camouflaged is inconspicuous, result- ing in high imperceptibility. In addition, since steganography aims at covert communication, a lin- guistic stegosystem should allow sufficient embed- ding capacity, known as the payload. There is a fun- …

Content truncated to 500 words