Авторефераты по всем темам >>
Авторефераты по техническим специальностям
На правах рукописи
Кабатянский Григорий Анатольевич
Блоковые коды, исправляющие ошибки, и их применения к задачам защиты информации
05.13.17 - Теоретические основы информатики
Автореферат диссертации на соискание ученой степени доктора физико-математических наук
Москва - 2009
Работа выполнена в Институте проблем передачи информации им. А.А. Харкевича Российской академии наук
Официальные оппоненты: доктор технических наук, профессор Э.М. Габидулин доктор физико-математических наук А.М. Райгородский доктор физико-математических наук С.А. Степанов
Ведущая организация: Институт математики им. С.Л. Соболева СО РАН
Защита состоится У Ф 2009 г. в 11 часов на заседании Диссертационного совета Д.002.077.01 при Институте проблем передачи информации им. А.А. Харкевича РАН по адресу: 127994, Москва, ГСП-4, Б. Каретный пер., 19, стр. 1.
С диссертацией можно ознакомиться в библиотеке Институте проблем передачи информации им. А.А. Харкевича РАН Автореферат разослан У Ф 2009 г.
Ученый секретарь Диссертационного совета Д.002.077.доктор физико-математических наук И.И. Цитович
Общая характеристика работы
Актуальность темы. Теория кодирования или теория кодов, исправляющих ошибки, ведет свой отсчет от опубликованной 60 лет назад работы Хэмминга, в которой были построены коды, исправляющие одиночные ошибки. С математической точки зрения теория кодирования может рассматриваться как теория упаковок одного специального класса дискретных метрических пространств, называемых пространствами Хэмминга. В теоретически наиболее изученном и, одновременно, наиболее интересном для практики случае двоичных корректирующих кодов n соответствующее двоичное пространство Хэмминга H2 есть не что иное как n-мерный булев куб {0, 1}n с расстоянием, называемым расстоянием Хэмминга и определяемым как число координат, в которых две данные вершины куба различны. Код, исправляющий t ошибок, это упаковка n пространства H2 шарами радиуса t, а кодовые слова - это центры шаров упаковки. Таким образом, код это произвольное подмножество C n пространства H2, и код исправляет t ошибок, если d(C) > 2t, где расстояние кода d(C) определяется как минимальное попарное расстояние между точками (словами) кода. Размерность n объемлющего пространn ства H2 принято называть длиной кода. Основная проблема теории кодирования - нахождение максимальной мощности A2(n, 2t+1) двоичного кода длины n, исправляющего t ошибок, может быть переформулирована как нахождение максимальной плотности (n, t; 2) упаковки n-мерного n пространства Хэмминга H2 шарами радиуса t. Построенные Хэммингом n коды являются плотными упаковками пространств H2 шарами радиуса 1 при n = 2m - 1, т.е. (2m - 1, 1; 2) = 1. Несмотря на многочисленные результаты теории кодирования (библиография к книге МакВильямс и Слоэна УТеория кодов, исправляющих ошибкиФ, изданной в 1977 г., насчитывает почти полторы тысячи статей, посвященных теории кодирования) вопрос о величине (n, t; 2) не решен даже асимптотически. В частности, до работ автора был открытым вопрос о существовании предела (n, 1; 2) при n . В пользу естественной гипотезы lim (n, 1; 2) = 1, (1) n был опубликован ряд работ, в которых последовательно доказывалось, что lim(n, 1; 2) , где равно 5/8; 5427/8192; 5589/8192 (Sloane N.J.A. and Whitehead D.S., 1970; Кацман Г.Л., 1981; Лицин С.Н., 1984).
Эти работы основывались на конкретных хороших нелинейных кодах.
Hamming R.W. Error-Detecting and Error-Correcting Codes // Bell System Tech. J.
1950. V.29. № 1. P. 147-1Однако такой метод Упоследовательного улучшенияФ не мог дать окончательный (и ожидаемый) ответ, так как для доказательства этой гипотезы нужна бесконечная серия кодов возрастающей длины с плотностью упаковки, стремящейся к 1.
Для теории кодирования принципиально важным является не только построение кода, исправляющего ошибки, но и разработка для данного кода эффективного алгоритма декодирования, т.е. алгоритма нахоn ждения для произвольного вектора y H2 ближайшего кодового вектора, называемого декодированием по максимуму правдоподобия, или же алгоритма нахождения всех кодовых векторов, достаточно близких к y, называемого списочным декодированием. В частности, задача о наилучшем приближении произвольной булевой функции от m переменных многочленом (Жегалкина) степени не выше s равносильна задаче о декодировании кода Рида-Маллера (РМ) RM(s, m) длины n = 2m, где s называется порядком кода РМ. Отметим, что известное решение задачи о наилучшем приближении произвольной булевой функции линейными функциями, называемое машиной (алгоритмом) Грина, состоит в применении быстрого преобразования Фурье (БПФ) для группы Z2... Z2, а списочное декодирование кода Рида-Маллера первого порядка (РМ-1) в этом случае равносильно вычислению не всех, а лишь наиболее значимых коэффициентов дискретного преобразования Фурье. Сложность БПФ имеет порядок n log n, тогда как декодирование кода РМ-1 до половины расстояния имеет линейную (по n) сложность. Какое максимальное число ошибок можно исправлять с линейной сложностью было неизвестно даже в этом, наиболее изученном случае кодов РМ первого порядка.
Еще меньше было известно про сложность списочных алгоритмов декодирования для кодов РМ произвольного порядка.
Из множества задач защиты информации, понимаемой как обеспечение целостности информации в процессе ее передачи или хранения (под воздействием разнообразных атак и угроз), в диссертации рассмотрены те задачи, где для соответствующего Уканала передачи информацииФ была неизвестна положительность его пропускной способности, т.е. возможность УпередаватьФ сообщений экспоненциально много от некоторого параметра задачи, который естественно называть Удлиной кодаФ, обеспечивая при этом нулевую или стремящуюся к нулю вероятность ошибки с ростом Удлины кодаФ. Для каждой из рассмотренных задач нетривиальным является ее сведение к некоторой задаче теории информации и уже затем доказательство положительности пропускной способности соответствующего Уканала передачи информацииФ. Среди таких важных задач особо отметим задачу обнаружения целенаправленных ошибок, также известную как задача аутентификации сообщений. Начиная с первой открытой публикации, этой задаче уделялось большое внимание, однако до работ автора было неизвестно возможно ли, чтобы число сообщений росло экспоненциально от числа ключей.
В некотором смысле схожая ситуация возникла в задаче защиты информации от копирования группой (коалицией) пользователей. Эту задачу принято подразделять на задачи Упоиска пиратовФ и Уцифровых отпечатков пальцевФ. Возникающие при решении этих задач математические объекты называются t-идентифицирующими кодами и кодами цифровых отпечатков пальцев, соответственно. Лучший известный результат о кодах цифровых отпечатков пальцев показывал существование таких кодов длины n = O(t4 log(M/ ) log 1/ ) с вероятностью ошибки Perr , где M - это число пользователей, а размер коалиций не превышает t.
Тем самым, эти коды не обеспечивали привычной для теории информации экспоненциально малой от n вероятности ошибки даже при очень малых скоростях кода. Кроме того, для этих кодов был предложен только переборный алгоритм декодирования (идентификации). Для задачи о t-идентифицирующих кодах, существование таких кодов со скоростью, отделенной от нуля, было известно лишь для t = 2.
В отличие от предыдущих задач защиты информации, которые являются современными (возникли в XX веке), задаче стеганографии (скрытописи) несколько тысяч лет. Правда, первая формализованная постановка задачи стеганографии также появилась менее сорока лет назад в работе Г.Симмонса. В ней предлагались две модели поведения противника (УнадзирателяФ - в терминологии Симмонса): пассивная и активная.
И если для пассивной модели ее Упропускная способностьФ была найдена независимо рядом исследователей в силу эквивалентности этой задачи с задачей о кодах-покрытиях, то вопрос о положительности Упропускной способностиФ для активной модели оставался открытым до работ автора.
Цель работы. Целью работы является исследование свойств оптимальных или близких к оптимальным блоковых кодов, исправляющих ошибки, и возможностей их применения в задачах защиты информации.
Методы исследования. В наших исследованиях использованы методы теории информации и теории кодирования, в частности, метод случайного кодирования, а также методы алгебры, комбинаторики и теории сложности вычислений.
Gilbert E.N., MacWilliams F.J., Sloane N.J.A. Codes which detect deception // Bell System Tech. J. 1974. V.53. № 3. P. 405-4Simmons G.J. The PrisonerТs Problem and the Subliminal Channel // Proc.
CRYPTOТ83. 1984. P. 51-Научная новизна. Научная новизна работы определяется следующими новыми, впервые полученными автором результатами:
- построены покрытия и упаковки шарами радиуса 1 пространств Хэмминга, плотность которых стремится к 1 с ростом размерности пространств;
- разработаны алгоритмы списочного декодирования кодов РидаМаллера фиксированного порядка, которые при числе исправляемых ошибок не более расстояния кода имеют Упочти линейнуюФ (n log n) от длины кода n сложность, тогда как ранее известные методы списочного декодирования имели сложность порядка n3;
- разработаны алгоритмы списочного декодирования кодов РидаМаллера первого порядка с асимптотически минимальной сложностью;
- построены ансамбли кодов с асимптотически ненулевой скоростью для ряда каналов, возникающих в таких задачах защиты информации как: аутентификация сообщений, стеганография, Упоиск пиратовФ и Уцифровые отпечатки пальцевФ.
Теоретическая и практическая ценность.
Работа носит теоретический характер. Теоретическая ценность диссертации определяется разработанными в ней новыми методами исследования кодов с исправлением ошибок, которые в сочетании с известными методами позволили получить новые результаты и доказать утверждения, существовавшие ранее в виде гипотез.
В частности, с помощью предложенного метода однородных упаковок и покрытий были построены коды-упаковки и коды-покрытия пространств Хэмминга шарами радиуса 1 с плотностью, равномерно стремящейся к 1 с ростом длины кода, и, тем самым, доказать одну из самых старых гипотез теории кодирования.
Разработанные методы декодирования позволяют списочно декодировать коды Рида-Маллера первого порядка с асимптотически минимальной сложностью и, тем самым, находить с линейной сложностью наиболее значимые коэффициенты дискретного преобразования ФурьеАдамара.
Предложенные методы построения ансамблей асимптотически хороших кодов с рядом специальных свойств позволили доказать положительность пропускной способности ряда Уканалов передачи информацииФ, соответствующих таким задачам защиты информации как аутентификация сообщений, Упоиск пиратовФ, Уцифровые отпечатки пальцевФ и стеганография.
Практическая ценность диссертационной работы определяется прежде всего разработанными алгоритмами списочного декодирования для кодов Рида-Маллера фиксированного порядка, сложность которых не только близка к теоретически минимальной, но и с практической точки зрения они весьма привлекательны для реализации в силу их логической простоты и рекурсивного характера. Представляют определенный практический интерес предложенные коды для построения цифровых отпечатков пальцев, так как они обладают достаточно простыми алгоритмами как порождения УотпечатковФ (кодирования), так и определения по фальшивому УотпечаткуФ одного из членов коалиции, создавшей этот УотпечатокФ (декодирование).
Апробация результатов и публикации. Результаты работы неоднократно докладывались на научных семинарах в МГУ им. М.В. Ломоносова под руководством В.И. Левенштейна (70еЦ90-е гг.), на научных семинарах в ИППИ РАН под руководством Р.Л. Добрушина, Р.А. Минлоса и М.С. Пинскера (1975 - по настоящее время), на VII-IX Всесоюзных конференциях по теории кодирования и передачи информации, а также на многочисленных международных конференциях по теории информации, в частности, на симпозиумах IEEE по теории информации (1994, 1996, 2001-04,2006-07), на конференциях EurocryptТ93, CryptoТ94,95, на конференциях Algebra, Geometry and Coding Theory, Luminy, France, 2003-09, на семинарах Algebraic and Combinatorial Coding Theory, 2004, 2006, 2008.
Основные материалы диссертации изложены в 28 работах.
Структура и объем работы. Диссертация состоит из введения, трех глав, заключения и списка литературы. Текст работы изложен на 186 страницах. Список литературы содержит 207 наименований.
Содержание работы Во введении дано неформальное описание основных задач теории кодирования, известных результатов и открытых проблем. Кратко поставлены задачи, решаемые в диссертации, и сформулированы получаемые результаты.
В первой главе изложено решение задачи об асимптотике мощности упаковок (кодов) и покрытий пространства Хэмминга шарами радиуса 1. Как уже было отмечено ранее, самые первые результаты по теории кодирования - граница Хэмминга и коды Хэмминга, утверждают, что максимальная мощность A2(n, 3) двоичного кода, исправляющего одиночные ошибки, не больше чем 2n/(n + 1), и что эта граница достигается на кодах Хэмминга при n = 2r - 1, r = 2, 3,.... В пользу гипотезы об асимптотической точности этой границы (эквивалентной гипотезе (1)), т.е. справедливости равенства lim (n + 1)A2(n, 3)2-n = 1, (2) n был опубликован ряд работ4,5,6, в которых последовательно доказывалось, что lim(n + 1)A2(n, 2t + 1)2-n , где равнялось, соответственно, 5/8; 5427/8192; 5589/8192. Эти работы основывались на конструкции Плоткина (см. ниже) и некоторых новых хороших нелинейных кодах длин 11, 66, 67 и 143 с плотностями упаковки равными, соответственно, 27/32, 201/256, 187/256, (27/32)2. Как уже отмечалось в начале автореферата, таким образом можно последовательно улучшать оценки на lim(n, 1; 2), но нельзя доказать гипотезу (1-2). Была известна и аналогичная гипотеза для покрытий - предполагалось, что плотность лучших покрытий двоичных пространств Хэмминга шарами радиуса также стремится к 1. Более того, естественно рассматривать обобщения обеих гипотез на пространства Хэмминга над произвольным конечным алфавитом.
Для изложения результатов нам понадобятся следующие определеn ния. Множество Hq, состоящее из всех слов длины n над некоторым конечным алфавитом Hq из q букв, называется q-ичным n-мерным пространством Хэмминга. Нам будет удобно рассматривать алфавит Hq как абелеву группу по сложению (например, как группу Zq вычетов по модулю q), а если q есть степень простого числа - то как конечное поле Fq.
n На множестве Hq задаются вес и расстояние Хэмминга, определяемые как wt(x) = |{i : xi = 0}| и d(x, y) = |{i : xi = yi}| = wt(x - y), соот ветственно. Подмножество (код) C пространства Хэмминга называется n упаковкой (покрытием) шарами радиуса t, если для любого a Hq существует не более (соответственно, не менее) одного c C такого, что n d(a, c) t, или что тоже самое, если для любого a Hq уравнение c + e = a, c C, wt(e) t (3) имеет не более (не менее) одного решения (c, e).
Sloane N.J.A., Whitehead D.S. A New Family of Single-Error-Correcting Codes // IEEE Trans. Inform. Theory. 1970. V.16. № 6. P. 717-719.
Кацман Г.Л. О плотности упаковки шаров радиуса 1 в пространстве Хэмминга // Пробл. передачи информации. 1981. Т. 17. No 2. С. 52-56.
Litsyn S.N. New Non-Linear Codes with a Minimum Distance of 3 // Problems of Control and Inform. Theory. 1984. V.13. № 1. P. 13-15.
Если точки (слова) упаковки использовать для передачи сообщений по каналу связи, в котором при передаче n символов происходит не более t ошибок, то на приемной стороне возможно однозначное восстановление переданных сообщений, так как шары радиуса t с центрами в разных n кодовых словах не пересекаются. По этой причине упаковка C Hq шарами радиуса t также называется q-ичным кодом длины n, исправляющим t ошибок. Расстояние d(C) кода C определяется как минимальное из попарных расстояний между его словами d(C) = min d(c, c ), c =c C и код C является упаковкой шарами радиуса t (т.е. исправляет t ошибок), если и только если d(C) 2t + 1. Про код C мощности M = |C| говорят, что он способен передавать M сообщений, а величина R = R(C) = n-1 logq M называется скоростью кода. Коды (класс) называются хорошими, если их скорость R a > 0 (т.е. отделена от нуля) при n .
Для кода C, рассматриваемого как упаковка или покрытие шарами радиуса t, определим соответствующую плотность |C||Sq(n, t)| (C, t) =, (4) qn t где |Sq(n, t)| = (q-1)i (n) это мощность шара Sq(n, t) радиуса t в проi i=n странстве Хэмминга Hq. Очевидно, что плотность покрытия не менее 1, а упаковки (кода), соответственно, не более 1 (последнее неравенство в теории кодирования принято называть границей Хэмминга). Обозначив через (n, t; q) максимальную плотность упаковки n-мерного пространства n Хэмминга Hq шарами радиуса t (т.е. (n, t; q) = q-n|Sq(n, t)|Aq(n, 2t+1), где Aq(n, d) - максимальная мощность q-ичного кода с расстоянием не менее d), а через (n, t; q), соответственно, минимальную плотность покрытия, перепишем эти неравенства в виде (n, t; q) 1 (n, t; q) (5) Основной результат первой главы состоит в том, что для алфавитов, которые можно представить как конечное поле, т.е. для q = pm, где m = 1, 2,..., а p - простое число, справедливо lim (n, 1; q) = lim (n, 1; q) = 1 (6) n n Доказательство (6) основывается на на предложенной автором конструкции однородных упаковок и покрытий (см. Теорему 1 и Следствие 1), позволяющей строить упаковку (покрытие) шарами радиуса 1 из упаковки (покрытия) пространства Хэмминга произвольным однородным множеn ством. Множество U Hq называется однородным, если u U для любых u U, Fq. Говорят, что код C задает упаковку (покрытие) n пространства Hq множеством U, если {c+U}{c +U} = для c = c C n (соответственно, {c + U} = Hq ), или, что тоже самое, для любого cC n a Hq уравнение c + u = a, c C, u U (7) имеет не более (не менее) одного решения (c, u). Определим, как и в случае упаковок (покрытий) шарами, соответствующую плотность кода C как |C||U| (C, U) =. (8) qn Выберем в однородном U какую-либо систему попарно неколлинеарных представителей {u1, u2,..., uN}, где N = (|U| - 1)/(q - 1), т.е.
N U = {0} {ui} i=1 0 =Fq Теорема 1. Пусть код C является упаковкой (покрытием) пространn ства Hq однородным множеством U с системой попарно неколлинеарных представителей {u1, u2,..., uN }. Тогда код N VC,U = {x = (x1,..., xN ) Hq : x1u1 +... + xN uN C} (9) N является упаковкой (покрытием) пространства Hq шарами радиуса 1.
Доказательство теоремы следует из более общего утверждения, что N для любого b = (b1,..., bN) Hq уравнение вида (3) v + y = b, v VC,U, wt(y) имеет столько же решений, что и уравнение вида (7) c + u = S(b), c C, u U N с S(b) = biui.
i=n Так как для любого a Hq коды C и C + a одновременно являются n упаковкой (покрытием) пространства Hq множеством U, то, применив Теорему 1 ко всем кодам VC+a,U и посчитав среднюю плотность соответствующих упаковок (покрытий) VC+a,U шарами радиуса 1, получим, что среди них есть хотя бы одна (одно) с плотностью не УхужеФ чем (C, U).
А именно, справедливо n Следствие 1. Существуют a, a Hq такие, что (VC+a,U, 1) (C, U) для упаковок и (VC+a,U, 1) (C, U) для покрытий. Более того, если ранг U максимален, т.е. равен n, то (VC+a,U, 1) = (C, U) для всех a.
С помощью этой конструкции удается просто объяснить большинство ранее известных результатов об упаковках (покрытиях) пространств Хэмминга шарами радиуса 1. Так, из упаковок (покрытий) Ci пространств ni Hq, i = 1, 2 шарами радиуса 1 с плотностями i строится упаковка (поN крытие) пространства Hq шарами радиуса 1 с плотностью = 12, где N = (q - 1)n1n2 + n1 + n2. В частности, если выбрать в качестве одного из Ci код длины 1, состоящий из одного слова, то получим известную конструкцию Плоткина, позволяющую строить из произвольной упаковn ки (покрытия) шарами радиуса 1 пространства Hq упаковку (покрытие) пространства Хэмминга размерности (n+1)q -1 с той же плотностью.
Несмотря на казалось бы достаточную общность конструкции однородных упаковок и покрытий до сих пор известен лишь один пример семейства упаковок (покрытий) множествами U, который приводит к доказательству гипотезы (6), и этот пример, как это ни странно, снова упаковки (покрытия) шарами радиуса 1, но только пространств Хэмминга над nl другим алфавитом HQ. А именно, рассмотрим в пространстве Hq однородное множество Ul,n, состоящее из векторов, у которых ненулевые координаты принадлежат одному из n УотрезковФ {jl+1, jl+2,..., jl+l-1}, где j {0, 1,..., n - 1}. Это множество известно в теории кодирования как фазированные пакеты ошибок и очевидно, что упаковки (покрытия) такими множествами есть не что иное как упаковки (покрытия) шарами n радиуса 1 пространства Хэмминга HQ с Q = ql. Для того, чтобы поn строить нетривиальные упаковки (покрытия) HQ, т.е. отличные от укорочения (удлинения для покрытий) соответствующих кодов Хэмминга, используется следующая конструкция, известная для кодов (упаковок) как конструкция подкода над подмножеством.
Пусть V является упаковкой (покрытием) шарами радиуса 1 проn n странства HR. Тогда для любого a HR множество n Wa,V ; = {x HQ : ((x1), (x2),..., (xn)) a + V } n является упаковкой (покрытием) шарами радиуса 1 пространства HQ 1 при условии, что отображение : HQ HR инъективно в случае упаковок и сюръективно в случае покрытий. Применив эту конструкцию к R-ичным кодам Хэмминга, которые являются одновременно упаковками и покрытиями шарами радиуса 1, и воспользовавшись усреднением по a, получим следующий результат.
Предложение 1. Пусть R - степень простого числа, i - натуральное число и n = (Ri - 1)/(R - 1). Тогда для любого Q < R существует упаn ковка W пространства HQ шарами радиуса 1 с плотностью (W, 1) > (Q-1)/(R-1), и для любого Q > R существует покрытие W пространn ства HQ шарами радиуса 1 с плотностью (W, 1) < (Q - 1)/(R - 1).
Теперь положим Q = ql и рассмотрим упаковки и покрытия Предln ложения 1 как упаковки и покрытия множеством Ul,n пространства Hq.
Применив к ним Следствие 1, получим Теорема 2. Пусть R - степень простого числа, i, l - натуральные числа и (Ri - 1)(ql - 1) n =.
(R - 1)(q - 1) n Тогда в пространстве Hq при ql < R существует упаковка B шарами радиуса 1 с плотностью (B, 1) > (ql - 1)/(R - 1), а при ql > R существует покрытие C шарами радиуса 1 с плотностью (C, 1) < (ql - 1)/(R - 1).
Если в Теореме 2 брать l , а в качестве R выбирать простое число, достаточно близкое к ql, то получается последовательность упаковок (покрытий) с плотностью, стремящейся к 1, но эта последовательность длин недостаточно плотна, чтобы с ее помощью прямо доказывать гипотезу (6). Оставшиеся шаги доказательства используют очевидные процедуры укорочения упаковки (кода) и, соответственно, удлинения покрытия, упомянутую выше конструкцию Плоткина и известное утверждение из теории чисел, что для любой константы [11/20, 1] существует число N такое, что если x N, то между x и x имеется хотя бы одно простое число. В результате получаем основной результат первой главы.
Теорема 3. При фиксированном q, являющемся степенью простого числа, справедливо неравенство ln ln n |1 - (n, 1; q)| 4e ln2 q (1 + o(1)), (10) ln n где значок при (n, 1; q) опущен, так как соотношение (10) справедливо и для упаковок, и для покрытий.
Если мощность алфавита не есть степень простого числа и, следовательно, алфавит не может быть представлен в качестве конечного поля, то неизвестны ни справедливость гипотезы (6), ни существование хотя бы одной упаковки (покрытия) шарами радиуса 1 с плотностью 1, т.е., на языке теории кодирования, существование кода, исправляющего одиночные ошибки и достигающего границы Хэмминга. В несколько иной постановке задачи об исправлении ошибок, известной как коды с исправлением локализованных ошибок, построение кодов, исправляющих одиночные ошибки и достигающих границы Хэмминга, возможно, как показано в последнем параграфе первой главы, при любом q.
В общей формулировке задачи о кодах, исправляющих t локализованных ошибок, отправителю известны t позиций, где могут произойти ошибки. Поэтому правильнее говорить не о коде, а о кодировании = (m, E), которое сопоставляет сообщению m M и множеству E позиций, где возможны ошибки, кодовое слово (m, E), передаваемое по каналу. Уже в первой работе по кодам, исправляющим локализованные ошибки, было доказано, что для числа |M| передаваемых сообщений попрежнему справедлива граница Хэмминга. В частности, число сообщений |M| для q-ичного кода, исправляющего одиночные локализованные ошибки, не превышает qn/(1 + (q - 1)n). В з1.4 для произвольного q рекурсивно строятся коды длины nr = (qr - 1)/(q - 1) при r = 2, 3,... с числом сообщений |M| = qn-r, т.е. коды лежат на границе Хэмминга.
УНачальныйФ код длины n2 = q + 1 задается кодированием q-(m, j) = (m1,..., mq-1, - mi, j), i=где m = (m1,..., mq-1) M, mi Hq и j {1, 2,...q + 1} - местоположение возможной ошибки.
Содержание первой главы диссертации изложено в работах [3,4,8-10,18].
Во второй главе изучаются алгоритмы декодирования кодов РидаМаллера, в особенности, алгоритмы списочного декодирования. За почти 60 лет от момента их изобретения коды Рида-Маллера (РМ) были предметом многочисленных исследований. Хорошо известно, что только УкрайниеФ коды в этом классе, а именно, первого и последнего порядков, являются оптимальными. Популярность же кодов РМ в основном объясняется их простой и естественной структурой, а также эффективными алгоритмами их декодирования, построение которых началось с работы Рида (1954). С математической точки зрения декодирование двоичных кодов РМ - это интерполяция двоичных многочленов от многих переменных в ситуации, когда часть известных значений многочлена ошибочна.
Bassalygo L.A., Gelfand S.I., Pinsker M.S. Coding for channels with localized errors // Proc. Fourth Joint Swedish-Soviet International Workshop on Information Theory.
Gotland,Sweden, August, 1989. P. 95-99.
При этом классическая задача интерполяции, когда все известные значения функции верны и нужно восстановить функцию полностью, в теории кодирования называется задачей об исправлении стираний. Алгоритмически задача об исправлении стираний довольно проста, так как для любого линейного кода она сводится к задаче о решении системы линейных уравнений и, тем самым, имеет полиномиальную (от длины кода) сложность, тогда как задача об исправлении ошибок линейным кодом является NP -полной. В теории кодирования рассматривают и более общую задачу о совместном исправлении ошибок и стираний, а также ее дальнейшее обобщение на случай, когда известным значениям функции приписаны коэффициенты надежности, т.е. вероятности того, что данное значение правильно. Декодирование, соответствующее последней задаче, называется мягким (soft decoding).
Основным объектом исследования второй главы являются алгоритмы списочного декодирования кодов РМ. По определению, списочное декодирование радиуса T состоит в нахождении всех кодовых слов в шаре радиуса T вокруг произвольного принятого слова. Говоря формально, входом алгоритма списочного декодирования кода C с радиусом декодирования T является произвольный вектор y = (y1,...yn), а выходом множество (список) LT ;C(y) = {c C : d(y, c) T }. (11) Про алгоритм списочного декодирования с радиусом T говорят, что он исправляет T ошибок, понимая под этим, что если при передаче кодового слова c C произошло не более T ошибок (т.е. d(y, c) T ), то оно содержится в выходе алгоритма - списке LT ;C(y) (но как его дальше искать в этом списке - отдельная задача). Важный частный случай списочного d-декодирования, когда радиус T =, является наиболее популярной задачей декодирования, известной как Уисправление до d/2 ошибокФ. В этом случае результат декодирования (список) либо состоит из одного кодового слова, либо пуст.
В классе кодов Рида-Маллера особое внимание уделялось декодированию кодов первого порядка. Предложенный для них алгоритм МП декодирования, известный как Умашина ГринаФ, имеет сложность (в элементарных бинарных операциях) O(n log2 n) и является алгоритмом БПФ для группы Z2... Z2 (также называемым быстрым преобразованием Адамара) плюс алгоритм быстрой сортировки. С другой стороны, было известно (8 и [5]), что декодирование Удо d/2 ошибокФ имеет линейную сложность для любых кодов РМ фиксированного порядка. Но было Лицин С.Н. О сложности декодирования низкоскоростных кодов Рида-Маллера //Труды IX Всес. конф. по теории кодиров. и передачи информ.1988. Т.1. С. 202Ц204.
неизвестно, возможно ли списочное декодирование кодов РМ-1 с линейной сложностью при радиусе декодирования T d/2 ошибок. В з2.описан новый алгоритм списочного декодирования кодов РМ, названный автором алгоритмом критерия сумм (сокращенно, КС), который для кодов первого порядка находит список при радиусе декодирования T = (1 - )n/2 со сложностью O(n ln2(min{-2, n})) двоичных операций (здесь и всюду ниже 0 < 1). Частными случаями нового алгоритма при = 1/ n и = 1/2 являются Умашина ГринаФ и алгоритм декодирования Удо d/2 ошибокФ, соответственно.
Рассмотрим множество всех линейных булевых функций и сопоставим каждой такой функции c(x) = c0 + cixi (12) 1im n двоичный вектор c = (..., c(x),...) H2, где n = 2m, а x = (x1,..., xm) проm бегает по всем n точкам m-мерного булева куба H2. Получаемый двоичный код называется кодом Рида-Маллера первого порядка RM(1, m) и является оптимальным кодом, состоящим из 2n слов при кодовом расстоянии d = n/2. Из известной границы Джонсона на размер списка LT,C(y) для произвольного кода C с расстоянием d(C) d(C) |LT,C(y)| (13) d(C) - 2n-1T (n - T ) (при условии, что знаменатель дроби положителен) и очевидного замечания, что в список радиуса T < n/2 не могут одновременно входить кодовые слова c и c 1, следует, что для кода RM(1, m) размер списка L;m(y) := LT ;RM(1,m)(y) радиуса T = (1 - )n/2 не более min{-2, n}.
Для произвольной линейной булевой функции c(x1,..., xm) = c1x1 +... + cmxm + c0 ее j-м префиксом называется функция c(j)(x1,..., xj) = c1x1 +... + cjxj, а функция c(x1,..., xm), в свою очередь, называется продолжением (префикса) c(j)(x1,..., xj). Обозначим L(j) (y) список j-х ;m префиксов всех искомых функций c(x1,..., xm) L;m(y). Алгоритм КС работает рекурсивно, находя на j-м шаге свой список L(j) (y), содер;m жащий список L(j) (y), но, возможно, содержащий при этом и другие ;m префиксы. Один из ключевых моментов алгоритма это нижняя оценка (15) расстояния Хэмминга от принятого слова y до любой линейной функции c(x1,..., xm) = c(j)(x1,..., xj) + cj+1xj+1 +... + cmxm + c0, являющейся продолжением данного префикса c(j)(x1,..., xj), см. лемму 1. Затем с помощью этой оценки формируется критерий сумм (16)(см. ниже), на основании которого происходит УотсевФ заведомо непригодных префиксов, и, в результате, объем порождаемых списков достаточно мал (не более -2) для всех j.
m Будем рассматривать в m-мерном булевом кубе H2 j-мерные грани вида Sa = {(x1,..., xj, aj+1,..., am)}, где переменные x1,..., xj произвольные (и пробегают все 2j двоичных j-мерных векторов), переменные xj+1 = aj+1,..., xm = am фиксированы, а вектор a = (aj+1,..., am) будем называть УномеромФ грани. Для произвольных функций-векторов f и g обозначим через d(f, g|Sa) расстояние Хэмминга между их ограничениями на j-мерную грань Sa. Определим j-ое УрасстояниеФ между векторами f и g как (j)(f, g) = (f, g|Sa), (14) aHm-j где по определению (f, g|Sa) = min{d(f, g|Sa), d(f, g 1|Sa)}.
Пусть c(x1,..., xm) -произвольная линейная булева функция и c(j) = c1x1 +... + cjxj - ее j-й префикс. Ограничение c(x1,..., xm) на j-мерную грань Sa равно c(j)(x1,..., xj) + ca, где ca = cj+1a1 +... + cmam-j + c0 {0, 1}. Отсюда следует Лемма 1. Для любой булевой функции y, любой линейной функции c = c1x1 +... + cmxm + c0 и ее префикса c(j) = c1x1 +... + cjxj справедливо d(y, c) (j)(y, c(j)) (15) Будем говорить, что для данной (принятой) булевой функции y префикс c(j) = c1x1 +... + cjxj удовлетворяет критерию сумм, если (j)(y, c(j)) (1 - )n/2. (16) Предлагаемый алгоритм КС на (j +1)-м шаге рассматривает все возможные продолжения префиксов, найденных на j-м шаге, т.е. рассматривает префиксы вида c(j)(x1,..., xj) + cj+1xj+1, где c(j) L(j) (y), cj+1 {0, 1}, ;m и из них алгоритм оставляет только префиксы, удовлетворяющие критерию сумм (16), что и составляет список L(j+1)(y).
;m Мы будем оценивать сложность алгоритма КС количеством элементарных бинарных операций (а не операций над целыми или действительными числами). Воспользуемся рекуррентной структурой алгоритма и для сокращения сложности будем УпересчитыватьФ расстояния (c(j+1), y|Sa) на основе результатов предыдущего шага алгоритма. Соответствующий анализ сложности приводит к одному из основных результатов второй главы.
Теорема 4. Для произвольного > 0 алгоритм КС осуществляет списочное декодирование кодов Рида-Маллера первого порядка со сложностью O(nlog2(min{-2, n})) при радиусе декодирования T = (1 - )n/2.
Замечание. Можно заменить первые J = log2 -2 шагов предлагаемого алгоритма на алгоритм Грина, примененный ко всем 2m-J Jмерным граням Sa. На выходе алгоритма Грина получаются значения d(y, c(J)|Sa) и d(y, c(J) 1|Sa) для всех c(J) RM(1, J), из них вычисляются (y, c(J)|Sa), а затем подаются на вход (J + 1)-го шага алгоритма КС. Сложность применения алгоритма Грина равна O(J22J) 2m-J, т.е.
такого же порядка как и у первых J шагов алгоритма КС. В действительности алгоритм КС на первых шагах делает тоже, что и алгоритм Грина, плюс дополнительно УотсеиваетФ лишние префиксы за счет критерия сумм, что на этих шагах является, как мы только что отметили, несущественным. Однако на следующих шагах это УотсеиваниеФ играет ключевую роль в получении асимптотически меньшей, чем у алгоритма Грина, итоговой сложности алгоритма.
В з2.2 алгоритм КС обобщается на случай мягкого списочного декодирования кодов РМ-1. Рассматривается канал передачи информации без памяти с двоичным входным алфавитом X = {-1, +1} и выходным алфавитом Y, задаваемый переходными вероятностями (или соответствующими плотностями) p(y = |x = a). Пусть для передачи сообщений используется двоичный код C длины n, в словах которого 0 и 1 заменены на 1 по правилу x x = (-1)x. При такой замене код C становится сферическим кодом CR Rn, лежащим на евклидовой сфере Sn-1( n) радиуса n, а расстояние Хэмминга d(x, y), евклидово расстояние D(x, y) и скалярное произведение (x, y) связаны простым соотношением (x, y) = n - D2(x, y) = n - 2d(x, y) (17) n Пусть y = (y1,..., yn) Y принятое из канала слово. Обозначим через i логарифм отношения правдоподобия для i-го символа yi P r(+1|yi) i = ln, (18) P r(-1|yi) где P r(+1|yi) и P r(-1|yi) - это апостериорные условные вероятности. По определению, мягкое списочное декодирование должно выдавать список наиболее вероятных, по отношению к принятому слову y, кодовых слов, т.е. список LP ;C(y) = {c C : P r(c|y) P }. (19) Рассмотрим вектор = (..., n) и, домножив на скаляр n/||, бу, дем считать, что Sn-1( n). Известно, что мягкое списочное декоди рование равносильно поиску ближайших к слов кода CR в евклидовом пространстве Rn, а список LP ;C(y) совпадает со списком - ) L;C() = {c C : ( c, n} (20) для соответствующего .
Рассмотрим теперь двоичный код RM(1, m) как сферический, заменив 0 и 1 на 1, т.е. сопоставим произвольной линейной булевой функции c(x), см.(12), вектор (21) c = (..., (-1)c(x),...) Rn, m где n = 2m и x = (x1,..., xm) пробегает по всем 2m точкам H2. Получаемый сферический код RMR(1, m) из 2n точек с минимальным угловым расстоянием /2 - это правильный n-мерный октаэдр, так же часто называемый в литературе по теории кодирования биортогональным кодом.
Таким образом, задача мягкого списочного декодирования кодов РМ-может быть сформулирована как задача нахождения для любого Упри нятогоФ вектора Sn-1( n) списка слов кода RMR(1, m) на угловом расстоянии от не более arccos - ) LR () = {c RM(1, m) : ( c, n} (22) ;m Половина слов сферического кода RMR(1, m), соответствующих линейным функциям с c0 = 0, образуют ортогональный базис Rn, известный как матрица Адамара размерности n = 2m. Если бы были известны n координат 1,..., n вектора в этом ортогональном базисе, то дальнейшее вычисление очевидно и требует n операций сравнения вещественных чисел 1,..., n с УпорогомФ . Быстрое вычисление всех координат i известно как быстрое преобразование Адамара (или быстрое ДПФ при n = 2m) и требует O(n ln n) операций над вещественными числами. В з2.рассматривается УмягкийФ алгоритм КС, который естественно обобщает алгоритм КС на случай евклидова пространства и позволяет находить -УзначимыеФ (т.е. модуль которых не меньше ) коэффициенты ДПФ за O(n ln(min{-2, n})) операций над вещественными числами. Перейдем к описанию УмягкогоФ алгоритма КС.
Для произвольного вектора u Rn, где по-прежнему n = 2m и коm ординаты УзанумерованыФ точками H2, обозначим через ua его ограничение на j-мерную грань Sa. Определим j-ое Ускалярное произведениеФ между векторами u, v Rn как (ср. с (14)) (j)(u, v) = |(ua, va)|. (23) aHm-j Сопоставим, следуя (21), произвольной линейной булевой функции c(x) = c1x1 +...cmxm + c0 и ее j-му префиксу c(j)(x) векторы c и c(j). Так как для любой j-мерной грани Sa выполняется равенство (24) ca = a c(j), a j+где a = (-1)c aj+1+...+cmam+c0, то верно следующее обобщение леммы 1.
Лемма 2. Для любого вектора Sn-1( n), любой линейной функции c = c1x1 +... +cmxm +c0 и ее префикса c(j) = c1x1 +... +cjxj справедливо - (, c) (j)(, c(j)) (25) Будем говорить, аналогично (16), что для данного вектора префикс c(j) = c1x1 +... + cjxj удовлетворяет УмягкомуФ критерию сумм, если (j)(, c(j)) n. (26) Далее УмягкийФ алгоритм КС работает также как и описанный выше алгоритм КС, рассматривая на j + 1-м шаге все возможные продолжения префиксов, найденных на j-м шаге, и оставляя только те, что удовлетворяют УмягкомуФ критерию сумм (26). Для мягкого алгоритма справедлив, почти дословно, аналог теоремы 4 и сложность алгоритма, как уже упоминалось выше, имеет порядок n log -1 операций.
В з2.3 исследуются алгоритмы списочного декодирования кодов РидаМаллера фиксированного порядка. Двоичный код Рида-Маллера s-го поn рядка RM(s, m) состоит из векторов f = (..., f(x),...) H2, где f(x) = f(x1,..., xm) - многочлен степени не больше s, n = 2m и x = (x1,..., xm) m пробегает по всем n точкам m-мерного булева куба H2. Размерность s (число информационных символов) кода RM(s, m) равна ks,m = (m), i i=а расстояние кода ds,m = ns, где s = 2-s- относительное расстояние кода. Обозначим через l(s, m; T ) = max |LT ;RM(s,m)(y)| (27) yHn максимально возможный объем списка радиуса T для кода Рида-Маллера RM(s, m). Определим критический радиус Tcrit как такой, что при любой константе > 0 имеем l(s, m; Tcrit(1 - )) c, т.е. размер списка ограничен константой (зависящей от ), а с другой стороны, l(s, m; Tcrit(1 + )) с ростом длины кода. До недавнего времени для кодов Рида Маллера было известно лишь то, что Tcrit Js = 2-1(1 - 1 - 2-s+1), где Js - значение границы Джонсона для кода RM(s, m). В работе было доказано, что для кода Рида-Маллера s-го порядка Tcrit = s = 2-s и более того, l(s, m, ) 2(2s+5-2)4s, (28) где l(s, m, ) := l(s, m; (s-)n). Другим важным инструментом, используемым при построении алгоритмов списочного декодирования кодов Gopalan P., Klivans A.R., Zuckerman D. List-Decoding Reed-Muller Codes over Small Fields //Proc. 40th annual ACM symposium on Theory of computing. 2008. P. 265-2РМ, является конструкция Плоткина (уже использованная нами в главе 1). Так как позиции кодовых слов УнумеруютсяФ точками x из m-мерного m булева куба H2, то разобьем произвольное кодовое слово f на две половины, например, в первую f войдут координаты, стоящие на позициях x : xm = 0, а во вторую f - стоящие на позициях x : xm = 1, и будем записывать f = (f, f ). Тогда f, f RM(s, m-1) и f +f RM(s-1, m-1).
Это и есть (u, u + v)-конструкция Плоткина применительно к кодам РМ, а именно, f = (u, u + v), где u RM(s, m - 1) и v RM(s - 1, m - 1).
Аналогично будем разбивать и принятый вектор y на y и y. Опишем алгоритм (s, m, ), декодирующий принятое слово y в список (s, m, )(y) = {f RM(s, m) : d(f, y) n(s - )}.
Пусть алгоритмы (s, m - 1, ) и (s - 1, m - 1, ) уже построены. Алгоритм (s, m, ) вычисляет три вспомогательных списка Lv = (s - 1, m - 1, 2)(y + y ), L = (s, m - 1, )(y ), L = (s, m - 1, )(y ), а затем формирует два списка A = {(u, u + v) : u L, v Lv} B = {(u + v, u ) : u L, v Lv} Далее алгоритм завершает работу, оставляя только те слова из списков A и B, что находятся от принятого слова на расстоянии не более n(s - )}.
Иначе говоря, (s, m, )(y) = {f A B : d(f, y) n(s - )}.
Сложность (s, m, ) этого алгоритма удовлетворяет неравенству (s, m, ) (s - 1, m - 1, 2) + 2(s, m - 1, ) (29) +2nl(s, m - 1, )l(s - 1, m - 1, 2).
Используя алгоритм КС списочного декодирования кодов РМ первого порядка со сложностью O(n ln2 ), оценку Джонсона (13) размера списка для кодов РМ первого порядка и оценку (28) для кодов РМ более высокого порядка, получаем, что сложность построенного алгоритма списочного декодирования для кода Рида-Маллера RM(s, m) при s > 2 имеет вид (s, m, ) = O(-18n lns-1 n) + O(8-16sn ln n), и (2, m, ) = O(-18n ln n).
В з2.4 исследуются различные обобщения кодов Рида-Маллера на недвоичный случай. Особое внимание уделено предложенной автором конструкции недвоичных кодов РМ как обобщенных кодов-произведений, которая впоследствии неоднократно переоткрывалась.
Содержание второй главы диссертации изложено в работах [1,5-7,19,2227].
В третьей главе исследуются некоторые задачи защиты информации, в решении которых удалось добиться существенного прогресса благодаря использованию методов и результатов теории кодирования. В з3.изучается задача безусловной аутентификации сообщений, которая, посуществу, является задачей теории кодирования. А именно, эта задача возникает, когда в классической, идущей от Шеннона, математической модели передачи информации место природы, порождающей ошибки, занимает оппонент (противник). Очевидно, что исправление ошибок в такой ситуации невозможно и речь идет только об их обнаружении. Более того, в силу стандартного для задач защиты информации предположения, что оппоненту известно все, кроме УслучайностиФ, наличие одного кода также бесполезно, так как оппонент, зная код и передаваемое кодовое слово, может заменить его на другое кодовое слово. Поэтому в этой задаче используется не один код, а семейство кодов Ck, УнумеруемыхФ элементами k K (элементы k принято называть ключами), и выбор конкретного кода происходит случайно с некоторым распределением вероятностей p(k), известным и оппоненту тоже. Основное предположение состоит в том, что конкретный выбор ключа k известен передатчику и приемнику, но не оппоненту. Семейство кодов Ck вместе с распределением вероятностей p(k), которое, как правило, предполагается равномерным, принято называть аутентификационной схемой, или кратко, A-схемой. В работе рассматриваются систематические A-схемы, когда кодовое слово v Ck имеет вид v = (m, z), где m M - это передаваемое сообщение, а УметкаФ z = (m, k) Hq является функцией сообщения и ключа. Для полученного из канала слова y = (m, z ) приемник проверяет верно ли равенство z = (m, k), где k - это используемый в данный момент ключ. Если УНЕТФ, то происходит обнаружение ошибки (которую принято называть целенаправленной), если УДАФ, то считается, что передавалось сообщение m, и если при этом m = m, то говорят, что оппонент успешно подменил сообщение. Основной характеристикой Aсхемы является вероятность успешной подмены PS, определяемая как максимальная вероятность успеха оппонента в подмене сообщения, передаваемого по каналу, и равная |{k K : (m, k) = z, (m, k) = z }| PS = max max (30) (m,z)MHq m =mM, z Hq |{k K : (m, k) = z}| Другой важной характеристикой A-схемы является вероятность имперсонификации PI, определяемая как максимальная вероятность успеха оппонента в подстановке сообщения в отсутствии передачи сообщения легальным отправителем и равная |{k K : (m, k) = z}| PI = max (31) (m,z)MHq |K| Очевидно, что PI 1/q, и далее мы, без заметного ограничения общности, ограничимся изучением A-схем с PI = 1/q.
В ряде работах высказывалось предположение о существовании связи между задачей аутентификации и теорией кодирования, см., однако попытки найти эту связь не были успешными, так как не шли далее поверхностного факта, что каждое отображение (., k) задает некоторый код. Занумеруем произвольным образом множество ключей K = {k1,..., kn} и рассмотрим q-ичный код V = {vm = ((m, k1),..., (m, kn)) : m M} (32) мощности M = |M| и длины n = |K|, который мы будем называть An кодом (соответствующим A-схеме). Определим A-УрасстояниеФ на Hq как DA(x, y) = n - q max |{i : xi = z, yi = z }| (33) (z,z )Hq и, соответственно, определим A-УрасстояниеФ кода V как DA(V ) = min DA(v, v ).
v =v V Из определений PS, DA(V ) и предположения PI = 1/q следует, что DA(V ) PS = 1 - (34) n Таким образом, исследование A-схем с вероятностью подмены PS равносильно изучению A-кодов, т.е. q-ичных кодов с A-УрасстояниемФ DA(V ) = n(1-PS). Первым следствием из этой связи является возможность, в силу Simmons G.J. Authentication theory/coding theory //Proc. CRYPTO 84, LNCS V.196. 1985. P. 411-4очевидного неравенства DA(V ) d(V ), использовать развитые в теории кодирования верхние оценки на мощность кода с заданным расстоянием.
В частности, из границы Плоткина следует, что |V | (n - 1)/(q - 1) при PS = 1/q и, тем самым, скорость A-кодов стремится к нулю с ростом длины при PS 1/q.
С другой стороны, можно показать, что скорость наилучших A-кодов отделена от нуля при любой PS = const < 1/q и, следовательно, можно передавать экспоненциально много (от числа ключей) сообщений с заданной вероятностью успешной подмены PS. А именно, как показано ниже, из q-ичного кода с расстоянием (Хэмминга) d = n можно построить код той же мощности и с тем же относительным A-УрасстояниемФ, но в q раз более длинный. Более точно, пусть U - линейный (n, k)-код с расстоянием d = n, содержащий вектор 1 из всех единиц, и пусть U некоторый его k - 1-мерный подкод, не содержащий 1, т.е. U = U 1.
Нетрудно убедиться, что для кода V = {(u, u + 11,..., u + q-11) : u U, {0, 1,..., q-1} = Fq} (35) справедливо, что PI = 1/q, его A-УрасстояниеФ DA(V ) N, где N = qn - длина кода V, а мощности кодов V и U равны. Отсюда, в силу известных результатов теории кодирования и соотношения 34, уже следует, что для любой PS = const < 1/q скорость наилучших A-кодов отделена от нуля. Отметим, что схожие результаты о скорости лучших A-кодов были независимо получены в.
Кроме того, предложенная конструкция позволяет строить конкретные оптимальные A-коды. Так, если в качестве кода U взять q-ичный код Рида-Соломона, то итоговый A-код будет оптимальным в том смысле, что на нем достигается минимум вероятности успешной подмены PS при данных n, q и M.
В з3.2 и з3.3 рассматривается следующая математическая задача, возникающая при защите авторских прав при коммерческом распространении мультимедийных продуктов (таких как фильмы, музыка, игры, программное обеспечение и т.п.). Для произвольного множества U = {u1,..., ut} Hqn будем называть позицию i {1,..., n} U-неразличимой, если векторы u U имеют в этой позиции одно и тоже значение, и будем обозначать через (U) множество всех таких позиций. Определим выпуклую оболочку множества U как U = {x = (x1,..., xn) Hqn : xi Ui, i = 1,..., n}, (36) Бассалыго Л.А., Бурнашев М.В. Оценка максимального числа сообщений при заданной вероятности успешной подмены //Пробл. передачи информации. 1994. Т.
30. № 2. С. 42-48.
где Ui = {ui : u = (u1,..., un) U}, и расширенную выпуклую оболочку как U = {x = (x1,..., xn) Hqn : xi = Ui для i (U)}, (37) Код C называется t-идентифицирующим, если для любого y C(t), U = , (38) UC y U, |U|t где C(t) = X XC, |X|t - это объединение всех выпуклых оболочек t-подмножеств кода C.
Эти коды возникли в задаче о нахождении коалиций пользователей, нелегально распространяющих/копирующих данные (например, видео), передаваемые широковещательно. Таких недобросовестных пользователей стали называть (видео)УпиратамиФ, а саму задачу - задачей Упоиска пиратовФ. В схеме, рассмотренной в (и названной открытой одноуровневой), имеется n множеств ключей шифрования K1,..., Kn (|Ki| = q), каждый пользователь c получает вектор c из n ключей c = (c1,..., cn) :
ci Ki, и коалиция пользователей U может создать любой набор ключей y = (y1,..., yn) из имеющихся у них ключей, т.е. из yi Ui для всех i = 1,..., n, или, согласно данному выше определению, породить y U.
Тем самым, свойство t-идентифицируемости есть не что иное как способность кода по любому такому y найти хотя бы одного из членов коалиции, создавшей y, т.е. найти хотя бы одного УпиратаФ.
Очевидно, что если алфавит слишком мал, а именно, если q t, то мощность t-идентифицирующего кода тоже мала - не превосходит q. С другой стороны, в было показано, что существуют хорошие 2идентифицирующие троичные коды. Положительное решение вопроса о существовании хороших t-идентифицирующих кодов при всех q t + дано в з3.2. Это решение основывается на использовании аналога теоремы Хэлли для гиперграфов и новом понятии частичного (t, u)-хэш кода. А именно, код C Hqn называется частичным (t, u)-хэш кодом, где u > t, если для любых двух подмножеств T и U таких, что T U C, |T | = t, |U| = u, существует координата i {1,..., n} такая, что xi = yi для любых x T и y U, y = x. При u = t + 1 получается обычное определение t + 1-хэш кода, т.е. когда для любых t + 1 кодовых Hollmann H.D.L., van Lint J.H., Linnartz J.-P., Tolhuizen L.M.G.M. On codes with identifiable parent property // J. Combinatorial Theory (A). V.82. 1998. P. 121-133.
Chor B., Fiat A., and M. Naor M. Tracing traitors //Proc. CryptoТ94. LNCS V. 839.
1994. P. 257-270.
слов существует различающая их координата. При доказательстве существования хороших t-идентифицирующих кодов ключевую роль играет следующий результат.
емма 3. Любой частичный (t, u)-хэш код с u = (t/2 + 1)2 является t-идентифицирующим кодом.
В работе также были введены t-идентифицирующие по минимуму расстояния (сокращенно, t-ИМР) коды со свойством, что ближайший кодовый вектор к УпринятомуФ вектору y обязательно соответствует одному из членов коалиции, и, следовательно, поиск УпиратовФ можно осуществлять с помощью декодирования по минимуму расстояния. Обозначим через qt минимальное q такое, что существуют хорошие q-ичные t-ИМР коды. Там же было замечено, что любой код C с расстоянием Хэмминга d(C) > (1 - t-2)n является t-ИМР кодом и, следовательно, qt t2 + 1. Значение qt было неизвестно ни для какого t. В з3.2 показано, что q2 = 3 и, более того, доказано, что существуют хорошие линейные троичные 2-ИМР коды.
Если в определении (38) t-идентифицирующих кодов выпуклую оболочку U заменить на расширенную выпуклую оболочку U, то получится определение кода Уцифровых отпечатков пальцевФ, устойчивого к t-коалициям. Эти коды возникли как усиление техники Уцифровых водяных знаковФ (УметокФ), довольно эффективной в случае подделки данных одним пользователем, однако весьма уязвимой в ситуации, когда подделку осуществляет коалиция недобросовестных пользователей.
В этом случае коалиция может найти расположение УметкиФ (путем побитового сравнения файлов) и заменить ее на другую, не позволяющую найти даже одного участника коалиции, если только УметкиФ не были выбраны специальным образом. В работе было сделано предположение, ставшее популярным и определившим постановку задачи о Уцифровых отпечатках пальцевФ, что члены коалиции не могут менять те позиции, где все они имеют одинаковые значения, но могут ставить произвольный q-ичный символ там, где они различаются. Это отличие от определения t-идентифицирующих кодов (там членам коалиции разрешается подставлять только те символы алфавита, которые они имеют в данной позиции) является принципиальным, так как оказывается, что с помощью одного кода нельзя решить задачу Уцифровых отпечатков пальцевФ, устойчивых к t-коалициям, и надо рассматривать семейства кодов аналогично тому, как это делалось в з3.1.
Boneh D., Shaw J. Collusion-secure fingerprinting for digital data // IEEE Trans.
Inform. Theory. 1998. V.44. № 3. P. 480-4Семейство кодов Ck Hqn одинаковой мощности M, УзанумерованныхФ элементами множества K и выбираемых с распределением вероятностей (k), и алгоритм УдекодированияФ (идентификации участника коалиции) Dk(y) : Hqn Ck характеризуется вероятностью правильного декодирования Pcor, определяемой как минимальная по всем стратегиям коалиций размера t вероятность правильного декодирования, т.е. вероятность события Dk(y) U. Дополнительная величина Perr = 1 - Pcor называется вероятностью ошибочной идентификации, или сокращенно, вероятностью ошибки. В работе было доказано существование кодов длины n = O(t4 log log( /M)) с вероятностью ошибки Perr .
Как уже отмечалось выше (в разделе Актуальность темы), недостатками этих кодов является экспоненциально сложный алгоритм их декодирования и то, что при любой асимптотически ненулевой скорости передачи вероятность ошибки имеет порядок 2-O( n) вместо желаемого 2-O(n). В з3.3 построены ансамбли кодов, свободные от обоих этих недостатков. В основе построения лежит каскадная конструкция, использующая в качестве внутренних двоичные (t, t)-разделимые коды (т.е. для любых двух непересекающихся t-множеств кодовых векторов существует разделяющая их координата, см. ), а в качестве внешних - q-ичные коды с УбольшимФ расстоянием Хэмминга d > (1 - t-3)n и эффективным алгоритмом декодирования, например, алгебро-геометрические коды с алгоритмом Судана-Гурусвами. Получаемые в результате коды имееют асимптотически ненулевую скорость и обладают алгоритмом декодирования (идентификации) с полиномиальной от n сложностью, обеспечивающим экспоненциально малую вероятность ошибки. В частности, для коалиций из двух участников справедлива Теорема 5. Для произвольного R 0.0269 существует двоичный код длины n со скоростью R и алгоритм его декодирования с полиномиальной (от n) сложностью, идентифицирующий одного из двух участников коалиции с вероятностью ошибки Perr < 2-5n/252.
В последнем параграфе рассматривается задача стеганографии, состоящая в УмаскировкеФ сообщений, содержащих конфиденциальную информацию, под сообщения, не содержащие такой информации. Как принято в неформальных описаниях задач защиты информации, передача информации происходит между Алисой и Бобом, а третий участник, их оппонент Ева, старается этому в той или иной степени помешать. В данной задаче обмен сообщениями происходит через Еву, и если она заподозрит, что сообщения содержат секретную (от нее) информацию, то прекратит обмен сообщениями. Поэтому сообщения, несущие и не несущие Сагалович Ю.Л. Разделяющие системы // Пробл. передачи информации. 1994.
Т. 30. № 2. С. 14-35.
секретную информацию, должны быть практически неотличимы. В комбинаторной модели, рассматриваемой нами, это означает, что при передаче секретной информации Алиса и Боб могут УнемногоФ видоизменять исходное сообщение. Формально это означает, что сообщения рассматриваются как слова в некотором конечном алфавите, а понятие УнемногоФ измеряется расстоянием в метрике Хэмминга между исходным словом и видоизменным, содержащим секретную информацию. В такой постановке задачи у Евы появляется Устепень свободыФ- перенося сообщения, Ева также может вносить в них малозаметные изменения. Такая комбинаторная модель называется активной, в противоположность к пассивной, когда Ева просто передает сообщения, без их изменения. Мы показываем, что активная модель эквивалентна задаче о шаровых кодах, исправляющих ошибки, и предлагаем явную конструкцию таких кодов с асимптотически ненулевой скоростью, т.е. эффективный метод передачи информации для активной комбинаторной модели.
В работе была исследована модель задачи о Уцифровых отпечатках пальцевФ, близкая по духу к рассмотренной активной стеганографической модели. А именно, было предположено, что нелегальная копия должна быть достаточно близко в метрике Хэмминга к по крайней мере одной из копий участников коалиции U. Мы показываем, что в такой постановке задачи шаровые коды позволяют безошибочно указать на одного из членов коалиции. При этом скорость кодов отделена от нуля при любом размере коалиции, что показывает ошибочность основных результатов работы, утверждавшей, что скорость кода стремится к нулю с ростом размера коалиции даже при более слабом условии, что вероятность ошибки не обязательно ноль, но стремится к нулю.
Содержание третьей главы изложено в работах [11-17,20,21,28].
В заключении диссертации сформулированы основные результаты диссертационной работы.
Бассалыго Л.А., Пинскер М.С. Шаровые коды, исправляющие ошибки // Пробл.
передачи информации. 1999. Т. 35. № 1. С. 30-37.
Somekh-Baruch A., N. Merhav N. On The Capacity Game of Private Fingerprinting Systems Under Collusion Attacks // IEEE Trans. Inform. Theory. 2005. V. 51. № 6. P.
884Ц899.
Основные результаты В диссертации исследованы свойства блоковых кодов, исправляющих ошибки, а также возможности их применения к задачам защиты информации.
Предложен метод однородных упаковок и покрытий, позволивший построить асимптотически совершенные коды-упаковки и покрытия единичными шарами и, тем самым, решить одну из самых старых проблем теории кодирования.
Разработаны новые алгоритмы списочного декодирования двоичных кодов Рида-Маллера фиксированного порядка с Упочти линейнойФ(n log n) сложностью при числе исправляемых ошибок вплоть до расстояния кода.
Построен алгоритм мягкого списочного декодирования двоичных кодов Рида-Маллера первого порядка, который эквивалентен вычислению -УзначимыхФ коэффициентов преобразования Фурье-Адамара с линейной от n сложностью.
Вероятностно-комбинаторными и алгебро-геометрическими методами построены ансамбли кодов с асимптотически ненулевой скоростью для таких задач защиты информации как аутентификация сообщений, Упоиск пиратовФ, Уцифровые отпечатки пальцевФ и стеганография.
Основные результаты диссертации изложены в следующих опубликованных работах.
Список литературы 1. Кабатянский Г.А. Два обобщения произведения кодов // Докл.
Академии Наук СССР. 1977. Т. 232. № 6. С. 1277-1280.
2. Кабатянский Г.А. О существовании хороших почти линейных кодов над непростыми полями// Пробл. передачи информации. 1977.
Т. 13. № 3. С. 18-21.
3. Кабатянский Г.А., Панченко В.И. Упаковки и покрытия пространства Хэмминга единичными шарами // Докл. Академии Наук СССР.
1988. Т. 303. № 3. С. 550-552.
4. Кабатянский Г.А., Панченко В.И. Упаковки и покрытия пространства Хэмминга шарами радиуса один // Пробл. передачи информации. 1988. Т. 24. № 4. С. 3-16.
5. Kabatianskii G. A. On decoding of Reed-Muller codes in semicontinuous channels // Proc. 2nd Int. Workshop Algebr. and Comb. Coding Theory.
Leningrad, USSR. 1990. P. 87-6. Kabatianskii G. A. About Metrics and Decoding Domains of ForneyТs Algorithm // Proc. Fifth Joint Soviet-Swedish Int. Workshop on Information Theory. Moscow, USSR. 1991. P. 81-85.
7. Kabatianskii G. A. On Decoding Concatenated Codes in Certain Spaces // Proc. Fifth Joint Soviet-Swedish Int. Workshop on Information Theory.
Moscow, USSR. 1991. P. 86-90.
8. Геворкян Д.Н., Кабатянский Г.А. О кодах Варшамова-Тененгольца и одной гипотезе Л.А.Бассалыго //Пробл. передачи информации.
1992. Т. 28. № 4. С. 106-108.
9. Кабатянский Г.А. Конструкция кодов, исправляющих одиночные локализованные ошибки //Пробл. передачи информации. 1994. Т.
30. № 2. С. 96-98.
10. Kabatianskii G. Codes correcting localized errors of known value // Proc. 1994 IEEE Int. Symp. Inform. Theory, Norway. 1994. P. 249.
11. Johansson T., Kabatianskii G.A., Smeets B. On relation between Acodes and codes correcting independent errors // Proc. EurocryptТ93.
LNCS V. 765. 1994. P. 1-11.
12. Kabatianskii G.A., Smeets B. and Johansson T. On the cardinality of systematic authentication codes via error-correcting codes// IEEE Trans. Inform. Theory. 1996. V. 42. № 4. P. 566-578.
13. Блейкли Г.Р., Кабатянский Г.А. Обобщенные схемы разделения секрета и матроиды //Пробл. передачи информации. 1997. Т. 33. № 3.
С. 102-110.
14. Кабатянский Г.А. О кодах, разделяющих пары// Пробл. передачи информации. 2001. Т. 37. № 4. С. 60-62.
15. A.Barg, G.Cohen, S.Encheeva, G. Kabatiansky,and G.Zemor A Hypergraph Approach to the Identifying Parent Property: The Case of Multiple Parents// SIAM J. Discrete Math. 2001. V. 14. № 3. P. 423-431.
16. Barg A., Blakley G.R. and G. Kabatiansky G. Digital fingerprinting codes: problem statements, constructions, identification of traitors// IEEE Trans. Inform. Theory. 2003. V. 49. № 6. P. 852-865.
17. Barg A., Kabatiansky G.>
18. Kabatiansky G.A., Rush J.A. Sphere Packing and Coding Theory.
Handbook on Discrete and Computational Geometry, Second edition, J.E.Goodman and J.O.Rurke editors,CRC Press. 2004. P. 1355-1376.
19. Kabatiansky G., Tavernier C. List decoding of Reed-Muller codes of the first order.// Proc. IX Int. Workshop Algebraic and Combinatorial Coding Theory, Kranevo, Bulgaria. 2004. P. 230Ц235.
20. Kabatiansky G. Good ternary 2-traceability codes exist// Proc. 20IEEE Int. Symp. Information Theory, Chicago,USA. 2004. P. 204.
21. Кабатянский Г.А. Коды для защиты от копирования: случай двух пиратов//Пробл. передачи информации. 2005. Т.41. №2. С.123-127.
22. Kabatiansky G., Krouk E. and Semenov S. Error Correcting Codes and Security for Data Networks. Wiley. 2005.
23. Kabatiansky G., Tavernier C. List decoding of second order Reedth Muller Codes// Proc. 8 Int. Symp. Comm. Theory and Applications, Ambleside, UK. 2005. P. 36-38.
24. Dumer I., Kabatiansky G., Tavernier C. List decoding of Reed-Muller codes up to the Johnson bound with almost linear complexity// Proc.
2006 IEEE Int. Symp. Information Theory, USA. 2006. P. 138-142.
25. Думер.И., Кабатянский Г.А., Тавернье С. Списочное декодирование двоичных кодов Рида-Маллера первого порядка// Пробл. передачи информации. 2007. Т. 43. № 3. С. 66-74.
26. Dumer I., Kabatiansky G., Tavernier C. List Decoding of Biorthogonal Codes and the Hadamard Transform with Linear Complexity//IEEE Trans. Inform. Theory. 2008. V. 54. № 10. P. 4488-4492.
27. Dumer I., Kabatiansky G., Tavernier C. Fast list decoding of ReedMuller codes up to their distances// Proc. XI Int. Workshop Algebraic and Combinatorial Coding Theory, Pamporovo, Bulgaria. 2008. P. 8285.
28. Галан Ф., Кабатянский Г.А. Покрытия, центрированные коды и комбинаторная стеганография // Пробл. передачи информации.
2009. Т. 45. № 3. С. 106-111.
Авторефераты по всем темам >>
Авторефераты по техническим специальностям