Блоковые коды, исправляющие ошибки, и их применения к задачам защиты информации тема диссертации и автореферата по ВАК РФ 05.13.17, доктор физико-математических наук Кабатянский, Григорий Анатольевич

• Кабатянский, Григорий Анатольевич
• доктор физико-математических наук
• 2009

Оглавление диссертации доктор физико-математических наук Кабатянский, Григорий Анатольевич

Введение

1 Коды, исправляющие одиночные ошибки

1.1 Метод однородных упаковок и покрытий

1.2 Упаковки и покрытия одиночными фазированными пакетами

1.3 Асимптотика лучших упаковок и покрытий единичными шарами.

1.4 Коды, исправляющие одиночные локализованные ошибки

2 Списочное декодирование кодов Рида-Маллера

2.1 Списочное декодирование линейной сложности двоичных кодов Рида-Маллера первого порядка

2.2 Мягкое списочное декодирование кодов Рида-Маллера первого порядка.

2.2.1 Граница Джонсона для сферических кодов.

2.2.2 Алгоритм КС (критерия сумм) декодирования кодов Ш(1, /п) в евклидовом пространстве.

2.3 Списочное декодирование почти линейной сложности для двоичных кодов Рида-Маллера фискированного порядка

2.3.1 Верхняя граница на мощность списка при частично известном весовом спектре кода.

2.3.2 Списочное декодирование кодов Рида-Маллера второго порядка.

2.3.3 Алгоритм КО (критерия отношений) списочного декодирования кодов Рида-Маллера фиксированного порядка.

2.3.4 Алгоритм "двух попыток" списочного декодирования кодов Рида-Маллера фиксированного порядка

2.4 Построение и свойства недвоичных кодов Рида-Маллера

3 Применения теории кодирования к задачам защиты информации

3.1 Коды, обнаруживающие целенаправленные ошибки, или коды для безусловной аутентификации.

3.1.1 Определения и предшествующие результаты

3.1.2 Аутентификационные схемы и коды, исправляющие ошибки.

3.1.3 Одна конструкция аутентификационных кодов

3.2 Коды для защиты авторских прав, I - коды, идентифицирующие родителей

3.2.1 Одноуровневые схемы поиска пиратов и коды, идентифицирующие родителей

3.2.2 Недвоичные коды, идентифицирующие пары по минимуму расстояния.

3.2.3 Асимптотически хорошие идентифицирующие коды

3.2.4 Асимптотически хорошие идентифицирующие коды с полиномиальной сложностью

3.3 Коды для защиты авторских прав, II - коды цифровых отпечатков пальцев, устойчивые к коалициям.

3.3.1 Постановка задачи.

3.3.2 Асимптотически хорошие и полиномиально реализуемые коды цифровых отпечатков пальцев, устойчивые к коалициям

3.3.3 Асимптотически хорошие и полиномиально реализуемые коды цифровых отпечатков пальцев, устойчивые к парам.

3.4 Центрированные коды, исправляющие ошибки, и комбинаторная стеганография

3.4.1 Коды-покрытия и пассивная комбинаторная модель

3.4.2 Шаровые коды, исправляющие ошибки, и активная комбинаторная модель.

3.4.3 Шаровые коды, исправляющие ошибки, и одна модель "цифровых отпечатков пальцев".

Введение диссертации (часть автореферата) на тему «Блоковые коды, исправляющие ошибки, и их применения к задачам защиты информации»

В этом разделе дается краткий обзор метрических и алгоритмических проблем теории кодирования, а также вопросов использования её идей, методов и результатов для решения задач защиты информации. Такой обзор, как нам представляется, позволит, несмотря на свою возможную неполноту, лучше оценить место и значимость решаемых в диссертации задач.

Теория кодирования или теория кодов, исправляющих ошибки, ведет свой отсчет от опубликованной 60 лет назад работы Хэмминга [1], в которой были построены коды, исправляющие одиночные ошибки. С математической точки зрения основная часть теории кодирования может рассматриваться как теория упаковок одного класса дискретных метрических пространств, называемых пространствами Хэмминга.

Множество Н™, состоящее из всех слов длины п над некоторым конечным алфавитом Ня из д букв, с расстоянием Хэмминга ¿¿(х, у) между словами х = (хь .,хп) и у = (т/1, .,2/п)» определяемом как число координат, в которых эти слова различны, называется д-ичным п-мерным пространством Хэмминга. В теоретически наиболее изученном и, одновременно, наиболее интересном для практики частном случае д — 2 соответствующее двоичное пространство Хэмминга есть не что иное как п-мерный булев куб {0,1}п, рассматриваемый как граф, а расстояние Хэмминга - это длина кратчайшего пути между вершинами х и у.

Нам будет удобно рассматривать алфавит как абелеву группу по сложению (например, как группу Ъч вычетов по модулю д), а если д есть степень простого числа - то как конечное поле На пространстве

Нд задается вес Хэмминга, определяемый как ш£(х) — |{г : ф 0}| = ¿¿(х, 0), и, в свою очередь, с£(х,у) = ги£(х — у). Обозначим через вя{п, £)(а) = {хе^: с*(х, а) < £} шар радиуса £ в пространстве Хэмминга Нд с центром в точке (слове) а, а его мощность обозначим ¿(9 -1)4?). г=0

Подмножество С пространства Хэмминга называется упаковкой шарами радиуса £, если шары радиуса £ с центрами в точках С непересекаются, т.е. с) £)(с') = 0 для с ф с' е С (1) и называется покрытием шарами радиуса £, если шары радиуса £ с центрами в точках С покрывают все пространство, т.е. и^(п;£)(с) = ^. (2) сеС

Вместо этих, привычных определений упаковок и покрытий мы будем использовать эквивалентное им определение, которое позволит нам в первой главе единообразно работать и с упаковками, и с покрытиями.

Подмножество С пространства Хэмминга называется упаковкой (покрытием) шарами радиуса £, если для любого а е К™ уравнение с + е = а, с е С, wt(e) < £ (3) имеет не более (не менее) одного решения (с,е).

Если точки (слова) упаковки С с использовать для передачи сообщений по каналу связи, в котором при передаче п символов происходит не более £ ошибок, то на приемной стороне возможно однозначное восстановление (декодирование ) переданного сообщения, так как шары радиуса t с центрами в разных кодовых словах не пересекаются. По этой причине упаковка шарами радиуса t также называется q-ичным кодом длины п, исправляющим t ошибок. Расстояние d(C) кода С определяется как минимальное из попарных расстояний между его словами d(C)= min ¿(с, с'), (4) и код С является упаковкой шарами радиуса t, т.е. исправляет t ошибок, если и только если d(C) > 21. Это приводит к следующему хорошо известному определению, см. [2].

Подмножество С пространства Хэмминга Н™ называется q-ичным кодом длины п, исправляющим t ошибок, если его расстояние d(C) > 2t + 1.

Всюду в диссертации (как и в теории кодирования) код - это синоним подмножества пространства Хэмминга, а линейный код это синоним линейного подпространства пространства Хэмминга (и в этом случае q автоматически есть степень простого числа). Про код С мощности М = \С\ говорят, что он способен передавать М сообщений, величина k = к(С) = logqM называется числом информационных символов кода, а величина R = R(C) = к(С)/п называется скоростью кода. Для линейного кода число информационных символов к это его размерность и линейный код длины п и размерности к принято сокращенно называть (п, /с)-кодом. Величина г = г (С) = п — к(С) называется числом проверочных символов кода или его избыточностью.

Код С С Tiq, рассматриваемый как покрытие, характеризуется радиусом покрытия Т(С), определяемым как минимальный радиус такой, что шары этого радиуса с центрами в кодовых словах покрывают все пространство, т.е.

Т(С) = max min die, a) aew» ceC 4 '

Для кода С, рассматриваемого как упаковка или покрытие шарами радиуса ¿, определим соответствующую плотность

Очевидно, что плотность покрытия не менее 1, а упаковки (кода), соответственно, не более 1. Обозначив через /.¿*(тг,£;д) максимальную плотность упаковки п-мерного пространства Хэмминга Н™ шарами радиуса £, а через /¿*(п, ¿; <?) - минимальную плотность покрытия, перепишем эти неравенства в виде п, ¿;д) < 1 < /¿*(тг,£;<?) (6)

Обозначим через Ач(п,с1) максимальную мощность д-ичного кода с расстоянием не менее <1 Тогда /х*(п, £; д) — д~Т1Зя(п, 1)Ад(п) 2£ + 1) и левая половина неравенства (6) есть не что иное как граница Хэмминга, см. [2] I 0

Коды, достигающие границу Хэмминга, называются совершенными - они плотно, " без дыр" заполняют все пространство Хэмминга и являются одновременно и упаковками, и покрытиями. Построенные Хэммингом коды, исправляющие одиночные ошибки, являются совершенными - при длине п — 2Г — 1 они имеют мощность 2П-Г, где г = 2,3,. Известны также недвоичные совершенные коды, исправляющие одиночные ошибки, но только для случая, когда д есть степень простого числа. Эти коды линейные, они имеют длину п = (дг —1)/(д —1) и число информационных символов (размерность) к — п — г.

Также на заре теории кодирования были построены два совершенных кода: двоичный код Голея длины 23, исправляющий три ошибки, и троичный код Голея, длины 11, исправляющий две ошибки, см. [2]. Одним из самых замечательных результатов теории кодирования является доказанная в начале 70-х годах XX века гипотеза, что других совершенных кодов, исправляющих £ ошибок, при £ > 1 не существует (ван Линт [3], Титвайнен [4], Зиновьев и Леонтьев [5]). Однако, кажущийся более простым случай кодов, исправляющих одиночные ошибки, остается нерешенным до сих пор - правдоподобная гипотеза о несуществовании совершенных g-ичных кодов, исправляющих одиночные ошибки, для q, которое не есть степень простого числа, не доказана ни для одного такого q.

Так как совершенных кодов очень мало, то возникает вопрос о поведении плотности наилучших упаковок и покрытий с ростом размерности пространства Хэмминга, т.е. с ростом длины кода. Так, в течении долгого времени существовала гипотеза, что lim /^(n, 1;2) = 1, (8) п—> оо т.е., что для двоичных кодов, исправляющих одиночные ошибки, граница Хэмминга асимптотически точна. В пользу этой гипотезы был опубликован ряд работ [6], [7], [8], в которых последовательно доказывалось, что \ш1цАпЛ\2) > 6, где ö равнялось 5/8; 5427/8192; 5589/8192, соответственно. Эти работы основывались на известной конструкции Плоткина и некоторых новых хороших нелинейных кодах длин 11, 66, 67 и 143 с плотностями упаковки равными 27/32, 201/256, 187/256 и (27/32)2, соответственно. Однако такой метод "последовательного улучшения" не мог дать окончательный (и ожидаемый) ответ, так как для доказательства гипотезы (8) нужна бесконечная серия кодов возрастающей длины с плотностью упаковки, стремящейся к 1. Была известна и аналогичная гипотеза для покрытий - предполагалось, что плотность лучших покрытий двоичных пространств Хэмминга единичными шарами также стремится к 1.

