The square root law does not require a linear key
Andrew D. Ker · 2010
Square root laws are theorems about imperfect steganography, embedding which fails to preserve all statistical properties of covers. They show that, in various situations, capacity of covers grows only with the square root of the available cover size. In a paper given at this conference last year [14], we showed an important caveat: when the sender's and recipient's shared embedding key determines the embedding path, its length must be at least linear in the size of the hidden payload to avoid their enemy exhausting over all possible sets of locations. It was left open to show that a linear key is sufficient.