  This paper considers the problem of simultaneously communicating two
messages, a high-security message and a low-security message, to a legitimate
receiver, referred to as the security embedding problem. An
information-theoretic formulation of the problem is presented. A coding scheme
that combines rate splitting, superposition coding, nested binning and channel
prefixing is considered and is shown to achieve the secrecy capacity region of
the channel in several scenarios. Specifying these results to both scalar and
independent parallel Gaussian channels (under an average individual
per-subchannel power constraint), it is shown that the high-security message
can be embedded into the low-security message at full rate (as if the
low-security message does not exist) without incurring any loss on the overall
rate of communication (as if both messages are low-security messages).
Extensions to the wiretap channel II setting of Ozarow and Wyner are also
considered, where it is shown that "perfect" security embedding can be achieved
by an encoder that uses a two-level coset code.
