# Efficiency of Steganography with Linear Codes

I have read some papers about steganography using perfect linear codes. The aim is sending more hidden message bits with changing less cover message bits. For example using the parity check matrix of [7,4,3] Hamming code, we can embed 3 bits of message in 7 bits by changing at most one of them.

It looks great. However, we are not free for choosing positions to be changed. Our message forces us when choosing positions that we will change. But what if the position we will change belongs to the most significant bit (MSB) or any other bits that the colour of the pixel changes perceptibly when we change that position? Is not it a handicap?

Think about it at a higher level. Steganography is the act of disguising a secret message by embedding it in an innocent message. It doesn't have to be hidden in a picture. It could be hidden in a music file, or a video, or a spam email. Picking a disguise is a choice, not a requirement.

So now we choose the type of file, and we pick a picture. That doesn't say anything about how we will hide the messsge in the file. We can choose to hide it only in the least significant bit of the color blue, for example. Or we could hide it by altering only pixels that are set to true black, or the alpha channel, or by modifying the EXIF thumbnail.

Your scheme would work if you chose to treat the least significant bit of a group of 8 bytes as the locations of the hidden bits.

But what would that gain you? Every eighth byte would have a statistically unusual distribution, because a normal picture won't have a parity bit there. If an analyst is looking for evidence of an unusual image that might be hiding data, your modified images will stand out as surely as if you had embedded the message directly.

• Now I doubt that whether I understood correctly the use of perfect linear codes in steganography. Firstly, let me clarify that I want to embed some hidden message in a picture. A classical method is to exchange the least significant bits of each pixel with the next bit of the message we want to hide. Hence, the difference will be indetectable to the human eye. However, we can hide only one bit by altering one bit with this method. – faith Dec 4 '13 at 8:22
• Nevertheless, as far as I understand, if sender and reciever agree on a parity check matrix of a Hamming code, it is possible to hide three bits by altering one bit in the cover message. Let me give an example: – faith Dec 4 '13 at 8:22
• Assume H is the parity check matrix whose columns are (1,0,0),(0,1,0),(0,0,1),(0,1,1),(1,0,1),(1,1,0) and (1,1,1). Also assume the original message is sent as blocks of 7 bits. (I don't know how can it be used in real life while 1 byte = 8 bits.) Let our original message be x=(1,0,0,1,1,1,0). We compute the syndorme of x, s(x)=H(x^t)=(1,0,0). Suppose that we want to embed (1,1,1). It is enough to change the fourth position. In fact, if the reciever multiply H by (1,0,0,0,1,1,0)^t the result will be (1,1,1). – faith Dec 4 '13 at 8:23
• Note that, whichever the positions among seven bits we change, the sydrome will be different from the others. Hence we can hide three bits by altering only one bit. My question is again that: We have changed the fourth position. Considering all the pixels that are changed, one can easily notice that the picture was changed. But according to the papers I read, such algorithms are being used. Do I misunderstand something? – faith Dec 4 '13 at 8:23
• They may still spread the impacted bits across the Least Significant Bits of a series of bytes, impacting no more than one bit per byte. In steganography, there are no rules that require all 7 related bits to be collocated in the same byte. – John Deters Dec 4 '13 at 23:51