the debugger with the result that it is possible to overwrite any existing mark and replace it with another one.
Exhaustive search for the personal code can be prevented without difficulty, but there is no obvious solution to the disassembly attack. If tamper resistant software  can- not give enough protection, then one can always have an online system in which each user shares a secret stego-key with a trusted party and uses this key to embed some kind of digital signature. Observe that there are two separate keyed operations here; the authentication (such as a digital signature) and the embedding or hiding operation.
Although we can do public key steganography – hiding information using a public key so that only someone with the corresponding private key can detect its existence 
we still do not know how to do the hiding equivalent of a
digital signature; that is, to enable someone with a private key to embed marks in such a way that anyone with the corresponding public key can read them but not remove them. Some attempts to create such watermarks can be found in . But unless we have some new ideas, we appear compelled to use either a central ‘mark reading’ service or a tamper-resistant implementation, just as cryp- tography required either central notarisation or tamper- evident devices to provide a non-repudiation service in the days before the invention of digital signatures.
However, there is one general attack on tamper-resistant mark readers due to Cox et al. . The idea is to ex- plore, pixel by pixel, an image at the boundary where the detector changes from ‘mark absent’ to ‘mark present’ and iteratively construct an acceptable image in which the mark is not detected. Of course, with a programmable tamper- proof processor, one can limit the number of variants of a given picture for which an answer will be given, and the same holds for a central mark reading service. But in the absence of physically protected state, it is unclear how this attack can be blocked.
V. A basic theory of steganography
This leads naturally to the question of whether we can develop a comprehensive theory of information hiding, in the sense that Shannon provided us with a theory of se- crecy systems  and Simmons of authentication sys- tems . Quite apart from intellectual curiosity, there is a strong practical reason to seek constructions whose secu- rity is mathematically provable. This is because copyright protection mechanisms may be subjected to attack over an extraordinarily long period of time. Copyright subsists for typically 50–70 years after the death of the artist, depend- ing on the country and the medium; this means that mech- anisms fielded today might be attacked using the resources available in a hundred years’ time. Where cryptographic systems need to provide such guarantees, as in espionage, it is common to use a one-time pad because we can prove that the secrecy of this system is independent of the com- putational power available to the attacker. Is it possible to get such a guarantee for an information hiding system?
A. Early results
An important step in developing a theory of a subject is to clarify the definitions. Intuitively, the purpose of ste- ganography is to set up a secret communication path be- tween two parties such that any person in the middle can- not detect its existence; the attacker should not gain any information about the embedded data by simply looking at cover-text or stego-text. This was first formalised by Sim- mons in 1983 as the ‘prisoners’ problem’ . Alice and Bob are in jail and wish to prepare an escape plan. The problem is that all their communications are arbitrated by the warden Willie. If Willie sees any ciphertext in their messages, he will frustrate them by putting them into soli- tary confinement. So Alice and Bob must find a way to exchange hidden messages.
Simmons showed that such a channel exists in certain digital signature schemes: the random message key used in these schemes can be manipulated to contain short mes- sages. This exploitation of existing randomness means that the message cannot even in principle be detected and so Simmons called the technique the ‘subliminal channel’. The history of the subliminal channel is described in , while further results may be found in , , , .
In the general case of steganography, where Willie is al- lowed to modify the information flow between Alice and Bob, he is called an active warden; but if he can only observe it he is called a passive warden. Further studies showed that public key steganography is possible (in this model, Alice and Bob did not exchange secrets before go- ing to jail, but have public keys known to each other) – although the presence of an active warden makes public key steganography more difficult .
This difficulty led to the introduction, in , of the supraliminal channel, which is a very low bandwidth chan- nel that Willie cannot afford to modify as it uses the most perceptually significant components of the cover object as a means of transmission. For example, a prisoner might write a short story in which the message is encoded in the succes- sion of towns or other locations at which the action takes place. Details of these locations can be very thoroughly woven into the plot, so it becomes in practice impossible for Willie to alter the message – he must either allow the message through or censor it. The effect of this technique is to turn an active warden into a passive one. The same effect may be obtained if the communicating parties are allowed to use a digital signature scheme.
B. The general role of randomness
Raw media data rates do not necessarily represent infor- mation rates. Analog values are quantised to n bits giving, for instance, a data rate of 16 bit/sample for audio or 8 bit/pixel for monochrome images. The average informa- tion rate is given by their entropy; indeed, the entropy of monochrome images is generally around 4–6 bits per pixel. This immediately suggests the use of this difference to hide information. So if C is the cover-text and E the embed- ded text, transmitted on a perfect n bit channel, one would