Эффективный метод рандомизации сообщений на основе арифметического кодирования

Рассматривается задача полной рандомизации сообщений, возникающая в криптографии при конструировании безусловно стойких шифров с секретным ключом. Одним из основных параметров любого метода рандомизации является избыточность $r$, определяемая как разность между средней длиной кодового слова и энтропией на символ источника. Известно, что для получения произвольно низкой избыточности достаточно $O(1 /r)$ памяти и $O(\log 2(l/r)$ $\log\log(l/r))$ времени кодирования и декодирования. В настоящей работе предлагается метод, для которого объем памяти и времени определяется соответственно как $O(\log(l/r))$ и $O(\log(l/r)\log\log(l/r)\log\log\log(l/r))$ при $r\to 0$. Предлагаемый метод, однако, использует существенно большее количество случайных символов, чем известные методы.
Табл. 3, ил. 6, библиогр. 11