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

Определение 2 (Задча о ближайшем векторе, CVPy). Пусть даны решетка <math>\mathcal{L} (\mathbf{B})</math> и целевая точка t. Требуется найти вектор решетки Bx (где x 2 Zn) такой, что kBx - t k у - ||By - tk для любого y2Zn.

Проблема поиска эффективного (за полиномиальное время) решения SVPy для решеток произвольной размерности была впервые решена при помощи знаменитого алгоритма редукции решеток Ленстры, Ленстры и Ловаса [ ], получившего известность как алгоритм LLL.

Теорема 1. Существует алгоритм решения задачи SVPу за полиномиальное время для у = (2/p3)n, где n – ранг входной решетки.

Следствие 1. Существует алгоритм решения задачи CVPy за полиномиальное время для у = O(2/p3)n, где n – ранг входной решетки.

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

Известно, что и SVPy, и CVPy являются NP-трудными при точных (y = 1) или даже приближенных версиях для малых значений y – например, при постоянной у, не зависящей от размерности. (Самые актуальные результаты см. в [13, гл. 3 и 4] и [4,10]). Поэтому, скорее всего, не существует эффективного алгоритма для точного решения этих задач в произвольной размерности. Для любой фиксированной размерности n обе задачи, и SVP, и CVP, могут быть точно решены за полиномиальное время с помощью алгоритма Каннана [ ]. Однако время работы зависит от размерности решетки по формуле nO(n). Используя рандомизацию, можно вероятностно решить точную задачу SVP с затратами 2O(n) времени и памяти при помощи алгоритма на основе решета, предложенного Айтаем, Кумаром и Сивакумаром [1].

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

Основной открытой задачей в вычислительном исследовании решеток является определение сложности приближенных алгоритмов SVPу и CVPу для коэффициентов аппроксимации у = nc, полиномиальных относительно ранга решетки. А именно:

• Существуют ли алгоритмы с полиномиальным временем выполнения, которые решают задачу SVPy или CVPy для полиномиальных коэффициентов у = nc? (Нахождение таких алгоритмов даже для очень большой экспоненты c стало бы серьезным прорывом в вычислительных науках).

• Существует ли e > 0 такое, что аппроксимация SVPy или CVPy в пределах у = n€ является NP-трудной? (Самые сильные известные сведения о неаппроксимируемости [ ] относятся к коэффициентам вида nO(1/loglog n), которые растут быстрее любой полилогарифмической функции, но медленнее любой полиномиальной).

Существует теоретическое доказательство того, что для больших полиномиальных коэффициентов у = nc задачи SVP у и CVPy не являются NP-трудными. В частности, обе задачи принадлежат к классу сложности со AM для коэффициента аппроксимации у = O(n/logn) (см. [12, гл. 9]). Таким образом, эти задачи не могут быть NP-трудными в пределах таких коэффициентов, если только не нарушается полиномиальная иерархия классов сложности.