Основным результатом первой главы является доказательство обеих гипотез, и даже в несколько более общем виде. А именно, доказано, что для любого основания q, которое есть степень простого числа, справедливы следующие равенства lim //*(n, 1; q) — lim ц*{п, 1; q) = 1, (9) n—»oo re—»oo и более того, оценена скорость сходимости этих величин к 1.

В основе доказательства лежит новый, предложенный автором в [177], [178], метод однородных упаковок и покрытий, позволяющей строить упаковку (покрытие) шарами радиуса 1 из упаковки (покрытия) пространства Хэмминга произвольным однородным множеством с той же плотностью упаковки. Множество U С Н™ называется однородным, если Ли е U для любых и е U, \ e¥q. Так как без ограничения общности можно считать, что 0 € U, то для двоичного случая требование однородности не накладывает никаких ограничений.

Несмотря на казалось бы достаточную общность конструкции однородных упаковок и покрытий до сих пор известен лишь один пример семейства упаковок (покрытий) множествами U, который приводит к доказательству гипотезы (9), и этот пример, как это ни странно, снова упаковки (покрытия) шарами радиуса 1, но только пространств Хэмминга над другим алфавитом Hq. А именно, рассмотрим в пространстве Н™1 однородное множество UijTl, состоящее из векторов, у которых ненулевые координаты принадлежат одному из п "отрезков" {jl+L, jl+2,., jl+l—1}, где j е {0,1,.,п— 1}. Это множество известно в теории кодирования как фазированные пакеты ошибок и очевидно, что упаковки (покрытия) такими множествами есть не что иное как упаковки (покрытия) шарами радиуса 1 пространства Хэмминга Hq с Q — ql. Для того, чтобы построить нетривиальные упаковки (покрытия) Hq, т.е. отличные от укорочения (удлинения для покрытий) соответствующих кодов Хэмминга, используется еще одна конструкция, известная для кодов (упаковок) как конструкция подкода над подмножеством. В результате удается не только доказать гипотезу (9), но и оценить скорость сходимости к 1 плотности лучших упаковок(покрытий). В итоге, основным результатом первой главы является следующий результат.

При фиксированном q, являющемся степенью простого числа, справедливо неравенство м , , о 1п 1п п, . . |1 - р(п, 1; < 4е 1п д--(1 + о(1)),

Ю) где значок * при р(п, 1;д) опущен, так как соотношение (10) справедливо и для упаковок, и для покрытий.

Если мощность алфавита д не есть степень простого числа и, следовательно, алфавит не может быть представлен в качестве конечного поля, то неизвестны ни справедливость гипотезы (9), ни, как было отмечено выше, существование хотя бы одной упаковки (покрытия) шарами радиуса 1 с плотностью 1, т.е. существование совершенного кода, исправляющего одиночные ошибки.

Также отметим, что известные результаты о плотности наилучших упаковок и покрытий принципиально различаются при I > 1. Так, известно, что т.е. плотность лучших покрытий шарами фиксированного радиуса не превышает некоторой константы, зависящей от ¿ и д. В тоже время, для упаковок-кодов аналогичный результат известен только для двоичных кодов где С£ можно положить равным 1/(2^!) для кодов БЧХ и их укорочений, или несколько улучшить эту константу до 1/((2£ + 1)£!), рассматривая коды, основанные на теореме Боуза-Човлы из аддитивной теории чисел, см. [197]. Следовательно, плотность лучших двоичных упаковок шарами фиксированного радиуса отделена от нуля. Это верно также для троичных и четверичных кодов, исправляющих двойные ошибки (т.е. для для упаковок шарами радиуса 2), [9], [10]. В остальных случаях, даже когда алфавит - это поле, неизвестен порядок избыточности лучших кодов, т.е. порядок величины гч{п,в) — п — 1о^дАя(п,с1). Обозначим

Нш74+0о/^*(п, д) < а^ для t — сопбЬ,

НШп-->ооМ*(М;2) > С4 > О,

Сд(71, в) = п -к^ Ад(п, (£) к^п

Тогда только что сказанное дает, что lim^oo 02(71, 2t + 1) = t (двоичные коды БЧХ) и lim^oo сз(п, 5) = limn^00 04(72, 5) = t. Из недвоичных кодов БЧХ следует, что cq(n, 2t + 1) < 2t - 1 - [(2t - 1 )/q, J а результаты И.Думера и К.Еханина [11], [12] говорят, что при q > 2t lmn-,ooCq(n, 2t + 1) < 2t - 2 + ^i-y, и, в частности, для кодов, исправляющих две ошибки, это дает избыточность порядка ^log9n вместо "ожидаемой" 2\ogqn. Асимптотическая отделенность от нуля плотности лучших упаковок (кодов) шарами радиуса t намного превышает наши сегодняшние знания о недвоичных кодах, так как из нее следовало бы, что lim c„(n,2t+ 1) = t (11) n—»00

Отметим, что на недвоичный случай легко переносятся только коды Хэм-минга и двойственные к ним. Так, мало что известно о конструкциях недвоичных кодов, исправляющих "большое число" ошибок, см. работу [13] и литературу в ней.

Еще больше различие в асимптотическом поведении наилучших упаковок и покрытий при линейном от п радиусе t — тп шара, где т -константа, 0 < т < 1. Хорошо известно (см. [14], [16]), что тп; q) — 0(п2) (12)

Так как объем шара радиуса t = тп при г > 1 — q~l равен qn(1+°(l)\ а при т < 1 — q~l равен

Sq(7l,Tn) = дп(Щ(т)+т1оед(д-1)+о(1))} (13) где Нч(х) = — (ж log9 ж + (1 — ж) log9(1 — ж)) функция энтропии (по основанию q), то скорость лучших покрытий при т < 1 — q~l равна

Rcov(n, тп; q) = 1 - (Я9(г) + г log,(<7 - 1)) + о(1) (14) с о(1) = 0(logn/n), и стремится к нулю при т > 1 — q~l.

Для упаковок, т.е. кодов, исправляющих ошибки, известны лишь верхние и нижние границы на максимальную мощность кода, приводящие к сильно различающимся верхним и нижним границам для скорости Rq(n, 5п) = n~l log^ Aq(n, дп) оптимальных кодов. Так как оптимальная упаковка шарами радиуса t является покрытием шарами радиуса 21 (иначе можно было бы добавить еще шар радиуса £ к упаковке), то справедлива граница Варшамова-Гилберта (сокращенно, граница В-Г)

Aq(n,2t+1) >qn/Sq(n,2t) (15) или, в асимптотической форме,

Rq(n, Sn) > 1 - (Hq(S) + 5logq(q - 1)) + o(l) (16)

Эта граница в течении долгого времени являлась лучшей нижней асимптотической границей, пока в 1982 году в работе Цфасмана, Вледуца и Цинка [17] ( см. [18]) в классе алгебро-геометрических (сокращенно, АГ) кодов, введенных В.Д. Гоппой [20], для оснований q = р2т не были построены коды, лежащие на следующей границе

Rf(n, 5п)>1-5- + о(1), (17) которая асимптотически лучше границы В-Г при q > 49.

Отметим, что почти все линейные коды асимптотически лежат на границе В-Г [21], [22], [23]. Более того, для большинства "массивных" классов кодов (например, АГ-коды, каскадные коды, укороченные циклические коды, квазициклические коды и многие другие) справедливо, что почти все коды в классе лежат на границе ВГ или выше. Тем не менее, для циклических кодов, пожалуй, самого исследованного класса кодов, неизвестна справедливость даже более слабого утверждения -существование циклических кодов, для которых при фиксированной скорости передачи относительное расстояние отделено от нуля (линейный код называется циклическим, если для любого кодового слова его циклический сдвиг также является кодовым словом). Эта проблема, известная как проблема существования "хороших" циклических кодов, является одной из самых старых в теории кодирования. Среди немногих результатов вокруг этой проблемы отмечу собственный результат [175], что если рассматривать коды над непростым полем (q = рт, т > 1) и ослабить требования линейности кода до требования быть аддитивной подгруппой всего пространства, то такие "хорошие" коды существуют.

В теории кодирования верхним границам на максимальную мощность и скорость кода с заданным расстоянием уделялось особое внимание, в частности, как средству доказательства оптимальности кодов. Так, например, простая граница

Rq{n,d)< 1-—, (18) п известная как граница Синглетона (см. [2]), доказывает оптимальность кодов Рида-Соломона [24], являющихся важнейшим и простейшим частным случаем АГ-кодов.

Особо выделим границу Плоткина [25], qd qd — n(q — 1) справедливую при условии, что знаменатель дроби положителен. Из этой границы и границы В-Г следует, что асимптотически скорость наилучших кодов отделена от нуля в интервале 0 < д = d/n < 1 — q'1, и только в нем. Как ведет себя скорость оптимальных кодов, когда относительное расстояние 5 кода меняется в диапазоне (0,1 —д-1), является главной загадкой теории кодирования! Отметим, что если справедлива известная гипотеза о существовании п х «-матриц Адамара для всех п = 0 mod 4, то в двоичном случае граница Плоткина всегда достигается при d > п/2 - это замечательный результат В.И. Левенштейна [26], закрывающий проблему вычисления ^(гс, d) при этих значениях п и d.

Вернемся к рассмотрению асимптотических верхних границ. Мы уже рассматривали выше границу Хэмминга, асимптотика которой

5 6

V 2

14

ЛМ < 77—Г7—7Т (19)

Rq(n, 5п)< 1 - Hq(-) - - log9(g - 1) + о(1) (20) слишком неточна, в особенности для "больших" расстояний. Граница Плоткина, в сочетании с очевидным соотношением

Aq(n,d) <qAq{n-l,d), (21) применяемым столько раз, сколько необходимо для попадания в область справедливости границы Плоткина, дает еще одну границу, также называемую границей Плоткина, асимптотическая форма которой имеет вид

RJn,6n) < 1--+ 1), (22) q - 1

Отметим, что применение соотношения (21) при d — дает еще одну границу Плоткина, для этого специального случая, 1

Аа(п,-п) < qn. (23) Я

Граница Элайеса-Бассалыго, см. [27]

