Communicating by Information-embedding: Theory, Algorithms and Applications

0208883 Kannan Ramchandran加州大学伯克利分校通过信息隐藏或隐写术（来自希腊语steganos，意思是“覆盖”，graphein，意思是"写”）进行通信可以追溯到两千多年前的古希腊人，作为一种在战争期间秘密通信以发送重要间谍信息的方式。这种强大的通信模式的理论基础是来自优雅的信息理论框架的信道编码与边信息（CCSI）。CCSI指的是在编码器处可用但在解码器处不可用的关于传输信道的某些部分知识（以边信息的形式）的情况下在噪声信道上进行通信的问题。例如，在多媒体数据隐藏或水印问题中，边信息可能指的是多媒体“宿主”信号，诸如仅存在于编码器处的图像或音频或视频剪辑，其中可能期望嵌入消息。数据嵌入的规则通常是：（i）宿主媒体受到最小的干扰，这意味着嵌入的消息是最小的侵入;（ii）即使在存在中间“攻击者”的情况下，嵌入的消息也可以由预期的解码器可靠地和鲁棒地恢复，在不使嵌入的主机信号不可用的范围内，虽然信息隐藏领域起源于隐蔽通信，但这种范式的适用范围要广泛得多，并且也扩展到非隐蔽通信系统。具体来说，令人惊讶的是，一般来说，进行数字广播的最有效方法是遵循数据隐藏的原则，用户的消息嵌入到另一个用户的消息中。事实上，从信息论到今天，理论上最著名的可实现的广播速率可以追溯到Marton [1]的（不可读的）工作，其码本构造与数据隐藏的方法密切相关。与此相关的是Gelfand和Pinsker [2]关于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.