Задача о кратчайшем векторе: различия между версиями

Проблема поиска эффективного (за полиномиальное время) решения <math>SVP_\gamma</math> для решеток произвольной размерности была впервые решена при помощи знаменитого ''алгоритма редукции решеток'' Ленстры, Ленстры и Ловаса [11], получившего известность как алгоритм LLL.

Алгоритм LLL не ограничивается простым нахождением относительно короткого вектора решетки: он вычисляет так называемый ''редуцированный базис'' для входной решетки, т. е. полный базис, состоящий из относительно более коротких векторов решетки. Вскоре после разработки алгоритма LLL Бабай [2] показал, что редуцированные базисы могут быть использованы для эффективного решения <math>CVP_\gamma</math> также в пределах аналогичных коэффициентов аппроксимации.

Дополнительную информацию см. в оригинальных статьях [2, 11] и [12, гл. 2]. Вводные презентации алгоритма LLL также можно найти во многих других текстах, например, [5, глава 16] и [15, глава 27]. Интересно отметить, что CVP по крайней мере так же сложен, как SVP (см. [12 , глава 2]), в том смысле, что любой алгоритм, решающий задачу <math>CVP_\gamma</math>, может быть эффективно адаптирован для решения задачи <math>SVP_\gamma</math> с тем же коэффициентом аппроксимации.

Известно, что и <math>SVP_\gamma</math>, и <math>CVP_\gamma</math> являются NP-трудными при точных (y = 1) или даже приближенных версиях для малых значений y – например, при постоянной у, не зависящей от размерности. (Самые актуальные результаты см. в [13, гл. 3 и 4] и [4,10]). Поэтому, скорее всего, не существует эффективного алгоритма для точного решения этих задач в произвольной размерности. Для любой фиксированной размерности n обе задачи, и SVP, и CVP, могут быть точно решены за полиномиальное время с помощью алгоритма Каннана [9]. Однако время работы зависит от размерности решетки по формуле <math>n^{O(n)}</math>. Используя рандомизацию, можно вероятностно решить точную задачу SVP с затратами <math>2^{O(n)}</math> времени и памяти при помощи алгоритма на основе решета, предложенного Айтаем, Кумаром и Сивакумаром [1].

Что касается приближенных решений, то алгоритм редукции решетки LLL был улучшен как с точки зрения времени работы, так и с точки зрения гарантии аппроксимации (см. работу [14] и ссылки в ней). В настоящее время лучший (рандомизированный) алгоритм аппроксимации с полиномиальным временем выполнения достигает коэффициента аппроксимации <math>\gamma = 2^{O(n \; log \; log \; n / log \; n)}</math>.

В последнее время редукция базиса решетки широко использовалась для решения многих задач криптоанализа и теории кодирования, включая взлом нескольких вариантов криптосистемы RSA и алгоритма цифровой подписи DSA, поиск малых решений модулярных уравнений и расшифровку списков кодов китайской теоремы об остатках (Chinese Reminder Theorem, CRT). Обзор недавних вариантов применения, в основном в области криптоанализа, можно найти в работах [7, 13].

Последний класс приложений задач с решетками – это разработка криптографических функций (например, устойчивых к столкновениям хэш-функций, схем шифрования с открытым ключом и т.д.), основанное на очевидной неразрешимости задачи решения <math>SVP_\gamma</math> в пределах малых коэффициентов аппроксимации. В [12, глава 8] и [13] можно найти обзор таких приложений и указатели на соответствующую литературу. Отличительной особенностью многих таких криптографических функций, основанных на решетках, является доказанная сложность их взлома ''в среднем'', основываясь на предположении о неразрешимости ''в наихудшем случае'' лежащей в их основе задачи на решетки.

Основной открытой задачей в вычислительном исследовании решеток является определение сложности приближенных алгоритмов <math>SVP_\gamma</math> и <math>CVP_\gamma</math> для коэффициентов аппроксимации <math>\gamma = n^c</math>, полиномиальных относительно ранга решетки. А именно:

Существует теоретическое доказательство того, что для больших полиномиальных коэффициентов <math>\gamma = n^c</math> задачи <math>SVP_\gamma</math> и <math>CVP_\gamma</math> не являются NP-трудными. В частности, обе задачи принадлежат к классу сложности со AM для коэффициента аппроксимации <math>\gamma = O(\sqrt{n/log \; n})</math> (см. [12, гл. 9]). Таким образом, эти задачи не могут быть NP-трудными в пределах таких коэффициентов, если только не нарушается полиномиальная иерархия классов сложности.