R4(n, 5п)<1- + о{ 1), (24) сильнее обеих границ: и Хэмминга, и Плоткина, в их асимптотической форме. Следующее улучшение асимптотических верхних границ потребовало принципиально новых комбинаторных понятий, разработанных Дельсартом [28] под названием ассоциативные схемы отношений, и новой техники с использованием свойств дискретных ортогональных многочленов [29]. Полученная в результате граница для двоичных кодов [29] остается неулучшаемой вот уже более 30 лет, хотя большая часть исследователей (и автор диссертации, в их числе) предполагает, что в двоичном случае асимптотически точна не эта граница, а граница В-Г.

Особо выделим то, что двоичный случай во многом отличается от общего, недвоичного. Одним из таких отличий, и как нам представляется - принципиальным, является наличие естественного изометрического вложения двоичного пространства Хэмминга в евклидово пространство той же размерности (и такого вложения нет при ц > 2). А именно, заменим на 0 и 1 на ±1 по правилу х —> х = (—1)х. При такой замене (отображении) код С длины п становится сферическим кодом Сш С Мп, лежащим на евклидовой сфере §'1-1(Л/п) радиуса л/п, а расстояние Хэм-минга (¿(х, у), евклидово расстояние £)(х, у) и скалярное произведение (х, у) связаны простым соотношением х, у) = п - 1)2(5, у) = п - 2й(х, у) (25)

Из этого соотношения и известной для сферических кодов границы Ран-кина [30] следует граница Плоткина (19), а ¡из хороших двоичных кодов можно строить хорошие решетки (конструкция Лича-Слоэна, [31], [32]), в частности, из кода Голея - знаменитую решетку Лича. Эта связь между двоичными кодами и расположениями точек в евклидовом пространстве была предметом многочисленных исследований. Отметим работу [33], в которой несуществование некоторых расположений линий в евклидовом пространстве доказывалось алгебраическими методами, независимо открытыми в комбинаторике, см. книгу [34]. Далее связь между пространствами Евклида и Хэмминга была углублена в работе В.И.Левенштейна и автора [176], в которой была построена теория "непрерывных ассоциативных схем отношений" - аналог теории Дельсарта [28] для компактных римановых многообразий ранга 1, и, в частности, для сферы в евклидовом пространстве. В этой же работе с помощью применения к ортогональным многочленам Гегенбауэра методов, близких к [29], была получена лучшая на сегодня асимптотическая верхняя границу для плотности рп упаковок шарами евклидова пространства М"

Рп < (26)

Отметим, что нижняя граница, известная как граница Минковского, говорит, что

Рп > 2-(1+о(1))?\ (27) и до работ, мотивированных теорий кодирования, предполагалось, что "правильной" является верхняя граница Блихфельда рп <

Эту границу впервые улучшил В.М.Сидельников в [35], и хотя численное улучшение было незначительным (с 0.5 до 0.51), эта работа послужила толчком к пересмотру верхних границ, сначала в теории кодирования [29], а затем в дискретной геометрии [176]. Подход непрерывных ассоциативных схем отношений также позволил вычислить так называемое контактное число дп (максимальное число одинаковых сфер, которые можно приложить к сфере того же радиуса) для размерностей п = 8 и п = 24 [36], [38], а сравнительно недавно найти, что д4 = 24 [39], а также простое доказательство [40] того, что = 12. Заметим, что вопрос о том, равно ли дз = 12 или 13, стал широко известен благодаря спору Ньютона и Грегори, однако получил первое строгое решение лишь в середине XX века. Описанные выше приложения идей и методов теории кодирования к дискретной геометрии представляются мне наиболее весомым вкладом теории кодирования в классическую математику.

Конечно, тематика теории кодирования не ограничивается лишь упаковками в метрике Хэмминга. Во-первых, есть еще ряд "координатных" метрик, близких к метрике Хэмминга и исследуемых в теории кодирования. В частности, это модулярная метрика и метрика Ли, определяемые как Д„(х,у) = \xi-yi\ и DLee(x, у) = тт{|жг—2/г|, д-\хг-уг\}, соответственно. Во-вторых, есть так называемые матричные метрики, когда векторы (в том числе, кодовые) это матрицы, а расстояние определяется либо как некоторая функция матрицы разности. Так, ранговая метрика определяется как ранг матрицы разности, и задача об оптимальных кодах в ранговой метрике получила свое решение в работе Э.М.Габидулина [37], [?]. Другая популярная метрика, называемая НРЦ-метрикой по имени ее первооткрывателей [41], [42], или же упорядоченным пространством Хэмминга [43],оказалась очень полезна при решении задачи о наилучших приближениях, см. [44], [45], [46]. Широко известна метрика вставок и выпадений (или метрика Левенштейна [47]), придуманная для задач синхронизации и популярная в последние годы в связи с растущим интересом к генетическим кодам. Тем не менее, на сегодня число работ, посвященным кодам в метрике Хэмминга, заведомо превосходит суммарное число работ, посвященным кодам в других метриках.

В заключение раздела введения, посвященного метрическим проблемам теории кодирования, еще раз отметим, что границы Варшамова-Гилберта и Минковского справедливы "в среднем," т.е. обе справедливы для "почти всех" линейных кодов или решеток, соответственно. Поэтому довольно естественной представляется гипотеза об их асимптотической точности, но ни доказать, ни опровергнуть эту гипотезу при современном уровне развития как теории кодирования, так и дискретной геометрии не представляется возможным, по крайней мере, в ближайшем будущем.

Для теории кодирования принципиально важным является не только построение кода, исправляющего ошибки, но и разработка для данного кода эффективных алгоритмов "кодирования" и "декодирования". И если сложность задачи декодирования осознавалась с самого начала, то это было не так для задач кодирования, т.е. алгоритма нумерации кодовых слов, и, особенно, для задачи задания кода. Это объясняется тем, что на начальном периоде развития теории кодирования большая часть исследуемых кодов была линейными кодами, для которых задача кодирования очевидна (умножение информационного вектора на порождающую матрицу кода), а вопрос задания кода просто не возникал, так как коды задавались явно. Ситуация прояснилась в начале 70-х годов прошлого века при решении задачи построения "хороших" кодов, т.е. кодов, у которых при фиксированной скорости относительное расстояние не стремится к нулю с ростом длины кода (существование таких кодов было к тому времени хорошо известно). Из двух решений этой задачи, полученных почти одновременно, поначалу только решение Юстесена [49] воспринималось как искомое-решение, так как требуемые коды строились "явно", тогда как в решении В.В. Зяблова [50] присутствовал алгоритм перебора на этапе выбора внутреннего кода. Однако формальное рассмотрение с позиции теории сложности показывает, что оба алгоритма имеют полиномиальную сложность, и поэтому оба имеют равные права называться "решениями". Такой анализ был впервые проделан в работах [51], [52] и с тех пор вопросы сложности прочно вошли в теорию кодирования.

Основными вариантами постановки задачи декодирования являются следующие: списочное декодирование радиуса Т, которое состоит в нахождении всех кодовых слов в шаре радиуса Т вокруг произвольного принятого слова; декодирование (исправление) t ошибок при Ь < <¿/2, кратко называемое "декодированием до с1/2" и являющееся частным случаем списочного декодирования, когда радиус Т — декодирование по минимуму расстояния Хэмминга, чаще называемое декодированием по максимуму правдоподобия(МП) и состоящее в нахождении для произвольного вектора у £ Н™ ближайшего кодового вектора. Один из первых результатов о сложности задач декодирования состоял в доказательстве АГР-полноты задачи декодирования по максимуму правдоподобия [53] в классе всех линейных кодов, а сложность задачи декодирования до й/2 до сих пор неизвестна.

Особенно важную роль вопросы сложности в теории кодирования стали играть в последние 10-15 лет после того как были сделаны почти одновременно следующие три важные открытия.

Во-первых, на основе расширителей были построены коды с линейной сложностью декодирования, исправляющие линейное число ошибок при фиксированной кодовой скорости [54].

Во-вторых, коды с низкой плотностью проверок на четность или коды Галлагера [55] получили "второе рождение", так как было доказано, что с их помощью достигаются аналогичные результаты. В-третьих, был построен алгоритм списочного декодирования кодов Рида-Соломона с полиномиальной сложностью при числе исправляемых ошибок вплоть до границы Джонсона, т.е. был придуман полиномиальный алгоритм восстановления всех многочленов от одной переменной (т.е. слов кода Р-С), которые отличаются от некоторой д-ичной функции в не более чем заданном числе значений аргумента [56], [57]. Отметим, что последний алгоритм оказал сильное воздействие не только на теорию кодирования, но и на computer science и криптографию. Его обобщение в одном из двух возможных направлений - заменить проективную (или аффинную прямую) на произвольную алгебраическую кривую, и, соответственно, заменить кодов Р-С на произвольные алгебро-геометрические коды, произошло довольно естественно и быстро, см. [57]. А вот обобщение в другом направлении, с заменой многочленов от одной переменной на многочлены от многих переменных, и, соответственно, с заменой кодов Р-С на коды Рида-Маллера (РМ), в полном объеме не осуществлено до сих пор. Важность этого обобщения объясняется, в частности, тем, что задача о декодировании двоичного кода RAJ(s,m) длины п = 2т и порядка s эквивалентна задаче о наилучшем приближении произвольной булевой функции от т переменных многочленом (Жегалкина) степени не выше 5. Решению этой задачи и посвящена вторая глава.

В $ 2.1 строится алгоритм КС (критерия сумм), который осуществляет списочное декодирование кодов Рида-Маллера первого порядка с радиусом декодирования Т = (1 — е)п/2 и сложностью 0(п1од2(тт{£~2, п})) для любого е > 0. Отметим, что известное решение задачи о наилучшем приближении произвольной булевой функции (от многих переменных) линейными функциями, называемое машиной (алгоритмом) Грина, см. [2], состоит в применении быстрого преобразования Фурье-Адамара (БПФ) для группы ^2 0 •■•0-^2, а списочное декодирование кода Рида-Маллера первого порядка (РМ-1) в этом случае равносильно вычислению не всех, а лишь наиболее значимых коэффициентов дискретного преобразования Фурье-Адамара. Сложность БПФ имеет порядок nlogn, тогда как предлагаемый алгоритм имеет линейную сложность. До работ автора с линейной сложностью умели исправлять только вдвое меньше ошибок - до d/2 — п/4 ошибок [58].

В §2.2 алгоритм КС обобщается на случай мягкого списочного декодирования кодов РМ-1. Пусть для передачи сообщений используется некоторый двоичный код С длины п, в словах которого 0 и 1 заменены на ±1 по правилу х —» х — (—1)^. При такой замене код С становится сферическим кодом Сх С лежащим на евклидовой сфере Вп~1(л/п) радиуса Л/п. Известно, что мягкое списочное декодирование равносильно поиску слов кода Ск, ближайших к некоторому "принятому" вектору "-у в евклидовом пространстве Предлагаемый "мягкий" алгоритм КС обобщает алгоритм КС на случай евклидова пространства и позволяет находить список за (9(п1п(тт{£~2, ?г})) операций над вещественными числами.

