Об эффективности случайного кодирования линейными кодами, дуальными к кодам Юстесена, в модели "wire-tap channel"

А. Н. Алексейчук

Размещено на http://www.allbest.ru//

16

Размещено на http://www.allbest.ru//

Об эффективности случайного кодирования линейными кодами, дуальными к кодам Юстесена, в модели «wire-tap channel»

А. Н. Алексейчук

Получены аналитические верхние границы теоретико-информационных и вероятностных показателей стойкости защиты информации, передаваемой по каналу связи с отводом, при случайном кодировании источника сообщений кодом Vm,K, дуальным к (Km, 2(2m - 1)m)-коду Юстесена. Для рассматриваемого класса систем передачи информации со случайным кодированием предложены практически реализуемые алгоритмы случайного кодирования и декодирования сообщений в основном канале. Показано, что случайное кодирование кодом Vm,K обеспечивает сколь угодно высокую при m стойкость защиты информации в отводном канале при асимптотически ненулевой скорости передачи.

Ключевые слова: случайное кодирование линейным кодом, код Юстесена, канал с отводом, совершенная стойкость защиты информации.

Введение

В 1975 г. А. Вайнер [1] предложил теоретико-информационную модель системы передачи информации по каналу связи с отводом (wire-tap channel), включающую в себя формальное описание способа надежной передачи дискретных сообщений законному получателю при наличии отводного канала утечки информации. В наиболее полно изученном частном случае [2-7] указанная модель представляет собой два дискретных канала с общим входом: бесшумный основной канал от источника к законному получателю и отводной двоичный симметричный канал (ДСК) с вероятностью ошибки p, 0 < p < , контролируемый противником. Источник вырабатывает случайные равновероятные двоичные векторы S длины k. Для защиты передаваемых сообщений в отводном канале применяется способ «случайного кодирования источника линейным (n, n - k)-кодом V» [4, 5],при котором для передачи сообщения S используется вектор X длины n, выбираемый случайно и равновероятно в соответствующем S смежном классе векторного пространства Fn = GF(2)n по коду V. Так как основной канал является бесшумным, то законный получатель однозначно восстанавливает по вектору X переданное информационное сообщение. При этом на выходе отводного канала реализуется случайный вектор Y, представляющий собой результат искажения X в ДСК. Основными показателями стойкости защиты информации в рассматриваемой модели являются вероятность p(V) правильного декодирования сообщений оптимальным декодером отводного канала [6] и пропускная способность C(V) расширенного канала со случайным кодированием, образованного последовательным соединением случайного кодера, соответствующего коду V, и отводного канала связи [4]. Цель случайного кодирования состоит в обеспечении требуемой стойкости защиты информации при достаточно высокой скорости передачи ее законному получателю.

Асимптотические свойства систем со случайным кодированием, характеризующие потенциальные возможности описанного способа защиты сообщений, передаваемых по каналу связи с отводом, исследованы в [1, 8, 9]. В [1] впервые установлено существование «асимптотически надежных» линейных кодов, обеспечивающих сколь угодно высокую защищенность информации в отводном канале при скорости передачи, не стремящейся к нулю с ростом длины кодовых слов. Результаты [1] усилены в статье [9], где показано, в частности, что для любого фиксированного положительного (явно зависящего от вероятности искажения символа в ДСК) существует последовательность (n, n - k)-кодов Vn,k со скоростью , обеспечивающих сколь угодно близкую к совершенной стойкость защиты информации в отводе (удовлетворяющих условию C(Vn,k) 0, k ). Отметим, что доказательства основных результатов [1, 8, 9] являются неконструктивными (не содержат алгоритмов построения кодов Vn,k, обладающих указанными выше свойствами).

В [2-4, 7, 10] и ряде других работ были получены точные аналитические оценки параметров p(V), C(V) для различных классов линейных кодов V (фиксированной длины). Однако до последнего времени не было известно ни одного семейства линейных кодов Vn,k, допускающих конструктивное описание и простую реализацию алгоритмов случайного кодирования и декодирования сообщений в основном канале, обеспечивающих сколь угодно близкую к совершенной стойкость защиты информации в отводном канале и имеющих ненулевую при k скорость передачи.

В настоящей статье показано, что одним из классов двоичных линейных кодов, удовлетворяющих перечисленным выше условиям, является семейство кодов, дуальных к кодам Юстесена Jm,K с параметрами (Km, 2(2m - 1)m) [11]. С использованием известного результата об асимптотическом (m ) поведении минимального расстояния кода Jm,K [11] и аналитической оценки пропускной способности расширенного канала системы со случайным кодированием [10] установлена конструктивная верхняя граница скорости передачи информации, при которой достигается сколь угодно близкая к совершенной стойкость защиты сообщений в отводном канале. Получены также верхние границы вероятности правильного декодирования сообщений в отводном канале системы со случайным кодированием кодом, дуальным к коду Jm,K, характеризующие практическую стойкость защиты информации в отводе. Предложены алгоритмы случайного кодирования и декодирования сообщений в основном канале системы со случайным кодированием кодом, дуальным к Jm,K, реализуемые конечными автоматами, имеющими схемную сложность [12], пропорциональную длине используемого кода n = 2(2m - 1)m.

