Title: Hamiltonian graph approach to steganography

Authors: Sunil Kumar Muttoo, Vinay Kumar

Addresses: Department of Computer Science, University of Delhi, Delhi 110 007, India. ' Scientist 'E', NIC, Block A, CGO Complex, Lodhi Road, New Delhi 110 003, India

Abstract: A Hamiltonian graph approach is presented in this paper to ensure privacy and secrecy of a crucial secret message that is normally short and precise. A short secret message is treated as stream of bits. Each bit is compared with a functional output of a portion of cover image. The cover is partitioned into as many portions as there are bits in the message. If the bit in the message is equal to the functional output of the corresponding portion of cover, then nothing needs to be done. In case of inequality, a node of graph is created. Then adjacency among nodes is found so that exchange of colour components of pixels according to the direction of traversal in a Hamiltonian cycle makes the functional output of the portion equal to the corresponding bit. Whenever a node is not found to be adjacent to any other node, then the corresponding bit is spread over in the portion in such a way that net effect on the colour components of pixel remains < 0.01. The approach helps in retaining vital statistics of the cover in the stego.

Keywords: graph theory; minimum weight Hamiltonian cycle; steganography; directed graphs; embedding threshold; bit spreading; embedding tolerance; electronic security; privacy; secrecy; secret messages.

DOI: 10.1504/IJESDF.2010.038612

International Journal of Electronic Security and Digital Forensics, 2010 Vol.3 No.4, pp.311 - 332

Received: 04 Nov 2009
Accepted: 13 Aug 2010
Published online: 14 Feb 2011 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article