Обобщенные спектры некоторых линейных кодов

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

Проиллюстрируем связь между обобщенным кодовым расстоянием линейного кода, изучаемой в диссертации, и проблемой передачи сообщений по каналу с подслушиванием типа II, которую изучали Озаров и Вайнер [1].

Рассмотрим бесшумный канал связи, по которому передаются п-мерные двоичные векторы. Канал подслушивает злоумышленник, который по своему выбору может выбрать любые я координат и получить их значения в переданном векторе. Созданный таким образом злоумышленником побочный канал обычно называют подслушивающим каналом, а бесшумный канал в этой ситуации — каналом с подслушиванием типа II [1]. Отправитель стремится закодировать сообщения так, чтобы минимизировать количество информации о передаваемом сообщении в подслушивающем канале. Злоумышленник в свою очередь стремится к противоположной цели: выбрать 8 координат так, чтобы получить наибольшую информацию о передаваемом векторе.

Мы рассматриваем только один естественный класс кодировок сообщений, а именно, мы полагаем, что сообщения кодируются с помощью множества, которые представляют собой смежные классы по некоторому fc-мерному линейному подпространству С гг-мерного пространства F2n над конечным полем F2 ([п, fcj-коду С). Для того, чтобы передать сообщение, закодированное смежным классом х + С, х Е Fg, отправитель выбирает в нем случайный элемент v + х, v Er С, и посылает его получателю по бесшумному каналу связи.

В этом случае, как легко видеть [1], злоумышленник не получит о сообщении никакой информации, если s < d (С-1), где d (U) — кодовое расстояние линейного кода U и С1 — код, дуальный к С. Это следует из того, что при любом х в множестве векторов х + С (смежном классе) на любых s позициях одинаково часто появляются все s-ки, ибо любые s столбиков порождающей матрицы кода С линейно независимы.

Говоря более точно, злоумышленник получит s — dim Cg бит информации о сообщении из наблюдаемого множества позиций S = {zi,., г3}, где Cs — проекция кода С на множество позиций S. Пусть dim Cs = s — j. Как легко понять, в этом случае в пространстве С найдется j линейно независимых векторов, у которых на позициях из множества S стоят нули. Другими словами, в пространстве С есть j-мерное подпространство, у векторов которого позиции из S тождественно равны нулю.

Верно и обратное. Если у некоторого j-мерного подпространства пространства С позиции из S тождественно равны нулю, то злоумышленник может выбрать их для наблюдения и получить j бит информации.

Таким образом, одна из задач отправителя состоит в построении линейных кодов, у которых для любого 5, |5| = 5, размерность dim Cs была бы возможно большей. Более комбинаторный подход к решению этой и других подобных задач был предложен Вэем в работе [2]. Это вызвало новый интерес к понятию минимальных весов носителя, введенному ранее в работе [3] в другом контексте и с другой целью. Подход Вэя опирается на понятия носителя кода и обобщенного веса Хэмминга. К их определению мы и переходим.

Пусть С — линейный [п, к]-код. Носителем x (D) подкода D называется множество координат, не тождественно равных нулю на D. Мощность w (D) носителя x (D) называется весом подкода D (или его эффективной длиной), r-м обобщенным весом Хэмминга линейного [п, /г]-кода С называется следующее число: dr = dr© = mm{w (D)D — [п, г]-подкод кода С} .

Набор чисел {d, (?2,., ?4} называется весовой иерархией кода С.

Озаров и Вайнер в [1] предложили следующую схему решения. Рассматриваются смежные классы по С1″, в соответствии с к информационными символами выбирается один из смежных классов (их всего qk) — в этом смежном классе случайным образом выбирается слово, которое и передается по каналу. Другими словами, рассматривается произвольное дополнение С' кода С1 такое, что С±фС' = F™. Здесь dim С' = к, и кодирование состоит в том, что к слову из С' прибавляется случайный элемент из CL. Злоумышленник имеет полную информацию о кодах С1 и С', но не знает процедуру случайного выбора.

Рассмотрим координатное пространство F^ и проекцию F™ —" Fqпри подслушивании передаваемого слова злоумышленник знает его образ при этой проекции. Пусть и C’s — образы соответственно С-1 и С' при этой проекции. Информацией Inf^), полученной при подслушивании символов на позициях S, естественно считать размерность факторпространства C’s/(C'sf)Cg)] тогда.

Inf (5) = dimCg/(C'sПCg) = dimC’s — dim (Qn^).

Назовем неопределенностью при подслушивании s символов величину.

As = min{& — Inf (5) ||5| = s}. Оказывается, что ¿-4-д8 < s < dk-Aa+iДругими словами,.

As = к — г при dr < s < dr+.

Поскольку скачок неопределенности при передаче сообщений как элементов смежных классов по С1 происходит в точности в точках s = dr©, то весовая иерархия кода С полностью определяет его поведение при использовании его как криптографического в канале с подслушиванием типа II.

Значительное число работ посвящено нахождению весовых иерархий известных кодов. В [2] вычислены весовые иерархии двоичных кода Хэмминга, кода Голея и кодов Рида-Маллера всех порядков. В [4] вычислены первые и последние несколько обобщенных весов Хэмминга для двоичного примитивного кода БЧХ с минимальным расстоянием 2т~г — 1. В [5] вычислена иерархия весов для кодов на многомерных квадриках. В [6] вычислена весовая иерархия для алгебро-геометрических кодов по поверхностям Дель Пеццо. В [7] даются некоторые эффективные алгоритмы вычисления весовой иерархии для циклических кодов. В [8] и [9] обсуждаются обобщенные веса Хэмминга g-ичных кодов Рида-Маллера. В [10], [11] и [12] даются некоторые границы и соотношения для обобщенных весов Хэмминга линейного кода. В [13] вычислен ??2 = 8 для двоичного кода БЧХ длины 2 т — 1, исправляющего две ошибки.

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

Исследование обобщенных спектров некоторых линейных кодов и составляет цель данной диссертации.

Пусть.

Nj (r, С) = {DD — [п, rj-подкод кода С такой, что w (D) — j}, j = l,., n.

Назовем набор чисел N (r, С) = (Ni (r, С),., Nn (r, С)) r-ым обобщенным спектром кода С, или, кратко, r-спектром кода С, где г = l,., dimC. Отметим, что 1-спектр совпадает с традиционным спектром весов Хэмминга (без элемента с индексом 0) кода С. г-й обобщенный вес Хэмминга ¿-г является индексом первого отличного от нуля элемента г-спектра. В работе [14] принято несколько отличное определение обобщенного спектра. Некоторые коды имеют предельно простую весовую структуру. К таким кодам относятся код, дуальный к коду Хэмминга, и код Рида-Маллера первого порядка. Обобщенные спектры перечисленных кодов находятся прямым образом. Но для большинства линейных кодов вычислить элементы обобщенного спектра очень сложно. Даже для тех кодов, весовые спектры которых имеют относительно простую структуру, например, кода, дуального к коду БЧХ, исправляющему две ошибки, или кода Рида-Маллера второго порядка, вычисление элементов 2-спектра уже сводится к сложной алгебраической задаче. В работе [5] вычислены г-спектры кодов, ассоциированных с неособой квадрикой.

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

Полученные в диссертации результаты (вычисление обобщенных спектров кодов) также могут быть представлены и как расчет числа различных множеств позиций 5, |5| = в, которые позволяют злоумышленнику в канале с подслушиванием типа II получить 3 битов информации в передаваемом сообщении при использовании отправителем некоторых классических линейных кодов, в том числе кодов БЧХ и кодов Рида-Маллера.

Диссертация состоит из введения, трех глав, заключения и литературы.

Заключение

.

В диссертации исследованы обобщенные спектры некоторых линейных кодов. Получены следующие основные результаты.

1) Установлено линейное соотношение между спектром /^-наборов линейного кода и спектром^{-наборов} дуального кода для всех к.

2) Вычислены следующие спектры: г-спектр двоичного кода Хэммингаг-спектр двоичного кода Рида-Маллера первого порядка- 1-спектр кода, дуального к троичному коду БЧХ длины Зт — 1, исправляющего две ошибки, для которого 1, а, а2 являются корнями порождающего многочлена, где, а — примитивный элемент поля и первообразный корень степени п из единицы- 2-спектр кода, дуального к двоичному коду БЧХ (в узком смысле) длины 2 т — 1, исправляющему две ошибки, когда т нечетно.

3) Получены асимптотические выражения элементов следующих спектров: 1-спектра троичного кода БЧХ длины Зт — 1 с конструктивным расстоянием 6, когда длина кода стремится к бесконечности-^{-спектра} двоичного кода БЧХ длины 2Ш — 1, исправляющего I ошибок, когда длина кода стремится к бесконечности.

4) Разработан метод вычисления элементов спектра 2-наборов кода Рида-Маллера второго порядка, индексы которых лежат в диапазоне [|п, |), а также суммы каждой пары элементов, расположенных симметрично относительно §-п.