An Information-Theoretic Treatment of Homophonic Substitution

The history of cryptology shows that most secret-key cipher systems that have been broken were broken by exploiting the departure of the plaintext statistics from those of a completely random sequence. The technique of “homophonic substitution” is an old technique for converting an actual plaintext sequence into a (more) random sequence. At EUROCRYPT ’88, Günther [1] introduced an important generalization of homophonic substitution, which we will call “variable-length homophonic substitution”. The purpose of this paper is to give an information-theoretic treatment of Günther’s type of homophonic substitution.