Adjective Deletion for Linguistic Steganography and Secret Sharing

Proceedings of COLING 2012: Technical Papers, pages 493–510, COLING 2012, Mumbai, December 2012. Adjective Deletion for Linguistic Steganography and Secret Sharing 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 This paper describes two methods for checking the acceptability of adjective deletion in noun phrases. The first method uses the Google n-gram corpus to check the fluency of the remaining context after an adjective is removed. The second method trains an SVM model using n-gram counts and other measures to classify deletable and undeletable adjectives in context. Both methods are evaluated against human judgements of sentence naturalness. The application motivating our interest in adjective deletion is data hiding, in particular linguistic steganography. We demonstrate the proposed adjective deletion technique can be integrated into an existing stegosystem, and in addition we propose a novel secret sharing scheme based on adjective deletion. KEYWORDS: linguistic steganography, adjective deletion. 493 1 Introduction Linguistic steganography is a form of covert communication in which information is embedded in a seemly innocent cover text so that the presence of the information is imperceptible to an outside observer (human or computer) (Fridrich, 2009). An ideal linguistic stegosystem should fulfil two fundamental requirements: high imperceptibility and high payload capacity. The former aims at imposing minimum embedding distortion to the cover text so that the resulting stegotext in which a message is camouflaged is inconspicuous. The latter aims at providing sufficient embedding capacity in order to achieve efficient information transmission. There is a trade-off between imperceptibility and payload, since any attempt to embed additional information via changes to the cover text increases the chance of introducing anomalies into the text and thus raising the suspicion of an observer (Chang and Clark, 2010a). Another cryptographic method is secret sharing. Secret sharing (Blakley, 1979; Shamir, 1979) refers to methods for distributing a secret amongst a group of n people, each of whom is allocated a share of the secret. Individual shares are of no use on their own; only when any group of t (for threshold) or more shares are combined together can the secret be reconstructed. Such a system is called a (t, n)-threshold scheme. For example, a simple (3,3)-threshold scheme for a secret number s can be achieved by splitting s into three numerical shares s1, s2 and s3 such that s = s1 + s2 + s3. Note that there is no way to recover the secret number by only using one or two of the shares; all shares are required for effective recovery. There are some proposed (t, n)-threshold schemes where t ̸= n. For example, Shamir’s scheme (Shamir, 1979) allows that any t out of n shares may be used to recover the secret. This scheme relies on the idea that it takes t points to define a polynomial of degree t-1 (e.g. it takes two points to define a straight line, three points to define a quadratic, four points to define a cubic curve). …

Content truncated to 500 words