This section is devoted to the description of permutation steganography. Permutation steganography is an effective method for hiding messages provided that the contents of cover objects are not affected by the rearrangement of their elements. Even if rearrangement of the elements does affect the content, permutation steganography is useful if the original content can be restored by adjusting the cover object after rearrangement. Example of cover objects that can be used for permutation steganography include indexed color (palette) images (Kwan, 1998), polygonal meshes (Bogomjakov, Gotsman, & Isenburg, 2008), and HTML files (Huang, Zhong, & Sun, 2008).
In an indexed color image, color data are stored in a color map. Each color is associated with its index number in the color map, and the pixel data are specified by these color indices. The colors in the color map can be shuffled and the image appearance can be preserved if the pixel data are changed accordingly. A polygonal mesh is a geometric data set consisting of vertices and faces, both of which are indexed by numbers. The indices of vertices and faces are just arbitrary. We can change indices of vertices and faces while preserving the shape they represent. In HTML files, start-tags and empty-element tags can have attributes. The order of attribute specifications is insignificant. We can freely arrange attributes without affecting the result of rendering. These examples show that there are cover objects that can be described in more than one way while preserving their appearances completely. Permutation steganography exploits this kind of redundancy.