The steganographic algorithm introduced in this paper uses a planar graph (Berge, 1962) as cover object. A planar graph is also called a map. Normal data structure used to represent a graph does not provide enough redundancy for hiding. Before discussing the details, background of the approach, motivation behind the paper and the contribution that this paper can provide to the computing world need to be discussed.
1.1 Background
Steganography is the art of hiding a secret message inside a cover (host) object. The purpose is to allow two parties to communicate surreptitiously, without raising suspicion from an eavesdropper. Steganography (Katzenbeisser & Petitcolas, 2000) and cryptography (Stallings, 1999) are two techniques used for secret communication. Cryptography attempts to hide the contents of a message while steganography attempts to hide the existence of a message (Anderson & Petitcolas, 1998). A digital cover object may be an image, audio, video or a graph –a vector data. The cover object with embedded secret message is called stego object i.e.
cover + secret message = stego
Stego object is the medium that carries the secret message (hidden data). Main requirement for any steganographic technique is undetectability, robustness, tamper resistance and embedding capacity (Cole, 2003; Johnson & Jajodia, 1998a). These properties of any steganographic algorithm are mainly influenced by following four factors:
- •
The choice of the cover object,
- •
The selection rule used to identify individual elements of the cover that could be modified (or used without any modification) during embedding,
- •
The type of embedding operations that modifies the cover elements, and
- •
The number of embedding changes.
The embedding capacity and robustness in steganographic algorithm are so diagonally opposite placed that it is difficult to achieve both simultaneously at the maximum level (Saloman, 2003; Kumar & Muttoo, 2008, 2009b). Thus, a steganographic algorithm achieves robustness at low embedding capacity. The placement of embedding changes in the cover is called a selection channel. A channel is kept secret by the communicating partners in the similar way a secret key is maintained in cryptography. After embedding, stego medium should maintain similarity with cover to avoid any detection of the hidden data. It is achieved by minimizing the distortion in the cover medium while embedding the hidden data (Anderson & Petitcolas, 1998).
The way a cover is stored in digital form plays an important role in minimizing distortion introduced in cover while embedding secret message. A cover is collection of some basic elements. Basic element in image is pixel while that in a graph is node and segment. A segment consists of many intermediate points (Kumar & Muttoo, in press). More is the amount of bits available to store one element of a cover medium, less is the visible distortion after embedding and vice versa.