Том 4, серия 1, номер 2, 1997 г., Стр. 51-74

УДК 519.68
А. Н. Фионов
Эффективный метод рандомизации сообщений на основе арифметического кодирования

Аннотация:
Рассматривается задача полной рандомизации сообщений, возникающая в криптографии при конструировании безусловно стойких шифров с секретным ключом. Одним из основных параметров любого метода рандомизации является избыточность $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.

Фионов А. Н. ¹
1. Сибирская государственная академия телекоммуникаций и информатики,
ул. Кирова, 86, 630125 Новосибирск, Россия
е-mail: fionov@neic.nsk.su

Статья поступила 17 декабря 1996 г.