Конструкция линейного кода и алгоритмы реализации случайного кодирования и декодирования сообщений в системе передачи информации по каналу связи с отводом

Пусть R - (N, K)-код Рида-Соломона (РС) над полем GF(q), q = 2m, N = 2m - 1, 1 K N - 1, -- примитивный элемент поля GF(q) и = {1, …, m} -- некоторый базис этого поля над полем F = GF(2). Код Юстесена длины n = 2Nm и размерности k = Km представляет собой множество Jm,K двоичных векторов вида

((y0), (y0); (y1), (y1); …; (yN-1), (N-1yN-1)), (1)

удовлетворяющих условию (y0, …, yN-1) R [11]. (Здесь и далее символ (y) обозначает вектор координат элемента y GF(q) в базисе ). Обозначим через V =

= Vm,K код, дуальный к коду J = Jm,K, и рассмотрим систему передачи информации по каналу связи с отводом, построенную на основе кода V.

Пусть -- базис поля GF(q), дуальный к базису [11], (x) -- вектор координат произвольного элемента x GF(q) в базисе , R - код РС, дуальный к коду R.

Лемма 1. Код V состоит из двоичных векторов вида

((x0), (x0); (x1), (x1); …; (xN-1), (xN-1)), (2)

таких, что

(x0 + x0, x1 + x1, …, N-1xN-1 + xN-1) R. (3)

Доказательство. Обозначим через W совокупность всех векторов вида (2), удовлетворяющих условию (3). В силу дуальности басисов и поля GF(q) скалярное произведение <u, w> произвольных векторов u = ((y0), (y0); …; (yN-1), (N-1yN-1)) J и w = ((x0), (x0); …; (xN-1), (xN-1)) W над полем F равно

<u, v> = = , (4)

где Tr(z) = -- след элемента z GF(q) [11]. На основании условия (3) и соотношения (y0, …, yN-1) R выражение под знаком функции следа в правой части (4) равно нулю.

Итак, для любых u J, w W справедливо равенство <u, v> = 0, откуда следует, что W J = V. Так как коды W и V имеют одинаковую размерность над полем F (равную (2N - K)m), то из последнего соотношения вытекает равенство W = = V, что и требовалось доказать.

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

Пусть GR = (IK, C) -- порождающая матрица кода R, где IK -- единичная матрица порядка K, C -- матрица размера K (N - K) над полем GF(q). Отождествим элементы поля GF(q) с двоичными m-векторами их координат в базисе . Рассмотрим произвольный информационный вектор s = (s0, …, sK1) GF(q)(K).

Алгоритм случайного кодирования сообщения s кодом V состоит в последовательном выполнении двух этапов. На первом этапе генерируется случайный равновероятный вектор t длины N - K над полем GF(q) и вычисляется вектор x = (x0, …, xN-1) GF(q)(N)

x = (tCT + s, t), (5)

где CT -- матрица, транспонированная к С. На втором этапе алгоритма генерируются независимые в совокупности случайные равновероятные элементы 0, 1, …, N-1 поля GF(q) и для каждого вычисляется элемент zi = ii + xi

GF(q). Затем формируется двоичный вектор

z = ((z0), (0); (z1), (1); …; (xN-1), (N-1)) (6)

длины Nm, передаваемый по основному каналу связи.

При декодировании сообщений вида (6) законным получателем информации принятый вектор z разбивается на подвекторы ((zi), (i)), , по которым с использованием соотношений

xi = zi + ii, (7)

определяется вектор x = (x0, …, xN-1) вида (5). Информационное сообщение s вычисляется по формуле

s = xGRT = tCT + x. (8)

Непосредственно из равенств (5)-(8) и утверждения леммы 1 следует, что для любых информационных сообщений s, s GF(q)(K) двоичные векторы z, z вида (6), используемые для передачи s и s соответственно, принадлежат одному смежному классу по коду V тогда и только тогда, когда выполняется равенство s = s. Отсюда в силу равновероятности случайных векторов t и (0, 1, …, N-1) вытекает, что описанные выше алгоритмы являются корректными, то есть реализуют процедуры случайного кодирования и декодирования сообщений по кодовой книге, соответствующей коду V [1]. Используя результаты [12] о сложности арифметических операций в поле GF(q) и кодировании кодов Рида-Соломона, нетрудно убедиться в том, что процедуры вычисления векторов z и s по формулам (5), (6) и (7), (8) соответственно допускают реализацию конечными автоматами, схемная сложность каждого из которых пропорциональна длине n = 2Nm кода V.

