О генерической сложности некоторых проблем криптографии

МАТЕМАТИКА

Вестн. Ом. ун-та. 2014. № 4. С. 23-27.

УДК 510.52

А.Н. Рыбалов

О ГЕНЕРИЧЕСКОЙ СЛОЖНОСТИ НЕКОТОРЫХ ПРОБЛЕМ КРИПТОГРАФИИ*

Генерический подход к алгоритмическим проблемам был предложен в 2003 г. А.Г. Мясниковым, И. Каповичем, П. Шуппом и В. Шпильрайном. В рамках этого подхода алгоритмическая проблема рассматривается не для всего множества входов (сложность в худшем случае), а для множества «почти всех» входов. Термин «почти все входы» уточняется при помощи введения естественной меры на множестве входных данных. В настоящей статье изучается генерическая сложность следующих алгоритмических проблем: проблемы дискретного логарифма, проблемы извлечения квадратного корня в группах вычетов и поисковой проблемы изоморфизма графов. Эти проблемы имеют приложения в современной криптографии. Доказывается, что при условии трудноразрешимости в худшем случае эти проблемы остаются трудноразрешимыми и в генерическом случае.

Ключевые слова: генерическая сложность, проблема дискретного логарифма, проблема изоморфизма графов, группы вычетов.

Введение

В работе [1] была развита теория генерической сложности вычислений. В рамках этого подхода алгоритмическая проблема рассматривается не на всем множестве входов, а на некотором подмножестве «почти всех» входов. Такие входы образуют так называемое генерическое множество. Понятие «почти все» формализуется введением естественной меры на множестве входных данных. С точки зрения практики алгоритмы, решающие быстро проблему на генерическом множестве, так же хороши, как и быстрые алгоритмы для всех входов. Классическим примером такого алгоритма является симплекс-метод - он за полиномиальное время решает задачу линейного программирования для большинства входных данных, но имеет экспоненциальную сложность в худшем случае. Более того, может так оказаться, что проблема трудноразрешима или вообще неразрешима в классическом смысле, но легкоразрешима на генерическом множестве. В работах [1; 2] было доказано, что таким поведением обладают многие алгоритмические проблемы алгебры, а в работе [3] было построено генерическое множество, на котором разрешима классическая проблема остановки для машин Тьюринга с лентой, бесконечной в одном направлении. Для многих классических NP-полных проблем существуют полиномиальные генерические алгоритмы (см. работу [4]).

С точки зрения современной криптографии интересны такие алгоритмические проблемы, которые, являясь (гипотетически) трудными в классическом смысле, остаются трудными и в генерическом смысле, т. е. для «почти всех» входов. Это объясняется тем, что при случайной генерации ключей в криптографическом алгоритме происходит генерация входа некоторой трудной алгоритмической проблемы, лежащей в основе алгоритма. Если проблема будет генерически легкоразрешимой, то для «почти всех» таких входов ее можно будет быстро решить и ключи почти всегда будут нестойкими. Поэтому проблема должна быть генерически трудной.

В данной статье изучается генерическая сложность следующих классических проблем криптографии: проблемы дискретного логарифма в полях GF(p) , где p - простое; проблемы извлечения квадратного корня в

* Работа выполнена за счет гранта Российского научного фонда (проект № 14-11-00085).

© А.Н. Рыбалов, 2014

24

А.Н. Рыбалов

группах вычетов

Z/

поисковой пробле-

/(«)’

мы изоморфизма графов. До сих пор не известно полиномиальных алгоритмов для их решения. Более того, на предположении об их трудноразрешимости основаны многие криптографические алгоритмы (см. [5]). В данной статье доказывается, что эти проблемы неразрешимы за полиномиальное время на любых полиномиальных генерических множествах входов при условии отсутствия полиномиальных вероятностных алгоритмов для их решения в худшем случае. Более того, существует правдоподобная гипотеза о том, что любой полиномиальный вероятностный алгоритм можно эффективно дерандомизировать, т. е. построить полиномиальный детерминированный алгоритм, решающий ту же задачу. Хотя это пока еще не доказано, имеются серьезные результаты в пользу него (см. [6]). При доказательстве данного результата будут использованы методы, развитые в статьях [7; 8].

