Methods and devices are provided for embedding auxiliary information in a host content in a manner that reduces memory, bandwidth and computational complexity of the embedding and transmission systems. One methodology relates to receiving a set of watermark embedding parameters produced at a pre-processing node by pre-processing the host content. The watermark embedding parameters enable embedding each of a plurality of host content segments with any one of at least two different logical values. To embed the auxiliary information, the host content is modified on a segment-by-segment basis using the set of watermark embedding parameters and in accordance with a control signal that designates one of the at least two logical values for embedding into a selected segment of the host content. The generation of watermark embedding parameters at a pre-processing node reduces storage, transmission and computational complexity of embedding operations that can occur at locations other than the pre-processing node.