О генерической сложности проблемы дискретного логарифма | ПДМ. 2016. № 3(33). DOI: 10.17223/20710410/33/8

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

Генерический подход к алгоритмическим проблемам предложен А. Мясниковым, И. Каповичем, П. Шуппом и В. Шпильрайном в 2003 г. В рамках этого подхода рассматривается поведение алгоритмов на множествах почти всех входов. Изучается генерическая сложность классической проблемы дискретного логарифма в полях GF(p), где p - простое. Доказывается, что её естественная подпробле-ма генерически трудноразрешима (то есть трудна для почти всех входов) при условии, что проблема дискретного логарифма трудноразрешима в классическом смысле.

On generic complexity of the discrete logarithm problem.pdf Введение В работе [1] развита теория генерической сложности вычислений. В рамках этого подхода алгоритмическая проблема рассматривается не на всём множестве входов, а на некотором подмножестве «почти всех» входов. Такие входы образуют так называемое генерическое множество. Понятие «почти все» формализуется введением естественной меры на множестве входных данных. С точки зрения практики, алгоритмы, решающие быстро проблему на генерическом множестве, так же хороши, как и быстрые алгоритмы для всех входов. Классическим примером такого алгоритма является симплекс-метод - он за полиномиальное время решает задачу линейного программирования для большинства входных данных, но имеет экспоненциальную сложность в худшем случае. Более того, может так оказаться, что проблема трудноразрешима или вообще неразрешима в классическом смысле, но легкоразрешима на генерическом множестве. В [1, 2] доказано, что таким поведением обладают многие алгоритмические проблемы алгебры, а в [3] построено генерическое множество, на котором разрешима классическая проблема остановки для машин Тьюринга с лентой, бесконечной в одном направлении. Для многих классических NP-полных проблем существуют полиномиальные генерические алгоритмы [4]. С точки зрения современной криптографии интересны такие алгоритмические проблемы, которые, являясь (гипотетически) трудными в классическом смысле, остаются трудными и в генерическом смысле, т. е. для почти всех входов. Это объясняется тем, что при случайной генерации ключей в криптографическом алгоритме происходит генерация входа некоторой трудной алгоритмической проблемы, лежащей в основе алгоритма. Если проблема генерически легкоразрешима, то для почти всех таких входов её можно быстро решить и ключи почти всегда будут нестойкими. Поэтому проблема должна быть генерически трудной. В данной работе изучается генерическая сложность классической проблемы криптографии - проблемы дискретного логарифма в полях GF(p), где p простое. До сих пор не известно полиномиальных алгоритмов её решения; на предположении об её трудноразрешимости основаны многие криптографические алгоритмы [5]. В работе доказывается, что эта проблема генерически неразрешима за полиномиальное время при условии отсутствия полиномиального вероятностного алгоритма её решения в худшем случае. Более того, существует правдоподобная гипотеза о том, что любой полиномиальный вероятностный алгоритм можно эффективно дерандомизировать, т. е. построить полиномиальный детерминированный алгоритм, решающий ту же задачу. Хотя это пока ещё не доказано, имеются серьёзные результаты в этом направлении [6]. При доказательстве основного результата работы использованы методы, развитые в [7, 8]. 1. Генерические алгоритмы Пусть I есть множество всех входов некоторой алгоритмической проблемы и In - множество всех входов размера n. Для подмножества S С I определим последовательность Pn(S) = iS^, n =1, 2, 3,... Заметим, что pn(S) -это вероятность попасть в S при случайной и равновероятной генерации входов из In. Асимптотической плотностью S назовём предел (если он существует) p(S) = lim pn(S). Множество S называется генерическим, если p(S) = 1, и пренебрежимым, если p(S) = 0. Очевидно, что S генерическое тогда и только тогда, когда его дополнение I \ S пренебрежимо. Алгоритм A с множеством входов I и множеством выходов J U {?} (? G J) называется генерическим, если 1) A останавливается на всех входах из I; 2) множество {x G I : A(x) =?} пренебрежимо. Генерический алгоритм A вычисляет функцию f : I ^ J, если для всех x Е I A(x) = y Е J ^ f (x) = y. Ситуация A(x) =? означает, что A не может вычислить функцию f на аргументе x. Но условие 2 гарантирует, что A корректно вычисляет f на почти всех входах (входах из генерического множества). 2. Проблема дискретного логарифма Напомним, что проблема дискретного логарифма состоит в вычислении функции d/ : I ^ N, где I - это множество троек (a,p, gp), таких, что p - простое число, gp - фиксированный первообразный элемент в поле GF(p) и a Е GF(p), a = 0. Сама функция d/ определяется следующим образом: d/(a,p, gp) = x ^ gpX = a Е GF(p). Под размером входа понимается число разрядов в двоичной записи числа p. В настоящее время неизвестно полиномиальных алгоритмов (даже вероятностных), решающих проблему дискретного логарифма. Это обстоятельство лежит в основе криптостойко-сти многочисленных криптографических алгоритмов [5]. Для изучения генерической сложности этой проблемы необходимо провести некоторую стратификацию на множестве входов. Рассмотрим любую бесконечную последовательность простых чисел п = {P1,P2, ... ,Pn,...}, удовлетворяющую условию 2n ^ pn < 2п+; для любого n. Такие последовательности существуют благодаря известному постулату Бертрана, доказанному П. Л. Чебы-шевым. Будем называть такую последовательность экспоненциальной. Теперь определим функцию d/n как ограничение функции d/ на множество троек (a,p, gp), таких, что p Е п. Заметим, что для этой функции множество всех входов размера n состоит из троек (a,p,gp) с фиксированными p,gp и произвольным a Е {1,... ,p - 1}. Очевидно, что проблема вычисления d/n является подпроблемой вычисления d/. Следующая лемма показывает, что некоторые такие подпроблемы так же трудны, как и оригинальная проблема дискретного логарифма. Лемма 1. Если не существует полиномиального вероятностного алгоритма для вычисления d/, то найдется такая экспоненциальная последовательность простых чисел п, что и для вычисления d/n нет полиномиального вероятностного алгоритма. Доказательство. Пусть , P2,... - все полиномиальные вероятностные алгоритмы. Из предположения о том, что не существует полиномиального вероятностного алгоритма для вычисления d/, следует, что для любого алгоритма Pn существует бесконечно много полей GF(p), в которых он не может вычислить d/. Из этого следует, что можно выбрать последовательность п' = {p;,p2,...} так, чтобы алгоритм Pn не вычислял d/ в поле GF(pn) и для любого n выполнялось бы pn+; > 2pn. Последовательность п' можно расширить до экспоненциальной последовательности п, добавив где нужно новые члены. Заметим теперь, что d/n и будет той функцией, для вычисления которой не существует полиномиального алгоритма. ■ 3. Основной результат Следующий результат говорит о том, что проблема дискретного логарифма остаётся вычислительно трудной и в генерическом случае при условии её трудноразреши-мости в худшем. Теорема 1. Пусть п - любая экспоненциальная последовательность простых чисел. Если существует полиномиальный генерический алгоритм, вычисляющий функцию d/n, то существует полиномиальный вероятностный алгоритм, вычисляющий d/n для всех входов. Доказательство. Пусть существует полиномиальный генерический алгоритм A, вычисляющий функцию d/n. Построим вероятностный полиномиальный алгоритм B, вычисляющий d/n на всем множестве входов. Алгоритм B на входе (a,p,gp) будет работать следующим образом: 1) сгенерировать случайно и равномерно y £ {0,... ,p - 1} и вычислить a' = agy; 2) запустить алгоритм A на (a',p,gp); 3) если A(a',p, gp) = z £ N, то a' = gp = agy = gp+y, откуда x = z - y mod (p - 1) - дискретный логарифм для исходной задачи (a,p, gp); 4) если A(a',p, gp) = ?, то выдать 0. Заметим, что данный полиномиальный вероятностный алгоритм может выдать неправильный ответ только на шаге 4. Докажем, что вероятность этого меньше 1/2. Действительно, a' = agy при y £ {0,... ,p - 1} пробегает все ненулевые элементы поля GF(p), поэтому множество {(a',p,gp) : y £ {0,... ,p - 1}} совпадает с множеством всех входов размера n. Но алгоритм A генерический, поэтому доля тех входов (a',p, gp), на которых он выдаёт неопределённый ответ, стремится к 0 с ростом n и с некоторого момента становится меньше 1/2. ■ Непосредственным следствием доказанной теоремы является Теорема 2. Если для вычисления функции d/ не существует полиномиального вероятностного алгоритма, то существует экспоненциальная последовательность п, такая, что для вычисления функции d/n не существует генерического полиномиального алгоритма.

Ключевые слова

генерическая сложность, проблема дискретного логарифма, вероятностный алгоритм, generic complexity, discrete logarithm problem, probabilistic algorithm

Авторы

ФИООрганизацияДополнительноE-mail
Рыбалов Александр НиколаевичИнститут математики им. С. Л. Соболева СО РАНкандидат физико-математических наук, старший научный сотрудникalexander.rybalov@gmail.com
Всего: 1

Ссылки

Kapovich I., Miasnikov A, Schupp P., and Shpilrain V. Generic-case complexity, decision problems in group theory and random walks //J. Algebra. 2003. V. 264. No. 2. P. 665-694.
Kapovich I., Miasnikov A., Schupp P., and Shpilrain V. Average-case complexity for the word and membership problems in group theory // Adv. Math. 2005. V. 190. P. 343-359.
Hamkins J. D. and Miasnikov A. G. The halting problem is decidable on a set of asymptotic probability one // Notre Dame J. Formal Logic. 2006. V. 47. No. 4. P. 515-524.
GilmanR., Miasnikov A. G., Myasnikov A. D., and Ushakov A. Report on generic case complexity // Herald of Omsk University. 2007. Special Issue. P. 103-110.
Мао В. Современная криптография: теория и практика. М.: Вильямс, 2005. 768с.
Impagliazzo R. and Wigderson A. P = BPP unless E has subexponential circuits: Derandomizing the XOR Lemma // Proc. 29th STOC. El Paso: ACM, 1997. P. 220-229.
Myasnikov A. and Rybalov A. Generic complexity of undecidable problems //J. Symbolic Logic. 2008. V. 73. No. 2. P. 656-673.
Rybalov A. Generic complexity of presburger arithmetic // Theory Comput. Systems. 2010. V. 46. No. 1. P. 2-8.
 О генерической сложности проблемы дискретного логарифма | ПДМ. 2016. № 3(33). DOI: 10.17223/20710410/33/8

О генерической сложности проблемы дискретного логарифма | ПДМ. 2016. № 3(33). DOI: 10.17223/20710410/33/8