[Back]

S. Hetzl, P. Mutzel:
"A Graph-Theoretic Approach to Steganography";
in: "9th IFIP Conference on Communications and Multimedia Security (CMS 2005)", J. Dittmann, S. Katzenbeisser, A. Uhl (ed.); issued by: International Federation for Information Processing; Springer, LNCS 3677, 2005, ISBN: 3-540-28791-4, 119 - 128.

We suggest a graph-theoretic approach to steganography based on the
idea of exchanging rather than overwriting pixels. We construct a
graph from the cover data and the secret message. Pixels that need to
be modified are represented as vertices and possible partners of an
exchange are connected by edges. An embedding is constructed by
solving the combinatorial problem of calculating a maximum
cardinality matching. The secret message is then embedded by
exchanging those samples given by the matched edges. This embedding
preserves first-order statistics. Additionally, the visual changes
can be minimized by introducing edge weights.

We have implemented an algorithm based on this approach with support
for several types of image and audio files and we have conducted
computational studies to evaluate the performance of the algorithm.

http://aleph.ub.tuwien.ac.at/F?base=tuw01&func=find-c&ccl_term=AC05936259