Русская Википедия:Задачи теории решёток
Задачи теории решёток — это класс задач оптимизации на решётках (то есть дискретных аддитивных подгруппах, заданных на множестве <math>\mathbb{R}^n</math>). Гипотетическая плохая разрешимость таких задач является центральным местом для построения стойких криптосистем на решётках. Для приложений в таких криптосистемах обычно рассматриваются решётки на векторных пространствах (часто <math>\mathbb{Q}^n</math>) или свободных модулях (часто <math>\mathbb{Z}^n</math>).
Для всех задач ниже допустим, что нам даны (кроме других более конкретных входных данных) базис для векторного пространства V и норма N. Для норм обычно рассматривается L2. Однако другие нормы, такие как Lp), также рассматриваются и появляются в различных результатахШаблон:Sfn. Ниже в статье <math>\lambda(L)</math> означает длину самого короткого вектора в решётке L, то есть
- <math>\lambda(L) = \min_{v \in L \setminus \{\mathbf{0}\}} \|v\|_N.</math>
Задача нахождения кратчайшего вектора (ЗКВ)
В ЗКВ (Шаблон:Lang-en, SVP), для решётки L даны базис векторного пространства V и норма N (часто L2) и нужно найти ненулевой вектор минимальной длины в V по норме N в решётке L. Другими словами, выходом алгоритма должен быть ненулевой вектор v, такой, что <math>N(v)=\lambda(L)</math>.
В <math>\gamma</math>-приближённой версии ЗКВγ нужно найти ненулевой вектор решётки длины, не превосходящий <math>\gamma \lambda(L)</math>.
Трудность
Только точная версия задачи, как известно, является NP-трудной для рандомизированного сведе́нияШаблон:SfnШаблон:Sfn.
Для контраста, известно, что эквивалентная задача для равномерных норм, является NP-труднойШаблон:Sfn.
Алгоритмы для евклидовых норм
Для решения точной версии ЗКВ для евклидовой нормы известны несколько различных подходов, которые можно разбить на два класса — алгоритмы, требующие суперэкспоненциального времени (<math>2^{\omega(n)}</math>) и <math>\operatorname{poly}(n)</math> памяти, и алгоритмы, требующие экспоненциального времени и памяти (<math>2^{\Theta(n)}</math>), от размерности решётки. В первом классе алгоритмов наиболее значимы алгоритмы перечисления решёткиШаблон:SfnШаблон:SfnШаблон:Sfn и алгоритмы сокращения случайных выборокШаблон:SfnШаблон:Sfn, в то время как второй класс включает решеточное просеиваниеШаблон:SfnШаблон:SfnШаблон:Sfn, вычисление ячеек Вороного на решёткеШаблон:SfnШаблон:Sfn и дискретные гауссовы распределенияШаблон:Sfn. Открытой проблемой является, существуют ли алгоритмы, решающие точную ЗКВ за обычное экспоненциальное время (<math>2^{O(n)}</math>) и требующие память, полиномиально зависящую от размерности решёткиШаблон:Sfn.
Для решения <math>\gamma</math>-приближённой версии ЗКВγ для <math>\gamma > 1</math> для евклидовой нормы лучший известный подход базируется на использовании Шаблон:Не переведено 5. Для больших <math>\gamma = 2^{\Omega(n)}</math> Алгоритм Ленстры — Ленстры — Ловаса редукции базиса решётки может найти решение за полиномиальное время от размерности решётки. Для малых значений <math>\gamma</math> обычно используется блочный алгоритм Коркина — Золотарёва (БКЗ, Шаблон:Lang-en, BKZ)Шаблон:SfnШаблон:SfnШаблон:Sfn, где вход алгоритма (размер блока <math>\beta</math>) определяет временну́ю сложность и качество выхода — для больших аппроксимационных коэффициентов <math>\gamma</math> достаточен малый размер блока <math>\beta</math> и алгоритм завершается быстро. Для малых <math>\gamma</math> требуется больший <math>\beta</math>, чтобы найти достаточно короткие вектора решётки, и алгоритм работает дольше. БКЗ-алгоритм внутри использует алгоритм точного ЗКВ в качестве подпрограммы (работающей на решётке размерности, не превосходящей <math>\beta</math>), и общая сложность тесно связана со стоимостью этих вызовов ЗКВ в размерности <math>\beta</math>.
GapSVP
Задача <math>GapSVP_\beta</math> состоит в различении между вариантами ЗКВ, в которых ответ не превосходит 1 или больше <math>\beta</math>, где <math>\beta</math> может быть фиксированной функцией от размерности решётки <math>n</math>. Если задан базис решётки, алгоритм должен решить, будет <math>\lambda(L) \leqslant 1</math> или <math>\lambda(L)>\beta</math>. Подобно другим Шаблон:Не переведено 5, алгоритму разрешены ошибки во всех остальных случаях.
Другой версией задачи является <math>GapSVP_{\zeta,\gamma}</math> для некоторых функций <math>\zeta,\gamma</math>. Входом алгоритма является базис <math>B</math> и число <math>d</math>. Алгоритм обеспечивает, чтобы все вектора в ортогонализации Грама — Шмидта имели длину, не меньшую 1, чтобы <math>\lambda(L(B)) \leqslant \zeta(n) </math> и чтобы <math>1 \leqslant d \leqslant \zeta(n)/\gamma(n)</math>, где <math>n</math> — размерность. Алгоритм должен принять, если <math>\lambda(L(B)) \leqslant d</math> и отвергнуть, если <math>\lambda(L(B)) \geqslant \gamma(n).d</math>. Для больших <math>\zeta</math> (<math>\zeta(n)>2^{n/2}</math>) задача эквивалентна <math>GapSVP_\gamma</math>, посколькуШаблон:Sfn препроцессорный шаг с помощью алгоритма ЛЛЛ делает второе условие (а следовательно, <math>\zeta</math>) лишним.
Задача нахождения ближайшего вектора (ЗБВ)
В ЗБВ (Шаблон:Lang-en, CVP) для решётки L даны бaзис векторного пространства V и метрика M (часто L2), а также вектор v в V, но не обязательно в L. Требуется найти вектор в L, наиболее близкий к v (по мере M). В <math>\gamma</math>-приближённой версии ЗБВγ, нужно найти вектор решётки на расстоянии, не превосходящем <math>\gamma</math>.
Связь с ЗКВ
Задача нахождения ближайшего вектора является обобщением задачи нахождения кратчайшего вектора. Легко показать, что если задан предсказатель для ЗБВγ (определён ниже), можно решить ЗКВγ путём некоторых запросов предсказателюШаблон:Sfn. Естественный метод поиска кратчайшего вектора путём запросов к предсказателю ЗБВγ, чтобы найти ближайший вектор, не работает, поскольку 0 является вектором решётки и алгоритм, потенциально, может вернуть 0.
Сведение от ЗКВγ к ЗБВγ следующее: Предположим, что входом задачи ЗКВγ является базис решётки <math>B=[b_1,b_2,\ldots,b_n]</math>. Рассмотрим базис <math>B^i=[b_1,\ldots,2b_i,\ldots,b_n]</math> и пусть <math>x_i</math> будет вектором, который вернул алгоритм ЗБВ<math>\gamma(B^i, b_i)</math>. Утверждается, что кратчайший вектор в множестве <math>\{x_i-b_i\}</math> является кратчайшим вектором в данной решётке.
Трудность
Голдрайх, Миссиансио, Сафра и Seifert показали, что из любой сложности ЗКВ вытекает такая же сложность для ЗБВШаблон:Sfn. Используя средства Шаблон:Не переведено 5, Арора , Babai, Stern, Sweedyk показали, что ЗБВ трудна для аппроксимации до множителя <math>2^{\log^{1-\epsilon}(n)}</math>, если только не <math>\operatorname{NP} \subseteq \operatorname{DTIME}(2^{poly(\log n)})</math>Шаблон:Sfn. Динур, Киндлер, Сафра усилили это, указав NP-трудность с <math>\epsilon=(\log \log n)^c</math> для <math>c<1/2</math>Шаблон:Sfn.
Сферическое декодирование
Алгоритм для ЗБВ, особенно вариант Финке и ПостаШаблон:Sfn используется, например, для обнаружения данных в беспроводных системах связи с многоканальным входом/многоканальным выходом (MIMO) (для кодированных и раскодированных сигналов)Шаблон:SfnШаблон:Sfn. В этом контексте он называется сферическим декодированиемШаблон:Sfn.
Алгоритм был применён в области целочисленного разрешения неоднозначности фазы несущей GNSS (GPS)Шаблон:Sfn. В этой области это называется LAMBDA-методом.
GapCVP
Эта задача подобна задаче GapSVP. Для <math>GapCVP_\beta</math>, входом является базис решётки и вектор <math>v</math>, а алгоритм должен ответить, какое из условий выполняется
- существует вектор решётки, такой, что расстояние между ним и <math>v</math> не превосходит 1.
- любой вектор решётки находится от <math>v</math> на расстоянии, большем <math>\beta</math>.
Известные результаты
Задача тривиально содержится в классе NP для любого коэффициента аппроксимации.
Шаблон:Iw в 1987 показал, что алгоритмы с детерминированным полиномиальным временем могут решить задачу для <math>\beta=2^{O(n(\log \log n)^2/\log n)}</math>Шаблон:Sfn. Айтаи, Кумар, Сивакумар показали, что вероятностные алгоритмы могут получить слегка более лучший аппроксимационный коэффициент <math>\beta=2^{O(n \log \log n/\log n)}</math>Шаблон:Sfn.
В 1993 Банашчик показал, что <math>GapCVP_n</math> содержится в <math>NP \cap coNP</math>Шаблон:Sfn. В 2000 Голдрайх и Голдвассер показали, что <math>\beta=\sqrt{n/\log n}</math> помещает задачу в классы как NP, так и coAMШаблон:Sfn. В 2005 Ааронов и Реджев показали, что для некоторой константы <math>c</math> задача с <math>\beta=c\sqrt{n}</math> входит в <math>NP \cap coNP</math>Шаблон:Sfn.
Для нижних границ Динур, Киндлер и Сафра показали в 1998, что задача является NP-трудной для <math>\beta=n^{o(1/\log{\log{n}})}</math>Шаблон:Sfn.
Задача о кратчайших независимых векторах
Если дана решётка L размерности n, алгоритм должен выдать n линейно независимых векторов <math>v_1, v_2, \ldots, v_n</math>, таких, что <math>\max \|v_i\|< \max_{B} \|b_i\|</math>, где правая часть состоит из всех базисов <math>B=\{b_1,\ldots,b_n\}</math> решётки.
В <math>\gamma</math>-приближённой версии, если дана решётка L размерности n, алгоритм находит n линейно независимых векторов <math>v_1, v_2,\ldots, v_n</math> длины <math>\max||v_i||\leqslant \gamma \lambda_n(L)</math>, где <math>\lambda_n(L)</math> является <math>n</math>-ым последующим минимумом <math>L</math>.
Декодирование с ограниченным расстоянием
Эта задача подобна ЗБВ. Если дан вектор, такой, что его расстояние от решётки не превосходит <math>\lambda(L)/2</math>, алгоритм должен выдать ближайший вектор решётки.
Задача покрытия решётки радиусами
Если дан базис для решётки, алгоритм должен найти самое большое расстояние (или, в некоторых версиях, его аппроксимацию) от любого вектора до решётки.
Задача поиска кратчайшего базиса
Многие задачи становятся проще, если входной базис состоит из коротких векторов. Алгоритм, который решает задачу поиска кратчайшего базиса (ПКБ), должен по заданному базису решётки <math>B</math> дать эквивалентный базис <math>B'</math>, такой, что длина самого длинного вектора в <math>B'</math> настолько коротка, насколько возможно.
Аппроксимированная версия задачи ПКБγ заключается в поиске базиса, самый длинный вектор которого не превосходит по длине в <math>\gamma</math> раз самого длинного вектора в кратчайшем базисе.
Использование в криптографии
Трудность Шаблон:Не переведено 5 задач образует базис для доказательства стойкости большинства криптографических схем. Однако экспериментальные данные наталкивают на предположение, что для большинства NP-трудных задач это свойство отсутствует — они трудны лишь в худшем случае. Для многих задач теории решёток было предположено или доказано, что они трудны в среднем, что делает их привлекательными для криптографических схем. Однако трудность в худшем случае некоторых задач теории решёток используется для создания схем стойкой криптографии. Использование трудности в худшем случае в таких схемах помещает их в класс очень немногих схем, которые, с большой долей вероятности, устойчивы даже для квантовых компьютеров.
Вышеприведённые задачи теории решёток легко решаются, если дан «хороший» базис. Цель алгоритмов Шаблон:Не переведено 5 по данному базису решётки выдать новый базис, состоящий из относительно коротких почти ортогональных векторов. Алгоритм Ленстры — Ленстры — Ловаса редукции базиса решётки (ЛЛЛ, Шаблон:Lang-en, LLL) был ранним эффективным алгоритмом для этой задачи, который может выдать редуцированный базис решётки за полиномиальное времяШаблон:Sfn. Этот алгоритм и его дальнейшие улучшения были использованы для взлома некоторых криптографических схем, что сформировало его статус как очень важного средства в криптографии. Успех ЛЛЛ на экспериментальных данных привел к вере, что редукция базиса решётки на практике может быть простой задачей. Однако эта вера была разрушена, когда в конце 1990s-х были получены новые результаты о трудности задач теории решёток, начиная с результатов АйтаиШаблон:Sfn.
В своей основополагающей работе Айтаи показал, что ЗКВ был NP-трудным и обнаружил некоторые связи между сложностью в худшем случае и сложностью в среднем некоторых задач теории решётокШаблон:Sfn. Основываясь на этих результатах, Айтаи и Дворк создали криптосистему с открытым ключом, секретность которой может быть доказана, используя лишь худший случай трудности определённой версии ЗКВШаблон:Sfn, что было первым результатом по созданию защищённых систем с использованием трудности в худшем случаеШаблон:Sfn.
См. также
Примечания
Литература
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Статья
Литература для дальнейшего чтения
