Summary: We present a practical algorithm for the homophonic coding of a message source, as required for cryptographic purposes. The purpose of homophonic coding is to transform the output of a non-uniformly distributed message source into a sequence of uniformly distributed symbols. This is achieved by randomly mapping each source symbol into one of a set of homophones. The selected homophones are then encoded by means of arithmetic coding, after which they can be encrypted with a suitable cryptographic algorithm. The advantage of homophonic coding above source coding is that source coding merely protects against a ciphertext-only attack, whereas homophonic coding provides additional protection against known-plaintext and chosen-plaintext attacks. This paper introduces a fast algorithm for homophonic coding based on arithmetic coding, termed the shift-and-add algorithm, which makes use of the fact that the set of homophones are chosen according to a dyadic probability distribution. This leads to a particularly simple, efficient implementation, requiring no multiplications but only shifts and additions. The usefulness of the algorithm is demonstrated by the homophonic coding of an ASCII textfile. The simulation results show that homophonic coding increases the entropy by less than 2 bits per symbol, and also provides source encoding (data compression).
For the entire collection see [Zbl 0829.68005].