Генерическая вычислимость и сложность

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

р (S) _ S п 11 Pn (S) _ и.. i ,

где In - множество всех входов проблемы размера n. В данной статье мы будем иметь дело со множествами натуральных чисел, представленными двоичными строками, и под размером числа будем понимать длину его двоичной записи. Если случайно и равновероятно генерировать входы размера n, то вероятность попасть в S равна pn

KS) = limp,(S).

n——^

Если предела не существует, то считаем, что асимптотическая плотность не определена.

Множество входов S с I называется генерическим, если p(S) = 1, и пренебрежи-мым, если p(S) = 0 . Непосредственно из определения следует, что S является генерическим тогда и только тогда, когда I \ S пренебрежимо. Понятие генерического

множества формализует интуитивное понятие множества «почти всех» входов в том смысле, что при увеличении размера входа вероятность того, что случайно сгенерированный вход попадет в генерическое множество, стремится к 1.

Алгоритмическая проблема S с I гене-рически полиномиально разрешима, если существует множество G с I такое, что:

1. G - генерическое.

2. G - разрешимое за полиномиальное время.

3. S п G - разрешимое за полиномиальное время.

Генерический алгоритм, решающий проблему S , работает следующим образом. Сначала определяет, принадлежит ли вход генерическому множеству. Если да, то проверяет принадлежность входа S . Если нет, то отвечает «НЕ ЗНАЮ». Такой алгоритм правильно решает проблему S на «почти всех» входах.

Проблема дискретного логарифма

Напомним, что проблема дискретного логарифма DL состоит в следующем:

ВХОД: ненулевые натуральные числа

a, g, p , где p - простое число, a, g < p и g -

первообразный элемент в поле GF(р) .

ВЫХОД: натуральное число x такое, что gx = a в поле GF(р).

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

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

П = {рх,р2,...,Pn,...} , удовлетворяющую условию: 2n < рп < 2n+1 для любого n . Это можно сделать благодаря известному постулату Бертрана, доказанному П.Л. Чебышевым. Будем называть такую последовательность экспоненциальной. Теперь определим алгоритмическую проблему DL(n) следующим образом:

ВХОД: ненулевые натуральные числа

a, g, р , где р ед, a, g < р и g - первообразный элемент в поле GF(р) .

ВЫХОД: натуральное число x такое, что gx = a в поле GF(р) .

Заметим, что входами размера n в проблеме DL(n) являются всевозможные

тройки вида

оставить по одному представителю GF

О генерической сложности некоторых проблем криптографии

25

с числом pn из интервала |^2И ,2K+1 J . Тем не

менее можно доказать, что среди проблем DL(n) существуют столь же трудные, как и оригинальная DL .

Лемма 1. Если не существует полиномиального алгоритма для проблемы DL , то найдется такая экспоненциальная последовательность п, что и для проблемы DL(n) не существует полиномиального алгоритма.

Доказательство. Пусть P1,P2,... - все

полиномиальные алгоритмы. Из предположения о том, что не существует полиномиального алгоритма для проблемы DL , следует, что для любого алгоритма Pn существует бесконечно много полей GF(p) , в которых он не может решить DL . Из этого следует, что можно выбрать последовательность П = {p1,p2,...,pn,...} так, чтобы алгоритм Pn не решал DL в поле GF (pn) и для любого n выполнялось бы pn+1 > 2pn . Последовательность П можно расширить до экспоненциальной последовательности П, добавив, где нужно, новые члены. Заметим теперь, что DL(n) и будет той проблемой, для которой не существует полиномиального алгоритма.

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

Доказательство. Допустим, существует генерический полиномиальный алгоритм A , разрешающий проблему DL(n) на некотором полиномиальном генерическом множестве G . Построим вероятностный полиномиальный алгоритм B , решающий DL(n) на всем множестве входов. Алгоритм B на входе (a, gn, pn) будет работать следующим образом:

