  A solution to the problem of asymptotically optimum perfect universal
steganography of finite memoryless sources with a passive warden is provided,
which is then extended to contemplate a distortion constraint. The solution
rests on the fact that Slepian's Variant I permutation coding implements
first-order perfect universal steganography of finite host signals with optimum
embedding rate. The duality between perfect universal steganography with
asymptotically optimum embedding rate and lossless universal source coding with
asymptotically optimum compression rate is evinced in practice by showing that
permutation coding can be implemented by means of adaptive arithmetic coding.
Next, a distortion constraint between the host signal and the
information-carrying signal is considered. Such a constraint is essential
whenever real-world host signals with memory (e.g., images, audio, or video)
are decorrelated to conform to the memoryless assumption. The constrained
version of the problem requires trading off embedding rate and distortion.
Partitioned permutation coding is shown to be a practical way to implement this
trade-off, performing close to an unattainable upper bound on the
rate-distortion function of the problem.
