On the generic complexity of the decoding problem for linear codes.pdf Введение Криптосистема Мак-Эллиса [1] является одной из первых криптосистем с открытым ключом. В отличие от популярных криптосистем с открытым ключом, использующих теоретико-числовые и алгебраические конструкции [2], система Мак-Эллиса основана на теории кодов, исправляющих ошибки. В этой области были найдены эффективные семейства методов преобразования и восстановления информационных блоков - так называемые коды, которые позволяют исправлять ошибки, возникающие при передаче этих блоков по каналам связи. Наиболее известные коды - это коды Рида - Маллера, Рида - Соломона, Боуза - Чоудхури - Хоквингема, Гоппы и др. Для этих кодов известны эффективные алгоритмы кодирования и декодирования [3]. Идея, лежащая в основе работы криптосистемы Мак-Эллиса, состоит в том, что «хороший» код, для которого известны эффективные алгоритмы декодирования, некоторым образом «маскируется» под более общий код - линейный. Для линейных кодов есть только эффективные алгоритмы кодирования, но неизвестно эффективных алгоритмов декодирования. Более того, доказано [4], что проблема их декодирования является NP-полной, то есть, при условии P = NP, таких эффективных алгоритмов не существует. Криптостойкость системы Мак-Эллиса как раз и основана на трудности проблемы декодирования линейных кодов. В [5] развита теория генерической сложности вычислений. В рамках этого подхода алгоритмическая проблема рассматривается не на всём множестве входов, а на некотором подмножестве «почти всех» входов. Такие входы образуют так называемое генерическое множество. Понятие «почти все» формализуется введением естественной меры на множестве входных данных. С точки зрения современной криптографии интересны такие алгоритмические проблемы, которые, являясь (гипотетически) трудными в классическом смысле, остаются трудными и в генерическом смысле, т. е. для почти всех входов. Это объясняется тем, что при случайной генерации ключей в криптографическом алгоритме происходит генерация входа некоторой трудной алгоритмической проблемы, лежащей в основе алгоритма. Если проблема является генерически легкоразрешимой, то для почти всех таких входов её можно быстро решить и ключи почти всегда будут нестойкими. Поэтому проблема должна быть генерически трудной. В работе доказывается, что естественная подпроблема проблемы декодирования линейных кодов над конечными полями GF(p) генерически неразрешима за полиномиальное время при условии отсутствия полиномиального вероятностного алгоритма для её решения в худшем случае. Существует правдоподобная гипотеза о том, что любой полиномиальный вероятностный алгоритм можно эффективно дерандомизиро-вать, т. е. построить полиномиальный детерминированный алгоритм, решающий ту же задачу. Хотя это пока не доказано, имеются серьезные результаты в пользу этого [6]. 1. Генерические алгоритмы Пусть I есть множество всех входов некоторой алгоритмической проблемы и In - множество всех входов размера n. Для подмножества S С I определим последовательность |S n In| 1 _ _ Pn(S) = |М , n =1, 2, 3,... Заметим, что pn(S) -это вероятность попасть в S при случайной и равновероятной генерации входов из In. Асимптотической плотностью S назовём предел (если он существует) p(S) = lim pn(S). n-^^o Множество S называется генерическим, если p(S) = 1, и пренебрежимым, если p(S) = 0. Очевидно, что S генерическое тогда и только тогда, когда его дополнение I \\ S пренебрежимо. Алгоритм A с множеством входов I и множеством выходов J U {?} (? ^ J) называется генерическим, если 1) A останавливается на всех входах из I; 2) множество {x Е I : A(x) =?} пренебрежимо. Генерический алгоритм A вычисляет функцию f : I ^ J, если для любого x Е I, такого, что A(x) =?, имеет место A(x) = f (x). Ситуация A(x) =? означает, что A не может вычислить функцию f на аргументе x. Условие 2 гарантирует, что A корректно вычисляет f на почти всех входах (входах из генерического множества). 2. Проблема декодирования линейных кодов Пусть G - порождающая k х n-матрица линейного (n, к)-кода над конечным полем GF(q), исправляющего t ошибок. Проблема декодирования данного линейного кода состоит в вычислении функции decG : Ig ^ GF(q)k, где Ig -это множество векторов y Е GF(q)n, таких, что y = xG + e, где x Е GF(q)k, а e Е GF(q)n такой, что его вес Хэмминга (число ненулевых компонент) w(e) ^ t. Обозначим также через IG,e множество векторов y Е GF(q)n, таких, что y = xG + e, где x Е GF(q)k. Сама функция decG определяется следующим образом: decG(y) = x, если y = xG + e, x Е GF(q)k, u(e) ^ t. Под размером входа понимается размерность вектора y, то есть кодовая длина n. oo Пусть GF(q)* = U GF(q)k, а I есть множество пар (G,Ig) по всем порождающим k= 1 матрицам линейных кодов G. Теперь определим проблему декодирования линейных кодов как проблему вычисления функции dec : I ^ GF(q)* так, что dec(G, IG) = decG. В настоящее время неизвестно полиномиальных алгоритмов (даже вероятностных) для вычисления функции dec. Более того, доказано [4], что проблема вычисления этой функции является NP-трудной, то есть, при условии P = NP, таких эффективных алгоритмов не существует. Для изучения генерической сложности этой проблемы необходимо провести некоторую стратификацию на множестве входов. Рассмотрим любую бесконечную последовательность пар порождающих матриц линейных кодов и векторов ошибок над GF(q) Y = {(G1,e1), (G2,e2),..., (Gn,e,n),...}, таких, что для любого n имеет место: 1) число столбцов матрицы Gn равно n; 2) размер вектора en равен n; 3) u(en) не превосходит числа ошибок, которые код с матрицей Gn может исправлять. Определим функцию decY как ограничение функции dec на множество U IGn,en. (Gn,en)€ Y Очевидно, что проблема вычисления decY является подпроблемой вычисления dec. Следующая лемма показывает, что некоторые такие подпроблемы так же трудны, как и оригинальная проблема. Лемма 1. Если не существует полиномиального вероятностного алгоритма для вычисления dec, то найдётся такая последовательность пар порождающих матриц линейных кодов и векторов ошибок y , что и для вычисления decY нет полиномиального вероятностного алгоритма. Доказательство. Пусть P1,P2,... - все полиномиальные вероятностные алгоритмы. Из предположения о том, что не существует полиномиального вероятностного алгоритма для вычисления dec, следует, что для любого алгоритма Pn существует бесконечно много пар (G, e), для которых он не может вычислить dec. Из этого следует, что можно выбрать последовательность 7' = {(G1, e1), (G2, e2),..., (Gn, en),...} так, чтобы алгоритм Pn не вычислял dec для (Gn, en) и чтобы число столбцов матриц в этой последовательности возрастало. В последовательность 7' можно добавить пары так, чтобы для каждого n там была матрица с числом столбцов n - для любого n существует линейный код с повторениями длины n. Получится нужная последовательность 7, такая, что для вычисления функции decY не существует полиномиального алгоритма. ■ 3. Основной результат Следующий результат говорит о том, что проблема декодирования линейных кодов остаётся вычислительно трудной и в генерическом случае при условии её труднораз-решимости в худшем случае. Теорема 1. Пусть 7 - любая последовательность пар порождающих матриц линейных кодов и векторов ошибок. Если существует полиномиальный генерический алгоритм, вычисляющий функцию decY, то существует полиномиальный вероятностный алгоритм, вычисляющий decY для всех входов. Доказательство. Пусть существует полиномиальный генерический алгоритм A, вычисляющий функцию decY. Построим вероятностный полиномиальный алгоритм B, вычисляющий decY на всём множестве входов. Зафиксируем размер n. Напомним, что множество входов Ic„,e„ размера n есть множество векторов y Е GF(q)n, таких, что y = xG + en, где x пробегает всё множество GF(q)k. Алгоритм B на входе y работает следующим образом: 1) Генерирует случайно и равномерно z Е GF(q)k. 2) Вычисляет y' = y + zGn. 3) Запускает алгоритм A на y'. 4) Если A(y') =?, то выдаёт 0. 5) Если A(y') = x', то x' = x + z. Выдаёт ответ x = x' - z для исходной задачи y. Заметим, что алгоритм B может выдать неправильный ответ только на шаге 4. Докажем, что вероятность этого меньше 1/2. Действительно, множество {y' = y + zGn : z Е GF(q)k} совпадает с множеством Icn,en всех входов размера n. Но алгоритм A генерический, поэтому доля тех входов y', на которых он выдаёт неопределённый ответ, стремится к нулю с ростом n и с некоторого момента становится меньше 1/2. ■ Непосредственным следствием теоремы 1 и леммы 1 является следующее утверждение. Теорема 2. Если для вычисления функции dec не существует полиномиального вероятностного алгоритма, то существует последовательность пар порождающих матриц линейных кодов и векторов ошибок 7, такая, что для вычисления функции decY не существует генерического полиномиального алгоритма.

Скачать электронную версию публикации