О генерической сложности проблемы дискретного логарифма в группах точек эллиптических кривых над конечными полями | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/41

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

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

On the generic complexity of discrete logarithm problem in groups of elliptic curves over finite fields.pdf Введение Эллиптическая криптография занимается разработкой криптосистем с открытым ключом, основанных на эллиптических кривых над конечными полями. В качестве базиса для этих криптосистем используется проблема дискретного логарифма в группах точек эллиптических кривых над конечными полями. Основное преимущество эллиптической криптографии заключается в том, что на сегодняшний день не известно даже субэкспоненциальных алгоритмов решения проблемы дискретного логарифма на эллиптических кривых, в отличие от проблемы дискретного логарифма в конечных полях. Рассмотрим проблему дискретного логарифма в группах точек эллиптических кривых над конечными полями GF(p), где p - простое. Эллиптические кривые над такими полями используются в протоколах электронной цифровой подписи ECDSA и ГОСТ Р 34.10-2012. В [1] развита теория генерической сложности вычислений. В рамках этого подхода алгоритмическая проблема рассматривается не на всём множестве входов, а на некотором подмножестве «почти всех» входов. Такие входы образуют так называемое генерическое множество. Понятие «почти все» формализуется введением естественной меры на множестве входных данных. С точки зрения современной криптографии интересны такие алгоритмические проблемы, которые, являясь (гипотетически) трудными в классическом смысле, остаются трудными и в генерическом смысле, т. е. для почти всех входов. Это объясняется тем, что при случайной генерации ключей в криптографическом алгоритме происходит генерация входа некоторой трудной алгоритмической проблемы, лежащей в основе алгоритма. Если проблема является генерически легкоразрешимой, то для почти всех таких входов её можно быстро решить и ключи почти всегда будут нестойкими. Поэтому проблема должна быть генерически трудной. В работе доказывается, что естественная подпроблема проблемы дискретного логарифма в группах точек эллиптических кривых над конечными полями GF(p) генериче-ски неразрешима за полиномиальное время при условии отсутствия полиномиального вероятностного алгоритма для её решения в худшем случае. Существует правдоподобная гипотеза о том, что любой полиномиальный вероятностный алгоритм можно эффективно дерандомизировать, т. е. построить полиномиальный детерминированный алгоритм, решающий ту же задачу. Хотя это пока не доказано, имеются серьезные результаты в пользу этого [2]. 1. Генерические алгоритмы Пусть I есть множество всех входов некоторой алгоритмической проблемы и In - множество всех входов размера п. Для подмножества S С I определим последовательность fQ, IS n In| 1 _ _ pn(S) = |M , n = 1, 2, 3,... |In| Заметим, что pn(S) -это вероятность попасть в S при случайной и равновероятной генерации входов из In. Асимптотической плотностью S назовём предел (если он существует) p(S) = lim pn(S). n-y^o Множество S называется генерическим, если p(S) = 1, и пренебрежимым, если p(S) = 0. Очевидно, что S генерическое тогда и только тогда, когда его дополнение I \ S пренебрежимо. Алгоритм A с множеством входов I и множеством выходов J U {?} (? (j J) называется генерическим, если 1) A останавливается на всех входах из I; 2) множество {x ( 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. Эллиптические кривые и проблема дискретного логарифма Пусть p > 3 - простое число. Эллиптической кривой над конечным полем GF(p) называется множество точек E = {(x, y) ( GF(p)2 : y2 = x3 + ax + b}, где a,b ( GF(p) такие, что A = 4a3 + 27b2 = 0. К этим точкам добавляется так называемая «точка на бесконечности». На точках эллиптической кривой E вводится операция сложения [3], относительно которой E становится абелевой группой G(E) с нулем - точкой на бесконечности. Для точки B ( G(E) обозначим (Б) = {A ( G(E) : A = nB,n ( N}. Проблема дискретного логарифма для эллиптических кривых над конечными полями состоит в вычислении функции dle : I ^ N, где I - это множество четвёрок (A,B,E,p), таких, что p - простое число, E - фиксированная эллиптическая кривая над GF(p), B - фиксированная точка из G(E), A - произвольная точка из (B). Сама функция dle определяется следующим образом: dle(A, B, E,p) = x ^ xB = A G G(E). Под размером входа понимается число разрядов в двоичной записи числа p. В настоящее время неизвестно полиномиальных алгоритмов (даже вероятностных) для вычисления функции dle. Это обстоятельство лежит в основе криптостойкости многочисленных криптографических алгоритмов [3]. Для изучения генерической сложности этой проблемы необходимо провести некоторую стратификацию на множестве входов. Рассмотрим любую бесконечную последовательность простых чисел п = {pi,p2,... ,Pn,...}, удовлетворяющую условию 2n ^ pn < 2n+1 для любого n. Будем называть такую последовательность экспоненциальной. Теперь определим функцию dlen как ограничение функции dle на множество четвёрок (A, B, E,p), таких, что p G п. Заметим, что для этой функции множество всех входов размера n состоит из четвёрок (A, B, E,p) с фиксированными B, E,p и произвольной точкой A G (B). Очевидно, что проблема вычисления dlen является подпроблемой вычисления dle. Следующая лемма показывает, что некоторые такие подпроблемы так же трудны, как и оригинальная проблема. Лемма 1. Если не существует полиномиального вероятностного алгоритма для вычисления dle, то найдётся такая экспоненциальная последовательность простых чисел п, что и для вычисления dlen нет полиномиального вероятностного алгоритма. Доказательство. Пусть P1, P2,... - все полиномиальные вероятностные алгоритмы. Из предположения о том, что не существует полиномиального вероятностного алгоритма для вычисления dle, следует, что для любого алгоритма Pn существует бесконечно много троек B, E,p, для которых он не может вычислить dle. Из этого следует, что можно выбрать последовательность п' = {p1,p2,...} так, чтобы алгоритм Pn не вычислял dle для B, E,p и для любого n выполнялось бы pn+1 > 2pn. Последовательность п' можно расширить до экспоненциальной последовательности п, добавив, где нужно, новые члены. Заметим теперь, что dlen и будет той функцией, для вычисления которой не существует полиномиального алгоритма. ■ 3. Основной результат Следующий результат говорит о том, что проблема дискретного логарифма для эллиптических кривых над конечными полями остается вычислительно трудной и в ге-нерическом случае при условии её трудноразрешимости в худшем случае. Теорема 1. Пусть п - любая экспоненциальная последовательность простых чисел. Если существует полиномиальный генерический алгоритм, вычисляющий функцию dlen, то существует полиномиальный вероятностный алгоритм, вычисляющий d/en для всех входов. Доказательство. Пусть существует полиномиальный генерический алгоритм A, вычисляющий функцию dlen. Построим вероятностный полиномиальный алгоритм B, вычисляющий dlen на всём множестве входов. Алгоритм B на входе (A,B,E,p) работает следующим образом: 1) Сгенерировать случайно и равномерно y Е {0,...,p - 1} и вычислить A' = A + yB. 2) Запустить алгоритм A на (A', B, E,p). 3) Если A(A', B, E,p) = z Е N, то A' = zB = A+yB, откуда x = z-y - дискретный логарифм для исходной задачи (A, B, E,p). 4) Если A(A', B, E,p) =?, то выдать 0. Заметим, что алгоритм B может выдать неправильный ответ только на шаге 4. Докажем, что вероятность этого меньше 1/2. Действительно, A' = A+yB при y = 0,... , p- 1 пробегает все элементы (B), поэтому множество {(A', B, E,p) : y Е {0,... ,p - 1}} совпадает с множеством всех входов размера n. Но алгоритм A генерический, поэтому доля тех входов (A',B,E,p), на которых он выдаёт неопределённый ответ, стремится к 0 с ростом n и с некоторого момента становится меньше 1/2. ■ Непосредственным следствием теоремы 1 является следующая Теорема 2. Если для вычисления функции dle не существует полиномиального вероятностного алгоритма, то существует экспоненциальная последовательность п, такая, что для вычисления функции dlen не существует генерического полиномиального алгоритма.

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

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

Авторы

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

Ссылки

Романьков В. А. Введение в криптографию. 2-е изд., испр. М.: ФОРУМ, 2012. 240с.
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.
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.
 О генерической сложности проблемы дискретного логарифма в группах точек эллиптических кривых над конечными полями | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/41

О генерической сложности проблемы дискретного логарифма в группах точек эллиптических кривых над конечными полями | ПДМ. Приложение. 2018. № 11. DOI: 10.17223/2226308X/11/41