1. Проверяет, принадлежит ли (a, gn, pn ) множеству G . Это делается за полиномиальное время, так как множество G разрешимо за полиномиальное время. Если (a, gn, pn) е G, то с помощью алгоритма A

находит дискретный логарифм. Если нет, переходит к шагу 2.

2. Генерирует равномерно случайное число 0 < y < pn -1. Вычисляет a' = agny в GF (pn).

3. Проверяет, принадлежит ли новая тройка (a', gn, pn ) множеству G .

4. Если (a' , gn, pn) е G , то с помощью алгоритма A находит z такое, что gz = a' или gnz = agy , откуда X = (z - y)mod(p -1) -

дискретный логарифм для исходной задачи

(a, gn, pn).

5. Если (a' , gn, pn ) £ G , выдает ответ 0. Заметим, что алгоритм может выдать неправильный ответ только на шаге 5. Докажем, что вероятность этого меньше %. Нужно показать, что (a' , gn, pn) е G с вероятностью больше %. Заметим, что a' = agny при 0 < y < pn -1 пробегает все ненулевые элементы поля GF(pn) . А так как G генери-

ческое, то вероятность того, что

(a' , gn, pn) е G , будет стремиться к 1 при увеличении n . Это означает, что полиномиальный вероятностный алгоритм B корректно решает проблему DL(n) на всем

множестве входов. Теорема доказана.

Проблема извлечения квадратного корня в группах вычетов

Пусть Z/

- мультипликативная груп-

па вычетов по модулю m. Проблема извле-

чения квадратного корня в

SR

состо-

ит в следующем:

ВХОД: пара натуральных чисел

такая, что a е

ВЫХОД: X е у

такой, что X2 = a

в

, если такой X существует; 0 - иначе.

Заметим, что квадратных корней может быть несколько, в проблеме достаточно найти какой-либо один из них. Опять под размером входа понимается число бит в двоичной записи числа m. Так же, как и для проблемы дискретного логарифма, для этой проблемы не известно полиномиальных алгоритмов даже для частного случая, когда m = pq , где p, q - различные простые чис-

ла. Существуют криптосистемы, основанные на проблеме извлечения квадратного корня (см. [5]).

Для стратификации проблемы SR рассмотрим последовательности rj = {m1, m2,..., mn,...}

натуральных чисел, являющихся произведением двух различных простых чисел и удо-

2n ^ '~\n+1

— mn < 2 для

любого n. Существование таких последовательностей опять следует из постулата Бертрана. Далее определим проблему SR(rf) :

ВХОД: пара натуральных чисел (a, mn) такая, что aе ^^m ).

26

А.Н. Рыбалов

ВЫХОД:

хе Z

Ч)

такой, что

х2 = a

в

если такой х существует; 0 - иначе.

Аналогично лемме 1 доказывается лемма 2.

Лемма 2. Если не существует полиномиального алгоритма для проблемы SR , то найдется такая экспоненциальная последовательность п , что и для проблемы SR

не существует полиномиального алгоритма. Теорема 2. Если проблема SR(n) гене-

рически полиномиально разрешима, то существует полиномиальный вероятностный алгоритм, решающий SR(n) для всех вхо-

дов.

Доказательство. Доказательство аналогично доказательству теоремы 1, единственное различие заключается в том, что, для того чтобы попасть в генерическое множество, нужно из входа (a, mn) получить вход

(ay2, mn), где у е ^щт ) - случайно и равномерно сгенерированный элемент. То, что попадание будет происходить с вероятностью, близкой к 1, следует из двух фактов:

1 В группе ) , где тп = pq и Р, q -

различные простые числа, ровно % элемен-

2

тов являются квадратами. Поэтому ay принимает % значений в ^щт

2. С ростом n более % элементов попадают в генерическое множе-

ство.

Теперь если a = х2 и ay2 = z2, то х = zy-. Если же из ay2 не извлекается квадратный корень, то и из a он тоже не будет извлекаться.

