Communicating by Information-embedding: Theory, Algorithms and Applications

通过信息隐藏或隐写术（源于希腊语steganos，意思是“覆盖”，而graphein意思是“写”）进行通信可以追溯到两千多年前的古希腊，是在第一次战争期间秘密通信以发送重要间谍信息的一种方式。这种强大的通信范式的理论基础来自于带有侧信息的信道编码（CCSI）的优雅信息理论框架。CCSI指的是在一个有噪声的信道上进行通信的问题，其中关于传输信道的一些部分知识（以边信息的形式）在编码器可用，但在解码器不可用。例如，在多媒体数据隐藏或水印问题中，副信息可能指的是一个多媒体“主机”信号，如图像或音频或视频片段，它只存在于编码器中，其中可能希望嵌入消息。数据嵌入的规则通常是：(i)主机媒介的干扰最小，这意味着嵌入的信息具有最小的侵入性；（ii）即使在中间攻击者存在的情况下，嵌入的信息也可以被预期的解码器可靠地和健壮地恢复，中间攻击者在不使嵌入的主机信号不可用的范围内，可能会试图破坏或擦除信息或水印。虽然信息隐藏领域起源于秘密通信，但这种范式的适用性范围要广泛得多，并且也扩展到非秘密通信系统。具体来说，令人惊讶的是，一般来说，最有效的数字广播方式是遵循数据隐藏的原则，即用户的消息嵌入到另一个用户的消息中。事实上，从信息论到今天，理论上最著名的可实现广播速率可以追溯到Marton[1]的（不可读的）工作，他的密码本结构与数据隐藏的方法密切相关。与此相关的是Gelfand和Pinsker[3]关于CCSI的作品，以及Costa[3]关于所谓“在脏纸上写字”的问题，其中的妙处是通过适应宿主媒介而不是试图“压倒”它来嵌入数据。这些思想为信息嵌入问题奠定了理论基础，构成了本文的核心。

0208883Kannan RamchandranUniversity of California - BerkeleyCommunicating by message-hiding or steganography (derived from the Greek words steganos meaning \covered" and graphein meaning \to write") goes back over two thousand years ago to the ancient Greeks as a way of communicating secretly to send important espionage infor- mation during war 1 . The theoretical foundations for this powerful communications paradigm are derived from the elegant information-theoretical framework of channel coding with side information (CCSI). CCSI refers to the problem of communicating over a noisy channel with some partial knowledge about the transmission channel (in the form of side information) avail- able at the encoder but not at the decoder. For example, in the multimedia data-hiding or watermarking problem, the side information might refer to a multimedia \host" signal such as an image or audio or video clip that is present only at the encoder, in which the message may be desired to be embedded. The rules of data-embedding are usually that (i) the host medium is minimally perturbed, implying that the embedded message be minimally intrusive; (ii) the embedded message can be reliably and robustly recovered by theintended decoder even in the presence of an intermediate \attacker" who, within the bounds of not rendering the embedded host signal unusable, might attempt to corrupt or erase the message or watermark.While the field of information-hiding has its origins in covert communications, the scope of applicability ofthis paradigm is far more general, and extends to non-covert communication systems as well. Specifically, it turns out, rather surprisingly, that in general, the most e Ecient way to do digital broadcast is to follow the principles of data-hiding with users' messages being embedded in one another's. Indeed, the theoretically best-known achievable broadcast rates from information-theory to this day date back to the (unreadable) work of Marton [1], whose codebook construction is intimately connected to the methodology for data-hiding. Related to this are the works of Gelfand and Pinsker [2] on CCSI, and by Costa [3] on the so-called problem of \writing on dirty paper" where the punchline is to embed data by adapting to the host medium rather than by trying to \overpower" it. These ideas lay the theoretical foundations for the problem of information-embedding and form the core of this proposal.