Задача о кратчайшем векторе

Ключевые слова и синонимы

Редукция базиса решетки; алгоритм LLL; задача о ближайшем векторе; задача о минимальном расстоянии

Постановка задачи

Точечная решетка представляет собой множество всех целочисленных линейных комбинаций [math]\displaystyle{ \mathcal{L} (\mathbf{b}_1, ..., \mathbf{b}_n) = \Bigg\{ \sum_{i = 1}^n x_i \mathbf{b}_i : x_1, ..., x_n \in \mathbb{Z} \Bigg\} }[/math] из n линейно независимых векторов [math]\displaystyle{ \mathbf{b}_1, ..., \mathbf{b}_n \in \mathbb{R}^m }[/math] в m-мерном евклидовом пространстве. Для удобства вычислений векторы решетки [math]\displaystyle{ \mathbf{b}_1, ..., \mathbf{b}_n }[/math] часто предполагаются целыми (или рациональными), так что решетка может быть представлена целочисленной матрицей [math]\displaystyle{ \mathbf{B} = [\mathbf{b}_1, ..., \mathbf{b}_n] \in \mathbb{R}^{m \times n} }[/math] (называемой базисом) с порождающими векторами в качестве столбцов. Используя матричную нотацию, точки решетки в [math]\displaystyle{ \mathcal{L} (\mathbf{B}) }[/math] удобно представить в виде [math]\displaystyle{ \mathbf{Bx} }[/math], где [math]\displaystyle{ \mathbf{x} }[/math] – целочисленный вектор. Целые числа m и n называются размерностью и рангом решетки, соответственно. Заметим, что любая решетка допускает несколько базисов, но все они имеют одинаковые ранг и размерность.

Основными вычислительными задачами на решетках являются задача о кратчайшем векторе (Shortest Vector Problem, SVP), в которой требуется найти кратчайший ненулевой вектор в данной решетке, и задача о ближайшем векторе (Closest Vector Problem, CVP), в которой требуется найти точку решетки, ближайшую к заданной цели. Обе задачи могут быть определены относительно любой нормы, но евклидова норма [math]\displaystyle{ \parallel \mathbf{v} \parallel = \sqrt {\sum_i v^2_i} }[/math] является наиболее распространенной. Также в приложениях вычислительных наук часто встречаются такие нормы, как норма [math]\displaystyle{ \ell_1 }[/math], [math]\displaystyle{ \parallel \mathbf{v} \parallel _1 = \sum_i |v_i| }[/math], и норма max, [math]\displaystyle{ \parallel \mathbf{v} \parallel _\infty = max_i |v_i| }[/math]. Далее будет рассматриваться евклидова норма.

Поскольку эффективные алгоритмы для точного решения SVP и CVP в произвольно высокой размерности неизвестны, эти задачи обычно определяются в их аппроксимационной версии, где коэффициент аппроксимации у > 1 может быть функцией размерности или ранга решетки.

Определение 1 (Задача о кратчайшем векторе, SVPy). Дана решетка L(B). Требуется найти ненулевой вектор решетки Bx (где x2Znnf0g), такой, что kBx k у ■ ||By|| для любого yeZ"\{0}.

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

Решетки веками исследовались математиками на эквивалентном языке квадратичных форм; они являются основным объектом изучения в геометрии чисел – направлении, предложенном Минковским в качестве связующего звена между геометрией и теорией чисел. Математическое введение в решетки см. в работе [3]. В [6, 12] дается введение в решетки с акцентом на вычислительные и алгоритмические вопросы.

Основные результаты

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

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

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

Следствие 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].

Что касается приближенных решений, то алгоритм редукции решетки LLL был улучшен как с точки зрения времени работы, так и с точки зрения гарантии аппроксимации (см. работу [ ] и ссылки в ней). В настоящее время лучший (рандомизированный) алгоритм аппроксимации с полиномиальным временем выполнения достигает коэффициента аппроксимации у = 2O(nloglogn/l°gn).

Применение

Несмотря на большой (экспоненциальный от n) коэффициент аппроксимации, алгоритм LLL нашел множество применений и позволил решить многие алгоритмические задачи вычислительных наук. Количество и разнообразие приложений слишком велики, чтобы составить их полный список. Ниже приведены некоторые из наиболее показательных приложений в различных областях компьютерных наук.

