by Ann Lewis

Consider the following problem. Alice and Bob are prisoners who are allowed to communicate via e-mail; they wish to use this communication channel to make escape plans. Unfortunately, the prison warden, Ward, monitors the email between prisoners and if he detects the slightest evidence that Alice and Bob are planning an escape, he will throw them in solitary confinement. So Alice and Bob need to communicate secretly, without appearing to do so. They need to use steganography.

Steganography, literally meaning, covered writing", refers to the task of communicating secret messages over a publicly observable channel in a way which conceals the very existence of a message. A recent paper by Hopper, Langford and von Ahn gives the first steganographic protocols which have rigorous proofs of security. The authors show several constructions and prove that if certain cryptographic primitives exist, then these constructions can be instantiated by steganographically secure protocols. These protocols are also unusual in that they are the first known protocols (provably secure or not) that can hide information in unformatted, plain text. An important application of these protocols is as proofs of authorship. Anyone who hides information in a text using these protocols can later prove authorship of that text using zero knowledge proofs of knowledge. Thus these protocols can be used to protect intellectual property in both academic and corporate settings. The embedding performed by these protocols is the result of an > interactive process between the stegosystem and a user. So any implementation will require an interactive environment such as a text editor. We have chosen XEmacs.