The square root law requires a linear key

We extend the square root law of steganographic capacity, for the simplest case of iid covers, in two ways. First, we show that the law still holds under a more realistic embedding assumption, where the payload is of fixed length (instead of, in the classic result, independent embedding at each location). Second, we consider the case of nonuniform embedding paths, which is forced when the stegosystem's secret key is of limited size: we show that the secret key must be of length at least linear in the payload size, if a square root law is to hold. The latter is parallel to Shannon's perfect cryptography bound. Copyright 2009 ACM.