Linear codes for high payload steganography.

Discrete Applied Mathematics 157 (2009), 971-981.

Steganography is concerned with communicating hidden messages
in such a way that no one apart from
the sender and the intended recipient can detect
the very existence of the message. We study the * syndrome
coding method* (sometimes also
called ``matrix embedding method''), which uses a linear code
as an ingredient. Among all codes of a fixed block length
and fixed dimension (and thus of a fixed information rate), an optimal code
is one that makes it most difficult for an eavesdropper
to detect the presence of the hidden message.
We show that the average distance to code is the appropriate
concept that replaces the covering radius for this particular application.
We completely classify the optimal codes in the cases when
the linear code used in the syndrome coding method is
a 1- or 2-dimensional code over GF(2). In the steganography
application this translates to cases when the code carries
a high payload (has a high information rate).