This method for data hiding is a generalization of DCT coefficients manipulation [WW98].
Its value is especially for digital watermarking of images.
The basic approach is to manipulate the greater coefficients of a projection of the image over an orthonormal basis, so that the hidden information are stored in the most important part of the data and they are less likely to be destroyed by normal processing and lossy compression.
This technique is similar to some extent to LSB insertion in its philosophy, because it changes the greater coefficients in a relatively small way, but the target of the modification is less trivial.
The method we describe here briefly is an improvement over the classical DCT approach, and it conveys better security.
We said it is a generalization because the orthonormal basis used for projection is not made of cosine functions anymore. Its vectors are generated from a secret key and then the other steps are the same as the DCT ones.
An abstract for the encoding process can be:
The decoding process will work backwards, obtaining the differencies between the coefficients calculated over the stego-image and the original ones. This points this method as a cover escrow one, since the original image is usually needed in order to extract the embedded message.
The key choice for this method is the generation algorithm for the orthonormal basis, which must be dependent enough on key. The authors used a generator of maps with a pseudorandom function, then they othonormalized the set using a Gramm-Schmidt algorithm. The interesting property of this technique is that it doesn't need to have a full basis for the space, only the more vectors in the basis, the safer the embedding will usually be.
The data rate for these techniques is very dependent on the nature of the original image and the basis used, because we need big coefficients to be able to hide data. Thus, an image can convey a different amount of data using different keys.
The method illustrated has proven to be resistant to a lot of attacks, including high lossy compression rates, filtering by photo manipulation packages and deliberate attempts at removal with dedicated software such as Stirmark and Unzign.
Resistance to cropping can be achieved using a redundant encoding, embedding the same message in multiple blocks of the image.
Since the basis' vectors for this technique are always changing, then the extraction process is very hard without knowing the key.
Obiouvsly, an attacker can gain precious statistical informations when the same key is used to embed messages in different images, thus the need to change key frequently.
Due to its robustness and the need for the original medium in order to extract the embedded data, this technique is useful especially for digital watermarking.
However, DCT techniques, a subset of these algorithms, are used for steganography because of their relatively high data rate.
[WW98]
[FBS98]
Previous: patchwork
Matteo Fortini