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

0034817В5

На правах рукописи

Кабатянский Григорий Анатольевич

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

05.13.17 - Теоретические основы информатики

Автореферат диссертации на соискание ученой степени доктора физико-математических наук

Москва - 2009

003481785

Работа выполнена в Институте проблем передачи информации им. A.A. Харкевича Российской академии наук

Официальные оппоненты: доктор технических наук,

профессор Э.М. Габидулин

доктор физико-математических наук A.M. Райгородский

доктор физико-математических наук С.А. Степанов

Ведущая организация: Институт математики им. C.J1. Соболева

СО РАН

Защита состоится " «w " HO^ofö 2009 г. в И часов на заседании Диссертационного совета Д.002.077.01 при Институте проблем передачи информации им. A.A. Харкевича РАН по адресу: 127994, Москва, ГСП-4, Б. Каретный пер., 19, стр. 1.

С диссертацией можно ознакомиться в библиотеке Институте проблем передачи информации им. A.A. Харкевича РАН

Автореферат разослан "/Sj' 0^^3-^2009 г.

Ученый секретарь Диссертационного совета Д.002.077.01

доктор физико-математических наук И.И. Цитович

Общая характеристика работы

Актуальность темы. Теория кодирования или теория кодов, исправляющих ошибки, ведет свой отсчет от опубликованной 60 лет назад работы Хэмминга \ в которой были построены коды, исправляющие одиночные ошибки. С математической точки зрения теория кодирования может рассматриваться как теория упаковок одного специального класса дискретных метрических пространств, называемых пространствами Хэмминга. В теоретически наиболее изученном и, одновременно, наиболее интересном для практики случае двоичных корректирующих кодов соответствующее двоичное пространство Хэмминга НУ, есть не что иное как n-мерный булев куб {0,1}п с расстоянием, называемым расстоянием Хэмминга и определяемым как число координат, в которых две данные вершины куба различны. Код, исправляющий t ошибок, это упаковка пространства TL^ шарами радиуса t, а кодовые слова - это центры шаров упаковки. Таким образом, код это произвольное подмножество С пространства и код исправляет t ошибок, если d(C) > 2t, где расстояние кода d(C) определяется как минимальное попарное расстояние между точками (словами) кода. Размерность п объемлющего пространства Щ принято называть длиной кода. Основная проблема теории кодирования - нахождение максимальной мощности Л2(п, 2i+l) двоичного кода длины п, исправляющего t ошибок, может быть переформулирована как нахождение максимальной плотности /J»(n, i;2) упаковки п-мерного пространства Хэмминга шарами радиуса t. Построенные Хэммингом коды являются плотными упаковками пространств шарами радиуса 1 при п = 2т — 1, т.е. /1*(2Т" — 1,1;2) = 1. Несмотря на многочисленные результаты теории кодирования (библиография к книге МакВильямс и Слоэна "Теория кодов, исправляющих ошибки", изданной в 1977 г., насчитывает почти полторы тысячи статей, посвященных теории кодирования) вопрос о величине fj,*(n,i;2) не решен даже асимптотически. В частности, до работ автора был открытым вопрос о существовании предела д*(п, 1;2) при п —» оо. В пользу естественной гипотезы

lim /*.(п,1;2) = 1, (1)

п—»оо

был опубликован ряд работ, в которых последовательно доказывалось, что Итц*(п, 1; 2) > 5, где Ö равно 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-160

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

Для теории кодирования принципиально важным является не только построение кода, исправляющего ошибки, но и разработка для данного кода эффективного алгоритма декодирования, т.е. алгоритма нахождения для произвольного вектора у £ 712 ближайшего кодового вектора, называемого декодированием по максимуму правдоподобия, или же алгоритма нахождения всех кодовых векторов, достаточно близких к у, называемого списочным декодированием. В частности, задача о наилучшем приближении произвольной булевой функции от т переменных многочленом (Жегалкина) степени не выше s равносильна задаче о декодировании кода Рида-Маллера (РМ) RM(s,m) длины п = 2т, где s называется порядком кода РМ. Отметим, что известное решение задачи о наилучшем приближении произвольной булевой функции линейными функциями, называемое машиной (алгоритмом) Грина, состоит в применении быстрого преобразования Фурье (БПФ) для группы Z2 ф... © а списочное декодирование кода Рида-Маллера первого порядка (РМ-1) в этом случае равносильно вычислению не всех, а лишь наиболее значимых коэффициентов дискретного преобразования Фурье. Сложность БПФ имеет порядок п log п, тогда как декодирование кода РМ-1 до половины расстояния имеет линейную (по п) сложность. Какое максимальное число ошибок можно исправлять с линейной сложностью было неизвестно даже в этом, наиболее изученном случае кодов РМ первого порядка. Еще меньше было известно про сложность списочных алгоритмов декодирования для кодов РМ произвольного порядка.

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

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

В некотором смысле схожая ситуация возникла в задаче защиты информации от копирования группой (коалицией) пользователей. Эту задачу принято подразделять на задачи "поиска пиратов" и "цифровых отпечатков пальцев". Возникающие при решении этих задач математические объекты называются ¿-идентифицирующими кодами и кодами цифровых отпечатков пальцев, соответственно. Лучший известный результат о кодах цифровых отпечатков пальцев показывал существование таких кодов длины п = 0(tA log(М/е) log 1 /е) с вероятностью ошибки Регг < е, где М - это число пользователей, а размер коалиций не превышает t. Тем самым, эти коды не обеспечивали привычной для теории информации экспоненциально малой от п вероятности ошибки даже при очень малых скоростях кода. Кроме того, для этих кодов был предложен только переборный алгоритм декодирования (идентификации). Для задачи о ¿-идентифицирующих кодах, существование таких кодов со скоростью, отделенной от нуля, было известно лишь для t = 2.

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

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

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

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

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

Научная новизна. Научная новизна работы определяется следующими новыми, впервые полученными автором результатами:

- построены покрытия и упаковки шарами радиуса 1 пространств Хэмминга, плотность которых стремится к 1 с ростом размерности пространств;

- разработаны алгоритмы списочного декодирования кодов Рида-Маллера фиксированного порядка, которые при числе исправляемых ошибок не более расстояния кода имеют "почти линейную" (nlogn) от длины кода п сложность, тогда как ранее известные методы списочного декодирования имели сложность порядка п3;

- разработаны алгоритмы списочного декодирования кодов Рида-Маллера первого порядка с асимптотически минимальной сложностью;

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

Теоретическая и практическая ценность.

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

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

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

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

тификация сообщений, "поиск пиратов", "цифровые отпечатки пальцев" и стеганография.

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

Апробация результатов и публикации. Результаты работы неоднократно докладывались на научных семинарах в МГУ им. М.В. Ломоносова под руководством В.И. Левенштейна (70е-90-е гг.), на научных семинарах в ИППИ РАН под руководством Р.Л. Добрушина, P.A. Минлоса и М.С. Пинскера (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. Как уже было отмечено ранее, самые первые результаты по теории кодирования - граница Хэмминга и коды Хэмминга, утверждают, что максимальная мощность ^(и, 3) двоичного кода, исправляющего оди-

ночные ошибки, не больше чем 2"/(п+1), и что эта граница достигается на кодах Хэмминга при п = 2Г — 1, г = 2,3,.... В пользу гипотезы об асимптотической точности этой границы (эквивалентной гипотезе (1)), т.е. справедливости равенства

был опубликован ряд работ4,5'6, в которых последовательно доказывалось, что lim(n+ 1)А2(п, 2£ + l)2-n > S, где д равнялось, соответственно, 5/8; 5427/8192; 5589/8192. Эти работы основывались на конструкции Плоткина (см. ниже) и некоторых новых хороших нелинейных кодах длин 11, 66, 67 и 143 с плотностями упаковки равными, соответственно, 27/32, 201/256, 187/256, (27/32)2. Как уже отмечалось в начале автореферата, таким образом можно последовательно улучшать оценки на Итц*(п, 1; 2), но нельзя доказать гипотезу (1-2). Была известна и аналогичная гипотеза для покрытий - предполагалось, что плотность лучших покрытий двоичных пространств Хэмминга шарами радиуса 1 также стремится к 1. Более того, естественно рассматривать обобщения обеих гипотез на пространства Хэмминга над произвольным конечным алфавитом.

Для изложения результатов нам понадобятся следующие определения. Множество Нд, состоящее из всех слов длины п над некоторым конечным алфавитом Hq из q букв, называется д-ичным n-мерным пространством Хэмминга. Нам будет удобно рассматривать алфавит TLq как абелеву группу по сложению (например, как группу Ъч вычетов по модулю q), а если q есть степень простого числа - то как конечное поле F,. На множестве Tig задаются вес и расстояние Хэмминга, определяемые как wt(x) = |{г : Xi ф 0}| и d(x,у) = |{г : Х{ ф yi\\ = wt(x — у), соответственно. Подмножество (код) С пространства Хэмминга называется упаковкой (покрытием) шарами радиуса t, если для любого а £ существует не более (соответственно, не менее) одного с € С такого, что d(а, с) < t, или что тоже самое, если для любого a G Н™ уравнение

имеет не более (не менее) одного решения (с, е).

4Sloane 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.

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

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

lim (n + 1 )A2(n, 3)2~n = 1,

(2)

с + e = а, с G С, wt(e) < t

(3)

Если точки (слова) упаковки использовать для передачи сообщений по каналу связи, в котором при передаче п символов происходит не более t ошибок, то на приемной стороне возможно однозначное восстановление переданных сообщений, так как шары радиуса t с центрами в разных кодовых словах не пересекаются. По этой причине упаковка С С шарами радиуса t также называется g-ичным кодом длины п, исправляющим t ошибок. Расстояние d(C) кода С определяется как минимальное из попарных расстояний между его словами

d(C) = min d(с, с'),

с^с'6 С

и код С является упаковкой шарами радиуса t (т.е. исправляет t ошибок), если и только если d(C) > 2t + 1. Про код С мощности M = |С| говорят, что он способен передавать M сообщений, а величина R = R(C) = п"1 logg M называется скоростью кода. Коды (класс) называются хорошими, если их скорость R > а > 0 (т.е. отделена от нуля) при п —* оо.

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

где |<Sg(n, £)| = ^¿=0(<?—1)' Ci) это мощность шара Sq(n, t) радиуса t в пространстве Хэмминга Н™. Очевидно, что плотность покрытия не менее 1, а упаковки (кода), соответственно, не более 1 (последнее неравенство в теории кодирования принято называть границей Хэмминга). Обозначив через /х,(п, t; q) максимальную плотность упаковки п-мерного пространства Хэмминга шарами радиуса t (т.е. /х»(п, £; q) = q~n\Sq(n, t)\Aq(n, 2t + l), где Aq(n,d) - максимальная мощность g-ичного кода с расстоянием не менее d), а через /г* (га, i; q) , соответственно, минимальную плотность покрытия, перепишем эти неравенства в виде

fj,*(n,t;q) > 1 > fit(n,t-,q) (5)

Основной результат первой главы состоит в том, что для алфавитов, которые можно представить как конечное поле, т.е. для q = р"\ где m = 1,2,..., ар- простое число, справедливо

lim /х,(га, 1; q) = lim ß*(n, 1; q) = 1 (6)

n—* oo n—*oo

Доказательство (6) основывается на на предложенной автором конструкции однородных упаковок и покрытий (см. Теорему 1 и Следствие 1), позволяющей строить упаковку (покрытие) шарами радиуса 1 из упаковки

(покрытия) пространства Хэмминга произвольным однородным множеством. Множество 11 С Нд называется однородным, если Ли е 17 для любых и 6 {/, А 6 Говорят, что код С задает упаковку (покрытие) пространства Нд множеством £/, если {с+[/}п{с'+С/} = 0 для с ф с' € С (соответственно, исес{с + = или, что тоже самое, для любого а 6 Нд уравнение

с + и = а, с е С, и € Г/ (7)

имеет не более (не менее) одного решения (с,и). Определим, как и в случае упаковок (покрытий) шарами, соответствующую плотность кода С как

= (8)

Выберем в однородном II какую-либо систему попарно неколлинеарных представителей {иь и2,..., и^}, где N = (|С/| — 1)/(д— 1), т.е.

и = { о)11 11

¿=1 о/лек,

Теорема 1. Пусть код С является упаковкой (покрытием) пространства Н^ однородным множеством и с системой попарно неколлинеарных представителей {щ, иг,..., идт}. Тогда код

Ус,и = {х = (хь ..., хм) 6 : ®1и1 + ... + хмим е С} (9) является упаковкой (покрытием) пространства Н^ шарами радиуса 1.

Доказательство теоремы следует из более общего утверждения, что для любого Ь = (&1,..., Ьм) € Н^ уравнение вида (3)

V + у = Ь, V 6 Ус,и, иЛ(у) < 1 имеет столько же решений, что и уравнение вида (7) с + и = Б(Ь), се С, и ее/

Так как для любого а € Нд коды С и С + а одновременно являются упаковкой (покрытием) пространства Нд множеством [/, то, применив Теорему 1 ко всем кодам Ус+п,и и посчитав среднюю плотность соответствующих упаковок (покрытий) Ус+&,и шарами радиуса 1, получим, что среди них есть хотя бы одна (одно) с плотностью не "хуже" чем /х(С, (/). А именно, справедливо

Следствие 1. Существуют а, а' £ Н" такие, что fj,(Vc+a,u, 1) > /^(С, U) для упаковок и /i(Vc+a',r/, 1) < /-í(C, U) для покрытий. Более того, если ранг U максимален, т.е. равен п, то /i(Vc+a,c/> 1) = U) для всех а.

С помощью этой конструкции удается просто объяснить большинство ранее известных результатов об упаковках (покрытиях) пространств Хэмминга шарами радиуса 1. Так, из упаковок (покрытий) C¿ пространств i = 1,2 шарами радиуса 1 с плотностями ¡м строится упаковка (покрытие) пространства Н^ шарами радиуса 1 с плотностью /i = /11/Í2, где N = (q — l)nin2 + тц + n2. В частности, если выбрать в качестве одного из С i код длины 1, состоящий из одного слова , то получим известную конструкцию Плоткина, позволяющую строить из произвольной упаковки (покрытия) шарами радиуса 1 пространства Н™ упаковку (покрытие) пространства Хэмминга размерности (n+l)q — 1 с той otee плотностью.

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

Пусть V является упаковкой (покрытием) шарами радиуса 1 пространства Hr. Тогда для любого a S Н\ множество

= {хеЩ: Ми), <р(х2), ••., Фп)) £а + У}

является упаковкой (покрытием) шарами радиуса 1 пространства 7Íq при условии, что отображение <р : Hq —> HlR инъективно в случае упаковок и сюръективно в случае покрытий. Применив эту конструкцию к Д-ичным кодам Хэмминга, которые являются одновременно упаковками и покрытиями шарами радиуса 1, и воспользовавшись усреднением по а, получим следующий результат.

Предложение 1. Пусть R - степень простого числа, i - натуральное число ип = {Rl — 1 )/(R — 1). Тогда для любого Q < R существует упаковка W пространства Hq шарами радиуса 1 с плотностью fi(W, 1) > (Q— l)/(R— 1), и для любого Q > R существует покрытие W пространства Hq шарами радиуса 1 с плотностью /j.(W, 1) < (Q — 1 )/{R — 1).

Теперь положим Q = ql и рассмотрим упаковки и покрытия Предложения 1 как упаковки и покрытия множеством {/;,п пространства Н1™. Применив к ним Следствие 1, получим

Теорема 2. Пусть R - степень простого числа, i,l - натуральные числа

(Д* - !)(<?' - 1) П (Л-1)(д-1)"

Тогда в пространстве Н.™ при ql < R существует упаковка В шарами радиуса 1 с плотностью [г(В, 1) > (ql — 1 )/{R — 1), а при ql > R существует покрытие С шарами радиуса 1 с плотностью ц{С, 1) < (9'-1)/(Я-1).

Если в Теореме 2 брать I —» оо, а в качестве R выбирать простое число, достаточно близкое к ql, то получается последовательность упаковок (покрытий) с плотностью, стремящейся к 1, но эта последовательность длин недостаточно плотна, чтобы с ее помощью прямо доказывать гипотезу (6). Оставшиеся шаги доказательства используют очевидные процедуры укорочения упаковки (кода) и, соответственно, удлинения покрытия, упомянутую выше конструкцию Плоткина и известное утверждение из теории чисел, что для любой константы (3 £ [11/20,1] существует число Np такое, что если х > Np , то между х и х-1 имеется хотя бы одно простое число. В результате получаем основной результат первой главы.

Теорема 3. При фиксированном q, являющемся степенью простого числа, справедливо неравенство

|1 - 1;«)| < 4е1п2 9^(1 + о(1)), (Ю)

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

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

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

В общей формулировке задачи о кодах, исправляющих £ локализованных ошибок, отправителю известны / позиций, где могут произойти ошибки. Поэтому правильнее говорить не о коде, а о кодировании (р = <р{т,Е), которое сопоставляет сообщению т £ М. и множеству Е позиций, где возможны ошибки, кодовое слово </з(ш, Е), передаваемое по каналу. Уже в первой работе 7 по кодам, исправляющим локализованные ошибки, было доказано, что для числа 1Л11 передаваемых сообщений по-прежнему справедлива граница Хэмминга. В частности, число сообщений \М\ для 5-ичного кода, исправляющего одиночные локализованные ошибки, не превышает + (д — 1)п). В §1.4 для произвольного ц рекурсивно строятся коды длины пг = (дг — 1)/(<7 - 1) при г = 2,3,... с числом сообщений = дп_г, т.е. коды лежат на границе Хэмминга. "Начальный" код длины п2 = д + I задается кодированием

где т = (т i,..., mq-i) £ М, rrii EH, и j е {1,2, ...q + 1} - местоположение возможной ошибки.

Содержание первой главы диссертации изложено в работах [3,4,8-10,18].

Во второй главе изучаются алгоритмы декодирования кодов Рида-Маллера, в особенности, алгоритмы списочного декодирования. За почти 60 лет от момента их изобретения коды Рида-Маллера (РМ) были предметом многочисленных исследований. Хорошо известно, что только "крайние" коды в этом классе, а именно, первого и последнего порядков, являются оптимальными. Популярность же кодов РМ в основном объясняется их простой и естественной структурой, а также эффективными алгоритмами их декодирования, построение которых началось с работы Рида (1954). С математической точки зрения декодирование двоичных кодов РМ - это интерполяция двоичных многочленов от многих переменных в ситуации, когда часть известных значений многочлена ошибочна.

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

i=1

При этом классическая задача интерполяции, когда все известные значения функции верны и нужно восстановить функцию полностью, в теории кодирования называется задачей об исправлении стираний. Алгоритмически задача об исправлении стираний довольно проста, так как для любого линейного кода она сводится к задаче о решении системы линейных уравнений и, тем самым, имеет полиномиальную (от длины кода) сложность, тогда как задача об исправлении ошибок линейным кодом является Л^Р-полной. В теории кодирования рассматривают и более общую задачу о совместном исправлении ошибок и стираний, а также ее дальнейшее обобщение на случай, когда известным значениям функции приписаны коэффициенты надежности, т.е. вероятности того, что данное значение правильно. Декодирование, соответствующее последней задаче, называется мягким (soft decoding).

Основным объектом исследования второй главы являются алгоритмы списочного декодирования кодов РМ. По определению, списочное декодирование радиуса Т состоит в нахождении всех кодовых слов в шаре радиуса Т вокруг произвольного принятого слова. Говоря формально, входом алгоритма списочного декодирования кода С с радиусом декодирования Т является произвольный вектор у = (yi, ...уп), а выходом -множество (список)

LT.c(y) = {ceC:d(y,c)<T}. (11)

Про алгоритм списочного декодирования с радиусом Т говорят, что он исправляет Т ошибок, понимая под этим, что если при передаче кодового слова с £ С произошло не более Т ошибок (т.е. d(y, с) < Т), то оно содержится в выходе алгоритма - списке LT-c{y) (но как его дальше искать в этом списке - отдельная задача). Важный частный случай списочного декодирования, когда радиус Т = L^jrJ > является наиболее популярной задачей декодирования, известной как "исправление до d/2 ошибок". В этом случае результат декодирования (список) либо состоит из одного кодового слова, либо пуст.

В классе кодов Рида-Маллера особое внимание уделялось декодированию кодов первого порядка. Предложенный для них алгоритм МП декодирования, известный как "машина Грина", имеет сложность (в элементарных бинарных операциях) 0(п log2 п) и является алгоритмом БПФ для группы Z2$...0Z2 (также называемым быстрым преобразованием Адамара) плюс алгоритм быстрой сортировки. С другой стороны, было известно (8 и [5]), что декодирование "до (1/2 ошибок" имеет линейную сложность для любых кодов РМ фиксированного порядка. Но было

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

неизвестно, возможно ли списочное декодирование кодов РМ-1 с линейной сложностью при радиусе декодирования Т > d/2 ошибок. В §2.1 описан новый алгоритм списочного декодирования кодов РМ, названный автором алгоритмом критерия сумм (сокращенно, КС), который для кодов первого порядка находит список при радиусе декодирования Т = (1 — е)п/2 со сложностью 0(nln2(min{e~2, п})) двоичных операций (здесь и всюду ниже 0 < е < 1). Частными случаями нового алгоритма при е = 1 / д/гг и £ = 1/2 являются "машина Грина" и алгоритм декодирования "до d/2 ошибок", соответственно.

Рассмотрим множество всех линейных булевых функций и сопоставим каждой такой функции

с(х) = Со + CiXi (12)

1<г<т

двоичный вектор с = (...,с(х),...) £ "Щ, гдеп = 2m, ах = (xi,...,xm) пробегает по всем п точкам m-мерного булева куба Ti™. Получаемый двоичный код называется кодом Рида-Маллера первого порядка RM(l,m) и является оптимальным кодом, состоящим из 2п слов при кодовом расстоянии d = п/2. Из известной границы Джонсона на размер списка Ьт,с{у) для произвольного кода С с расстоянием d(C)

IWrtl<d(c)„2S(„_r) Р»)

(при условии, что знаменатель дроби положителен) и очевидного замечания, что в список радиуса Т < п/2 не могут одновременно входить кодовые слова с и сф 1, следует, что для кода RM(l,m) размер списка £е;,п(у) ••= LT.RM(\,m){y) радиуса Т = (1 - е)п/2 не более min{e~2, п}.

Для произвольной линейной булевой функции c(xi, ...,xm) = С\Х\ + ... + СтХт + со ее j-м префиксом называется функция с^Цхi,..., Xj) = С\Х\ + ... + CjXj, а функция с(хi,...,xm), в свою очередь, называется продолжением (префикса) с^Цхi,...,Xj). Обозначим С^)т(у) список j-x префиксов всех искомых функций с(х1;..., хт) £ £е;т(у). Алгоритм КС работает рекурсивно, находя на j-м шаге свой список CÍ^niy) , содержащий список С%{у), но, возможно, содержащий при этом и другие префиксы. Один из ключевых моментов алгоритма это нижняя оценка (15) расстояния Хэмминга от принятого слова у до любой линейной функции с(х 1, ..., Хт) = C^(xi, ..., Xj) + Cj+iXj+i + ... + стхт + Со, являющейся продолжением данного префикса é3\x\,..., x¡), см. лемму 1. Затем с помощью этой оценки формируется критерий сумм (16)(см. ниже), на основании которого происходит "отсев" заведомо непригодных префиксов, и, в результате, объем порождаемых списков достаточно мал (не более е-2) для всех j.

Будем рассматривать в m-мерном булевом кубе 7i™ j-мерные граии вида S'a = {(жх,..., Xj, a,j+i,..., ат)}, где переменные xlt... ,Xj произвольные (и пробегают все 2; двоичных j-мерных векторов), переменные Xj+1 = (Lj+i,..., хт = агп фиксированы, a вектор a = (oj+i, • ■ •, a m) будем называть "номером" грани. Для произвольных функций-векторов / и g обозначим через d(f,g\S&) расстояние Хэмминга между их ограничениями на j-мсрную грань Sa. Определим j-oe "расстояние" между векторами / и g как

Aij\f,g)= £ Д(/,а|5.), (14)

аб

где по определению Д(/, з|5а) = min{d(f, g\Sa),d(f, g ф l|5a)}.

Пусть c(xi,..., xm) -произвольная линейная булева функция и с^ = С\Х\ + ... + CjXj - ее j-й префикс. Ограничение с{х\,хт) на j-мерную грань S'a равно é3)(xx,..., Xj) + са, где са = c1+iai + ... + статч + cq 6 {0,1}. Отсюда следует

Лемма 1. Для любой булевой функции у, любой линейной функции с = С\Х\ + ... + стхт + с0 и ее префикса с^ = с\Х\ + ... + CjXj справедливо

d(y,c)>A^(y)C^) (15)

Будем говорить, что для данной (принятой) булевой функции у префикс с^ = с\х 1 + ... + CjXj удовлетворяет критерию сумм, если

&{Л(у,си)) < (1-е)п/2. (16)

Предлагаемый алгоритм КС на (j + 1)-m шаге рассматривает все возможные продолжения префиксов, найденных iiaj-м шаге, т.е. рассматривает префиксы вида c(j)(x1,...,xj) + cj+1xj+i, где ¿^ G Л;тЫ> cj+1 G {0,1}, и из них алгоритм оставляет только префиксы, удовлетворяющие критерию сумм (16), что и составляет список

Мы будем оценивать сложность алгоритма КС количеством элементарных бинарных операций (а не операций над целыми или действительными числами). Воспользуемся рекуррентной структурой алгоритма и для сокращения сложности будем "пересчитывать" расстояния ¡/|5а)

на основе результатов предыдущего шага алгоритма. Соответствующий анализ сложности приводит к одному из основных результатов второй главы.

Теорема 4. Для произвольного е > 0 алгоритм КС осуществляет списочное декодирование кодов Рида-Маллера первого порядка со сложностью 0(nlog2(mm{e~2,n})) при радиусе декодирования Т = (1 — е)п/2.

Замечание. Можно заменить первые J = [log2e~2] шагов предлагаемого алгоритма на алгоритм Грина, примененный ко всем 2m~J J-мерным граням Sa. На выходе алгоритма Грина получаются значения d(y,c^|5a) и d(y,c(J) ф 1|5а) для всех c(J) G RM(1,J), из них вычисляются А(у, c^\Sa), а затем подаются на вход (J+ 1)-го шага алгоритма КС. Сложность применения алгоритма Грина равна 0(J22J) х 2m~J, т.е. такого же порядка как и у первых J шагов алгоритма КС. В действительности алгоритм КС на первых шагах делает тоже, что и алгоритм Грина, плюс дополнительно "отсеивает" лишние префиксы за счет критерия сумм, что на этих шагах является, как мы только что отметили, несущественным. Однако на следующих шагах это "отсеивание" играет ключевую роль в получении асимптотически меньшей, чем у алгоритма Грина, итоговой сложности алгоритма.

В §2.2 алгоритм КС обобщается на случай мягкого списочного декодирования кодов РМ-1. Рассматривается канал передачи информации без памяти с двоичным входным алфавитом X = {—1,+1} и выходным алфавитом У, задаваемый переходными вероятностями (или соответствующими плотностями) р(у = а\х = а). Пусть для передачи сообщений используется двоичный код С длины п, в словах которого 0 и 1 заменены на ±1 по правилу х —> х = (—I)1. При такой замене код С становится сферическим кодом С® С Мп, лежащим на евклидовой сфере S»"1^ радиуса л/гг, а расстояние Хэмминга с?(х, у), евклидово расстояние D(x, у) и скалярное произведение (х, у) связаны простым соотношением

(x,y)=n-D2(x,y)=n-2d(x,y) (17)

Пусть у = (г/i,..., уп) Е Yn принятое из канала слово. Обозначим через 7г логарифм отношения правдоподобия для г-го символа у*

_ Pr{+l\yi)

(18)

где Pr(-\-l\yi) и Pr(—l\yi) - это апостериорные условные вероятности. По определению, мягкое списочное декодирование должно выдавать список наиболее вероятных, по отношению к принятому слову у, кодовых слов, т.е. список

ЬР;с{у) = {с G С : Pr(c|y) > Р). (19)

Рассмотрим вектор = (ji, ...,7„) и, домножив на скаляр vWI бу~ дем считать, что 7 € §"_1(\/п). Известно, что мягкое списочное декодирование равносильно поиску ближайших к 7 слов кода CR в евклидовом пространстве Rn, а список Ьр;с(у) совпадает со списком

Ь£;с(?) = {сеС:(с,^)>гге} (20)

для соответствующего s.

Рассмотрим теперь двоичный код RM(l,m) как сферический, заменив 0 и 1 на ±1, т.е. сопоставим произвольной линейной булевой функции с(х), см.(12), вектор

c = (..,(-l)£W,...)er, (21)

где п = 2т и х = (xi, ...,xm) пробегает по всем 2т точкам Tí™. Получаемый сферический код RMR(l,m) из 2п точек с минимальным угловым расстоянием 7г/2 - это правильный n-мерный октаэдр, так же часто называемый в литературе по теории кодирования биортогональным кодом. Таким образом, задача мягкого списочного декодирования кодов РМ-1 может быть сформулирована как задача нахождения для любого "принятого" вектора G Sn~1(^/ñ) списка слов кода RMR(í,m) на угловом расстоянии от т* не более arceos £

£?¡m(t) = {с G RM( 1, m) : (с, > ne} (22)

Половина слов сферического кода RMr(1, m), соответствующих линейным функциям с Со = 0, образуют ортогональный базис R™, известный как матрица Адамара размерности п = 2т. Если бы были известны п координат 7i, ...,т„ вектора в этом ортогональном базисе, то дальнейшее вычисление очевидно и требует п операций сравнения вещественных чисел 7i, •■■, 7п с "порогом" е. Быстрое вычисление всех координат 7¿ известно как быстрое преобразование Адамара (или быстрое ДПФ при п = 2т) и требует (Э(п In п) операций над вещественными числами. В §2.2 рассматривается "мягкий" алгоритм КС, который естественно обобщает алгоритм КС на случай евклидова пространства и позволяет находить е-"значимые" (т.е. модуль которых не меньше е) коэффициенты ДПФ за ö(nln(min{e_2,n})) операций над вещественными числами. Перейдем к описанию "мягкого" алгоритма КС.

Для произвольного вектора u G Кп, где по-прежнему п — 2т и координаты "занумерованы" точками Н™, обозначим через иа его ограничение на j-мерную грань Sa. Определим j-oe "скалярное произведение" между векторами u,v€R" как (ср. с (14))

Ä«(u,v)= £ |(ua,va)|. (23)

Сопоставим, следуя (21), произвольной линейной булевой функции с(х) — CiXi + ...стхт + Со и ее j-му префиксу с^(х) векторы с и с^. Так как для любой j-мерной грани S& выполняется равенство

Ca = Ааг£>, (24)

где Аа = (—l)cj+iaj+1+,"+c'"am+Cfl, т0 верно следующее обобщение леммы 1.

Лемма 2. Для любого вектора £ Sn любой линейной функции

с = С1Х1 + ... +cmxm + cQ и ее префикса с^ = С\Хi + ... +CjXj справедливо

(25)

Будем говорить, аналогично (16), что для данного вектора префикс = ciXi + ■ • • + CjXj удовлетворяет "мягкому" критерию сумм, если

дШ^^й')) >П£. (26)

Далее "мягкий" алгоритм КС работает также как и описанный выше алгоритм КС, рассматривая на j + 1-м шаге все возможные продолжения префиксов, найденных на j-м шаге, и оставляя только те, что удовлетворяют "мягкому" критерию сумм (26). Для мягкого алгоритма справедлив, почти дословно, аналог теоремы 4 и сложность алгоритма, как уже упоминалось выше, имеет порядок nloge-1 операций.

В §2.3 исследуются алгоритмы списочного декодирования кодов Рида-Маллера фиксированного порядка. Двоичный код Рида-Маллера s-ro порядка RM(s,m) состоит из векторов f = (...,/(х),...) £ Tí?], где /(х) = /(xi,...,xm) - многочлен степени не больше s, п = 2т и х = (xi,...,xm) пробегает по всем п точкам гп-мерного булева куба Ti™. Размерность (число информационных символов) кода RM(s, тп) равна ks^rn = о (?)> а расстояние кода ds¡m = nós, где 6„ = 2~3- относительное расстояние кода. Обозначим через

T(s, m; Т) = max \Ьт.нм(з<т){у)\ (27)

максимально возможный объем списка радиуса Т для кода Рида-Маллера RM(s, m). Определим критический радиус TCTit как такой, что при любой константе е > 0 имеем l*(s, тп; Тсп1{\ — е)) < се, т.е. размер списка ограничен константой (зависящей от е), а с другой стороны, l*(s, тп; Тстц(1 + е)) —» оо с ростом длины кода. До недавнего времени для кодов Рида-Маллера было известно лишь то, что Tcrit > Js = 2_1(1 — \/1 — 2~s+1), где J, - значение границы Джонсона для кода RM(s, m). В работе 9 было доказано, что для кода Рида-Маллера s-ro порядка Тсгц = 8а = 2~а и более того,

l(s,m,e) < 2(2s+5e~2)4s, (28)

где l(s, m, е) := l*(s, m; (5S — e)n). Другим важным инструментом, используемым при построении алгоритмов списочного декодирования кодов

9Gopaian P., Klivans A.R., Zuckerman D. List-Decoding Reed-Muüer Codes over Smaü Fields //Proc. 40th annual ACM symposium on Theory of computing. 2008. P. 265-274

РМ, является конструкция Плоткина (уже использованная нами в главе 1). Так как позиции кодовых слов "нумеруются" точками х из т-мерного булева куба Н™, то разобьем произвольное кодовое слово Г на две половины, например, в первую {' войдут координаты, стоящие на позициях х : хт = 0, а во вторую Р - стоящие на позициях х : хт = 1, и будем записывать í = (Г, {"). Тогда Г, Г е М(б,т-1) и Г+Г € ДМ^-1, т-1). Это и есть (и, и + у)-конструкция Плоткина применительно к кодам РМ, а именно, { = (и, и + у), где и 6 ЯМ(в, т — 1) и V е 7?М(я — 1, т — 1). Аналогично будем разбивать и принятый вектор у на у' и у". Опишем алгоритм Ф(з,т,е), декодирующий принятое слово у в список

Ф(в, т, е)(у) = V € т) : с1({, у) < п(53 - е)}.

Пусть алгоритмы т — 1, е) и Ф(й — 1, т — 1, е) уже построены. Алгоритм Ф(.5, т, е) вычисляет три вспомогательных списка

V = Ф(й — 1,т — 1,2е)(у' + у"),

Ь' = Ф(Я, тп - 1, е)(у'), Ь" = Ф(8, тп- 1, е)(у"), а затем формирует два списка

А = {(и', и' + V) : и' е Ь', V е Ь"}

В = {(и" + V, и") : и" еЬ",у£ Г}

Далее алгоритм завершает работу, оставляя только те слова из списков А и В, что находятся от принятого слова на расстоянии не более п(53 — е)}. Иначе говоря,

Ф(5, ш, е)(у) = {{ е А и В : <1% у) < п(63 - е)}.

Сложность тп, е) этого алгоритма удовлетворяет неравенству

Х(я, тп, е) < х(я — 1, ш — 1, 2е) + 2х(в, т-1,е) (29)

+2п1(з, ш — 1, е)1(з - 1, т — 1,2е).

Используя алгоритм КС списочного декодирования кодов РМ первого порядка со сложностью 0(п\п2 е), оценку Джонсона (13) размера списка для кодов РМ первого порядка и оценку (28) для кодов РМ более высокого порядка, получаем, что сложность построенного алгоритма списочного декодирования для кода Рида-Маллера КМ(з, т.) при в > 2 имеет вид

Х(з,т,е) = 0(е-18п1па'1п) + 0(е8'16зп1пп),

и x(2,m,e) = 0(e~18nlnn).

В §2.4 исследуются различные обобщения кодов Рида-Маллера на недвоичный случай. Особое внимание уделено предложенной автором конструкции недвоичных кодов РМ как обобщенных кодов-произведений, которая впоследствии неоднократно переоткрывалась.

Содержание второй главы диссертации изложено в работах [1,5-7,19,2227].

В третьей главе исследуются некоторые задачи защиты информации, в решении которых удалось добиться существенного прогресса благодаря использованию методов и результатов теории кодирования. В §3.1 изучается задача безусловной аутентификации сообщений, которая, по-существу, является задачей теории кодирования. А именно, эта задача возникает, когда в классической, идущей от Шеннона, математической модели передачи информации место природы, порождающей ошибки, занимает оппонент (противник). Очевидно, что исправление ошибок в такой ситуации невозможно и речь идет только об их обнаружении. Более того, в силу стандартного для задач защиты информации предположения, что оппоненту известно все, кроме "случайности", наличие одного кода также бесполезно, так как оппонент, зная код и передаваемое кодовое слово, может заменить его на другое кодовое слово. Поэтому в этой задаче используется не один код, а семейство кодов С к, "нумеруемых" элементами к £ К (элементы к принято называть ключами), и выбор конкретного кода происходит случайно с некоторым распределением вероятностей р{к), известным и оппоненту тоже. Основное предположение состоит в том, что конкретный выбор ключа к известен передатчику и приемнику, но не оппоненту. Семейство кодов Ск вместе с распределением вероятностей р(к), которое, как правило, предполагается равномерным, принято называть аутентификационпой схемой, или кратко, А-схемой. В работе рассматриваются систематические А-схемы, когда кодовое слово v СЕ С^ имеет вид v = (то, z), где m £ Л4 - это передаваемое сообщение, а "метка" -г = ф(т, k) £ TLq является функцией сообщения и ключа. Для полученного из канала слова у = (m', z') приемник проверяет верно ли равенство z' = ip(rri', к), где к - это используемый в данный момент ключ. Если "НЕТ", то происходит обнаружение ошибки (которую принято называть целенаправленной), если "ДА", то считается, что передавалось сообщение т', и если при этом т! ф т, то говорят, что оппонент успешно подменил сообщение. Основной характеристикой А-схемы является вероятность успешной подмены определяемая как максимальная вероятность успеха оппонента в подмене сообщения, пере-

даваемого по каналу, и равная Ps = max max —-—--—--—-г.-1 (30)

(m,z)€MxHq т'фтеМ, z'eH, \{к £ К : 1р(т, К) = Z}\

Другой важной характеристикой Л-схемы является вероятность им-персонификации Pi, определяемая как максимальная вероятность успеха оппонента в подстановке сообщения в отсутствии передачи сообщения легальным отправителем и равная

й_ ^ И»6

(m,z)eMxHq \К\

Очевидно, что Р/ > l/q, и далее мы, без заметного ограничения общности, ограничимся изучением Л-схем с Р[ = l/q.

В ряде работах высказывалось предположение о существовании связи между задачей аутентификации и теорией кодирования, см. 10, однако попытки найти эту связь не были успешными, так как не шли далее поверхностного факта, что каждое отображение ip(.,k) задает некоторый код. Занумеруем произвольным образом множество ключей К = {ki,..., kn} и рассмотрим g-ичный код

V = {vm = {-ф{т, ki),..., ф(т, kn)) : т £ М} (32)

мощности М = \М\ и длины п = \К\, который мы будем называть Л-кодом (соответствующим Л-схеме). Определим Л-"расстояние" на Н™ как

Ai(x,y)=n-q max |{г: х{ = z, yt = z'}\ (33)

и, соответственно, определим Л-"расстояние" кода V как DA(V) = min Da(v,v').

v^v'ev

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

НИ-« (34)

п

Таким образом, исследование Л-схем с вероятностью подмены Ps равносильно изучению Л-кодов, т.е. g-ичных кодов с Л-"расстоянием" DA(V) = п{1—Ps). Первым следствием из этой связи является возможность, в силу

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

очевидного неравенства Da(V) < d(V), использовать развитые в теории кодирования верхние оценки на мощность кода с заданным расстоянием. В частности, из границы Плоткина следует, что |V| < (п — l)/{q — 1) при Ps — 1/q и, тем самым, скорость Л-кодов стремится к нулю с ростом длины при Ps > 1/q.

С другой стороны, можно показать, что скорость наилучших Л-кодов отделена от нуля при любой Ps = const < 1 /q и, следовательно, можно передавать экспоненциально много (от числа ключей) сообщений с заданной вероятностью успешной подмены Ps- А именно, как показано ниже, из q-ичиого кода с расстоянием (Хэмминга) d = Sn можно построить код той же мощности и с тем же относительным Л-"расстоянием", но в q раз более длинный. Более точно, пусть U' - линейный (п, к)-код с расстоянием d = Sn, содержащий вектор 1 из всех единиц, и пусть U -некоторый его к — 1-мерный подкод, не содержащий 1, т.е. U' = f/ф 1. Нетрудно убедиться, что для кода

V = {(и, и + ají,..., и + a9_il) : и € U, {0, аь ..., a,_i} = FJ (35)

справедливо, что Pj = 1/q, его Л-"расстояние" DA(V) > SN, где N = qn - длина кода V, а мощности кодов V и IJ равны. Отсюда, в силу известных результатов теории кодирования и соотношения 34, уже следует, что для любой Ps = const < 1/q скорость наилучших Л-кодов отделена от нуля. Отметим, что схожие результаты о скорости лучших Л-кодов были независимо получены в 11.

Кроме того, предложенная конструкция позволяет строить конкретные оптимальные Л-коды. Так, если в качестве кода U' взять ^-ичный код Рида-Соломона, то итоговый Л-код будет оптимальным в том смысле, что на нем достигается минимум вероятности успешной подмены Ps при данных п, q и М.

В §3.2 и §3.3 рассматривается следующая математическая задача, возникающая при защите авторских прав при коммерческом распространении мультимедийных продуктов (таких как фильмы, музыка, игры, программное обеспечение и т.п.). Для произвольного множества U = {и1,..., uÉ} С Hqn будем называть позицию i G {1,..., п} [/-неразличимой, если векторы ц б U имеют в этой позиции одно и тоже значение, и будем обозначать через А({/) множество всех таких позиций. Определим выпуклую оболочку множества U как

(U) = {х = (хъ ..., хп) € Hqn :xi£Ui,i = 1,..., n}, (36)

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

где Ui = {ui : u = (щ,..., un) G [/}, и расширенную выпуклую оболочку как ___

(U) = {х= (хъ ...,хп) G Пдп :xí = Uí для i G A(t/)}, (37) Код С называется t-идентифицирующим , если для любого У G С«,

П U * (38)

UCC

ve(u),m<t

где

C« = (J (X)

xcc,\x\<t

- это объединение всех выпуклых оболочек í-подмножеств кода С.

Эти коды возникли в задаче о нахождении коалиций пользователей, нелегально распространяющих/копирующих данные (например, видео), передаваемые широковещательно. Таких недобросовестных пользователей стали называть (видео)"пиратами", а саму задачу - задачей "поиска пиратов". В схеме, рассмотренной в 13 (и названной открытой одноуровневой), имеется п множеств ключей шифрования К\,Кп (|A"¿| = ?), каждый пользователь с получает вектор с из п ключей с = (ci, ...,с„) : с, € Ki, и коалиция пользователей U может создать любой набор ключей у = (у\,..., уп) из имеющихся у них ключей, т.е. из t/¿ G Ui для всех i = 1,..., п, или, согласно данному выше определению, породить у G (U). Тем самым, свойство ¿-идентифицируемости есть не что иное как способность кода по любому такому у найти хотя бы одного из членов коалиции, создавшей у, т.е. найти хотя бы одного "пирата".

Очевидно, что если алфавит слишком мал, а именно, если q < t, то мощность ¿-идентифицирующего кода тоже мала - не превосходит q. С другой стороны, в 12 было показано, что существуют хорошие 2-идентифицирующие троичные коды. Положительное решение вопроса о существовании хороших ¿-идентифицирующих кодов при всех q > t + 1 дано в §3.2. Это решение основывается на использовании аналога теоремы Хэлли для гиперграфов и новом понятии частичного (Ь,и)-хэш кода. А именно, код С С 7íqn называется частичным (£, и)-хэт кодом, где и > t, если для любых двух подмножеств Т и U таких, что Т С U С С, |Г| = t, \U\ = и, существует координата i G {1, ...,п} такая, что xi Ф Vi Для любых х G Т и у G U, у ф х. При и = t + 1 получается обычное определение t + 1-хэш кода, т.е. когда для любых t + 1 кодовых

12Hollmann 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.

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

слов существует различающая их координата. При доказательстве существования хороших ¿-идентифицирующих кодов ключевую роль играет следующий результат.

Лемма 3. Любой частичный (Ь,и)-хэш код си— |_(£/2 + 1)2J является t-идентифицирующим кодом.

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

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

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

Семейство кодов С Tiqn одинаковой мощности М, "занумерованных" элементами множества К и выбираемых с распределением вероятностей тт(к), и алгоритм "декодирования" (идентификации участника коалиции) Dfc(у) : Ti,™ н-> Cfc характеризуется вероятностью правильного декодирования Рсаг, определяемой как минимальная по всем стратегиям коалиций размера t вероятность правильного декодирования, т.е. вероятность события Dfc(y) € U. Дополнительная величина Perr = 1 — РСОГ называется вероятностью ошибочной идентификации, или сокращенно, вероятностью ошибки. В работе 14 было доказано существование кодов длины п = 0(í4logelog(e/M)) с вероятностью ошибки Регт < е. Как уже отмечалось выше (в разделе Актуальность темы), недостатками этих кодов является экспоненциально сложный алгоритм их декодирования и то, что при любой асимптотически ненулевой скорости передачи вероятность ошибки имеет порядок 2-°(\/ñ) вместо желаемого 2-o(n)_ J3 §з з построены ансамбли кодов, свободные от обоих этих недостатков. В основе построения лежит каскадная конструкция, использующая в качестве внутренних двоичные (t, £)-разделимые коды (т.е. для любых двух непересекающихся i-множеств кодовых векторов существует разделяющая их координата, см. 15), а в качестве внешних - д-ичные коды с "большим" расстоянием Хэмминга d > (1 — t~3)n и эффективным алгоритмом декодирования, например, алгебро-геометрические коды с алгоритмом Судана-Гурусвами. Получаемые в результате коды имееют асимптотически ненулевую скорость и обладают алгоритмом декодирования (идентификации) с полиномиальной от п сложностью, обеспечивающим экспоненциально малую вероятность ошибки. В частности, для коалиций из двух участников справедлива

Теорема 5. Для произвольного R < 0.0269 существует двоичный код длины п со скоростью R и алгоритм его декодирования с полиномиальной (от п) слоэ/сностыо, идентифицирующий одного из двух участников коалиции с вероятностью ошибки РСТГ < 2~5п/252.

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

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

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

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

Содержание третьей главы изложено в работах [11-17,20,21,28].

В заключении диссертации сформулированы основные результаты диссертационной работы.

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

17Somekh-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.

Основные результаты

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

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

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

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

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

Основные результаты диссертации изложены в следующих опубликованных работах.

Список литературы

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

6. Kabatianskii G. A. About Metrics and Decoding Domains of ForneyTs 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 Т., 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. Class of i.p.p codes with effective tracing algorithm // J. Complexity. 2004. V. 20. № 2-3. P. 137-147.

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. 2004 IEEE Int. Symp. Information Theory, Chicago,USA. 2004. P. 204.

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

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

23. Kabatiansky G., Tavernier C. List decoding of sccond order Reed-Muller Codes// Proc. 8 th 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 С. 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 Reed-Muller codes up to their distances// Proc. XI Int. Workshop Algebraic and Combinatorial Coding Theory, Pamporovo, Bulgaria. 2008. P. 82-

28. Галан Ф., Кабатянский Г.А. Покрытия, центрированные коды и комбинаторная стеганография // Пробл. передачи информации.

85.

2009. Т. 45. № 3. С. 106-111.

Подписано в печать 05.10.2009 г. Печать лазерная цифровая Тираж 120 экз.

Типография Aegis-Print 115230, Москва, Варшавское шоссе, д. 42 Тел.: (495) 785-00-38 www.autoref.ae-print.ru

Введение

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

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.