An efficient method for the randomization of messages based on arithmetic coding

We consider the problem of complete randomization of messages. This problem arises in cryptology during the construction of unconditionally stable codes with a secret key. One of the basic parameters of any randomization method is redundancy $r$, defined as the difference between the average length of a code word and the entropy for a source symbol. To obtain an arbitrarily low redundancy using the method from earlier papers of B. Ya. Ryabko and Fionov requires $O(1/r)$ memory and $O(\log^2(1/r)\log\log (1/r))$ coding and decoding time. In this paper we present a method for which the memory and time are defined as $O(\log(1/r))$ and $O(\log(1/r)\log\log(1/r)\log\log\log(1/r))$, respectively, as $r\to 0$. This method, however, uses subtantially more random symbols than the well-known methods.