В §2.3 исследуются алгоритмы списочного декодирования для двоичных кодов Рида-Маллера произвольного фиксированного порядка. Двоичный код Рида-Маллера й-го порядка ЯМ(з, т) состоит из векторов £ = (.,/(х),.) е Щ, где /(х) = /(хх,., хт) - многочлен степени не больше й, п — 2т и х = (х1,.,хт) пробегает по всем п точкам т-мерного булева куба Н™. Размерность (число информационных символов) кода ЯМ(з,гп) равна к8}ГП = Х)/=о (Т)> а расстояние кода с/Я)7П = где 63 = относительное расстояние кода.

Один из возможных подходов к построению списочного декодирования двоичных кодов Рида-Маллера (РМ) произвольного фиксированного порядка, предложенный в работе Пеликана и Ву [59], основан на двух фактах: во-первых, коды РМ (укороченные на один символ) являются подкодами кодов БЧХ с тем же конструктивным расстоянием; во-вторых, коды БЧХ являются подкодами над подполем кодов РС с тем же расстоянием, см. [2], [59]. Эти два факта непосредственно приводят к алгоритму списочного декодирования кодов РМ с полиномиальной сложностью, однако этот алгоритм не обладает ни желаемым радиусом декодирования (он меньше границы Джонсона), ни сложностью, которую желательно иметь линейной или почти линейной, тогда как для данного алгоритма она имеет порядок г?3.

В совместной работе автора с И.И.Думером и С.Тавернье [203] был предложен алгоритм, который для кода ЯМ(з,т) имеет сложность порядка п^^п и находит список при радиусе декодирования меньше границы Джонсона. Открытым оставался вопрос о том, возможно ли списочное декодирование кодов РМ с полиномиальной сложностью при радиуса декодирования, превышающем границу Джонсона. Положительный ответ был дан.в недавней работе Гопалан и др. [60], где был построен алгоритм списочного декодирования со сложностью порядка п3 и радиусом декодирования вплоть до кодового расстояния для любого кода РМ фиксированного порядка. Используя идеи алгоритма КС, в $2.3 построен алгоритм, который для кода ЯМ(з,т) находит список при радиусе декодирования Т — (2— е)п с существенно меньшей сложностью х(5,т,г) чем в [60], а именно, т,е) — 0(б~18п\пп) и

Х(з,т,е) = 0(£-18п 1пй1 п) + 0(£8~1б5п1п7г).

Отметим, что в этой же работе [60] был переоткрыт алгоритм автора и С.Тавернье [198] для "почти полного" (т.е. с радиусом декодирования сколь угодно близким к п/2) списочного декодирования кодов РМ второго порядка.

В §2.4 исследуются различные обобщения кодов Рида-Маллера на недвоичный случай сточки зрения построения для них эффективных алгоритмов списочного декодирования. Особое внимание уделено предложенной автором [174] конструкции недвоичных кодов РМ как обобщенных кодов-произведений, которая впоследствии неоднократно переоткрывалась, см. [61], [62], [63], [64].

В третьей главе диссертации исследуются некоторые задачи защиты информации, в решении которых удалось добиться существенного прогресса благодаря использованию методов и результатов теории кодирования. Из множества математических задач защиты информации, понимаемой как обеспечение целостности информации под воздействием разнообразных атак и угроз в процессе ее передачи или хранения, выделены и рассмотрены те задачи, где для соответствующего "канала передачи информации" была неизвестна положительность его пропускной способности, т.е. возможность "передавать" экспоненциально много сообщений от некоторого параметра задачи, который естественно называть "длиной кода", обеспечивая при этом нулевую или стремящуюся к нулю вероятность ошибки с ростом "длины кода". Для каждой из рассмотренных задач нетривиальным является ее сведение к некоторой задаче теории информации и уже затем доказательство положительности пропускной способности соответствующего "канала передачи информации".

В §3.1 изучается задача обнаружения целенаправленных ошибок, также известная как задача безусловной аутентификации сообщений. Начиная с первой открытой публикации [65], этой задаче уделялось большое внимание, однако до работ автора было неизвестно возможно ли, чтобы число сообщений росло экспоненциально от числа ключей. Так, лучшие (с точки зрения числа сообщений) известные аутентификационные коды, построенные Вегманом и Картером [66], обеспечивали только е0^ сообщений, где п - число ключей. По-существу, эта задача является задачей теории кодирования. А именно, она возникает, когда в классической, идущей от К.Шеннона [67], математической модели передачи информации место природы, порождающей ошибки, занимает оппонент (противник). Очевидно, что исправление ошибок в такой ситуации невозможно и речь может идти только об их обнаружении. Более того, в силу стандартного для задач защиты информации предположения, что оппоненту известно все, кроме "случайности", наличие одного кода также бесполезно, так как оппонент, зная код и передаваемое кодовое слово, может заменить его на другое кодовое слово. Поэтому в этой задаче используется не один код, а семейство кодов С"нумеруемых" элементами к б К (элементы к принято называть ключами), и выбор конкретного кода происходит случайно с некоторым распределением вероятностей р(к), известным и оппоненту тоже. Основное предположение состоит в том, что конкретный выбор ключа к известен передатчику и приемнику, но не оппоненту. Семейство кодов С^ вместе с распределением вероятностей р(к), которое, как правило, предполагается равномерным, принято называть аутентификационной схемой, или кратко, А-схемой. В §3.1 рассматриваются систематические A-схемы, когда все коды Ck являются систематическими, т.е. кодовое слово v Е С/с имеет вид v — (т, z), где т G М - это передаваемое сообщение, а "метка" ~ = ф(т, к) е Нч является функцией сообщения и ключа. Для полученного из канала слова у = (m',z') приемник проверяет верно ли равенство z' = ф(т!,к), где к - это используемый в данный момент клк)ч. Если "НЕТ", то происходит обнаружение ошибки (которую принято называть целенаправленной), если "ДА", то считается, что передавалось сообщение га/, а если при этом т! т, то говорят, что оппонент успешно подменил сообщение. Основной характеристикой /1-схемы является вероятность успешной подмены Ps, определяемая как максимальная вероятность успеха оппонента в подмене сообщения, передаваемого по каналу, и равная

Ps = max max --—--—---y-— (28) m,z)€MxHr¡m'¿meM, z'enq \{k € К \ ф(т, к) = z}\

В ряде работах высказывалось предположение о существовании связи между задачей аутентификации и теорией кодирования, см. [68] , однако попытки найти эту связь не были успешными, так как не шли далее поверхностного факта, что Л-схема это набор кодов CV

Занумеруем произвольным образом множество ключей К = {/сь ., кп} и рассмотрим g-ичный код

V = {vm = (ф(т, kL),., ф(т, кп)) : т G М} (29) мощности М — \М\ и длины п = \К\, который мы будем называть А-кодом, соответствующим Л-схеме. Определим ^-''расстояние" на Ti" как

