Results concerning the bandwidth of subliminal channels

In conjunction with a six-month research program on Computer Security, Cryptology and Coding Theory hosted by the Isaac Newton Institute of Mathematical Sciences, University of Cambridge, Cambridge, U.K., a Workshop on Information Hiding was held from May 30 through June 1, 1996. This workshop was devoted to all aspects of information hiding-other than the usual cryptographic concealment of content, including steganography, subliminal channels, fingerprinting, covert channels, etc. Two surprising results pertaining to subliminal channels were presented or grew out of presentations made at this workshop. One is of interest to the secure communications protocol designer concerned with denying the use of subliminal channels, while the other is important to the designer, or user, of subliminal channels. The first raises the question of whether the notion of a "subliminal-free" communication channel is an oxymoron, i.e., is it possible to force the bandwidth of the subliminal channel to be truly zero? The second forces a more precise formulation of a conjecture the author had made that the bandwidth of a subliminal channel is logarithmically limited if the transmitter is unwilling to trust the subliminal receiver unconditionally. Motivated by these results, this paper reexamines the fundamental questions of the bandwidth available for subliminal communication as a function of the trust the transmitter has in the subliminal receiver and of a logically sound interpretation of the term "subliminal-free."