Linear codes for high payload steganography

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 the “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 one- or two-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).