Введение к работе
Актуальность темы Задача рандомизации сообщений, т. е. кодирование, превращающее их в последовательность равновероятных и независимых символов, находит широкое применение в системах защиты информации, в частности, передаваемой по линиям связи, а также при генерировании шумоподобных случайных процессов, находящих широкое применение при разработке и моделировании систем связи.
Решение задачи рандомизации может быть основано на двух различных подходах к процессу кодирования: статическом (неадаптивном) и универсальном (адаптивном). Статические методы позволяют решить проблему полной рандомизации, т. е. обеспечивают получение кодов с точно равновероятными и независимыми символами, но могут быть использованы только в случае известной статистики источника информации. Универсальные методы кодирования позволяют с некоторой (наперед заданной) точностью приблизить кодовую последовательность к последовательности равновероятных и независимых символов и могут применяться в случае неизвестной статистики источника.
Построение и исследование методов рандомизации сообщений привлекает внимание многих специалистов. Статические методы разрабатывались и изучались в работах К. Гюнтера (Ch. Giinther), Дж. Месси (J. Massey), К. Гирмана (Ch. Gehrmann), В. Пенцхорна (W. Penzhorn) и многих других. Методам универсального и адаптивного кодирования посвящены многочисленные исследования. Основные результаты в этой области принадлежат как отечественным исследователям В. Ф. Бабкину, Р. Е. Кри-чевскому, Б. Я. Рябко, В. К. Трофимову, Б. М. Фитингофу, Ю. М. Штарькову, так и зарубежным исследователям Я. Зиву (J. Ziv), Дж. Клири (J. Cleary), А. Лемпелу (A. Lempel), Й. Рисса-нену (J. Rissanen), И. Уиттену (I. Witten), П. Элайесу (P. Elias) и др.
Основными параметрами методов рандомизации являются избыточность, определяемая как разность между средней длиной кодового слова и энтропией источника, и количество используе-
мых при кодировании случайных символов. Для основных областей применения рандомизации крайне важно обеспечение заданных (произвольно низких) значений этих параметров.
Известные до недавнего времени статические методы рандомизации были чрезвычайно трудоемкими с вычислительной точки зрения, а именно, для достижения низкой избыточности и числа используемых случайных символов они требовали экспоненциально растущей памяти кодера и декодера (или экспоненциально растущего времени кодирования и декодирования). Высокая сложность этих методов препятствовала их практическому применению. В области универсального кодирования также оставались проблемы сложности методов, ограничивающие их практическое применение.
Цель работы:
1. Построение эффективных методов полной рандомизации со
общений, характеризуемых неэкспоненциально растущими
памятью и временем при достижении заданных, произволь-
. но малых избыточности и числа используемых случайных символов.
2. Разработка адаптивных методов кодирования источников,
обладающих на порядок более низкой вычислительной слож
ностью, чем ранее известные.
Задачи исследования Для достижения указанных целей в рамках диссертационной работы решаются следующие задачи.
-
Построение эффективного метода полной рандомизации, характеризующегося неэкспоненциальным ростом объема памяти кодера и декодера и времени кодирования и декодирования, и использующего при кодировании небольшое число случайных символов.
-
Построение метода полной рандомизации, характеризующегося логарифмическим ростом объема памяти и времени, однако использующего два случайных бита на кодируемый символ.
-
Синтез двух выше указанных методов для обеспечения одновременно заданных, произвольно низких избыточности и числа случайных символов, используемых при кодировании.
-
Построение быстрых алгоритмов для выполнения операций с кумулятивными вероятностями при возрастающем размере алфавита источника.
-
Построение и применение эффективных структур данных для оценивания статистики произвольного источника с заданной точностью.
Методы исследования В процессе исследований были использованы основные положения теории передачи сообщений, кодирования дискретных источников, теории сложности алгоритмов и теории вероятностей.
Научная новизна результатов работы:
-
Разработан метод полной рандомизации сообщений, основанный на эффективном блоковом кодировании, обеспечивающий произвольно низкую избыточность при линейном росте объема памяти и логарифмическом росте времени кодирования. Данный метод использует сколь угодно малое число случайных бит.
-
Разработан метод полной рандомизации сообщений, основанный на арифметическом кодировании, обеспечивающий произвольно низкую избыточность кода при экспоненциально меньшем, чем для первого метода, объеме памяти, но большом количестве случайных бит, используемых при кодировании.
-
Осуществлен синтез двух вышеуказанных методов для обеспечения одновременно заданных, произвольно низких избыточности и числа случайных символов при некоторой средней вычислительной сложности.
-
Разработан метод кодирования источников с неизвестной статистикой, обеспечивающий заданную избыточность на
классе всех бернуллиевских и марковских источников и требующий лишь логарифмического роста времени кодирования и декодирования при увеличении размера алфавита источника.
5. Разработан метод кодирования для источников с неизвестной статистикой, основанный на мнимом скользящем окне и арифметическом кодировании, позволяющй на порядок снизить необходимый объем памяти кодера и декодера по сравнению с ранее известными методами.
Практическая ценность результатов:
-
Разработанные методы полной рандомизации обеспечивают построение безусловно стойких и высокоскоростных методов защиты информации для систем с известной статистикой.
-
Предложенные методы адаптивного кодирования применяются в случае источников с неизвестной статистикой для построения стойких криптосистем или для повышения практической стойкости существующих шифров.
-
Предложенные методы уменьшения вычислительной сложности адаптивного кодирования могут быть использованы в составе многих практических методов сжатия данных, применяемых к произвольным источникам информации, для повышения степени сжатия и производительности.
-
Разработанные методы омофонного декодирования применяются в многочисленных задачах, требующих генерации произвольно распределенных случайных величин, и обеспечивают низкую сложность генераторов.
Внедрение результатов работы Основные результаты получены в рамках работы по проекту №96-01-00052 "Асимптотически оптимальные коды для стационарных источников информации", финансируемому Российским фондом фундаментальных исследований, и в процессе выполнения НИР Государственного
комитета РФ по связи и информатизации "Аспект-Сибирь" по теме "Разработка высокоскоростных методов сжатия данных".
Планируется практическая реализация разработанных методов при решении задач защиты информации в Internet в рамках проекта №98-01-00772 "Теоретическое обоснование и реализация эффективных доказуемо-стойких методов защиты информации для полнотекстовых баз данных в среде Internet", финансируемого Российским фондом фундаментальных исследований.
Результаты диссертации используются в учебном процессе при чтении курсов "Основы криптографии" и "Теория вычислительных процессов и систем", а также при выполнении дипломных проектов в СибГУТИ.
Апробация работы и публикации Основные результаты работы докладывались и обсуждались на следующих российских и международных конференциях: Российская научно-техническая конференция "Информатика и проблемы телекоммуникаций" (Новосибирск, 1996); Международная научно-техническая конференция "Информатика и проблемы телекоммуникаций" (Новосибирск, 1997); Международная конференция по исследованию операций (Новосибирск, 1998); Международный семинар "Распределенная обработка информации" (Новосибирск, 1998); 7th International Symposium on Algorithms and Computation ISAAC'96 (Osaka, Japan, 1996); 8th International Symposium on Algorithms and Computation ISAAC'97 (Singapore, 1997); IEEE International Symposium on Information Theory ISIT'97 (Ulm, Germany, 1997); IEEE International Symposium on Information Theory ISIT'98 (Cambridge, USA, 1998);
По теме диссертации опубликовано 14 печатных работ, в том числе 5 статей, подготовлено 2 отчета о НИР.
Основные положения, выносимые на защиту:
1. Для решения задачи полной рандомизации при макимально ограниченном использовании случайных бит на основе эффективного блокового кодирования разработан метод, обеспечивающий произвольно низкую избыточность и требующий линейного роста объема памяти кодера и декодера и
логарифмического роста времени кодирования и декодирования.
-
Лля решения задачи полной рандомизации при неограниченном использовании случайных бит построен более эффективный метод, обеспечивающий произвольно низкую избыточность при логарифмическом росте как времени кодирования, так и объема памяти.
-
Синтез двух разработанных методов приводит к построению класса кодов, обеспечивающих одновременно заданные избыточность и число случайных символов при минимальной (на сегодняшний день) вычислительной сложности.
-
Известные методы, использующие арифметическое кодирование, требуют линейного роста времени кодирования и декодирования при увеличении размера алфавита источника. Метод, основанный на быстром вычислении кумулятивных вероятностей, требует лишь логарифмического роста времени при увеличении размера алфавита.
-
Использование структуры данных "мнимое скользящее окно" в сочетании с арифметическим кодированием позволяет на порядок снизить необходимый объем памяти кодера и декодера при обеспечении заданной, произвольно низкой избыточности в случае кодирования источника с неизвестной статистикой,
Структура и объем работы Диссертация состоит из
введения, пяти глав, заключения и списка литературы. Диссертация содержит 149 страниц машинописного текста, 10 рисунков и 7 таблиц. Список литературы включает 77 наименований.
Похожие диссертации на Методы эффективной рандомизации сообщений, базирующиеся на омофонном и арифметическом кодировании
