A Fast Method for Full Randomization of Messages

We consider the problem of homophonic coding (or full randomization) of source messages that arises in cryptography when provably secure secret-key systems are to be constructed. For the known methods of homophonic coding, the encoder and decoder memory grows exponentially as the redundancy $r$, which is defined as the difference between the average codeword length and the source entropy, tends to zero. We propose a method of homophonic coding for which the memory and the computing time grow, respectively, as $O(1/r)$ and $O(\log^2 1/r\log\log 1/r)$ as $r\to 0$.