Содержание к диссертации
Введение
1 Коды, исправляющие одиночные ошибки 31
1.1 Метод однородных упаковок и покрытий 31
1.2 Упаковки и покрытия одиночными фазированными пакетами 38
1.3 Асимптотика лучших упаковок и покрытий единичными шарами 42
1.4 Коды, исправляющие одиночные локализованные ошибки 51
2 Списочное декодирование кодов Рида-Маллера 55
2.1 Списочное декодирование линейной сложности двоичных кодов Рида-Маллера первого порядка 57
2.2 Мягкое списочное декодирование кодов Рида-Маллера первого порядка 70
2.2.1 Граница Джонсона для сферических кодов 72
2.2.2 Алгоритм КС (критерия сумм) декодирования кодов RM(1, т) в евклидовом пространстве 75
2.3 Списочное декодирование почти линейной сложности для двоичных кодов Рида-Маллера фискированного порядка . 81
2.3.1 Верхняя граница на мощность списка при частично известном весовом спектре кода 81
2.3.2 Списочное декодирование кодов Рида-Маллера второго порядка 85
2.3.3 Алгоритм КО (критерия отношений) списочного декодирования кодов Рида-Маллера фиксированного порядка 92
2.3.4 Алгоритм "двух попыток" списочного декодирования кодов Рида-Маллера фиксированного порядка 97
2.4 Построение и свойства недвоичных кодов Рида-Маллера 101
3 Применения теории кодирования к задачам защиты информации 106
3.1 Коды, обнаруживающие целенаправленные ошибки, или коды для безусловной аутентификации 106
3.1.1 Определения и предшествующие результаты 108
3.1.2 Аутентификационные схемы и коды, исправляющие ошибки 111
3.1.3 Одна конструкция аутентификационных кодов 114
3.2 Коды для защиты авторских прав, I - коды, идентифицирующие родителей 118
3.2.1 Одноуровневые схемы поиска пиратов и коды, иден тифицирующие родителей 120
3.2.2 Недвоичные коды, идентифицирующие пары по минимуму расстояния 124
3.2.3 Асимптотически хорошие идентифицирующие коды 129
3.2.4 Асимптотически хорошие идентифицирующие коды с полиномиальной сложностью 136
3.3 Коды для защиты авторских прав, II - коды цифровых отпечатков пальцев, устойчивые к коалициям 139
3.3.1 Постановка задачи 140
3.3.2 Асимптотически хорошие и полиномиально реализуемые коды цифровых отпечатков пальцев, устойчивые к коалициям 145
3.3.3 Асимптотически хорошие и полиномиально реализуемые коды цифровых отпечатков пальцев, устойчивые к парам 152
3.4 Центрированные коды, исправляющие ошибки, и комбинаторная стеганография 156
3.4.1 Коды-покрытия и пассивная комбинаторная модель 157
3.4.2 Шаровые коды, исправляющие ошибки, и активная комбинаторная модель 160
3.4.3 Шаровые коды, исправляющие ошибки, и одна модель "цифровых отпечатков пальцев" 163
Заключение 165
Литература 167
- Асимптотика лучших упаковок и покрытий единичными шарами
- Верхняя граница на мощность списка при частично известном весовом спектре кода
- Асимптотически хорошие идентифицирующие коды с полиномиальной сложностью
- Шаровые коды, исправляющие ошибки, и активная комбинаторная модель
Введение к работе
Актуальность темы. Теория кодирования или теория кодов, исправляющих ошибки, ведет свой отсчет от опубликованной 60 лет назад работы Хэмминга 1, в которой были построены коды, исправляющие одиночные ошибки. С математической точки зрения теория кодирования может рассматриваться как теория упаковок одного специального класса дискретных метрических пространств, называемых пространствами Хэмминга. В теоретически наиболее изученном и, одновременно, наиболее интересном для практики случае двоичных корректирующих кодов соответствующее двоичное пространство Хэмминга 7^2 есть не что иное как n-мерный булев куб {0, 1}п с расстоянием, называемым расстоянием Хэмминга и определяемым как число координат, в которых две данные вершины куба различны. Код, исправляющий t ошибок, это упаковка пространства 7^2 шарами радиуса , а кодовые слова - это центры шаров упаковки. Таким образом, код это произвольное подмножество С пространства 7-^, и код исправляет t ошибок, если d(C) > 2, где расстояние кода d(C) определяется как минимальное попарное расстояние между точками (словами) кода. Размерность п объемлющего пространства 7^2 принято называть длиной кода. Основная проблема теории кодирования - нахождение максимальной мощности А2(п, 2+1) двоичного кода длины п, исправляющего t ошибок, может быть переформулирована как нахождение максимальной плотности /х„.(п, ;2) упаковки п-мерного пространства Хэмминга 7^2 шарами радиуса t. Построенные Хэммингом коды являются плотными упаковками пространств TV^ шарами радиуса 1 при п = 2т — 1, т.е. /i*(2m — 1, 1; 2) = 1. Несмотря на многочисленные результаты теории кодирования (библиография к книге МакВильямс и Слоэна "Теория кодов, исправляющих ошибки", изданной в 1977 г., насчитывает почти полторы тысячи статей, посвященных теории кодирования) вопрос о величине /х„.(п, ;2) не решен даже асимптотически. В частности, до работ автора был открытым вопрос о существовании предела /х*(п, 1; 2) при п —> оо. В пользу естественной гипотезы
lim /х*(п, 1;2) = 1, (1)
п—>оо
был опубликован ряд работ, в которых последовательно доказывалось, что ИтуЛпЛ-Л) > 6, где 6 равно 5/8; 5427/8192; 5589/8192 (Sloane N.J.A. and Whitehead D.S., 1970; Кацман Г.Л., 1981; Лицин С.Н., 1984). Эти работы основывались на конкретных хороших нелинейных кодах.
1 Hamming R.W. Error-Detecting and Error-Correcting Codes // Bell System Tech. J. 1950. V.29. № 1. P. 147-160
Однако такой метод "последовательного улучшения" не мог дать окончательный (и ожидаемый) ответ, так как для доказательства этой гипотезы нужна бесконечная серия кодов возрастающей длины с плотностью упаковки, стремящейся к 1.
Для теории кодирования принципиально важным является не только построение кода, исправляющего ошибки, но и разработка для данного кода эффективного алгоритма декодирования, т.е. алгоритма нахождения для произвольного вектора у Є Ті^ ближайшего кодового вектора, называемого декодированием по максимуму правдоподобия, или же алгоритма нахождения всех кодовых векторов, достаточно близких к у, называемого списочным декодированием. В частности, задача о наилучшем приближении произвольной булевой функции от т переменных многочленом (Жегалкина) степени не выше s равносильна задаче о декодировании кода Рида-Маллера (РМ) RM(s, т) длины п = 2т, где s называется порядком кода РМ. Отметим, что известное решение задачи о наилучшем приближении произвольной булевой функции линейными функциями, называемое машиной (алгоритмом) Грина, состоит в применении быстрого преобразования Фурье (БПФ) для группы Z2 ф ... ф Z2, а списочное декодирование кода Рида-Маллера первого порядка (РМ-1) в этом случае равносильно вычислению не всех, а лишь наиболее значимых коэффициентов дискретного преобразования Фурье. Сложность БПФ имеет порядок nlogn, тогда как декодирование кода РМ-1 до половины расстояния имеет линейную (по п) сложность. Какое максимальное число ошибок можно исправлять с линейной сложностью было неизвестно даже в этом, наиболее изученном случае кодов РМ первого порядка. Еще меньше было известно про сложность списочных алгоритмов декодирования для кодов РМ произвольного порядка.
Из множества задач защиты информации, понимаемой как обеспечение целостности информации в процессе ее передачи или хранения (под воздействием разнообразных атак и угроз), в диссертации рассмотрены те задачи, где для соответствующего "канала передачи информации" была неизвестна положительность его пропускной способности, т.е. возможность "передавать" сообщений экспоненциально много от некоторого параметра задачи, который естественно называть "длиной кода", обеспечивая при этом нулевую или стремящуюся к нулю вероятность ошибки с ростом "длины кода". Для каждой из рассмотренных задач нетривиальным является ее сведение к некоторой задаче теории информации и уже затем доказательство положительности пропускной способности соответствующего "канала передачи информации". Среди таких важных задач особо отметим задачу обнаружения целенаправленных ошибок, также известную как задача аутентификации сообщений. Начиная с первой от-
крытой публикации 2, этой задаче уделялось большое внимание, однако до работ автора было неизвестно возможно ли, чтобы число сообщений росло экспоненциально от числа ключей.
В некотором смысле схожая ситуация возникла в задаче защиты информации от копирования группой (коалицией) пользователей. Эту задачу принято подразделять на задачи "поиска пиратов" и "цифровых отпечатков пальцев". Возникающие при решении этих задач математические объекты называются ^-идентифицирующими кодами и кодами цифровых отпечатков пальцев, соответственно. Лучший известный результат о кодах цифровых отпечатков пальцев показывал существование таких кодов длины п = 0(t4log(M/e) log І/є) с вероятностью ошибки Регг < Є, где М - это число пользователей, а размер коалиций не превышает t. Тем самым, эти коды не обеспечивали привычной для теории информации экспоненциально малой от п вероятности ошибки даже при очень малых скоростях кода. Кроме того, для этих кодов был предложен только переборный алгоритм декодирования (идентификации). Для задачи о і-идентифицирующих кодах, существование таких кодов со скоростью, отделенной от нуля, было известно лишь для t = 2.
В отличие от предыдущих задач защиты информации, которые являются современными (возникли в XX веке), задаче стеганографии (скры-тописи) несколько тысяч лет. Правда, первая формализованная постановка задачи стеганографии также появилась менее сорока лет назад в работе Г.Симмонса 3. В ней предлагались две модели поведения противника ("надзирателя" - в терминологии Симмонса): пассивная и активная. И если для пассивной модели ее "пропускная способность" была найдена независимо рядом исследователей в силу эквивалентности этой задачи с задачей о кодах-покрытиях, то вопрос о положительности "пропускной способности" для активной модели оставался открытым до работ автора.
Цель работы. Целью работы является исследование свойств оптимальных или близких к оптимальным блоковых кодов, исправляющих ошибки, и возможностей их применения в задачах защиты информации.
Методы исследования. В наших исследованиях использованы методы теории информации и теории кодирования, в частности, метод случайного кодирования, а также методы алгебры, комбинаторики и теории сложности вычислений.
2Gilbert E.N., Mac Williams F.J., Sloane N.J.A. 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-е гг.), на научных семинарах в ИППИ РАН под руководством Р.Л. Добрушина, Р.А. Минлоса и М.С. Пинскера (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 наименований.
Асимптотика лучших упаковок и покрытий единичными шарами
В заключение раздела введения, посвященного метрическим проблемам теории кодирования, еще раз отметим, что границы Варшамова-Гилберта и Минковского справедливы "в среднем," т.е. обе справедливы для "почти всех" линейных кодов или решеток, соответственно. Поэтому довольно естественной представляется гипотеза об их асимптотической точности, но ни доказать, ни опровергнуть эту гипотезу при современном уровне развития как теории кодирования, так и дискретной геометрии не представляется возможным, по крайней мере, в ближайшем будущем.
Для теории кодирования принципиально важным является не только построение кода, исправляющего ошибки, но и разработка для данного кода эффективных алгоритмов "кодирования" и "декодирования". И если сложность задачи декодирования осознавалась с самого начала, то это было не так для задач кодирования, т.е. алгоритма нумерации кодовых слов, и, особенно, для задачи задания кода. Это объясняется тем, что на начальном периоде развития теории кодирования большая часть исследуемых кодов была линейными кодами, для которых задача кодирования очевидна (умножение информационного вектора на порождающую матрицу кода), а вопрос задания кода просто не возникал, так как коды задавались явно. Ситуация прояснилась в начале 70-х годов прошлого века при решении задачи построения "хороших" кодов, т.е. кодов, у которых при фиксированной скорости относительное расстояние не стремится к нулю с ростом длины кода (существование таких кодов было к тому времени хорошо известно). Из двух решений этой задачи, полученных почти одновременно, поначалу только решение Юстесена [49] воспринималось как искомое-решение, так как требуемые коды строились "явно", тогда как в решении В.В. Зяблова [50] присутствовал алгоритм перебора на этапе выбора внутреннего кода. Однако формальное рассмотрение с позиции теории сложности показывает, что оба алгоритма имеют полиномиальную сложность, и поэтому оба имеют равные права называться "решениями". Такой анализ был впервые проделан в работах [51], [52] и с тех пор вопросы сложности прочно вошли в теорию кодирования.
Основными вариантами постановки задачи декодирования являются следующие: списочное декодирование радиуса Т, которое состоит в нахождении всех кодовых слов в шаре радиуса Т вокруг произвольного принятого слова; декодирование (исправление) t ошибок при t d/2, кратко называемое "декодированием до d/2" и являющееся частным случаем списочного декодирования, когда радиус Т — _- г_); декодирование по минимуму расстояния Хэмминга, чаще называемое декодированием по максимуму правдоподобия(МП) и состоящее в нахождении для произвольного вектора у є Tig ближайшего кодового вектора. Один из первых результатов о сложности задач декодирования состоял в доказательстве JVP-полноты задачи декодирования по максимуму правдоподобия [53] в классе всех линейных кодов, а сложность задачи декодирования до d/2 до сих пор неизвестна.
Особенно важную роль вопросы сложности в теории кодирования стали играть в последние 10-15 лет после того как были сделаны почти одновременно следующие три важные открытия. Во-первых, на основе расширителей были построены коды с линейной сложностью декодирования, исправляющие линейное число ошибок при фиксированной кодовой скорости [54].
Во-вторых, коды с низкой плотностью проверок на четность или коды Галлагера [55] получили "второе рождение", так как было доказано, что с их помощью достигаются аналогичные результаты. В-третьих, был построен алгоритм списочного декодирования кодов Рида-Соломона с полиномиальной сложностью при числе исправляемых ошибок вплоть до границы Джонсона, т.е. был придуман полиномиальный алгоритм восстановления всех многочленов от одной переменной (т.е. слов кода Р-С), которые отличаются от некоторой g-ичной функции в не более чем заданном числе значений аргумента [56], [57]. Отметим, что последний алгоритм оказал сильное воздействие не только на теорию кодирования, но и на computer science и криптографию. Его обобщение в одном из двух возможных направлений - заменить проективную (или аффинную прямую) на произвольную алгебраическую кривую, и, соответственно, заменить кодов Р-С на произвольные алгебро-геометрические коды, произошло довольно естественно и быстро, см. [57]. А вот обобщение в другом направлении, с заменой многочленов от одной переменной на многочлены от многих переменных, и, соответственно, с заменой кодов Р-С на коды Рида-Маллера (РМ), в полном объеме не осуществлено до сих пор. Важность этого обобщения объясняется, в частности, тем, что задача о декодировании двоичного кода RM(s,m) длины п — 2т и порядка s эквивалентна задаче о наилучшем приближении произвольной булевой функции от т переменных многочленом (Жегалкина) степени не выше s. Решению этой задачи и посвящена вторая глава. В $ 2.1 строится алгоритм КС (критерия сумм), который осуществляет списочное декодирование кодов Рида-Маллера первого порядка с радиусом декодирования Т = (1 — є)п/2 и сложностью 0(пІод2(тт{є 2,п})) для любого є 0. Отметим, что известное решение задачи о наилучшем приближении произвольной булевой функции (от многих переменных) линейными функциями, называемое машиной (алгоритмом) Грина, см. [2], состоит в применении быстрого преобразования Фурье-Адамара (БПФ) для группы 2 0 - 0- 2, а списочное декодирование кода Рида-Маллера первого порядка (РМ-1) в этом случае равносильно вычислению не всех, а лишь наиболее значимых коэффициентов дискретного преобразования Фурье-Адамара. Сложность БПФ имеет порядок nlogn, тогда как предлагаемый алгоритм имеет линейную сложность. До работ автора с линейной сложностью умели исправлять только вдвое меньше ошибок - до d/2 п/4 ошибок [58]. В 2.2 алгоритм КС обобщается на случай мягкого списочного декодирования кодов РМ-1. Пусть для передачи сообщений используется некоторый двоичный код С длины п, в словах которого 0 и 1 заменены на ±1 по правилу х —» х — (—1)х. При такой замене код С становится сферическим кодом С3- С Жп, лежащим на евклидовой сфере п-1(Л/п) радиуса л/п. Известно, что мягкое списочное декодирование равносильно поиску слов кода Ск, ближайших к некоторому "принятому" вектору "-у в евклидовом пространстве IRn. Предлагаемый "мягкий" алгоритм КС обобщает алгоритм КС на случай евклидова пространства и позволяет находить список за 0(п\п(тіп{є"2, г})) операций над вещественными числами.
В 2.3 исследуются алгоритмы списочного декодирования для двоичных кодов Рида-Маллера произвольного фиксированного порядка. Двоичный код Рида-Маллера s-ro порядка RM(s, т) состоит из векторов f = (..., /(х),...) є 7 2, где /(х) = f(xi,...,xm) - многочлен степени не больше s, п — 2т и х = (xi,...,xm) пробегает по всем п точкам т-мерного булева куба Н. Размерность (число информационных символов) кода RM(s,rn) равна kSjTn 2ыо СГ) а расстояние кода ds m = vSs, где Ss = 2"s- относительное расстояние кода.
Верхняя граница на мощность списка при частично известном весовом спектре кода
Основным объектом исследования в этой главе являются алгоритмы списочного декодирования двоичных кодов Рида-Маллера. Напомним, что списочное декодирование радиуса Т состоит в нахождении всех кодовых слов в шаре радиуса Т вокруг произвольного принятого слова. Говоря более формально, входом алгоритма списочного декодирования кода С с радиусом декодирования Т является произвольный вектор у = (yi,.. .уп), а выходом - множество (список)
За более чем 50 лет коды Рида-Маллера (РМ) были предметом многочисленных исследований. Только "крайние"коды в этом классе, а именно, первого и m — 1-го порядков, являются оптимальными, популярность же кодов РМ в основном объясняется их простой и естественной структурой, а также эффективными алгоритмами их декодирования, построение которых началось с работы [95]. Предложенный в [95] алгоритм был одним из первых примеров алгоритмов мажоритарного декодирования, см. [96], [97], и возможности таких алгоритмов применительно к двоичным кодам Рида-Маллера были оценены в [98]. В последствии были разработаны другие, более эффективные алгоритмы, близкие к максимуму правдоподобия, см. [99], [100]. С математической точки зрения декодирование кодов РМ есть не что иное как интерполяция двоичных многочленов от нескольких переменных в ситуации, когда часть известных значений многочлена ошибочна. При этом классическая задача интерполяции, когда все известные значения функции верны и нужно восстановить функцию полностью, в теории кодирования называется задачей об исправлении стираний. Алгоритмически задача об исправлении стираний довольно проста для любого линейного кода, так как сводится к задаче о решении системы линейных уравнений и, тем самым, имеет полиномиальную (от длины кода) сложность. Заметим, что и здесь структура кодов РМ позволяет предложить алгоритмы исправления стираний (т.е. интерполяции) более простые, чем в общем случае, см. [101]. В теории кодирования рассматривают и более общую задачу о совместном исправлении ошибок и стираний, а также ее дальнейшее обобщение на случай, когда известным значениям функции приписаны коэффициенты надежности, т.е. вероятности того, что данное значение правильно. Декодирование, соответствующее последней задаче, называется мягким (soft decoding) и представляет, как правило, наибольший интерес с практической точки зрения.
Рассматриваемые в диссертации алгоритмы списочного декодирования кодов Рида-Маллера являются детерминированными и безошибочными алгоритмами. Другой подход к списочному декодированию кодов РМ, основанный на вероятностных алгоритмах, был предложен в [102]. Основное отличие от рассматриваемых в диссертации детерминированных алгоритмов состоит в том, что вероятностный алгоритм не является алгоритмом декодирования в привычном для теории кодирования смысле, так как для него возможные ошибки декодирования связаны с не только с вероятностным характером ошибок в канале передачи информации, но и с вероятностной природой алгоритма. Такой алгоритм может включить в список "ошибочное" кодовое слово, т.е. находящееся слишком далеко от принятого слова, либо наоборот не включить в список "правильное", т.е. достаточно близкое, кодовое слово. Соответствующие вероятности ошибки обозначаются Pej и Ре,// а Ре — Ре 1 + РЄіП обозначает (полную) вероятность ошибки алгоритма. В [102] был построен вероятностный алгоритм списочного декодирования кодов RM(l,m) со сложностью, являющейся полиномиальной функцией ОТ ІПД, 1 и 1п(Ре-1) (сокращенно, poly(lnn,s l,ln(P 1)), при радиусе декодирования Т = (1 — s)d. То, что сложность этого алгоритма очень мала как функция от ті и имеет порядок poly(\og п) вместо привычных poly(n), частично объясняется тем, что результат декодирования может быть ошибочным (см. 2.1). Вопрос о существовании аналогичного алгоритма для кодов Рида-Маллера произвольного фиксированного порядка был положительно решен в недавней работе [60]. Подчеркнем, что вероятностные алгоритмы в диссертации не рассматриваются.
В $ 2.1 строится алгоритм КС (критерия сумм) списочного декодирования кодов Рида-Маллера первого порядка с радиусом декодирования Т — (1 — е)п/2 и сложностью 0(nlog2(mm{e 2,n})) для любого є 0. В 2.2 этот алгоритм обобщается на случай мягкого декодирования, или, что тоже самое, строится списочное декодирование для биортогонально-го кода в л-мерном Евклидовом пространстве. В 2.3 мы распространяем эти результаты на произвольные двоичные коды Рида-Маллера фиксированного порядка. В 2.4 четвертом параграфе рассматриваются различные обобщения кодов Рида-Маллера на недвоичный случай.
Рассмотрим множество всех линейных булевых функций и сопоставим каждой такой функции двоичный вектор где п — 2"\ а х = (хі, хт) пробегает по всем п точкам ги-мерного булева куба Н. Получаемый двоичный код называется кодом Рида-Маллера первого порядка RM(l,m) и является оптимальным кодом, состоящим из 2л слов при кодовом расстоянии d = л/2.
Наиболее известным алгоритмом декодирования кодов RM(l,m) является алгоритм Грина (также называемый "машиной" Грина), см. [2]. Основой алгоритма является быстрое преобразование Фурье-Адамара, с помощью которого за 0(п1п2п) двоичных (битовых) операций вычисляются расстояния Хэмминга от принятого слова до всех 2д слов кода. Упорядочивание этого списка расстояний по возрастанию, что не меняет порядок сложности, позволяет осуществлять как декодирование по максимуму правдоподобия, так и списочное декодирование произвольного радиуса Т. В работе [58] было показано, что сложность декодирования можно сделать линейной, если ограничиться декодированием до половины расстояния. Первый детерминированный (или безошибочный) алгоритм списочного декодирования для кодов RM(1, т) с радиусом декодирования Т = (1 — e)d и линейной по п сложностью 0(пє 3), где 1 є 0, был предложен автором совместно с С. Тавернье в [198].
Цель данного параграфа - построение детерминированного списочного алгоритма для кодов Рида-Маллера первого порядка, находящего все слова кода в шаре радиуса Т — (1 — s)d вокруг принятого слова и имеющего сложность 0{п 1іг(тіп{є_2,п})) двоичных операций. Тем самым и алгоритм Грина, и алгоритм "декодирования до половины расстояния" [58] оказываются частными случаями нового алгоритма при - 1/\/ и Е = J-/2. соответственно.
Асимптотически хорошие идентифицирующие коды с полиномиальной сложностью
Основным недостатком и алгоритма КО, и алгоритма "двух попыток" явяляется то, что они ни при каком радиусе декодирования не дают линейную сложность. В тоже время, такие алгоритмы для Т d/2 известны, см. [103], [179]. У алгоритма "двух попыток" этот недостаток неисправим - даже если убрать из рекуррентного соотношения 2.95 третий член, отвечающий за подсчет расстояний для векторов из списка ЛиВ, то коэффициент 2 и как минимум линейная сложность декодирования для кода первого порядка приводят к тому, что сложность все равно имеет порядок nlogs_1n. Формально та же ситуация и с алгоритмом КО. Заметим, что и алгоритм КС имел бы сложность nlogn, если бы мы разумно не пользовались результатами вычислений "расстояний" с предыдущего шага. Таким образом, построение алгоритмов списочного декодирования кодов Рида-Маллера фиксированного порядка с линейной сложностью при радиусе декодирования Т d/2 является, по моему мнению, наиболее важной открытой задачей в области декодирования-кодов РМ.
Другой важной открытой задачей является построение эффективных (полиномиальных) алгоритмов списочного декодирования для недвоичных кодов Рида-Маллера фиксированного порядка. В следующем параграфе рассматривается предложенная автором конструкция недвоичных кодов Рида-Маллера и их обобщений, и обсуждаются подходы к построению алгоритмов их списочного декодирования.
Код Рида-Маллера RMq(s,m) над полем q определяется как множество векторов f — (..., /(х),...) Є Hq, длины п = qm, получаемых как значения многочлена f(xi,..., хт) степени не больше s, когда х пробегает по всем п — qm точкам m-мерного g-ичного пространства Хэм-минга Н. Так как xq = х q, то можно считать, что степень по каждой переменной не больше чем q — 1. Именно таким образом недвоичные коды Рида-Маллера были определены в [108]. Поделим число s на q — 1 с остатком, т.е. s — a(q — 1) + b, где b є {0,..., q — 2}. Следующее утверждение было доказано Касами, Лином и Питерсоном в [108] (почему-то в computer science оно известно как Schwartz-Zippel Лемма).
Предложение 2.4. Расстояние кода RMq(s,m) равно Отметим, что вопрос о том, как обобщить коды Рида-Маллера на недвоичный случай, был весьма актуален в конце 60-х - начале 70-х годов прошлого века, и было предложено несколько разных обобщений, см. [109], [ПО]. В частности, рассматривались обобщения, идущие от предложенной С.Д. Берманом [111] конструкции кодов как радикалов соответствующей групповой алгебры (двоичный коды Рида-Маллера легко получались с помощью такой конструкции). При этом старались сохранить присущее двоичным кодам свойство мажоритарной декодируемое, см. [112], так как на тот момент мажоритарное декодирование представлялось одним из самых простых (если не самым) методов декодирования, см. [96]. В работе [113] была предложена конструкция, основанная на прямых суммах тензорных(итеративных) произведений кодов. Эта конструкция была обобщена в работе автора [174]. Пусть задано семейство из т линейных пространств Ц размерности п, над полем К с фиксированными базисами е\, и их подпространства где di это растояние кода К. Конструкция Бермана-Юданиной [113] получается как частный случай этой конструкции когда Vi С {х є Li : ХІ + ... -Ь хПг — 0} , т.е. все коды Vi являются подкодами кодов с общей проверкой "на четность". Двоичные коды Рида-Маллера, в свою очередь, являются частным случаем конструкции Бермана-Юданиной, когда все длины щ = 2, a Vi — {0,1} - код с проверкой на четность. Эта конструкция (m-кратного произведения s-ro порядка кодов Vi) обобщается дальше, если рассмотреть в каждом пространстве Li не по одному коду, а по семейству вложенных кодов. А именно, пусть в пространствах L{ заданы последовательности вложенных друг в друга под- пространств (кодов) V o С Цд С VijPi — L . Будем называть [174] произведением кодов Vij по множеству JcP = {(ji,... ,jm) 0 ji Рг} код (подпространство) В этой конструкции, как и в предыдущей, код есть сумма (вообще говоря, не прямая) кодов-произведений (итеративных), а расстояние кода равно минимальному из расстояний кодов-произведений Конечно, при pi = 1 получается предыдущая конструкция. Новую конструкцию можно рассматривать как некоторое обобщение конструкции из работы W.Gore [115], которая появилась одновременно с работой [113] как еще одно обобщение конструкции кодов Рида-Маллера, причем сразу на случай g-ичных кодов. В конструкции W.Gore в пространстве Li выбираются некоторые "специальные" базисы vifi,..., vi ni-i, тогда векторы vjlr .Jm = vi, .. .vmjm образуют базис пространства Lm = L\ g ... g Lm и порядком такого вектора будем называть ji + ... + jm. Код 5-го порядка определялся в [115] как линейное подпространство, порожденное векторами, порядок которых не более s. Самым интересным в [115] было построение таким образом g-ичных кодов Рида-Маллера [108]. В этом построении все пространства Ll одной и той же размерности q, поле q занумеровано как q = {cv0 = 0,Q!i,..., a:g_i}, базисный вектор v., получается как вектор из кода Рида-Соломона, т.е. как значения на элементах поля многочлена f,(x) = (х—ао)... (x—aj) степени j. Таким образом, если сопоставить базисным векторам у j порождаемый ими код Vj, то получится система вложенных кодов Рида-Соломона длины q, где код Vj состоит из векторов, соответствующих многочленам степени не больше j. Если в данном случае рассматривать векторы из пространств L,- как функции-многочлены, то их тензорному произведению соответствует произведение функции от разных переменных (в количестве га), т.е. соответствует многочлен от х\,... ,хт степени не более s, т.е. слово кода Рида-Маллера порядка s. Теперь проще объяснить, что за требования к "специальным" базисам предъявлялись в [115]. Рассматривался код Vy, порожденный первыми j + 1 векторами Vj,o,..., v,-,;, и требовалось, чтобы вес j-ro вектора равнялся расстоянию j-ro пространства, т.е. wt(vij) = d(Vij). При таких предположениях в [115] доказывалось фактически следующее утверждение, эквивалентное (2.101). Предложение 2.5. Расстояние кода W С Lm, порожденного как векторное пространство векторами vJb...Jm : (ji,... ,jm) Є J, равно минимальному из весов порождающих векторов.
Шаровые коды, исправляющие ошибки, и активная комбинаторная модель
В этом и следующем параграфах рассматриваются математические задачи, мотивированные проблемой защиты авторских прав при коммерческом распространении мультимедийных продуктов (таких как фильмы, музыка, игры, программное обеспечение и т.п.). В настоящее время известны некоторые технические и криптографические решения этой проблемы. Например, кодирование-шифрование фильмов при их широковещательной передаче по сети с тем, чтобы только легальный пользователь, имеющий соответствующий декодер, мог просмотреть фильм или воспроизвести запись. Очевидное решение такого типа, когда каждый пользователь получает собственный ключ, обладает и очевидным недостатком - слишком большое число ключей (равное числу пользователей), которые надо передавать в широковещательном режиме. Более эффективное решение, позволяющее существенно сократить объем ключевой информации, было впервые предложено в [71], а соответствующая проблематика получила название "поиска (видео)пиратов" (или tracing traitors) или "кодов, идентифицирующих родителей" [70].
Другим типом решения проблемы защиты авторских прав являются так называемые цифровые "водяные знаки" ("метки"). Например, если эта техника применяется к изображениям, то видимые изменения отсутствуют (чаще всего для расположения метки используются наименее значимые разряды), однако цифровой анализ позволяет указать (найти) присущую только этой копии уникальную метку и, тем самым, указать на недобросовестного пользователя, который распространяет нелегальные копии. Однако эти способы, довольно эффективные в случае подделки данных одним пользователем, оказываются весьма уязвимыми в ситуации когда подделку осуществляет коалиция недобросовестных пользователей (или владелец нескольких копий). В этом случае коалиция может найти расположение уникальной метки в записи путем побитного сравнения файлов и, если метки не выбраны специальным образом, заменить ее на другую, не позволяющую найти даже одного участника коалиции. Более того, такая подмена может ложно указывать на совершенно другого, не входящего в коалицию, легального пользователя. Специальные методы генерации меток, позволяющих бороться с коалициями недобросовестных пользователей, стали называть "цифровыми отпечатками пальцев". Их исследование было начато более двадцати пяти лет назад в работах [138], [139], но затем более десяти лет не было никаких ни публикаций, пока не появилась статья [72], вызвавшая поток исследований.
Коротко говоря, задаче о "поиска пиратов" (или кодов, идентифицирующих родителей) соответствует выпуклая оболочка, а задаче о "цифровых отпечатках пальцев" - расширенная выпуклая оболочка. Несмотря на близость математических постановок этих задач, методы их решения, как и получаемые результаты разнятся довольно сильно. В данном параграфе мы будем исследовать коды, идентифицирующие родителей. Обзор комбинаторных задач, возникающих в этой тематике, см. [142].
Рассмотрим задачу "поиска пиратов" как она была сформулирована в [71], [143]. Некие (медиа)данные (например, фильм) передаются широковещательно сразу М пользователям. Эти данные шифруются, но не только (и не столько) с целью не допустить их чтение нелегальными пользователями, а еще и с тем, чтобы предотвратить возможную передачу (продажу) этих данных легальными пользователями третьей стороне. Для этих целей дилер системы распределяет в начале работы индивидуальные ключи, поставляя г-му пользователю ключ с;. Очевидное решение состоит в том, чтобы зашифровать данные с помощью некоторого вспомогательного ключа (секрета) s, а его передать (вместе с зашифрованными данными) также в зашифрованном виде как z = (гг,..., ZM), где z% = E(s,Ci) - это секрет s, зашифрованный на персональном ключе с, г-го пользователя. Недостаток метода также очевиден - необходимость передавать вместе с данными последовательность длины, пропорциональной числу пользователей М.
В [71] была предложена следующая схема поиска "пиратов", названная одноуровневой. Секрет s "разделяется" на п "теней" si,...,sn , где s\,..., sn_i выбираются случайно, a sn так, чтобы выполнялось равенство Здесь и ниже s, si,...,sn рассматриваются как элементы некоторой конечной абелевой группы из Q элементов. Формула 3.27 задает так называемую пороговую (п, д)-схему с разделением секрета. Она обеспечивает ключевое свойство схем с разделением секрета, а именно, разрешенные множества пользователей могут однозначно восстановить секрет, тогда как неразрешенные множества пользователей не могут извлечь из своих "теней" никакой информации о секрете. Такие схемы разделения секрета называются совершенными. Совершенные пороговые (/с,п)-схемы были открыты в работах [144] и [145], с которых и началась теория схем разделения секрета, см., например, [189].
Далее каждая из теней шифруется с помощью q различных ключей, т.е. формируются Zjtk = E(s;, к) , где к б К{ = Hq, и КІ это множество ключей, используемых для шифрования і -ой тени. По каналу широковещательно передаются собственно данные, зашифрованные на ключе 5, а также последовательность всех zi}k, т.е. дополнительные nq символов. Еще до начала сеанса передачи данных каждый пользователь с получает, втайне от остальных пользователей, свой набор-вектор ключей с = (сі,...,сп) : СІ Є Кг с помощью которого он может расшифровать по одной zhk для каждого г, т.е. получить все S{, затем вычислить s по формуле (3.27) и расшифровать данные.
Рассмотрим попытку коалиции из t или менее недобросовестных пользователей предоставить некоторой третьей стороне возможность получать и дешифровать передаваемую информацию, как если бы эта третья сторона была легальным пользователем. Для этого, как следует из свойства совершенности пороговой схемы разделения секрета, коалиция должна предоставить набор-вектор ключей у — (уі,...,уп) "без пропусков", т.е. для каждого і Є {1,...,п} должен быть предоставлен хотя бы один ключ из множества ключей Кг. Так как каждый пользователь знает только собственный ключ, то вектор у составлен из ключей участников коалиции U, т.е. у І Є U{ = {иг : и = (щ,... ,ип) є U}, для всех і — 1,...,п, или, согласно данному выше определению, коалиция U порождает векторы из выпуклой оболочки (U) и только их. Множество С всех векторов, соответствующих пользователям системы, называется кодом (системы) . Заметим, что код С является д-ичным кодом длины п. Если таблица соответствия пользователю с его вектора ключей с, т.е. код С , считается известной всем пользователям, то схема называется открытой. Дилер системы хочет построить код С таким образом, чтобы при любой стратегии коалиции из не более t участников он мог по у гарантированно определить как минимум одного члена коалиции, т.е. найти хотя бы одного "пирата". Такой код называется (-идентифицирующим. Формальное определение дано ниже.