Поисковая проблема изоморфизма графов

Напомним, что два графа G1 и G2 называются изоморфными, если существует биекция п: V(G1) ^ V(G2), сохраняющая свойство «быть соединенными ребром», т. е. такая, что для любых вершин v1, v2 первого графа выполнено: v1, v2 соединены ребром

в G1 тогда и только тогда, когда n(v1),n(v2) соединены ребром в G2. Фактически биекция п - это некоторая перестановка на множестве вершин {1,...,n} . Поисковая проблема изоморфизма графов SGI состоит в следующем:

ВХОД: G1, G2 - изоморфные графы.

ВЫХОД: биекция п: V(G1) ^ V(G2),

осуществляющая изоморфизм.

Сами графы представляются обычно матрицами смежности (n X n - матрица, где n - число вершин; на месте (i, j) стоит 1, если вершина i соединяется с вершиной j

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

Для стратификации проблемы будем рассматривать последовательности графов вида y = {G1,G2,...,Gn,...} , где граф Gn имеет n вершин. Определим проблему SGI (у) следующим образом:

ВХОД: (G, Gn) - изоморфные графы.

ВЫХОД: биекция п: V(G) ^ V(Gn) ,

осуществляющая изоморфизм.

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

Лемма 3. Если не существует полиномиального алгоритма для проблемы SGI , то найдется такая последовательность графов Y , что и для проблемы SGI (у) не существует полиномиального алгоритма.

Теорема 3. Если проблема SGI (у) гене-рически полиномиально разрешима, то существует полиномиальный вероятностный алгоритм, решающий SGI(у) для всех входов.

Доказательство. Идея доказательства такая же, как и в доказательстве теоремы 1: в предположении существования полиномиального алгоритма, решающего проблему SGI(у) на генерическом множестве входов, строится вероятностный алгоритм, решающий ее для всех входов. Поясним, как происходит перенос входа (G, Gn) , который не принадлежит генерическому множеству в это множество. Для этого генерируем случайную биекцию (перестановку) <р на вершинах {1,..., n} и действуем ею на граф G , получаем граф G' = ф^) . Так как любой граф, изоморфный G , можно получить таким образом, то с вероятностью больше % пара (G', Gn) попадет в генерическое множество. Там мы эффективно решаем проблему и находим изоморфизм Т между

G' и Gn, т. е. t(G') = Gn или T(p(G)) = Gn, отсюда изоморфизм между G и Gn есть п = тф - произведение соответствующих перестановок.

О генерической сложности некоторых проблем криптографии

27

ЛИТЕРАТУРА

[1] Karpovich I., Myasnikov A. G., Schupp P., Shpil-rain V. Generic-case complexity, decision problems in group theory and random walks // Journal of Algebra. 2003. № 264. № 2. P. 665-694.

[2] Kapovich I., Myasnikov A, Schupp P., Shpil-rain V. Average-case complexity for the word and membership problems in group theory // Advances in Mathematics. 2005. № 190. P. 343-359.

[3] Hamkins J. D., Miasnikov A. The halting problem is decidable on a set of asymptotic probability one // Notre Dame Journal of Formal Logic. 2006. Vol. 47. № 4. P. 515-524.

[4] Gilman R., Miasnikov A. G., Myasnikov A. D., Ushakov A. Report on generic case complexity //

Herald of Omsk University. Special Issue. 2007. P. 103-110.

[5] Мао В. Современная криптография: теория и практика. М. : Вильямс, 2005.

[6] Impagliazzo R., Wigderson A. P=BPP unless E has Subexponential Circuits: Derandomizing the XOR Lemma // Proceedings of the 29th STOC. 1997. P. 220-229.

[7] Myasnikov A, Rybalov A. Generic complexity of undecidable problems // Journal of Symbolic Logic. 2008. Vol. 73. № 2. P. 656-673.

[8] Rybalov A. Generic Complexity of Presburger Arithmetic // Theory of Computing Systems. 2010. Vol. 46. № 1. P. 2-8.