Методы эффективной рандомизации сообщений, базирующиеся на омофонном и арифметическом кодировании тема диссертации и автореферата по ВАК РФ 05.12.13, кандидат технических наук Фионов, Андрей Николаевич
- Специальность ВАК РФ05.12.13
- Количество страниц 162
Оглавление диссертации кандидат технических наук Фионов, Андрей Николаевич
ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ
1 РАНДОМИЗАЦИЯ СООБЩЕНИЙ, ОСНОВАННАЯ
НА БЛОКОВОМ КОДИРОВАНИИ
1.1. Введение
1.2. Основные идеи омофонного кодирования и обзор известных методов
1.3. Основные понятия и идеи
1.4. Посимвольное омофонное кодирование при двоично-рациональных вероятностях символов
1.4.1. Обозначения
1.4.2. Кодирование
1.4.3. Декодирование
1.4.4. Основные свойства метода
1.5. Блоковое омофонное кодирование при двоично-рациональных вероятностях символов
1.5.1. Определения и обозначения
1.5.2. Кодирование блока
1.5.3. Декодирование блока
1.5.4. Сложность блокового кодирования
1.6. Посимвольное омофонное кодирование при произвольных рациональных вероятностях символов
1.6.1. Кодирование
1.6.2. Декодирование
1.6.3. Основные свойства метода
1.7. Блоковое омофонное кодирование при произвольных рациональных вероятностях символов
1.7.1. Кодирование блока
1.7.2. Декодирование блока
1.7.3. Сложность блокового кодирования
Выводы
2 РАНДОМИЗАЦИЯ СООБЩЕНИЙ, ОСНОВАННАЯ НА АРИФМЕТИЧЕСКОМ КОДЕ
2.1. Введение
2.2. Основные идеи арифметического кодирования с разделением интервала
2.3. Арифметическое кодирование с разделением интервала
2.3.1. Обозначения и определения
2.3.2. Масштабирование интервала
2.3.3. Разделение интервала
2.3.4. Алгоритм кодирования
2.3.5. Алгоритм декодирования
2.3.6. Избыточность и сложность кодирования
2.4. Реализация случайного выбора интервала
Выводы
3 ОБОБЩЕННЫЙ МЕТОД ПОЛНОЙ РАНДОМИЗАЦИИ И ЕГО ОСНОВНЫЕ ПРИЛОЖЕНИЯ
3.1. Введение
3.2. Синтез блокового и арифметического омофонного кодирования
3.3. Приложение омофонного кодирования к задачам криптографии
3.4. Применение омофонного декодирования в задачах генерации случайных чисел
3.4.1. Постановка задачи
3.4.2. Основная идея метода
Выводы
4 АДАПТИВНОЕ АРИФМЕТИЧЕСКОЕ КОДИРОВАНИЕ ИСТОЧНИКОВ С БОЛЬШИМИ АЛФАВИТАМИ
4.1. Введение
4.2. Обзор методов адаптивного кодирования
4.3. Избыточность арифметического кодирования
4.3.1. Арифметическое кодирование
4.3.2. Арифметическое декодирование
4.3.3. Избыточность и вычислительная сложность арифметического кодирования
4.4. Быстрое адаптивное кодирование с использованием скользящего окна
4.4.1. Определение скользящего окна
4.4.2. Эффективное кодирование источников с большими алфавитами
4.4.3. Избыточность и сложность адаптивного кодирования
Выводы
5 ЭФФЕКТИВНОЕ ПО ПАМЯТИ АДАПТИВНОЕ КО-
ДИРОВАНИЕ
5.1. Введение
5.2. Адаптивное кодирование на основе мнимого скользящего окна
5.2.1. Описание схемы кодирования
5.2.2. Точность представления статистики источника134
5.2.3. Реализация случайного выбора символа
5.2.4. Основные свойства метода, основанного на мнимом скользящем окне
5.2.5. Замечания о способах получения случайных
бит
5.3. Адаптивное кодирование марковских источников
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА
Рекомендованный список диссертаций по специальности «Системы, сети и устройства телекоммуникаций», 05.12.13 шифр ВАК
Эффективные методы построения идеальных криптографических систем защиты информации2005 год, доктор технических наук Фионов, Андрей Николаевич
Эффективные методы кодирования низкоэнтропийных источников1999 год, кандидат физико-математических наук Шарова, Марина Павловна
Программно - аппаратная реализация оптимального алгоритма декодирования каскадных кодов на базе кодов Рида - Соломона в адаптивных системах обмена данными2017 год, кандидат наук Тамразян Георгий Михайлович
Алгоритм защиты информации на основе тригонометрических функций2012 год, кандидат технических наук Сизов, Владимир Петрович
Разработка и анализ алгоритмов декодирования МПП- и ОЛО-кодов, допускающих распараллеливание и конвейеризацию2015 год, кандидат наук Жилин Игорь Витальевич
Введение диссертации (часть автореферата) на тему «Методы эффективной рандомизации сообщений, базирующиеся на омофонном и арифметическом кодировании»
ВВЕДЕНИЕ
Актуальность темы
Задача рандомизации сообщений, т. е. кодирование, превращающее их в последовательность равновероятных и независимых символов, находит широкое применение в системах защиты информации, в частности, передаваемой по линиям связи, а также при генерировании шумоподобных случайных процессов, находящих широкое применение при разработке и моделировании систем связи.
Решение задачи рандомизации может быть основано на двух различных подходах к процессу кодирования: статическом (неадаптивном) и универсальном (адаптивном). Статические методы позволяют решить проблему полной рандомизации, т. е. обеспечивают получение кодов с точно равновероятными и независимыми символами, но могут быть использованы только в случае известной статистики источника информации. Универсальные методы кодирования позволяют с некоторой (наперед заданной) точностью приблизить кодовую последовательность к последовательности равновероятных и независимых символов и могут применяться в случае неизвестной статистики источника.
Построение и исследование методов рандомизации сообщений привлекает внимание многих специалистов. Статические методы разрабатывались и изучались в работах К. Гюнтера (Ch. Günther), Дж. Месси (J. Massey), К. Гирмана (Ch. Gehrmann),
В. Пенцхорна (W. Penzhorn) и многих других. Методам универсального и адаптивного кодирования посвящены многочисленные исследования. Основные результаты в этой области принадлежат как отечественным исследователям В. Ф. Бабкину, Р. Е. Кри-чевскому, Б. Я. Рябко, В. К. Трофимову, Б. М. Фитингофу, Ю. М. Штарькову, так и зарубежным исследователям Я. Зиву (J. Ziv), Дж. Клири (J. Cleary), А. Лемпелу (А. Lempel), И. Рисса-нену (J. Rissanen), И. Уиттену (I. Witten), П. Элайесу (Р. Elias) и
ДР-
Основными параметрами методов рандомизации являются избыточность, определяемая как разность между средней длиной кодового слова и энтропией источника, и количество используемых при кодировании случайных символов. Для основных областей применения рандомизации крайне важно обеспечение заданных (произвольно низких) значений этих параметров.
Известные до недавнего времени статические методы рандомизации были чрезвычайно трудоемкими с вычислительной точки зрения, а именно, для достижения низкой избыточности и числа используемых случайных символов они требовали экспоненциально растущей памяти кодера и декодера (или экспоненциально растущего времени кодирования и декодирования). Высокая сложность этих методов препятствовала их практическому применению. В области универсального кодирования также оставались проблемы сложности методов, ограничивающие их практическое применение.
Цель работы
1. Построение эффективных методов полной рандомизации сообщений, характеризуемых неэкспоненциально растущими
пямятью и временем при достижении заданных, произвольно малых избыточности и числа используемых случайных символов.
2. Разработка адаптивных методов кодирования источников, обладающих на порядок более низкой вычислительной сложностью, чем ранее известные.
Задачи исследования
Для достижения указанных целей в рамках диссертационной работы решаются следующие задачи.
1. Построение эффективного метода полной рандомизации, характеризующегося неэкспоненциальным ростом объема памяти кодера и декодера и времени кодирования и декодирования, и использующего при кодировании небольшое число случайных символов.
2. Построение метода полной рандомизации, характеризующегося логарифмическим ростом объема памяти и времени, однако использующего два случайных бита на кодируемый символ.
3. Синтез двух выше указанных методов для обеспечения одновременно заданных, произвольно низких избыточности и числа случайных символов, используемых при кодировании.
4. Построение быстрых алгоритмов для выполнения операций с кумулятивными вероятностями при возрастающем размере алфавита источника.
5. Построение и применение эффективных структур данных для оценивания статистики произвольного источника с за-
данной точностью.
Методы исследования
В процессе исследований были использованы основные положения теории передачи сообщений, кодирования дискретных источников, теории сложности алгоритмов и теории вероятностей.
Научная новизна результатов работы
1. Разработан метод полной рандомизации сообщений, основанный на эффективном блоковом кодировании, обеспечивающий произвольно низкую избыточность при линейном росте объема памяти и логарифмическом росте времени кодирования. Данный метод использует сколь угодно малое число случайных бит.
2. Разработан метод полной рандомизации сообщений, основанный на арифметическом кодировании, обеспечивающий произвольно низкую избыточность кода при экспоненциально меньшем, чем для первого метода, объеме памяти, но большом количестве случайных бит, используемых при кодировании.
3. Осуществлен синтез двух вышеуказанных методов для обеспечения одновременно заданных, произвольно низких избыточности и числа случайных символов при некоторой средней вычислительной сложности.
4. Разработан метод кодирования источников с неизвестной статистикой, обеспечивающий заданную избыточность на
классе всех бернуллиевских и марковских источников и требующий лишь логарифмического роста времени кодирования и декодирования при увеличении размера алфавита источника.
5. Разработан метод кодирования для источников с неизвестной статистикой, основанный на мнимом скользящем окне и арифметическом кодировании, позволяющй на порядок снизить необходимый объем памяти кодера и декодера по сравнению с ранее известными методами.
Практическая ценность результатов
1. Разработанные методы полной рандомизации обеспечивают построение безусловно стойких и высокоскоростных методов защиты информации для систем с известной статистикой.
2. Предложенные методы адаптивного кодирования применяются в случае источников с неизвестной статистикой для построения стойких криптосистем или для повышения практической стойкости существующих шифров.
3. Предложенные методы уменьшения вычислительной сложности адаптивного кодирования могут быть использованы в составе многих практических методов сжатия данных, применяемых к произвольным источникам информации, для повышения степени сжатия и производительности.
4. Разработанные методы омофонного декодирования применяются в многочисленных задачах, требующих генерации произвольно распределенных случайных величин, и обеспечивают низкую сложность генераторов.
Основные положения, выносимые на защиту
1. Для решения задачи полной рандомизации при макимально ограниченном использовании случайных бит на основе эффективного блокового кодирования разработан метод, обеспечивающий произвольно низкую избыточность и требующий линейного роста объема памяти кодера и декодера и логарифмического роста времени кодирования и декодирования.
2. Для решения задачи полной рандомизации при неограниченном использовании случайных бит построен более эффективный метод, обеспечивающий произвольно низкую избыточность при логарифмическом росте как времени кодирования, так и объема памяти.
3. Синтез двух разработанных методов приводит к построению класса кодов, обеспечивающих одновременно заданные избыточность и число случайных символов при минимальной (на сегодняшний день) вычислительной сложности.
4. Известные методы, использующие арифметическое кодирование, требуют линейного роста времени кодирования и декодирования при увеличении размера алфавита источника. Метод, основанный на быстром вычислении кумулятивных вероятностей, требует лишь логарифмического роста времени при увеличении размера алфавита.
5. Использование структуры данных "мнимое скользящее окно" в сочетании с арифметическим кодированием позволяет на порядок снизить необходимый объем памяти кодера и декодера при обеспечении заданной, произвольно низкой из-
быточности в случае кодирования источника с неизвестной статистикой.
Структура и объем работы
Диссертация состоит из введения, пяти глав, заключения и списка литературы.
В первой главе формулируется задача полной рандомизации сообщений, дается определение омофонных кодов, обзор известных методов построения этих кодов с анализом их вычислительной сложности; излагаются основные идеи построения эффективного метода полной рандомизации при экономном расходовании случайных символов и приводится точное описание метода (раздельно для случаев с двоично-рациональными и произвольными рациональными вероятностями символов); исследуются основные свойства разработанного метода.
Во второй главе ставится задача разработки более эффективного метода полной рандомизации при отсутствии ограничений на число используемых при кодировании случайных символов, рассматриваются подходы к построению такого метода, дается точное описание метода и исследуются его основные свойства.
В третьей главе проводится синтез двух разработанных методов полной рандомизации, рассматриваются приложения построенных кодов, возникающие в криптографии и в задачах генерации случайных величин.
В четвертой главе рассматривается задача рандомизации при неизвестной статистике источника, дается обзор известных методов универсального и адаптивного кодирования, описывается разработанный метод адаптивного кодирования, эффективный
в случае больших алфавитов источника, исследуются основные свойства метода.
В пятой главе описывается разработанный метод адаптивного кодирования, обеспечивающий существенное уменьшение требуемого объема памяти кодера и декодера, исследуются свойства этого метода; дается обобщение методов адаптивного кодирования на случай марковских источников и рассматриваются некоторые детали реализации.
Заключение содержит основные выводы диссертационной работы, сведения об апробации, публикации и реализации результатов работы.
Диссертация содержит 149 страниц машинописного текста, 10 рисунков и 7 таблиц. Список литературы включает 77 наименований.
Похожие диссертационные работы по специальности «Системы, сети и устройства телекоммуникаций», 05.12.13 шифр ВАК
Методы адаптивной коррекции параметров помехоустойчивого кода и их применение в перспективных системах радиосвязи2010 год, доктор технических наук Квашенников, Владислав Валентинович
Методы лексикографического декодирования избыточных кодов на базе модификаций стирающего канала связи2015 год, доктор наук Гладких Анатолий Афанасьевич
Последовательное адаптивное кодирование в параметрически определенной системе счетных двоичных кодов для применения в алгоритмах LZ-компрессии2001 год, кандидат технических наук Гаджиев, Юрий Абдурахманович
Разработка и исследование характеристик LDPC кодов для спутникового канала2021 год, кандидат наук Ле Ван Шон
Разработка и моделирование алгоритмов мягкого декорирования блоковых кодов в каналах со стиранием элементов и использованием процедуры кластерного анализа2008 год, кандидат технических наук Мансуров, Алмаз Ингелович
Заключение диссертации по теме «Системы, сети и устройства телекоммуникаций», Фионов, Андрей Николаевич
Основные результаты диссертации получены в рамках работы по проекту №96-01-00052 "Асимптотически оптимальные коды для стационарных источников информации", финансируемому Российским фондом фундаментальных исследований, и в процессе выполнения НИР Государственного комитета РФ по связи и информатизации "Аспект-Сибирь" по теме "Разработка высокоскоростных методов сжатия данных".
Планируется практическая реализация разработанных методов при решении задач защиты информации в Internet в рамках проекта N298-01-00772 "Теоретическое обоснование и реализация эффективных доказуемо-стойких методов защиты информации для полнотекстовых баз данных в среде Internet", финансируемого Российским фондом фундаментальных исследований.
Результаты диссертации используются в учебном процессе при чтении курсов "Основы криптографии" и "Теория вычислительных процессов и систем", а также при выполнении дипломных проектов в СибГУТИ.
ЗАКЛЮЧЕНИЕ
Список литературы диссертационного исследования кандидат технических наук Фионов, Андрей Николаевич, 1998 год
ЛИТЕРАТУРА
[1] Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.
[2] Бабкин В. Ф. Метод универсального кодирования независимых сообщений неэкспоненциальной трудоемкости // Пробл. передачи информ. 1971. Т. 7, №4. С. 13-21.
[3] Галлагер Р. Теория информации и надежная связь. М.: Советское радио, 1974.
[4] Кнут Д. Искусство программирования для ЭВМ. Т. 2. М.: Мир, 1977.
[5] Кричевский Р. Е. Оптимальное кодирование источника на основе наблюдений // Пробл. передачи информ. 1975. Т. 11, №4. С. 37-42.
[6] Кричевский Р. Е. Сжатие и поиск информации. М.: Радио и связь, 1989.
[7] Рябко В. Я. Кодирование источника с неизвестными, но упорядоченными вероятностями // Пробл. передачи информ. 1979. Т. 14, т. С. 71-77.
[8] Рябко Б. Я. Сжатие данных с помощью "стопки книг" // Пробл. передачи информ. 1980. Т. 16, №4. С. 16-21.
[9] Рябко Б. Я. Дважды универсальное кодирование // Пробл. передачи информ. 1984. Т. 20, №3. С. 24-28.
[10] Рябко В. Я. Быстрый алгоритм адаптивного кодирования // Пробл. передачи информ. 1990. Т. 26, №4. С. 24-37.
[11] Рябко Б. Я. Эффективный метод кодирования источников информации, использующий алгоритм быстрого умножения // Пробл. передачи информ. 1995. Т. 31, №1. С. 3-12.
[12] Рябко Б. Я. Сжатие данных с помощью "мнимого скользящего окна" // Пробл. передачи информ. 1996. Т. 32, №2. С. 22-30.
[13] Трофимов В. К. Избыточность универсального кодирования произвольных марковских источников // Пробл. передачи информ. 1974. Т. 10, №4. С. 16-24.
[14] Феллер В. Введение в теорию вероятностей и ее приложения. М.: Мир, 1984.
[15] Фитингоф Б. М. Оптимальное кодирование при неизвестной и меняющейся статистике сообщений // Пробл. передачи информ. 1966. Т. 2, №2. С. 3-11.
[16] Шеннон К. Работы по теории информации и кибернентике. М.: Изд. иностр. лит., 1963. С. 333-402.
[17] Штарьков Ю. М. Универсальное последовательное кодирование отдельных сообщений // Пробл. передачи информ. 1987. Т. 23, №3. С. 3-17.
[18] Штарьков Ю. М. Некоторые теоретико-информационные задачи защиты дискретных данных // Пробл. передачи информ. 1994. Т. 30, №2. С. 49-60.
[19] Abrahams J. Generation of discrete distributions from biased coins // IEEE Trans. Inform. Theory. 1996. V. 42, №5. P. 1541-1546.
[20] Ahlswede R. Remarks on Shannon's secrecy systems // Probl. of Control and Inform. Theory. 1982. V. 11, №4. P. 301-318.
[21] Bell T. C., Cleary J. G., Witten I. H. Text compression. Englewood Cliffs, NJ: Prentice Hall, Inc., 1990.
[22] Bentley J. L., Sleator D. D., Tarjan R. E. Wei V. K. A
locally adaptive data compression scheme // Comm. ACM. 1986. Y. 29, №4. P. 320-330.
[23] Brickel E. F., Odlyzko A. M. Cryptoanalysis: a survey of recent results // Proc. of the IEEE. 1988. V. 76, №5. P. 578-593.
[24] Cleary J. G., Witten I. H. Data compression using adaptive coding and partial string matching // IEEE Trans. Commun. 1984. V. 32, №4. P. 396-402.
[25] Cleary J. G., Witten I. H. A comparison of enumerative and adaptive codes // IEEE Trans. Inform. Theory. 1984. V. 30, №2. P. 306-315.
[26] Cover T. M. Admissibility properties of Gilbert's encoding for unknown source probabilities // IEEE Trans. Inform. Theory. 1972. V. 18, m. P. 216-276.
[27] Cover T. M. Enumerative source encoding // IEEE Trans. Inform. Theory. 1973. V. 19, №1. P. 73-77.
[28] Davisson L. Universal noiseless coding // IEEE Trans. Inform. Theory. 1973. V. 19, №6. P. 783-795.
[29] Davisson L., Leon-Garcia A. Source matching approach to finding minimax codes // IEEE Trans. Inform. Theory. 1980. V. 26, №2. P. 166-174.
[30] Davisson L., McElies R., Pursley M., Wallace M. Universal noiseless codes // IEEE Trans. Inform. Theory. 1981. V. 27, №3. P. 269-279.
[31] Elias P. Minimax optimal universal codeword sets // IEEE Trans. 1983. V. 29, №4. P. 491-502.
[32] Elias P. Interval and recency rank source encoding: two on-line adaptive variable-length schemes // IEEE Trans. 1987. V. 33M. P. 3-10.
[33] Fitingof B., Waksman Z. Fuzed trees and some new approaches to source coding // IEEE Trans. Inform. Theory. 1988. V. 34, №3. P. 417-424.
[34] Gehrmann Ch. An adaptive homophonic algorithm // Proc. IEEE Int. Symp. on Inform. Theory. San Antonio, 1993. P. 280.
[35] Gehrmann Ch. Remarks on theoretical treatments of secrecy systems // Proc. 7th Joint Swedish-Russian Int. Workshop on Inform. Theory. St. Petersburg, June 1995. P. 84-88.
[36] Guazzo M. A general minimum-redundancy source-coding algorithm // IEEE Trans. Inform. Theory. 1980. V. 26, №1. P. 1525.
[37] Günther Ch. G. A universal algorithm for homophonic coding // Advances in Cryptology - EUROCRYPT'88. N.Y.: Springer, 1988. P. 405-414 (Lecture Notes in Comput. Sei.: V. 330).
[38] Han T. S., Hoshi M. Interval algorithm for random number generation // IEEE Trans. Inform. Theory. 1997. V. 43, №2. P. 599-611.
[39] Jelinek F. Probabilistic Information Theory. New York: McGraw-Hill, 1968. P. 476-489.
[40] Jendal H. N., Kuhn Y. J. B., Massey J. L. An information-theoretic treatment of homophonic substitution // Advances in Cryptology - EUROCRYPT'89. Berlin: Springer, 1990. P. 382-394 (Lecture Notes in Comput. Sei.: V. 434).
[41] Kahn D. The codebreakers, the story of secret writing. New York, NY: MacMillan, 1967.
[42] Knuth D. E., Yao A. C. The compexity of nonuniform random number generation // Algorithms and Complexity: New Directions and Recent Results. New York: Academic Press, 1976. P. 357-428.
[43] Krichevsky R. E., Trofimov V. K. The performance of universal encoding // IEEE Trans. Inform. Theory. 1981. V. 27, №2. P. 199207.
[44] Langdon G.G., Rissanen J. A simple general binary source code // IEEE Trans. Inform. Theory. 1982. V. 28, №9. P. 800-803.
[45] Langdon G. G. An introduction to arithmetic coding // IBM J. Res. Dev. 1984. V. 28, №2. P. 135-149.
[46] Massey J. L. An introduction to contemporary cryptology // Proc. of the IEEE. 1988. V. 76, №5. P. 533-549.
[47] Massey J. L. Some applications of source coding in cryptography // European Trans, on Telecommunications. 1994. V. 5, №4. P. 421— 429.
[48] Moffat A. A note on the PPM data compression algorithm. Res. Rep. 88/7, Dep. Comput. Sei. Univ. of Melbourne. Australia, 1988.
[49] Pasco R. Source coding algorithm for fast data compression. Ph. D. thesis, Dept. Elect. Eng. Stanford Univ. Stanford, CA, 1976.
[50] Penzhorn W. A fast homophonic coding algorithm based on arithmetic coding // Fast Software Encryption. Berlin: SpringerVerlag, 1995. P. 329-345 (Lecture Notes in Comput. Sei.; V. 1008).
[51] Rissanen J.J. Generalized Kraft inequality and arithmetic coding // IBM J. Res. Dev. 1976. V. 20, №5. P. 198-203.
[52] Rissanen J. J., Langdon G. G. Arithmetic coding // IBM J. Res. Dev. 1979. V. 23, №2. P. 149-162.
[53] Rissanen J., Langdon G. G. Universal modeling and coding // IEEE Trans. Inform. Theory. 1981. V. 27, №1. P. 12-23.
[54] Rissanen J., Mohiuddin K. M. A multiplication-free multialphabet arithmetic code // IEEE Trans, on Communications. 1989. V. 37, №2, P. 93-98.
[55] da Rocha Jr. V. C., Massey J. L. On the entropy bound for optimum homophonic substitution // Proc. IEEE Int. Symp. Inform. Theory. Ulm, July 1997. P. 93.
[56] Roche J. R. Efficient generation of random variables from biased coins // Proc. IEEE Int. Symp. Inform. Theory. 1991. P. 169.
[57] Rubin F. Arithmetic stream coding using fixed precision registers // IEEE Trans. Inform. Theory. 1979. V. 25, №6. P. 672-675.
[58] Ryabko B. Y. Fast and effective coding of information sources // IEEE Trans. Inform. Theory. 1994. V. 40, №1. P. 96-99.
[59] Shtarkov Y. M., Babkin V. F. Combinatorial encoding for discrete stationary sources // Proc. IEEE Int. Symp. Inform. Theory. Budapest, 1973. P. 249-257.
[60] Willems F. M. J., Shtarkov Y. M., Tjalkens T. J. The
context-tree weighting method: Basic properties // IEEE Trans. Inform. Theory. 1995. V. 41, №3. P. 653-664.
[61] Witten I. H., Neal R., Cleary J. G. Arithmetic coding for data compression // Comm. ACM. 1987. V. 30, №6. P. 520-540.
[62] Ziv J., Lempel A. A universal algorithm for sequential data compression // IEEE Trans. Inform. Theory. 1977. V. 23, №3. P. 337-343.
[63] Ziv J., Lempel A. Compression of individual sequences via variable-rate coding // IEEE Trans. Inform. Theory. 1978. V. 24, №5. P. 530-536.
Работы автора, в которых изложены основные результаты диссертации
Статьи
[64] Ryabko В. Y., Fionov А. N. A fast and efficient homophonic coding algorithm // Algorithms and Computation. Berlin: Springer, 1996. P. 427-438 (Lecture Notes in Comput. Sci.: V. 1178).
[65] Рябко Б. Я., Фионов А. Н. Быстрый метод полной рандомизации сообщений // Пробл. передачи информ. 1997. Т. 33, №3. С. 3-14.
[66] Фионов А. Н. Эффективный метод рандомизации сообщений на основе арифметического кодирования // Дискретный анализ и исследование операций. 1997. Т. 4, №2. С. 51-74.
[67] Рябко Б. Я., Федотов А. М., Фионов А. Н. Надежные системы защиты электронных публикаций, базирующиеся на эффективном омофонном кодировании // Вычислительные технологии. 1997. Т. 2, №3. С. 68-72.
[68] Ryabko В. Ya., Fionov А. N. Homophonic coding with logarithmic memory size // Algorithms and Computation. Berlin: Springer, 1997. P. 253-262 (Lecture Notes in Comput. Sci.; V. 1350).
Доклады на конференциях
[69] Фионов А.Н. Быстрый метод полной рандомизации сообщений // Российская научно-техн. конф. "Информатика и проблемы телекоммуникаций". Тезисы докладов. Новосибирск, 1996. Т. 1. С. 70.
[70] Фионов А. Н. Эффективная рандомизация сообщений на основе арифметического кодирования // Международная научно-техн. конф. "Информатика и проблемы телекоммуникаций". Материалы конференции. Новосибирск, 1997. С. 157158.
[71] Ryabko В., Fionov A. Decreasing redundancy of homophonic coding // Proc. IEEE Int. Symp. Inform. Theory. Ulm, July 1997. P. 94.
[72] Рябко Б. Я., Федотов А. М., Фионов А. Н. Современные средства криптографической защиты информации в сетях передачи данных // Международная конф. "Современные информационные технологии". Материалы конференции. Новосибирск, 1998. С. 42-44.
[73] Рябко Б. Я., Фионов А. Н., Федотов А. М. Конфиденциальность взаимодействий в открытых информационных сетях // Международный семинар "Перспективы развития современных средств и систем телекоммуникаций". Материалы семинара. Новосибирск, 1998. С. 38-42.
[74] Fionov А. N. Computationally efficient randomization of messages // Международная Сибирская конф. по исслед. операций. Материалы конференции. Новосибирск, 1998. С. 159.
[75] Ryabko В. Ya., Fionov А. N. Efficient algorithm of adaptive arithmetic coding // Международная Сибирская конф. по ис-
след. операций. Материалы конференции. Новосибирск, 1998. С. 151.
[76] Fionov А. N. Using homophonic decoding for random number generation // Международный семинар "Распределенная обработка информации". Материалы семинара. Новосибирск, 1998. С. 63-67.
[77] Ryabko В., Fionov A. Fast homohponic coding with logarithmic memory size // Proc. IEEE Int. Symp. Inform. Theory, Cambridge, August 1998. P. 52.
"УТВЕРЖДАЮ"
>р по научной работе СибГУТИ . МАИ, профессор
Ю. Д. Козляев
ря 1998 г.
научно-техническои комиссии о реализации научных данных, положений и выводов кандидатской диссертации Фионова Андрея Николаевича
Комиссия в составе:
начальник НИС, к.т.н. В. В. Шиф — председатель, доцент, к.т.н. И. В. Перцев, доцент, к.т.н. П. В. Сафонов,
констатирует, что в диссертационной работе аспиранта кафедры ПМиК А. Н. Фионова на тему "Методы эффективной рандомизации сообщений, базирующиеся на омофонном и арифметическом кодировании" рассматриваются теоретические вопросы и практические решения по разработке методов и алгоритмов рандомизации сообщений, обеспечивающие построение надежных систем защиты информации, передаваемой по каналам связи, а также позволяющие строить эффективные модели источников информации при отработке и моделировании систем связи.
Основные результаты диссертации А. Н. Фионова получены в рамках работы по проекту №96-01-00052 "Асимптотически оптимальные коды для стационарных источников информации", финансируемому Российским фондом фундаментальных исследований, и в процессе выполнения НИР Государственного комитета РФ по связи и информатизации "Аспект-Сибирь"|по теме "Разработка высокоскоростных методов сжатия данных''.
Председатель комиссии ' \ /В. Б. Шиф/
Члены комиссии ЦлС^ Перцев/
/ /./ '-" /П. В. Сафонов/
ЧГ» сентября 1998 г.
российская академия наук
ордена ленина сибирское отделение
ИНСТИТУТ ВЫЧИСЛИТЕЛЬНЫХ ТЕХНОЛОГИЙ
630090, г. Новосибирск-90, пр. Академика Лаврентьева, 6. Тел.: (383-2) 34-11-50, Факс: (383-2) 34-13-42, E-mail: ict@ict.nsc.ru ИНН 5408105390, БИК 045003821, ОКПО 05222159, ОКОНХ 95110, р/с 40503810400120000032 в ОАО "Сибакадембанк"; кор.сч. 30101810400000000821 в Советском РКЦ г. Новосибирска
От_№ 15312-_
на №_от_
Справка
о внедрении результатов диссертационной работы А. Н. Фионова "Методы эффективной рандомизации сообщений, базирующиеся на омофонном
и арифметическом кодировании"
Настоящим подтверждаю, что результаты научных исследований, полученные в диссертационной работе А.Н.Фионова, используются при разработке программного обеспечения для защиты информации полнотекстовых баз данных в среде Internet в рамках проекта № 98-01-00772 "Теоретическое обоснование и реализация эффективных доказуемо стойких методов защиты информации для полнотекстовых баз данных в среде Internet", финансируемого Российским фондом фундаментальных исследований.
Разработанные А.Н.Фионовым методы применяются при построении процедур шифрования данных на различных уровнях обработки информации, передаваемой в сети. Целесообразность применения этих методов объясняется тем, что известные практические методы защиты информации не обеспечивают доказуемую стойкость шифров, а известные доказуемо стойкие методы имеют высокую сложность, препятствующую их практическому применению.
АН.Фионовым был получен класс методов рандомизирующего кодирования источников информации, характеризуемый экспоненциально более низкими затратами времени и памяти по сравнению с известными методами. Построенные коды позволили впервые реализовать доказуемо стойкие шифры, достаточно быстрые и простые для их практического применения.
а
УТВЕРЖДАЮ
( 77 В. П. Бакалов
сентября 1998 г.
^осГ/^мстор СибГУТИ
АКТ ВНЕДРЕНИЯ
результатов диссертационной работы А. Н. Фионова "Методы эффективной рандомизации сообщений, базирующиеся
Комиссия в составе:
первый проректор СибГУТИ, проф. С. Г. Ситников — председатель,
доцент, к.т.н. В. И. Крамаренко,
доцент, к.т.н. Е. И. Ситняковская,
констатирует, что результаты диссертационной работы аспиранта кафедры ПМиК А. Н. Фионова активно используются в учебном процессе. Предложенные в диссертации методы рассматриваются в курсе "Основы криптографии" при изучении доказуемо стойких криптосистем с секретным ключом. Алгоритмы, разработанные А. Н. Фионовым, используются в лабораторных и курсовых работах в курсе "Теория вычислительных процессов и систем". На основе разработанных А. Н. Фионовым методов формируются задания на дипломное проектирование.
на омофонном и арифметическом кодирований
¿6" сентября 1998 г.
Председатель коми< Члены комиссии
Обратите внимание, представленные выше научные тексты размещены для ознакомления и получены посредством распознавания оригинальных текстов диссертаций (OCR). В связи с чем, в них могут содержаться ошибки, связанные с несовершенством алгоритмов распознавания. В PDF файлах диссертаций и авторефератов, которые мы доставляем, подобных ошибок нет.