DA(x,y) = n-q max |{¿ : x, = c. y{ = z'}\ (30) и, соответственно, определим ^-''расстояние" кода V как

Da{V) = min Da(v,v'). v^v'&V 24

Из определений Ps, DA(V) и предположения Р/ = 1/q следует, что

31) п

Таким образом, исследование А-схем с вероятностью подмены Ps равносильно изучению А-кодов, т.е. ¿/-ичных кодов с А-"расстоянием" Da{V) — n{l-Ps). Первым следствием из этой связи является возможность, в силу очевидного неравенства Da{V) < d(V), использовать развитые в теории кодирования верхние оценки на мощность кода с заданным расстоянием. В частности, из границы Плоткина следует, что \ V\ < (n—l)/(q—l) при Ps = 1/q и, тем самым, скорость А-кодов стремится к нулю с ростом длины при Ps > 1/q.

С другой стороны, можно показать, что скорость наилучших А-кодов отделена от нуля при любой Ps = const < 1/q и, следовательно, можно передавать экспоненциально много (от числа ключей) сообщений с заданной вероятностью успешной подмены Ps. А именно, в $ 3.1 описана конструкция, позволяющая построить из g-ичного кода с расстоянием (Хэмминга) d — 5п код той же мощности и с тем же относительным А-"расстоянием", но в q раз более длинный. Отсюда, в силу известных результатов теории кодирования, уже следует, что для любой Ps = const < 1/q скорость наилучших А-кодов отделена от нуля. Отметим, что схожие результаты о скорости лучших А-кодов были независимо получены Л.А.Бассалыго и М.В.Бурнашевым в [69]. Кроме того, предложенная конструкция позволяет строить конкретные оптимальные А-коды. Так, если в качестве кода U' взять g-ичный код Рида-Соломона, то итоговый А-код будет оптимальным в том смысле, что на нем достигается минимум вероятности успешной подмены Ps при данных п, q и М.

В следующих двух параграфах исследуются математические задачи защиты авторских прав при коммерческом распространении мультимедийных продуктов (таких как фильмы, музыка, игры и т.п.) от атак групп (коалиций) пользователей. Эту проблематику принято подразделять на задачи "поиска пиратов"и "цифровых отпечатков пальцев". Возникающие при решении этих задач математические объекты называются ¿-идентифицирующими кодами и кодами цифровых отпечатков пальцев, соответственно. Математическая формулировка задач выглядит следующим образом.

Для произвольного множества II = {и1,., и*} С Ндп будем называть позицию г б {1, .,п} [/-неразличимой, если векторы и е V имеют в этой позиции одно и тоже значение, и будем обозначать через Л(£7) множество всех таких позиций. Определим выпуклую оболочку множества и как и) = {х = (хи ., О Е Пчп 1,., п}, (32) где Щ = {щ : и = (щ,.,ип) £ и}, и расширенную выпуклую оболочку как

Ц) = {х = (хи хп) е Ччп : X, = 11г для г е Л(£/)}, (33) Код С называется ¿-идентифицирующим [70] , если для любого у е

П и ф (34) исс уе(и),\и\<1 где С^ = \Jxcc " эт0 объединение всех выпуклых оболочек

-подмножеств кода С.

Эти коды возникли в задаче о нахождении коалиций пользователей, нелегально распространяющих/копирующих данные (например, видео), передаваемые широковещательно. Таких недобросовестных пользователей стали называть (видео)"пиратами", а саму задачу - задачей "поиска пиратов". В схеме, рассмотренной в [71] и названной там открытой одноуровневой, имеется п множеств ключей шифрования К1,.,Кп (|А'г-| = д), каждый пользователь с получает вектор с из п ключей с = (с1,.,сп) : Сг 6 Кг, и коалиция пользователей и может создать любой набор ключей у — {у1,.,уп) из имеющихся у них ключей, т.е. из Уг Е Щ для всех г = 1,., п, или, согласно данному выше определению, породить у е (II). Тем самым, свойство ¿-идентифицируемости есть не что иное как способность кода по любому- такому у найти хотя бы одного из членов коалиции, создавшей у, т.е. найти хотя бы одного "пирата".

Очевидно, что если алфавит слишком мал, а именно, если д < ¿, то мощность ¿-идентифицирующего кода тоже мала - не превосходит д. С другой стороны, в [70] было показано, что существуют хорошие 2-идентифицирующие троичные коды. Положительное решение вопроса о существовании хороших ¿-идентифицирующих кодов при всех д > £ -Ь 1 дано в §3.2. Это решение основывается на использовании аналога теоремы Хэлли для гиперграфов и новом понятии частичного (Ь,и)-хэш кода. А именно, код С с Ндп называется частичным (¿,гг)-хэш кодом, где и > ¿, если для любых двух подмножеств Т и и таких, что Т С и С С, |Т\ = Ь, \и\ = и, существует координата г е {1, .,п} такая, что хг Ф у{ для любых х Е Т и у е и, у ф х. При и — t -{-1 получается обычное определение ¿ 4- 1-хэш кода, т.е. когда для любых ¿ + 1 кодовых слов существует различающая их координата. При доказательстве существования хороших ¿-идентифицирующих кодов ключевую роль играет то, что любой частичный (¿, и)-хэш код с и — [(¿/2 + I)2] является ¿-идентифицирующим кодом.

В работе [71] также были введены ¿-идентифицирующие по минимуму расстояния (сокращенно, ¿-ИМР) коды со свойством, что ближайший кодовый вектор к "принятому" вектору у обязательно соответствует одному из членов коалиции, и, следовательно, поиск "пиратов" можно осуществлять с помощью декодирования по минимуму расстояния. Обозначим через qt минимальное д такое, что существуют хорошие д-ичные Ь-ИМР коды. Там же было замечено, что любой код С с расстоянием Хэмминга ¿{С) > (1 — ¿~2)п является ¿-ИМР кодом и, следовательно, дг < ¿2 + 1. Значение было неизвестно ни для какого t. В §3.2 показано, что <?2 = 3 и, более того, доказано, что существуют хорошие линейные троичные 2-ИМР коды.

Если в определении ¿-идентифицирующих кодов выпуклую оболочку (11) заменить на расширенную выпуклую оболочку (II), то получится определение кода "цифровых отпечатков пальцев", устойчивого к t-коалициям . Эти коды возникли как усиление техники "цифровых водяных знаков"("меток"), довольно эффективной в случае подделки данных одним пользователем, однако весьма уязвимой в ситуации, когда подделку осуществляет коалиция недобросовестных пользователей. В этом случае коалиция может найти расположение "метки" (путем побитового сравнения файлов) и заменить ее на другую, не позволяющую найти даже одного участника коалиции, если только "метки" не были выбраны специальным образом. В работе [72] было сделано предположение, ставшее популярным и определившим постановку задачи о "цифровых отпечатках пальцев", что члены коалиции не могут менять те позиции, где все они имеют одинаковые значения, но могут ставить произвольный g-ичный символ там, где они различаются. Это отличие от определения ¿-идентифицирующих кодов (там членам коалиции разрешается подставлять только те символы алфавита, которые они имеют в данной позиции) является принципиальным, так как оказывается, что с помощью одного кода нельзя решить задачу "цифровых отпечатков пальцев", устойчивых к ¿-коалициям, и надо рассматривать семейства кодов аналогично тому, как это делалось в §3.1.

Семейство кодов Ck С 'Hqn одинаковой мощности М, "занумерованных" элементами множества К и выбираемых с распределением вероятностей 7г(/с), и алгоритм "декодирования" (идентификации участника коалиции) At (у) : Hqn i-» Ск характеризуется вероятностью правильного декодирования Рсог, определяемой как минимальная по всем стратегиям коалиций размера t вероятность правильного декодирования, т.е. вероятность события At (у) € U. Дополнительная величина Pcrr = 1 — Рсог называется вероятностью ошибочной идентификации, или сокращенно, вероятностью ошибки. В работе [72] было доказано существование кодов длины п = 0(t4\og£log(s/M)) с вероятностью ошибки Регг < е. Недостатками этих кодов является экспоненциально сложный алгоритм их декодирования и то, что при любой асимптотически ненулевой скорости передачи вероятность ошибки имеет порядок вместо желаемого В §3.3 построены ансамбли кодов, свободные от обоих этих недостатков. В основе построения лежит каскадная конструкция, использующая в качестве внутренних двоичные (¿, £)-разделимые коды (т.е. для любых двух непересекающихся ¿-множеств кодовых векторов существует разделяющая их координата, см. [73] ), а в качестве внешних - д-ичные коды с "большим" расстоянием Хэмминга с1 > (1 — ¿~3)п и эффективным алгоритмом декодирования, например, алгебро-геометрические коды с алгоритмом Судана-Гурусвами. Получаемые в результате коды имеют асимптотически ненулевую скорость и обладают алгоритмом декодирования (идентификации) с полиномиальной от п сложностью, который обеспечивает экспоненциально малую вероятность ошибки.

В отличие от предыдущих задач защиты информации, которые являются современными (возникли в XX веке), в последнем параграфе рассматривается задача стеганографии (скрытописи), история которой насчитывает несколько тысяч лет. Правда, первая формализованная постановка задачи стеганографии также появилась менее сорока лет назад в работе Г.Симмонса [74]. В ней предлагались две модели поведения противника ("надзирателя" - в терминологии Симмонса): пассивная и активная. И если для пассивной модели ее "пропускная способность" была найдена независимо рядом исследователей в силу эквивалентности этой задачи с задачей о кодах-покрытиях, то вопрос о положительности "пропускной способности" для активной модели оставался открытым до работ автора.

Как принято в неформальных описаниях задач защиты информации, передача информации происходит между Алисой и Бобом, а третий участник, их оппонент Ева, старается этому в той или иной степени помешать. В данной задаче обмен сообщениями происходит через Еву, и если она заподозрит, что сообщения содержат секретную (от нее) информацию, то прекратит обмен сообщениями. Поэтому сообщения, несущие и не несущие секретную информацию, должны быть практически неотличимы. В комбинаторной модели, рассматриваемой нами, это означает, что при передаче секретной информации Алиса и Боб могут "немного" видоизменять исходное сообщение. Формально-это означает, что сообщения рассматриваются как слова в некотором конечном алфавите, а понятие "немного" измеряется расстоянием в метрике Хэмминга между исходным словом и видоизменным, содержащим секретную информацию. В такой постановке задачи у Евы появляется "степень свободы"- перенося сообщения, Ева также может вносить в них малозаметные изменения. Такая комбинаторная модель называется активной, в противоположность к пассивной, когда Ева просто передает сообщения, без их изменения. Мы показываем, что активная модель эквивалентна задаче о шаровых кодах, исправляющие ошибки [75] , и предлагаем явную конструкцию таких кодов с асимптотически ненулевой скоростью, т.е. эффективный метод передачи информации для активной комбинаторной модели.

В работе [76] была исследована модель задачи о "цифровых отпечатках пальцев", близкая по духу к рассмотренной активной стеганографи-ческой модели. А именно, было предположено, что нелегальная копия должна быть достаточно близко в метрике Хэмминга к по крайней мере одной из копий участников коалиции и. Мы показываем, что в такой постановке задачи шаровые коды позволяют безошибочно указать на одного из членов коалиции. При этом скорость кодов отделена от нуля при любом размере коалиции, что показывает ошибочность основных результатов работы [76], утверждавшей, что скорость кода стремится к нулю с ростом размера коалиции даже при более слабом условии, что вероятность ошибки не ноль, но стремится к нулю.

Диссертационная работа состоит из введения, трех глав, заключения и списка литературы. Список литературы состоит из двух частей: в первой части статьи, книги и т.п. пронумерованы в порядке первой ссылки на них в диссертации, вторая же часть, начиная с № 174, состоит из работ, в которых участвовал автор, и они пронумерованы в соответствии с годом публикации.

Заключение диссертации по теме «Теоретические основы информатики», Кабатянский, Григорий Анатольевич

Заключение

В диссертации исследованы свойства оптимальных или близких к ним блоковых кодов, исправляющих ошибки, а также возможности их применения к задачам защиты информации.

Предложен метод однородных упаковок и покрытий, позволивший построить асимптотически совершенные коды-упаковки и покрытия пространств Хэмминга единичными шарами и, тем самым, решить одну из самых старых проблем теории кодирования.

Построен алгоритм мягкого списочного декодирования двоичных кодов Рида-Маллера первого порядка, который эквивалентен вычислению ^-''значимых" коэффициентов преобразования Фурье-Адамара с линейной от п сложностью.

Разработаны новые алгоритмы списочного декодирования двоичных кодов Рида-Маллера фиксированного порядка со сложностью порядка nlogn при числе исправляемых ошибок вплоть до расстояния кода.

Вероятностно-комбинаторными и алгебро-геометрическими методами построены ансамбли кодов с асимптотически ненулевой скоростью для таких задач защиты информации как аутентификация сообщений, "поиск пиратов", "цифровые отпечатки пальцев" и стеганография.

То, что автор хотел бы сделать, но не сумел: о продвинуться в доказательстве гипотезы, что плотность лучших покрытий двоичных пространств Хэмминга шарами фиксированного радиуса стремится к 1 с ростом размерности пространства (аналогичная гипотеза для упаковок-кодов вряд ли верна); о построить алгоритм списочного декодирования двоичных кодов Рида-Маллера фиксированного порядка с линейной сложностью при числе исправляемых ошибок больше чем половина расстояния кода (возможно, что вплоть до расстояния кода); о придумать (и решить) новые нетривиальные комбинаторно-алгебраические задачи, которые бы имели отношение к защите информации.

Список литературы диссертационного исследования доктор физико-математических наук Кабатянский, Григорий Анатольевич, 2009 год

1. Hamming R.W. Error-Detecting and Error-Correcting Codes // Bell System Tech. J. 1950. V.29. № 1. P. 147-160

2. Мак-Вильямс Ф.Дж., Слоэн Н.Дж.А. Теория кодов, исправляющих ошибки//1979. М.:Связь.

3. Lint van J.H. On the nonexistence of certain perfect codes //Computers in Number Theory. Academic Press, NY. 1971. P.227-282.

4. Tietavainen A. On the nonexistence of perfect codes over finite fields // SIAM J. Appl. Math. 1973. V.24. P. 88-96.

5. Зиновьев В.А., Леонтьев В.К. Несуществование совершенных кодов над полями Галуа // Problems of Control and Inform. Theory. 19723. T. 2. No 2. C. 123-132.

6. 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.

7. Кацман Г.JI. О плотности упаковки шаров радиуса 1 в пространстве Хэмминга // Пробл. передачи информации. 1981. Т. 17. No 2. С. 5256.

8. 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.

9. Геворкян Д.Н., Аветисян A.M. и Тигранян В.А. О конструкции кодов, исправляющих две ошибки в метрике Хэмминга, над полями Галуа //Вычислительная техника. Куйбышев. 1975. No 3. С. 19-21.

10. Думер И.И., Зиновьев В.А. Новые максимальные коды над полем Галуа GF(4) // Пробл. передачи информации. 1978. Т. 14. No 3. С. 24-34.

11. Думер И.И. Недвоичные коды с расстоянием 4,5 и 6 мощности больше чем коды БЧХ // Пробл. передачи информации. 1988. Т. 24. No 3. С. 42-54.

12. Yekhanin S., Dumer I. Long nonbinary codes exceeding the Gilbert-Varshamov bound for any fixed distance // IEEE Trans. Inform. Theory. 2004. V.50. P. 2357-2362.

13. Степанов С.А. Новый класс нелинейных -ичных кодов //Пробл. передачи информ. 2006. Т. 42. No 3. С. 45-58.

14. Блиновский В. М. Нижняя асимптотическая граница для числа слов линейного кода в произвольной сфере с заданным радиусом из F™ //Пробл. передачи информ.1987. Т. 23. No 2. С. 50-53.

15. Blinovsky V. Asymptotic Combinatorial Coding Theory // The Springer International Series in Engineering and Computer Science. 1997. V. 415.

16. Cohen G., Honkala I., Listyn S. and Lobstein A. Covering Codes. North-Holland, Amsterdam. 1997.

17. Tsfasman M.A., Vladut S.G. and Zink T. Modular curves, Shimura curves and Goppa codes better than the Varshamov-Gilbert bound // Math.Nachrichten. 1982. V.104. P. 13-28.

18. Вледуц С.Г., Ногин Д.Ю., Цфасман М.А. Алгеброгеометрические коды. МЦНМО, 2003.

19. Гоппа В. Д. Коды, ассоциированные с дивизорами // Пробл. передачи информ. 1977. Т. 13. No 1. С. 33-39.

20. Гоппа В.Д. Алгебраико-геометрические коды // Изв. АН СССР. Сер. матем. 1982. Т. 46. No 4. С. 762-781.

21. Козлов М.В. Корректирующая способность линейных кодов // Докл. Академии Наук СССР. 1969. Т. 14. С. 413-415.

22. Кошелев В.Н. О некоторых свойствах случайнх групповых кодов // Пробл. передачи информации. 1965. Т. 1. № 4. С. 45-48.

23. Pierce J.H. Limit distribution of the minimum distance of random linear codes // IEEE Trans. Inform. Theory. 1967. V.13. P. 595-599.

24. Reed I.S., Solomon G. Polynomial codes over certain finite fields // J. SIAM. 1960. V.8. C. 300-304.

25. Plotkin M. Binary Codes with Specified Minimum Distance // IRE Trans. Inform. Theory. 1960. V. 6. N 4. P. 445-450.

26. Левенштейн В.И. Применение матриц Адамара к одной задаче теории кодирования // Проблемы кибернентики. 1960. Т. 5. С. 123-136.

27. Бассалыго Л.А. Новые верхние границы для кодов, исправляющих ошибки // Пробл. передачи информации. 1965. Т. 1. № 4. С. 41-44.

28. Дельсарт Ф. Алгебраический подход к схемам отношений теории кодирования. М.:Мир, 1976.

29. McElice R.J., Rodemich E.R., Rumsey H.C.,Jr. and Welch L.R. New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities // IEEE Trans. Inform. Theory. 1977. V. 23. N 2. P. 157166.

30. Rankin R.A. On the closest packing of spheres in n dimensions // Annals of Math. 1947. V. 48. P. 1062-1081.

31. Leech J., Sloane N.J.A. Sphere packings and error-correcting codes // Canad. J. Math. 1971. V. 23. P. 718-745

32. Конвей Дж., Слоэн H. Упаковки шаров, решетки и группы. М.: Мир. 1990.

33. Delsarte P., Goethals J.M.,Siedel J.J. Bounds for systems of lines and Jacobi polynomilas // Philips Research Reports. 1975. V. 30. P. 91/ — —105*.

34. Райгородский A.M. Линейно-алгебраический метод в комбинаторике. М.: МЦНМО. 2007.

35. Сидельников В.М. О плотнейшей упаковке шаров на поверхности п-мерной евклидовой сферы и числе двоичных кодовых векторов с заданным кодовым расстоянием // Докл. Академии Наук СССР. 1973. Т. 14. С. 1851-1855.

36. Левенштейн В.И. О границах для упаковок в n-мерном евклидовом пространстве // Докл. АН СССР. 1979. Т. 245. № 6. С. 1299-1303.

37. Габидулин Э. М. Теория кодов с максимальным ранговым расстоянием // Пробл. передачи информ. 1985. Т. 21. № 1. С. 3-16.

38. Odlyzko A.M., Sloane N.J. A new bound of the number unit spheres that can touch a unit sphere in n dimensions // J.Comb.Theory. Ser. A. 1979. V. 26. P. 210-214.

39. Мусин О. P. Проблема двадцати пяти сфер // УМН. 2003. Т. 58. № 4. С. 153-154.

40. Niederreiter H. Low-discrepancy point sets 11 Monatsh. Math. 1986. V. 102. no. 2. P. 155-167.

41. Цфасман M.A., Розенблюм М.Ю. Коды для m-метрики Пробл. передачи информации. 1997. Т, 33. № 1. С. 45-52.

42. Barg A.,Punarbasu P. Bounds on ordered codes and orthogonal arrays // Moscow Mathematical Journal. 2009. V. 9. no 2. P. 211-243.

43. Скриганов M.M. Теория кодирования и равномерные распределения // Алгебра и анализ. 2001. Т. 13. № 2. С. 301-337.

44. Dougherty S. Т. and Skriganov М. М. MacWilliams duality and the Rosenbloom-Tsfasman metric // Mosc. Math. Journal. 2002. V. 2. no. 1. P. 81-97.

45. Martin W. J., Stinson D. R. Association schemes for ordered orthogonal arrays and (T,M,S)-nets // Canad. J. Math. 1999. V. 51. no. 2. P. 326346.

46. Левенштейн В.И. Двоичные коды с исправлением выпадений, вставок и замещений символов //Докл. Академии Наук СССР. 1965. Т. 163. № 4. С. 707-710.

47. Левенштейн В.И. О совершенных кодах в метрике выпадений и вставок // Дискрет, матем. 1991. Т. 3. № 1. С. 3-20.

48. Justesen J. A class of constructive asymptotically good algebraic codes //IEEE Trans. Inform. Theory. 1972. V. 18. P. 652-656.

49. Зяблов В. В. Оценка сложности построения двоичных линейных каскадных кодов // Пробл. передачи информ. 1971. Т. 7. № 1. С. 5-13.

50. Л. А. Бассалыго Л.А. Формализация задачи о сложности задания кода // Пробл. передачи информ. 1976. Т. 12. № 4. С. 105-106.,

51. JI. А. Бассалыго J1.A., Зяблов В.В., Пинскер М. С. Проблемы сложности в теории корректирующих кодов // Пробл. передачи информ. 1977. Т. 13. № 3. С. 5-17.

52. Berlekamp E.R. McEliece R.J., van Tilborg H.C.A. n the Inherent Intractability of Certain Coding Problems // IEEE Trans. Inform. Theory. 1978. V. 24. P. 384-386.

53. Sipser M., Spielman D.A. Expander codes // IEEE Trans. Inform. Theory. 1996. V. 42. № 6. P. 1710-1722.

54. Галлагер P. Коды с малой плотностью проверок на четность. М.: Мир. 1966.

55. Sudan М. Decoding of Reed Solomon codes beyond the error-correction bound // Journal of Complexity. 1997. V. 13. № 1. P. 180-193.

56. V.Guruswami and M.Sudan, "Improved decoding of Reed-Solomon and algebraic-geometry codes // IEEE Trans, on Information Theory. 1999. V. 45. P. 1757-1767.

57. Лицин C.H., О.Шеховцов О.И. Быстрый алгоритм декодирования кодов Рида-Маллера первого порядка // Пробл. передачи информации. 1983. Т. 19. № 2. С. 3-7.

58. Pellikaan R., Wu X-W. List Decoding of q-ary Reed-Muller Codes // IEEE Trans. Inform. Theory. 2004. V. 50. № 3. P. 679-682.

59. 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-274

60. Kschischang F.R. Constructing Reed-Muller codes from Reed-Solomon codes over GF(q) // Proc. 1993 IEEE Int. Symp. Information Theory. 1993. P. 195.

61. Blackmore Т., Norton G.H. Matrix-Product Codes over ¥q // Applicable Algebra in Engin., Commun. Comput. (AAECC). 2001. V. 12. P. 477500.

62. Niedderreiter H., Xing C. A propagation rule for linear codes // Applicable Algebra in Engin., Commun. Comput. (AAECC). 2000. V. 10. P. 449-462.

63. Ozbudak F., Stichtenoth H. Note on Niedderreiter-Xing propagation rule for linear codes // Applicable Algebra in Engin., Commun. Comput. (AAECC). 2002. V. 13. P. 53-56.

64. Gilbert E.N., MacWilliams F.J., Sloane N.J.A. Codes which detect deception // Bell System Tech. J. 1974. V.53. № 3. P. 405-424

65. Wegman M.N., Carter J.L. New hash functions and their use in authentication and set equality// J. Comput. Sys. Sci. 1981. V.22. № 3. P. 265-279

66. Шеннон К. Математическая теория связи // К. Шеннон. Работы по теории информации и кибернетике. М.: ИЛ, 1963.

67. Simmons G.J. Authentication theory/coding theory //Proc. CRYPTO 84, LNCS V.196. 1985. P. 411-431

68. Бассалыго Л.А., Бурнашев M.B. Оценка максимального числа сообщений при заданной вероятности успешной подмены //Пробл. передачи информации. 1994. Т. 30. № 2. С. 42-48.

69. Hollmann H.D.L., van Lint J.H., Linnartz J.-P., Tolhuizen L.M.G.M. On codes with identifiable parent property // J. Comb. Theory (A). V.82 . 1998. P. 121-133.

70. Chor В., Fiat A., and M. Naor M. Tracing traitors //Proc. Crypto'94. LNCS V. 839. 1994. P. 257-270.

71. Boneh D., Shaw J. Collusion-secure fingerprinting for digital data // IEEE Trans. Inform. Theory. 1998. V.44. № 3. P. 480-491

72. Сагалович Ю.Л. Разделяющие системы // Пробл. передачи информации. 1994. Т. 30. № 2. С. 14-35.

73. Simmons G.J. The Prisoner's Problem and the Subliminal Channel // Proc. CRYPTO'83. 1984. P. 51-67

74. Бассалыго Л.А., Пинскер M.C. Шаровые коды, исправляющие ошибки // Пробл. передачи информации. 1999. Т. 35. № 1. С. 30-37.

75. Somekh-Baruch А., 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.

76. Julin D. Two Improved Block Codes // IEEE Trans. Inform. Theory. 1965. V. 11. N 3. P. 459.

77. Васильев Ю.Л. О негрупповых плотно упакованных кодах // Проблемы кибернетики. Вып. 8. М.: Физматгиз. С. 337-339

78. Романов A.M. Новые двоичные коды с минимальным расстоянием 3 // Пробл. передачи информ. 1983. Т. 19. № 3. С. 101-102.

79. Питерсон У. Коды, исправляющие ошибки. М.: Мир. 1964.

80. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. М.: Мир, 1976.

81. Геворкян Д.Н. О недвоичных кодах с фиксированным кодовым расстоянием // Труды V Международного симпозиума по теории информации. М.-Тбилиси. 1979. С. 93-96.

82. Варшамов P.P. О возможностях увеличения мощности линейных корректирующих кодов // ДАН СССР, 1975. Т. 223. № 1. С. 6063.

83. Solomon G. A Note on Alphabet Codes and Fields of Computation 11 Inform, and Control. 1974. V. 25. N 4. P. 395-398.

84. Hamalainen H.O. (1988) Two new binary codes with minimum distance three // IEEE Trans. Inform. Theory. 1988. V. 34. № 4. P. 875. IEEE Trans Inform Theory 34(4):875.

85. Best M.R. Binary codes with a minimum distance of four // IEEE Trans. Inform. Theory. 1980. V. 26. № 6. P. 738-742.

86. Heath-Brown D.R., Iwaniec H. On the Difference Between Consecutive Primes // Inventiones Math. 1979. V. 55. N 1. P. 49-69.

87. Зиновьев В.А. Обобщенные каскадные коды // Пробл. передачи ин-форм. 1976. Т. 12. Ко. 1. С. 5-15.

88. Phelps К.Т. Product construction for Codes over Arbitrary Alphabets 11 IEEE Trans. Inform. Theory. 1984. V. 30. № 5. P. 769-771.

89. Панченко В. И. Упаковки и покрытия над произвольным алфавитом // Пробл. передачи информ. 1988. Т. 24. № 4. С. 93-96.

90. 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.

91. Ahlswede R., Bassalygo L.A., Pinsker M.S. Nonbinary codes correcting localized errors // IEEE Trans. Inform. Theory. 1993. V. 39. P. 14131416.

92. Алсведе P., Бассалыго JT.А., Пинскер M.C. Асимптотически оптимальные двоичные коды полиномиальной сложности, исправляющие локализованные ошибки // Пробл. передачи информ. 1988. Т. 31. № 2. С. 76-83.

93. Варшамов P.P., Тенегольц Г.М. Код, исправляющиу одиночные несимметрические ошибки // Автоматика и телемеханика. 1965. Т. 26. № 2. С. 288-292.

94. Reed I.S. A class of multiple error correcting codes and the decoding scheme // IEEE Trans. Inform. Theory. 1954. V. IT-4. P. 38-49.

95. Месси Дж. Пороговое декодирование. М.: Мир. 1966.

96. Колесник В. Д., Мирончиков Е. Т. Циклические коды Рида-Маллера и их декодирование // Пробл. передачи информации. 1968. Т. 4. № 4. С. 20-25.

97. Р.Е. Кричевский Р.Е. О числе ошибок, исправляемых кодом Рида-Маллера // Доклады АН СССР. 1970. Т. 191. С. 541-547.

98. В. М. Сидельников, А. С. Першаков, "Декодирование кодов Рида-Маллера при большом числе ошибок", Пробл. передачи информ., 28:3 (1992), 80-94

99. Dumer I. Recursive decoding and its performance for low-rate Reed-Muller codes //IEEE Trans. Inform. Theory. 2004. V. 50. P. 811-823.

100. Gaborit Ph., Ruatta O. Efficient erasure list-decoding of Reed-Muller codes // Proc.2006 IEEE Int. Symp. Information Theory, Seattle, WA, USA. 2006.

101. Goldreich O., Levin L.A. A Hard-Core Predicate for All One-Way Functions // Proc. 21 ACM Sympos. Theory of Computing. 1989. P. 25-32.

102. Лицин C.H. О сложности декодирования низкоскоростных кодов Рида-Маллера //Труды IX Всес. конф. по теории кодиров. и передачи информ.1988. Т.1. С. 202-204.

103. Johnson S.M. A new upper bound for error-correcting codes // IEEE Trans. Inform. Theory. 1962. V. 8. P. 203-207.

104. Kasami Т., Tokura N. On the weight structure of Reed-Muller codes // IEEE Trans. Inform. Theory.1970. V. 16. № 6. P. 752-759.

105. Goldreich O., Rubinfeld R. and Sudan M. Learning polynomials with queries: the highly noisy case // Proceedings of 36-th Symp. on Foundations of Computer Science. 1995. P. 294-303.

106. Goldreich O., Rubinfeld R. and Sudan M. Learning Polynomials with Queries: the Highly Noisy Case // SIAM J. Discrete Math. 2000. P. 535-570.

107. Kasami Т., Lin S., Peterson W. New Generalisations of the Reed -Muller Codes // IEEE Trans. Inform. Theory. 1968. V. 14. № 2. P. 189-199.

108. Delsarte P., Goethals G.-M., MacWilliams F.J. On generalized Reed Muller codes and their relatives // Info, and Control. 1974. V. 16. P. 403-442.

109. Massey J.L., D.J.Costello, Justesen J. Polynomial weights and code constructions // IEEE Trans. Inform. Theory. 1973. V. 19. P. 101-110.

110. Берман С. Д. К теории групповых кодов // Кибернетика. 1967. Т. 3. С. 31-39.

111. Грушко И. И. О мажоритарном декодировании обобщенных кодов Рида-Маллера // Пробл. передачи информации. 1990. Т. 26. № 3. С. 12-20.

112. Берман С. Д., Юданина А. Б. Коды с обобщенным мажоритарным декодированием и сверточные коды // Пробл. передачи информации. 1970. Т. 6. № 1. С. 6-19.

113. Elias P. Error-free coding // IEEE Trans. Inform. Theory. 1954. V. 4. P. 29-37.

114. Gore W.C. Further results on product codes // IEEE Trans. Inform. Theory. 1970. V. 16. P. 446-451.

115. Бояринов И.М., Кацман Г.Jl. Линейные коды с неравной защитой символов // В кн. Вопросы Кибернетики. М.: ВИНИТИ. 1977. Т. 34. С. 60-91.

116. Бояринов И.М. Метод декодирования прямых сумм произведений кодов и его применение // Пробл. передачи информации. 1981. Т. 17. № 2. С. 39-51.

117. Блох Э.Л., Зяблов В.В. Линейные каскадные коды. М.: Наука. 1982.

118. Блох Э. Л., Зяблов В.В. Кодирование обобщенных каскадных кодов // Пробл. передачи информации. 1974. Т. 10. № 3. С. 45-50.

119. Зиновьев В. А.,Зяблов В.В. Декодирование нелинейных обобщенных каскадных кодов // Пробл. передачи информ. 1978. Т. 14. № 2. С. 46-52.

120. Зиновьев В. А.,Зяблов В.В. Исправление пакетов ошибок и независимых ошибок обобщенными каскадными кодами // Пробл. передачи информации. 1979. Т. 15. № 2. С. 58-70.

121. Зубов А.Я. Совершенные шифры. М.: Гелиос АРВ. 2003.

122. Бассалыго Л.А. Нижние границы для вероятности успешной подмены сообщения // Пробл. передачи информации. 1993. Т. 29. № 2. С. 104-108.

123. Stinson D.R. Universal hashing and authentication codes // Des.Codes, Cryptogr. 1994. V. 4. P. 369-380.

124. Stinson D.R. The combinatorics of authentication and secrecy codes // J. Cryptology. 1990. V. 2. № 1. P. 23-49

125. Stinson D.R. The combinatorial characterizations of authentication codes // Des.Codes, Cryptogr. 1992. V. 2. P. 175-187.

126. Simmons G.J. A survey of information authentication //Contemporary Cryptology, The Science of Information Integrity. G.J.Simmons, Ed. NY, IEEE Press. 1992

127. Левенштейн В.И. О верхних оценках для кодов с фиксированным весом векторов // Проблемы передачи информации, 1971. т.7, N4, С.3-12.

128. Agrell Е., Vardy A., Zeger К. Upper bounds for constant-weight codes // IEEE Trans. Inform. Theory. 2000. V.46. No 7. P. 2373-2395.

129. Agrell E., Vardy A., Zeger K. A table of upper bounds for binary codes // IEEE Trans. Inform. Theory. 2001. V.47. No 7. P. 3004-3006.

130. Beutelspacher A., Rosenbaum D. Essentially Mold secure authentication systems // Advances in Cryptology, Proc.Eurocrypt 1990. 1990. P. 294-305.

131. Бассалыго JI.А., Бурнашев M.B. Аутентификация, идентификация и попарно разделенные меры //Пробл. передачи информации. 1996. Т. 32. № 1. С. 41-47.

132. Ahlswede R., Dueck G. Identification via Channels // IEEE Trans. Inform. Theory. 1989. V. 35. no.l. P. 15-29.

133. Ahlswede R., Dueck G. Identification in the Presence of Feedback A Discovery of New Capacity Formulas // IEEE Trans. Inform. Theory. 1989. V. 35. no.l. P.30-36.

134. Ahlswede R., Zhang Z.New Directions in the Theory of Identification via Channels // IEEE Trans. Inform. Theory. 1995. V. 41. no.4. P.1040-1050.

135. Wagner N. Fingerprinting // Proceedings of the 1983 IEEE Symposium on Security and Privacy. 1983. P.18-22.

136. Blakiey G.R., Meadows C. and Purdy G. Fingerprinting long forgiving messages // Proceedings Crypto-85. 1985. P.180-189.

137. Staddon J.N., Stinson D.R. and Wei R. Combinatorial properties of frameproof and traceability codes // IEEE Trans. Inform. Theory. 2001. V. 47. no.3. P.1042-1049.

138. Körner J. On the Extremal Combinatorics of the Hamming space // Journal of Combinatorial Theory, Ser.A. 1995. V. 71. P. 112-126.

139. Blackburn S. R. Combinatorial schemes for protecting digital content // Surveys in Combinatorics 2003, Cambridge University Press, Cambridge. 2003. P. 43-78.

140. Chor B., Fiat A., Naor M. and Pinkas B. Tracing traitors // IEEE Trans. Inform. Theory. 2000. V. 46. P. 893-910.

141. Shamir A. How to share a secret // Comm ACM. 1979. V.22.No 1. P.612-613.

142. Blakiey G.R. Safeguarding cryptographic keys // Proc AFIPS 1979 National Computer Conf. 1979. V.48. P.313-317.

143. Hoeffding W. Probability inequalities for sums of bounded random variables // J.Amer.Stat. Assoc. 1963. V.58. P. 13-30.

144. Simon R. Blackburn S.R., Etzion T. and Siaw-Lynn Ng. Traceability Codes // Cryptology ePrint Archive, Report 2009/046. 2009.

145. Körner J., Simonyi G. Separating partition systems and locally different sequences // SIAM J. Discrete Math. 1988. V. 1. P. 355-359.

146. Berge С. and Duchet P. A generalization of Gilmore's theorem // Recent Advances in Graph Theory, M.Fielder,ed.,Academia,Prague. 1975. P. 49-55.

147. Fredman M.L., Komlos J. On the size of separating systems and families of perfect hash functions // SIAM J. Alg. Discrete Methods. 1984. V.5 . P. 61-68.

148. Korner J., and A. Orlitski A. Zero-error information theory // IEEE Trans. Inform. Theory. 1998. V. 44. P. 2207-2229.

149. Сагалович Ю.Л. Метод повышения надежности конечного автомата // Пробл. передачи информации. 1965. Т. 1. № 2. С. 27-35.

150. Сагалович Ю.Л. Помехоустойчивое кодирование состояний асинхронного конечного автомата // Пробл. передачи информации. 1966. Т. 2. № 2. С. 54-59.

151. Friedman A.D., Graham R.L., Ulman J.D. Universal Single Transition Time Asynchronous State Assigments // IEEE Trans. Comput. 1969. V.18. № 6. P. 541-547.

152. Сагалович Ю.Л. Новые верхние границы мощности разделяющих систем // Пробл. передачи информации. 1993. Т. 29. № 2. С. 109— 111.

153. Cohen G., Encheva S., Litsyn S., Schaathun H-G. Intersecting codes and separating codes// Discrete Applied Mathematics. 2003. V. 128. P. 75-83.

154. Cohen G., Schaathun H-G. Separating codes : constructions and bounds. // Springer Lecture Notes in Computer Science. 2004. V. 2976. P. 322-328.

155. Cohen G., Schaathun H-G. Upper bounds on separating codes// IEEE Transaction on Inform. Theory. 2004. V.50. No 6. P. 1291-1295.

156. Бассалыго Jl.А., Гельфанд С.И., Пинскер М.С. Простые методы получения нижних границ в теории кодирования // Пробл. передачи информации. 1991. Т. 27. № 4. С. 3-8.

157. Alon N., Cohen G., Krivelevich M. and Litsyn S. Generalized hashing and parent-identifying codes // J. Comb. Theory, Ser. A. 2003. V. 104. P. 207-215.

158. Forney G.D. Concatenated Codes. Cambridge,MA. MIT Press. 1966.

159. Silverberg A., J. Staddon J., Walker J. L. Efficient traitor tracing algorithm using list decoding // Proc. ASIACRYPT 2001, Lect. Notes Comput. Sci. , V. 2248. 2001. P. 175-192.

160. Lovasz L. On the Shannon Capacity of a Graph // IEEE Transaction on Information Theory. 1979. V.25. No 1. P. 333-339.

161. Pfitzmann В., Schunter M. Asymmetric fingerprinting // EUROCRYPT 96. Springer LNCS. V. 1070. 1996. P. 84-95.

162. Stinson D. R., Wei R. Combinatorial properties and constructions of traceability schemes and frameproof codes // SIAM J. Discrete Math. 1998. V. 11. P. 41-53.

163. Tardos G. Optimal probabilistic fingerprint codes // Journal of the Association for Computing Machinery. 2008. V. 55. no. 2. Article 10.

164. Amiri E., Tardos G. High rate fingerprinting codes and the fingerprinting capacity // Proc. 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009). 2009. P. 336-345.

165. Anthapadmanabhan N. P., Barg A. and Durner I. On the fingerprinting capacity under the marking assumption // IEEE Trans. Information Theory. 2008. V. 54. No 6. P. 2678-2689.

166. Huang Y.-W., Moulin P. Saddle-point solution of the fingerprinting capacity game under the marking assumption // Proc. 2009 IEEE International Symposium on Information Theory, Seoul, Korea, June 28-July 3. 2009. P. 2256-2260.

167. Cachin C. An information-theoretic model for steganography // Springer LNCS. V. 1525. 1998. P. 306-318.

168. Рябко Б.Я., Рябко Д.Б. Асимптотически оптимальные совершенные стеганографические системы // Проблемы передачи информации. 2009. Т. 45, №2. С. 119-126. ■

169. Бассалыго JI.A., Пинскер М.С. Шаровые коды, исправляющие ощибки//Проблемы передачи информации.1999. Т. 35. №1.С.30-37.

170. Кабатянский Г.А. Два обобщения произведения кодов // Докл. Академии Наук СССР. 1977. Т. 232. № 6. С. 1277-1280.

171. Кабатянский Г.А. О существовании хороших почти линейных кодов над непростыми полями// Пробл. передачи информации. 1977. Т. 13. № 3. С. 18-21.

172. Кабатянский Г.А. , Левенштейн В.И. Границы для упаковок на сфере и в пространстве // Пробл. передачи информации. 1978. Т. 14. № 1. С. 3-25.

173. Кабатянский Г.А., Панченко В.И. Упаковки и покрытия пространства Хэмминга единичными шарами // Докл. Академии Наук СССР. 1988. Т. 303. № 3. С. .550-552.

174. Кабатянский Г.А., Панченко В.И. Упаковки и покрытия пространства Хэмминга шарами радиуса один // Пробл. передачи информации. 1988. Т. 24. № 4. С. 3-16.

175. 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-91.

176. Kabatianskii G. A. About metrics and decoding domain of Forney's algorithm // Proc. Fifth Joint Soviet-Swedish Int. Workshop on Information Theory. Moscow, USSR. 1991. P. 81-85.

177. Kabatianskii G. A. On decoding of concatenated codes in certain spaces // Proc. Fifth Joint Soviet-Swedish Int. Workshop on Information Theory. Moscow, USSR. 1991. P. 86-90.

178. Геворкян Д.H., Кабатянский Г.А. О кодах Варшамова-Тененголыда и одной гипотезе Л.А.Бассалыго //Пробл. передачи информации. 1992. Т. 28. № 4. С. 106-108.

179. Johansson Т., Kabatianskii G.A., Smeets В. On relation between Acodes and codes correcting independent errors // Proc. Eurocrypt'93. 1994. LNCS V. 765. P. 1-11.

180. Кабатянский Г.А. Конструкция кодов, исправляющих одиночные локализованные ошибки //Пробл. передачи информации. 1994. Т. 30. № 2. С. 96-98.

181. Kabatiansky G. Codes correcting localized errors of known value // Proc. 1994 IEEE Int. Symp. Information Theory, Norway. 1994. P. 249.

182. 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.

183. Кабатянский Г.А., Лебедев B.C. Разностные множества и коды, исправляющих одиночные локализованные ошибки известной величины //Пробл. передачи информации. 1996. Т. 32. № 2. С. 31-35.

184. Блейкли Г.Р., Кабатянский Г.А. Обобщенные схемы разделения секрета и матроиды //Пробл. передачи информации. 1997. Т. 33. № 3. С. 102-110.

185. Кабатянский Г.А. Математика разделения секрета// Введение в криптографию,гл.5, МССМЕ, Москва, 1998.

186. Bassalygo L.A., Burmester М., Dyachkov A., Kabatianski G. Hash codes // Proc. 1997 IEEE Int. Symp. Information Theory, Ulm, Germany. 1997. P. 174.

187. Кабатянский Г.А. О кодах, разделяющих пары// Пробл. передачи информации. 2001. Т. 37. № 4. С. 60-62.

188. Barg A., Cohen G., Encheeva S., Kabatiansky G., Zemor G. A Hypergraph Approach to the Identifying Parent Property: The Case of Multiple Parents// SIAM J. Discrete Math. 2001. V. 14. № 3. P. 423-431.

189. Barg A., Blakley G.R., Kabatiansky G. Digital fingerprinting codes: problem statements, constructions, identification of traitors// IEEE Trans. Inform. Theory. 2003. V. 49. № 6. P. 852-865.

190. Galand F., Kabaiansky G. Information Hiding by Coverings // Proceedings of the IEEE Information Theory Workshop 2003, Paris, France. 2003. P. 151-154.

191. Galand F., Kabaiansky G. Steganography via Covering Codes // Proceedings of the IEEE Symp. on Information Theory 2003, Yokohama, Japan. 2003. P. 192.

192. Barg A., Kabatiansky G. Class of i.p.p codes with effective tracing algorithm // J. Complexity. 2004. V. 20. № 2-3. P. 137-147.

193. 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.

194. 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.

195. Kabatiansky G. Good ternary 2-traceability codes exist// Proc. 2004 IEEE Int. Symp. Information Theory, Chicago,USA. 2004. P. 204.

196. Кабатянский Г.А. Коды для защиты от копирования: случай двух пиратов// Пробл. передачи информации. 2005. Т. 41. № 2. С. 123-127.

197. Kabatiansky G., Krouk Е. and Semenov S. Error Correcting Codes and Security for Data Networks. Wiley & Sons. 2005.

198. Kabatiansky G., Tavernier C. List decoding of second order Reed-Muller Codes// Proc. 8 fh Int. Symp. Comm. Theory and Applications, Ambleside, UK. 2005. P. 36-38.

199. 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, Seattle, WA, USA. 2006. P. 138-142.

200. Думер.И., Кабатянский Г.A. , Тавернье С. Списочное декодирование двоичных кодов Рида-Маллера первого порядка// Пробл. передачи информации. 2007. Т. 43. № 3. С. 66-74.

201. Dumer I., Kabatiansky G., Tavernier С. List Decoding of Biorthogonal Codes and the Hadamard Transform with Linear Complexity//IEEE Trans. Inform. Theory. 2008. V. 54. № 10. P. 4488-4492.

202. Dumer I., Kabatiansky G., Tavernier C. Fast list decoding of Reed-Muller codes up to their distances// Proc. XI Int. Workshop Algebraic and Combinatorial Coding Theory, Bulgaria. 2008. P. 82-85.

203. Галан Ф., Кабатянский Г.А. Покрытия, центрированные коды и комбинаторная стеганография // Пробл. передачи информации. 2009. Т.45. № 3. С. 84-90.