A game-theoretic analysis of content-adaptive steganography with independent embedding

We provide a game-theoretic analysis of a scenario from the field of content-adaptive steganography. Alice, a steganographer, wants to embed a secret message into a random binary sequence with a known distribution in which the value of each position is independently but non-identically distributed. Eve, a steganalyst, observes the sequence and wants to determine whether it contains a hidden message. Alice is allowed to flip binary values independently at random, with the constraint that the expected number of changes is a fixed constant. Eve may choose to classify each sequence as either unmodified (cover) or modified (stego). The payoff for Eve in the game is the probability that her classification is correct; and the payoff for Alice is the probability that Eve's classification is incorrect, so that the game is constant-sum. We show that Eve's best response strategy in this game can be expressed as a linear aggregation threshold formula similar to those used in practical steganalysis. We give a general formula for Alice's best response strategy; and we compute explicit pure strategy equilibria for the special case of changing one bit in a length-two sequence.