  We study the limitations of steganography when the sender is not using any
properties of the underlying channel beyond its entropy and the ability to
sample from it. On the negative side, we show that the number of samples the
sender must obtain from the channel is exponential in the rate of the
stegosystem. On the positive side, we present the first secret-key stegosystem
that essentially matches this lower bound regardless of the entropy of the
underlying channel. Furthermore, for high-entropy channels, we present the
first secret-key stegosystem that matches this lower bound statelessly (i.e.,
without requiring synchronized state between sender and receiver).
