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

''Точечная решетка'' представляет собой множество всех целочисленных линейных комбинаций <math>\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>\mathbf{b}_1, ..., \mathbf{b}_n \in \mathbb{R}^m</math> в m-мерном евклидовом пространстве. Для удобства вычислений векторы решетки <math>\mathbf{b}_1, ..., \mathbf{b}_n</math> часто предполагаются целыми (или рациональными), так что решетка может быть представлена целочисленной матрицей <math>\mathbf{B} = [\mathbf{b}_1, ..., \mathbf{b}_n] \in \mathbb{R}^{m \times n}</math> (называемой ''базисом'') с порождающими векторами в качестве столбцов. Используя матричную нотацию, точки решетки в L(B) удобно представить в виде Bx, где x – целочисленный вектор. Целые числа m и n называются размерностью и рангом решетки, соответственно. Заметим, что любая решетка допускает несколько базисов, но все они имеют одинаковые ранг и размерность.

Основными вычислительными задачами на решетках являются задача о кратчайшем векторе (Shortest Vector Problem, SVP), в которой требуется найти кратчайший ненулевой вектор в данной решетке, и задача о ближайшем векторе (Closest Vector Problem, CVP), в которой требуется найти точку решетки, ближайшую к заданной цели. Обе задачи могут быть определены относительно любой нормы, но евклидова норма kvk = Pi v2i является наиболее распространенной. Также в приложениях вычислительных наук часто встречаются такие нормы, как l\ норма kvk1 = Pi jvij и max норма KVK1 = maxi j v i j. Далее будет рассматриваться евклидова норма.

Поскольку эффективные алгоритмы для точного решения 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).

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