Оценки стойкости защиты информации в отводном канале системы передачи со случайным кодированием кодом Vm,K

кодирование линейный информация отводный канал

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

Обозначим pR() = q-K [0, 1] производящую функцию весового спектра (A0, A1, …, AN) кода РС R [11]. Пусть (A0, A1, …, AN) -- весовой спектр дуального кода РС R. Согласно тождеству Мак-Вильямс [11]

pR() =+ , [0, 1]. (9)

Для чисел Ai известны верхние границы [12]

Ai , (10)

A0 = 1, Ai = 0 при Подставляя (10) в (9), с использованием оценки Чернова [11] получим следующее неравенство

pR() + (q - 1)-K exp{- N} (11)

при условии , где E(a, b) = a, b [0, 1].

Теорема 1. Для вероятности p(V) правильного декодирования сообщений в отводном канале системы передачи информации со случайным кодированием кодом V = Vm,K справедливо неравенство

p(V) pR(2), (12)

где = 1 2p, p -- вероятность искажения символа в ДСК. В частности, при K =

= N - 1 вероятность правильного декодирования в отводе

p(Vm,N-1) + (13)

при скорости передачи информации законному получателю =

Доказательство. Из результатов, полученных в [6, 13], вытекает следующее равенство:

p(V) = q-K (14)

где = 1 2p, -- вес Хэмминга вектора u. Обозначим через y = (y0, …, yN-1) произвольный вектор, принадлежащий коду R. На основании (1), (14) имеют место соотношения

p(V) = q-K= q-K

q-K = q-K= pR(),

из которых следует справедливость неравенства (12). Наконец, оценка (13) непосредственно следует из (9), (10), (12). Теорема доказана.

Покажем теперь, что случайное кодирование кодами Vm,K обеспечивает сколь угодно высокую при m защищенность информации в отводном канале при скорости передачи , ограниченной снизу положительной константой (зависящей от вероятности искажения в ДСК).

Предварительно докажем следующее утверждение, сформулированное в [10], содержащее точную верхнюю границу пропускной способности C(G) расширенного канала со случайным кодированием произвольным двоичным линейным кодом G.

Лемма 2. Пусть G - (n, n - k)-код с дуальным расстоянием d. Тогда при выполнении условия < e1, = 1 2p имеет место неравенство

С(G) < (15)

Доказательство. Обозначим G1 = G, G2, …, GM (M = 2k) все различные смежные классы по коду G; положим

Pi = G =

Согласно [4], величина С(G) совпадает с информационной дивергенцией распределения вероятностей (Pi: ) относительно равномерного распределения на множестве смежных классов по коду G

С(G) = k + (16)

Применяя к (16) известное неравенство [14], связывающее информационную дивергенцию с расстоянием по вариации между распределениями вероятностей на конечном множестве, получим оценку

С(G) G(k - log2 G), (17)

справедливую при всех G 1. Убедимся в справедливости следующих неравенств:

(18)

На основании тождества Мак-Вильямс имеем [11]

Pi = (19)

где a Gi, au -- булево скалярное произведение векторов a и u. Непосредственно из (19) и определения числа d вытекает первое неравенство (18). Пусть теперь , a Gi и v G -- фиксированные векторы, удовлетворяющие условию va = 1. В силу (19) и неравенства d, uG справедливы оценки

+ += ,

в силу которых выполняется второе неравенство (18).

Используя (18), находим

G = < (20)

Так как функция f(x) = - xlog2 x монотонно возрастает на интервале (0, e-1), то на основании (17), (20) при выполнении условия < e1 справедливы следующие неравенства:

С(G) Gk - Glog2 G < k - = -

Итак, имеет место соотношение (15), что и требовалось доказать.

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

Теорема 2. Пусть -- фиксированное число, удовлетворяющее условию

0 < < (21)

где (0,) -- единственный корень уравнения - log2 - (1 - )log2 (1 - ) = = ( 0,110), = 1 2p, p -- вероятность искажения символа в ДСК. Тогда при всех достаточно больших натуральных m и

K = = (22)

пропускная способность C(Vm,K) расширенного канала со случайным кодированием кодом Vm,K удовлетворяет неравенству

C(Vm,K) < exp{- cNm}, (23)

где c -- положительная константа, зависящая от p.

В частности, при выполнении (21), (22) и m случайное кодирование кодами Vm,K обеспечивает сколь угодно близкую к совершенной стойкость защиты информации в отводном канале при скорости передачи .

