Задача о кратчайшем векторе
Ключевые слова и синонимы
Редукция базиса решетки; алгоритм 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{Z}^{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{ \lVert \mathbf{v} \rVert = \sqrt {\sum_i v^2_i} }[/math] является наиболее распространенной. Также в приложениях вычислительных наук часто встречаются такие нормы, как норма [math]\displaystyle{ \ell_1: \lVert \mathbf{v} \rVert _1 = \sum_i |v_i| }[/math], и норма [math]\displaystyle{ max: \lVert \mathbf{v} \rVert _\infty = max_i |v_i| }[/math]. Далее будет рассматриваться евклидова норма.
Поскольку эффективные алгоритмы для точного решения задач SVP и CVP в произвольно высокой размерности неизвестны, эти задачи обычно определяются в их аппроксимационной версии, где коэффициент аппроксимации [math]\displaystyle{ \gamma \ge 1 }[/math] может быть функцией размерности или ранга решетки.
Определение 1 (Задача о кратчайшем векторе, [math]\displaystyle{ SVP_\gamma }[/math]). Пусть дана решетка [math]\displaystyle{ \mathcal{L} (\mathbf{B}) }[/math]. Требуется найти ненулевой вектор решетки [math]\displaystyle{ \mathbf{Bx} }[/math] (где [math]\displaystyle{ \mathbf{x} \in \mathbb{Z}^n \backslash \{ \mathbf{0} \} }[/math]), такой, что [math]\displaystyle{ \lVert \mathbf{Bx} \rVert \le \gamma \cdot \lVert \mathbf{By} \rVert }[/math] для любого [math]\displaystyle{ \mathbf{y} \in \mathbb{Z}^n \backslash \{ \mathbf{0} \} }[/math].
Определение 2 (Задача о ближайшем векторе, [math]\displaystyle{ CVP_\gamma }[/math]). Пусть даны решетка [math]\displaystyle{ \mathcal{L} (\mathbf{B}) }[/math] и целевая точка [math]\displaystyle{ \mathbf{t} }[/math]. Требуется найти вектор решетки [math]\displaystyle{ \mathbf{Bx} }[/math] (где [math]\displaystyle{ \mathbf{x} \in \mathbb{Z}^n }[/math]), такой, что [math]\displaystyle{ \lVert \mathbf{Bx - t} \rVert \le \gamma \cdot \lVert \mathbf{By - t} \rVert }[/math] для любого [math]\displaystyle{ \mathbf{y} \in \mathbb{Z}^n }[/math].
Решетки веками исследовались математиками на эквивалентном языке квадратичных форм; они являются основным объектом изучения в геометрии чисел – направлении, предложенном Минковским в качестве связующего звена между геометрией и теорией чисел. Математическое введение в решетки см. в работе [3]. В [6, 12] дается введение в решетки с акцентом на вычислительные и алгоритмические вопросы.
Основные результаты
Задача поиска эффективного (за полиномиальное время) решения [math]\displaystyle{ SVP_\gamma }[/math] для решеток произвольной размерности была впервые решена при помощи знаменитого алгоритма редукции решеток Ленстры, Ленстры и Ловаса [11], получившего известность как алгоритм LLL.
Теорема 1. Существует алгоритм решения задачи [math]\displaystyle{ SVP_\gamma }[/math] за полиномиальное время для [math]\displaystyle{ \gamma = (2 / \sqrt{3})^n }[/math], где n – ранг входной решетки.
Алгоритм LLL не ограничивается простым нахождением относительно короткого вектора решетки: он вычисляет так называемый редуцированный базис для входной решетки, т. е. полный базис, состоящий из относительно более коротких векторов решетки. Вскоре после разработки алгоритма LLL Бабай [2] показал, что редуцированные базисы могут быть использованы для эффективного решения задачи [math]\displaystyle{ CVP_\gamma }[/math] также в пределах аналогичных коэффициентов аппроксимации.
Следствие 1. Существует алгоритм решения задачи [math]\displaystyle{ CVP_\gamma }[/math] за полиномиальное время для [math]\displaystyle{ \gamma = O(2 / \sqrt{3})^n }[/math], где n – ранг входной решетки.
Дополнительную информацию см. в оригинальных статьях [2, 11] и [12, гл. 2]. Вводные презентации алгоритма LLL также можно найти во многих других текстах, например, [5, глава 16] и [15, глава 27]. Интересно отметить, что CVP по меньшей мере так же сложен, как SVP (см. [12 , глава 2]), в том смысле, что любой алгоритм, решающий задачу [math]\displaystyle{ CVP_\gamma }[/math], может быть эффективно адаптирован для решения задачи [math]\displaystyle{ SVP_\gamma }[/math] с тем же коэффициентом аппроксимации.
Известно, что и [math]\displaystyle{ SVP_\gamma }[/math], и [math]\displaystyle{ CVP_\gamma }[/math] являются NP-трудными в их точных [math]\displaystyle{ (\gamma = 1) }[/math] или даже приближенных версиях для малых значений [math]\displaystyle{ \gamma }[/math] – например, при постоянной [math]\displaystyle{ \gamma }[/math], не зависящей от размерности. (Самые актуальные результаты см. в [13, гл. 3 и 4] и [4,10]). Поэтому, скорее всего, не существует эффективного алгоритма для точного решения этих задач в произвольной размерности. Для любой фиксированной размерности n обе задачи, и SVP, и CVP, могут быть точно решены за полиномиальное время с помощью алгоритма Каннана [9]. Однако время работы зависит от размерности решетки по формуле [math]\displaystyle{ n^{O(n)} }[/math]. Используя рандомизацию, можно вероятностно решить точную задачу SVP с затратами [math]\displaystyle{ 2^{O(n)} }[/math] времени и памяти при помощи алгоритма на основе решета, предложенного Айтаем, Кумаром и Сивакумаром [1].
Что касается приближенных решений, то алгоритм редукции решетки LLL был улучшен как с точки зрения времени работы, так и с точки зрения гарантии аппроксимации (см. работу [14] и ссылки в ней). В настоящее время лучший (рандомизированный) алгоритм аппроксимации с полиномиальным временем выполнения достигает коэффициента аппроксимации [math]\displaystyle{ \gamma = 2^{O(n \; log \; log \; n / log \; n)} }[/math].
Применение
Несмотря на большой (экспоненциальный от n) коэффициент аппроксимации, алгоритм LLL нашел множество применений и позволил решить многие алгоритмические задачи вычислительных наук. Количество и разнообразие приложений слишком велики, чтобы составить их полный список. Ниже приведены некоторые из наиболее показательных приложений в различных областях компьютерных наук.
Первыми мотивирующими приложениями редукции базиса решетки были решение целочисленных программ с фиксированным числом переменных и факторизация многочленов с рациональными коэффициентами (см. [11], [8] и [5, гл. 16]). Другие классические приложения – решение случайных экземпляров задач о суммировании подмножеств с низкой плотностью, вскрытие (усеченных) линейных конгруэнтных псевдослучайных генераторов, одновременная диофантова аппроксимация и опровержение гипотезы Мертенса (см. [8] и [5, гл. 17]).
В последнее время редукция базиса решетки широко использовалась для решения многих задач криптоанализа и теории кодирования, включая взлом нескольких вариантов криптосистемы RSA и алгоритма цифровой подписи DSA, поиск малых решений модулярных уравнений и расшифровку списков кодов китайской теоремы об остатках (Chinese Reminder Theorem, CRT). Обзор недавних вариантов применения, в основном в области криптоанализа, можно найти в работах [7, 13].
Последний класс приложений задач с решетками – это разработка криптографических функций (например, устойчивых к столкновениям хэш-функций, схем шифрования с открытым ключом и т.д.), основанное на очевидной неразрешимости задачи решения [math]\displaystyle{ SVP_\gamma }[/math] в пределах малых коэффициентов аппроксимации. В [12, глава 8] и [13] можно найти обзор таких приложений и указатели на соответствующую литературу. Отличительной особенностью многих таких криптографических функций, основанных на решетках, является доказанная сложность их взлома в среднем, основываясь на предположении о неразрешимости в наихудшем случае лежащей в их основе задачи на решетки.
Открытые вопросы
Основной открытой задачей в вычислительном исследовании решеток является определение сложности приближенных алгоритмов [math]\displaystyle{ SVP_\gamma }[/math] и [math]\displaystyle{ CVP_\gamma }[/math] для коэффициентов аппроксимации [math]\displaystyle{ \gamma = n^c }[/math], полиномиальных относительно ранга решетки. А именно:
• Существуют ли алгоритмы с полиномиальным временем выполнения, которые решают задачу [math]\displaystyle{ SVP_\gamma }[/math] или [math]\displaystyle{ CVP_\gamma }[/math] для полиномиальных коэффициентов [math]\displaystyle{ \gamma = n^c }[/math]? (Нахождение таких алгоритмов даже для очень большой экспоненты c стало бы серьезным прорывом в вычислительных науках).
• Существует ли [math]\displaystyle{ \epsilon \gt 0 }[/math], такое, что аппроксимация [math]\displaystyle{ SVP_\gamma }[/math] или [math]\displaystyle{ CVP_\gamma }[/math] в пределах [math]\displaystyle{ \gamma = n^{\epsilon} }[/math] является NP-трудной? (Самые сильные известные сведения о неаппроксимируемости [4] относятся к коэффициентам вида [math]\displaystyle{ n^{O(1 / log \; log \; n)} }[/math], которые растут быстрее любой полилогарифмической функции, но медленнее любой полиномиальной).
Существует теоретическое доказательство того, что для больших полиномиальных коэффициентов [math]\displaystyle{ \gamma = n^c }[/math] задачи [math]\displaystyle{ SVP_\gamma }[/math] и [math]\displaystyle{ CVP_\gamma }[/math] не являются NP-трудными. В частности, обе задачи принадлежат к классу сложности со AM для коэффициента аппроксимации [math]\displaystyle{ \gamma = O(\sqrt{n/log \; n}) }[/math] (см. [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)
