A Graph Theoretic Approach to Sustainable Steganography

Vinay Kumar ； Sunil Kumar Muttoo

《MIS REVIEW：An International Journal》 17卷1期 (2011/09) Pp. 19-37

https://doi.org/10.6131/MISR.201109_17(1).0002

並列摘要

An algorithm based on graph-theoretic approach is introduced in this paper. A bipartite graph is created from message and cover object. Message M is broken into units of x (= 2, 4, or 8) bits long. For each x, a matching with m number of such x bits from cover file is determined using the bipartite graph. Wherever a matching for a node in left side is found with a node in right side then this part of the message is treated as either naturally or cross embedded in that port of the cover. Nodes in left side correspond to bits in message and those in right side correspond to group of bits in cover. The matching relationship is then embedded in the extra bytes of cover, fully utilizing the available redundancy or alternatively the sequence of indices is compressed and sent through separate channel. The algorithm achieves almost 100% matching for message elements in cover elements. The embedding algorithm has been put through mathematical and statistical test to ensure that it not only retains visual similarity in stego with cover file but also leaves other statistics of cover undistorted after embedding. Therefore it achieves sustainability. In this paper, we have taken BMP file to implement the algorithm.

並列關鍵字

Extra Bytes ； Graph Theoretic Approach ； Steganography ； Information Hiding ； Sustainable Embedding ； Natural Embedding ； Partial Embedding ； Cross Embedding ； Explicit Embedding

參考文獻

Anonymous (1995), ‘Steganography (hidden writing)', WEPIN Store, available at http://www.wepin.com/pgp/stego.html (accessed 26 June 2007).

Anonymous (2001), ‘Steganography information, software and news to enhance your privacy', StegoArchive, avalable at http://www.StegoArchive.com (accessed 26 June 2007).

Kirkby, D. (n.d.), ‘Bmp format', Arbitrary Transmission Line Calculator, available at http://atlc.sourceforge.net/bmp.html (accessed 25 May 2008).

Krinn, J. (2000), ‘Introduction to steganography', Global Information Assurance Certification, available at http://www.giac.org/paper/gsec/35/introduction-steganography/101757 (accessed 25 May 2008).

Lenstra, A., Wang, X. and de Weger, B. (2005), ‘Colliding X.509 certificates', Cryptology ePrint Archive: Report 2005/067, available at http://eprint.iacr.org/2005/067 (accessed 23 December 2008).