Natural Language Steganography

The problem of central control and monitoring of communication is not new to history. What is new to history, is that we now rely heavily upon electronic means of communication. The fact that these infrastructures do not, by design, rule out the possibility of automated large-scale censorship, is dangerous in itself. However, the fact that we can now watch the necessary legislative and technical infrastructures being deployed should be highly alarming. Clearly the topic of steganography is more important today, than ever before.

Steganographic systems provide a secure medium to covertly transmit information in the presence of an arbitrator. In natural language steganography, in particular, machine-readable data is to be encoded to innocuous natural language text, thereby providing security against any arbitrator tolerating natural language as a communication medium.

We give detailed insights to the construction of a stegosystem that can embed a secret bitstring into an innocuous piece of natural language text. Furthermore we demonstrate, from a linguistic point of view, some interesting features of natural language, that allow the construction of linguistic stegosystems that are secure under the assumption that the arbitrator is a computer and not a human.

From these specific features of natural language, we will turn to the more general notion of the ``AI-complete security primitive, which is a problem we assume to be hard, in a cryptographic context, much like the NP-complete problems used for current numeric cryptography techniques.

Finally, it should be noted that the research presented herein is in a very early conceptual stage. However the topics outlined point out an exciting new direction of research in steganography and related fields and might give some inspiration for new creative uses of computer technology.