Доказательство. Обозначим через d = dm,K дуальное расстояние кода Vm,K (равное минимальному расстоянию кода Юстесена Jm,K c параметрами n = 2Nm,

k = Km). Покажем, что при выполнении условия теоремы

< - c1n + o(1), m , (24)

где c1 = c1(p) = const > 0 (неравенство (23) следует непосредственно из оценок (15) и (24)).

По теореме Юстесена [11] минимальное расстояние d кода Jm,K удовлетворяет соотношению

(1 - 2) + o(1), m .

Отсюда с использованием (22) получаем, что

= > (1 - 2)log2 -1 - + o(1), m , (25)

и на основании (21) выражение в правой части (25) ограничено снизу положительной константой. Итак, имеет место неравенство (24), что и требовалось доказать.

Ниже в таблице приведен ряд значений функции (p) = , p (0,), определяющей конструктивную верхнюю границу (21) скорости передачи, при которой достигается сколь угодно близкая к совершенной стойкость защиты информации в отводном канале. Для сравнения указаны также значения «секретной пропускной способности» h(p) = - plog2p - (1 - p)log2(1 - p) отводного канала (максимальной скорости, с которой теоретически возможна сколь угодно надежная передача информации законному получателю [1]).

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

Как видно из соотношения (21) и данных, приведенных в таблице, значения (p) достаточно медленно растут с ухудшением качества отводного канала, асимптотически приближаясь к при p .

В заключение отметим, что с помощью рассуждений, аналогичных использованным выше при доказательстве теоремы 2, можно установить «асимптотическую совершенность» [10] произвольной последовательности линейных кодов, дуальных к кодам, имеющим ненулевые при n скорость передачи и отношение минимального расстояния к длине кодового слова. Усилить конструктивную верхнюю границу (21) можно путем уточнения оценки (15) пропускной способности расширенного канала со случайным кодированием линейным кодом или, используя конструкции кодов с большими скоростью передачи и минимальным расстоянием [15].

Литература

Wyner A.D. The Wire-Tap Channel // Bell System Techn. J. -- 1975. -- Vol. 54, N 8. -- P. 1355-1388.

Коржик В.И., Яковлев В.А. Неасимптотические оценки кодового зашумления одного канала // Пробл. передачи информации. -- 1981. -- Т. 17. -- В. 4. -- С. 11-18.

Яковлев В.А. Границы для оценки неопределенности в системе передачи со случайным кодированием // Радиотехника. -- 1996. -- № 12. -- С. 58-63.

Коржик В.И., Яковлев В.А. Пропускная способность канала связи с внутренним случайным кодированием // Пробл. передачи информации. -- 1992. -- Т. 28. -- В. 4. -- С. 24-34.

Горицкий В.М. К оценке эффективности концепции WTC кодами Хэмминга для решения задач защиты заранее известных последовательностей // Защита информации: Сб. науч. тр. Национального авиационного ун-та. -- К.: КМУГА, 1999. -- С. 73-75.

Иванов В.А. О методе случайного кодирования // Дискретная математика. -- 1999. -- Т. 11. -- Вып. 3. -- С. 99-108.

Алексейчук А.Н. Оценки эффективности кодовой защиты дискретных сообщений с использованием линейных кодов с большим дуальным расстоянием // Реєстрація, зберігання і оброб. даних. -- 2001. -- Т. 3, № 2. -- С. 99-106.

Csiszar I., Korner J. Broadcast Channels with Confidential Messages // IEEE Trans. Inform. Theory. -- 1978. -- Vol. 24, N 3. -- P. 339-348.

Чисар И. Почти независимость случайных величин и пропускная способность криптостойкого канала // Пробл. передачи информации. -- 1996. -- Т. 32. -- Вып. 1. -- С. 48-57.

Алексейчук А.Н. Условия «практической эффективности» и «асимптотической совершенности» кодовой защиты случайных равновероятных сообщений // Защита информации: Сб. науч. тр. -- К.: НАУ, 2002. -- Вып. 2(9). -- С. 46-54.

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

Блох Э.Л., Зяблов В.В. Обобщенные каскадные коды. -- М.: Связь, 1976. -- 240 с.

Алексейчук А.Н. О вероятности безошибочного декодирования в отводном канале с аддитивным шумом, распределенным на конечной абелевой группе // Защита информации: Сб. науч. тр. Национального авиационного ун-та. -- К.: КМУГА, 2001. -- С. 9-16.

Чисар И., Кернер Я. Теория информации. Теоремы кодирования для дискретных систем без памяти: Пер. с англ. -- М.: Мир, 1985. -- 397 с.

Sugiyama Y., Kasahara M., Hirasawa S., Namekawa T. A new class of asymptotically good codes beyond the Zyablov bound // IEEE Trans. Inform. Theory. -- 1978. -- Vol. 24, N 2. --

Размещено на Allbest.ru