[owencm]

Just for clarity's sake, I use F5 to flip bits. Your suggestion in 1) makes sense to me, although I've not read of somebody trying this - if you have any more data on it I'd love to see it.

2) This general idea is a good one and the way it is used in steganography is Wet Paper Codes. These effectively provide options for how to encode short messages so you can select that which best matches the coefficients which already exist. A simple example:

Encode 00 as either 0000, 0001, 0010 or 0011 Encode 01 as either 0100, 0101, 0110 or 0111 And so on

Hence when we wish to send a 2-bit message we often only need to change a single bit in the coefficients to get to a correct code word.

Hence Wet Paper Codes are able to achieve a high ratio of bits transferred to bits flipped.

I'm sure a keyed shuffle is the right way to go, certainly also encrypting is helpful but I see no downside of more evenly spreading changes across an image using a shuffle.