Первыми мотивирующими приложениями редукции базиса решетки были решение целочисленных программ с фиксированным числом переменных и факторизация многочленов с рациональными коэффициентами (см. [11], [8] и [5, гл. 16]). Другие классические приложения – решение случайных экземпляров задач о суммировании подмножеств с низкой плотностью, вскрытие (усеченных) линейных конгруэнтных псевдослучайных генераторов, одновременная диофантова аппроксимация и опровержение гипотезы Мертенса (см. [ ] и [5, гл. 17]).

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

Последний класс приложений задач с решетками – это разработка криптографических функций (например, устойчивых к столкновениям хэш-функций, схем шифрования с открытым ключом и т.д.), основанное на кажущейся неразрешимости задачи решения 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-трудными в пределах таких коэффициентов, если только не нарушается полиномиальная иерархия классов сложности.

Ссылка на код

Алгоритм редукции решетки LLL реализован в большинстве библиотек и пакетов для вычислительной алгебры, например:

• GAP (http://www.gap-system.org)

• LiDIA (http://www.cdc.informatik.tu-darmstadt.de/TI/LiDIA/)

• Magma (http://magma.maths.usyd.edu.au/magma/)

• Maple (http://www.maplesoft.com/)

• Mathematica (http://www.wolfram.com/products/mathematica/index.html)

• NTL (http://shoup.net/ntl/).

NTL также включает реализацию блочного алгоритма редукции Коркина-Золотарева, которая широко используется в криптоанализе.

См. также

• Криптографическая стойкость обучения
• Метод рюкзака
• Изучение высоких коэффициентов Фурье булевых функций
• Квантовый алгоритм для решения задачи дискретного логарифмирования
• Квантовый алгоритм факторизации
• Задача об упаковке шаров

Литература

1. Ajtai, M., Kumar, R., Sivakumar, D.: A sieve algorithm for the shortest lattice vector problem. In: Proceedings of the thirty- third annual ACM symposium on theory of computing – STOC 2001, Heraklion, Crete, Greece, July 2001, pp 266-275. ACM, New York (2001)

2. Babai, L.: On Lovasz' lattice reduction and the nearest lattice point problem. Combinatorica 6(1), 1-13 (1986). Preliminary version in STACS 1985

3. Cassels, J.W.S.: An introduction to the geometry of numbers. Springer, New York (1971)

4. Dinur, I., Kindler, G., Raz, R., Safra, S.: Approximating CVP to within almost-polynomial factors is NP-hard. Combinatorica 23(2), 205-243 (2003). Preliminary version in FOCS 1998

5. von zur Gathen, J., Gerhard, J.: Modern Comptuer Algebra, 2nd edn. Cambridge (2003)

6. Grotschel, M., Lovasz, L., Schrijver, A.: Geometric algorithms and combinatorial optimization. Algorithms and Combinatorics, vol. 2, 2nd edn. Springer (1993)

7. Joux, A., Stern, J.: Lattice reduction: A toolbox for the cryptanalyst.J.Cryptolo. 11(3), 161-185(1998)

8. Kannan, R.: Annual reviews of computer science, vol. 2, chap. "Algorithmic geometry of numbers", pp. 231-267. Annual Review Inc., Palo Alto, California (1987)

9. Kannan, R.: Minkowski's convex body theorem and integer programming. Math. Oper. Res. 12(3), 415^40 (1987)

10. Khot, S.: Hardness of Approximating the Shortest Vector Problem in Lattices. J. ACM 52(5), 789-808 (2005). Preliminary version in FOCS 2004

11. Lenstra, A.K., Lenstra, Jr., H.W., Lovasz, L.: Factoring polynomials with rational coefficients. Math Ann. 261, 513-534 (1982)

12. Micciancio, D., Goldwasser, S.: Complexity of Lattice Problems: A Cryptographic Perspective. The Kluwer International Series in Engineering and Computer Science, vol. 671. Kluwer Academic Publishers, Boston, Massachusetts (2002)

13. Nguyen, P., Stern, J.: The two faces of lattices in cryptology. In:J.Silverman (ed.) Cryptography and lattices conference – CaLC 2001, Providence, RI, USA, March 2001. Lecture Notes in Computer Science, vol. 2146, pp. 146-180. Springer, Berlin (2001)

14. Schnorr, C.P.: Fast LLL-type lattice reduction. Inform. Comput. 204(1),1-25(2006)

15. Vazirani, V.V.: Approximation Algorithms. Springer (2001)