On generic complexity of the quadratic resi-duosity problem.pdf В работе [1] развита теория генерической сложности вычислений. В рамках этого подхода алгоритмическая проблема рассматривается не на всем множестве входов, а на некотором подмножестве «почти всех» входов. Такие входы образуют так называемое генерическое множество. Понятие «почти все» формализуется введением естественной меры на множестве входных данных. С точки зрения практики алгоритмы, решающие быстро проблему на генерическом множестве, так же хороши, как и быстрые алгоритмы для всех входов. С точки зрения современной криптографии интересны такие алгоритмические проблемы, которые, являясь (гипотетически) трудными в классическом смысле, остаются трудными и в генерическом смысле, т. е. для почти всех входов. Это объясняется тем, что при случайной генерации ключей в криптографическом алгоритме происходит генерация входа некоторой трудной алгоритмической проблемы, лежащей в основе алгоритма. Если проблема является генерически легко разрешимой, то для почти всех таких входов её можно быстро решить, и ключи почти всегда будут нестойкими. Поэтому проблема должна быть генерически трудной. Например, для проблемы дискретного логарифма такие результаты получены в работе [2]. Данная работа посвящена изучению генерической сложности классической проблемы распознавания квадратичных вычетов в группах вычетов. До сих пор не известно полиномиальных алгоритмов её решения. Более того, на предположении о её трудно-разрешимости основаны некоторые криптографические алгоритмы [3]. Пусть I - некоторое множество входов. На множестве I определена функция размера size : I ^ N, сопоставляющая каждому элементу a G I его размер size(a). Допустим, что для любого n множество In элементов из I размера n конечно. Для любого подмножества S С I определим следующую последовательность: |S n In| 1 _ _ Pn(S) = |М , n =1, 2, 3,... Mral Величина pn(S) -это вероятность получить вход из множества S при случайной и равномерной генерации элементов из In. Асимптотической плотностью S назовём следующий предел (если он существует): p(S) = lim pn(S). Множество S называется генерическим, если p(S)= 1, и пренебрежимым, если p(S)= 0. Очевидно, что S генерическое тогда и только тогда, когда его дополнение I \ S пренебрежимо. Понятие генерического множества является некоторой формализацией интуитивного понятия множества «почти всех» элементов множества I в том смысле, что при увеличении размера элемента вероятность попасть в генерическое множество при случайной и равновероятной генерации элементов стремится к 1. Алгоритмическая проблема распознования множества S С I генерически полиномиально разрешима, если существует множество G С I, такое, что 1) G - генерическое; 2) G - разрешимое за полиномиальное время; 3) G П S - разрешимое за полиномиальное время. Генерический алгоритм, решающий проблему S, работает на входе x G I следующим образом. Сначала определяет, принадлежит ли x генерическому множеству G. Если да, то проверяет принадлежность входа S. Если нет, то отвечает НЕ ЗНАЮ. Такой алгоритм правильно решает проблему S на почти всех входах. Пусть Z/(m) -мультипликативная группа вычетов по модулю m G N. Напомним, что квадратичным вычетом в группе Z/(m) называется любой элемент x, для которого существует y G Z/(m), такой, что x = y2. В противном случае элемент x называется квадратичным невычетом. Под проблемой распознавания квадратичных вычетов понимается проблема распознавания следующего множества: QR = {(m, x) G N2 : m = pq, где p, q - простые числа, x - квадратичный вычет в Z/ (m)}. В настоящее время неизвестно полиномиальных алгоритмов (в том числе и вероятностных), решающих проблему распознавания квадратичных вычетов для всех таких модулей m. Для изучения генерической сложности этой проблемы необходимо провести некоторую стратификацию на множестве входов. Рассмотрим любую бесконечную последовательность натуральных чисел ^ = {m1,m2,...}, удовлетворяющую следующим условиям: 1) 2n < mn < 2n+1 для любого n; 2) mn - произведение двух различных простых чисел для любого n > 1. Будем называть такую последовательность экспоненциальной. Из знаменитого постулата Бертрана, доказанного П. Л. Чебышевым, следует, что экспоненциальные последовательности существуют. Определим алгоритмическую проблему QR(^) как ограничение проблемы распознавания квадратичных вычетов QR на следующее множество входных данных: I = {(m, x) : m G x G Z/(m)}. Под размером входа (m, x) понимается количество бит в двоичной записи числа m минус 1. Заметим, что множество In входов проблемы QR(^) размера n состоит из всех пар (m,x), где m - единственное число m G удовлетворяющее условию 2n < < m < 2n+1, а x - любой элемент из Z/(m). Теорема 1. Если проблема QR(^) генерически полиномиально разрешима, то существует полиномиальный вероятностный алгоритм, решающий QR(^) для всех входов. Теорема 2. Если для проблемы QR не существует полиномиального вероятностного алгоритма, то существует экспоненциальная последовательность такая, что проблема QR(^) не является генерически полиномиально разрешимой. Более подробно полученные результаты представлены в [4].

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