Задачи теории решёток

Задачи теории решёток — это класс задач оптимизации на решётках (то есть дискретных аддитивных подгруппах, заданных на множестве $\mathbb {R} ^{n}$). Гипотетическая плохая разрешимость таких задач является центральным местом для построения стойких криптосистем на решётках. Для приложений в таких криптосистемах обычно рассматриваются решётки на векторных пространствах (часто $\mathbb {Q} ^{n}$) или свободных модулях (часто $\mathbb {Z} ^{n}$).

Для всех задач ниже допустим, что нам даны (кроме других более конкретных входных данных) базис для векторного пространства V и норма N. Для норм обычно рассматривается L². Однако другие нормы, такие как L^p), также рассматриваются и появляются в различных результатах. Ниже в статье $\lambda (L)$ означает длину самого короткого вектора в решётке L, то есть

$\lambda (L)=\min _{v\in L\setminus \{\mathbf {0} \}}\|v\|_{N}.$

Задача нахождения кратчайшего вектора (ЗКВ)

Иллюстрация задачи нахождения кратчайшего вектора (базисные векторы показаны синим цветом, кратчайший вектор показан красным).

В ЗКВ (англ. Shortest vector problem, SVP), для решётки L даны базис векторного пространства V и норма N (часто L²) и нужно найти ненулевой вектор минимальной длины в V по норме N в решётке L. Другими словами, выходом алгоритма должен быть ненулевой вектор v, такой, что $N(v)=\lambda (L)$.

В $\gamma$-приближённой версии ЗКВ_γ нужно найти ненулевой вектор решётки длины, не превосходящий $\gamma \lambda (L)$.

Трудность

Только точная версия задачи, как известно, является NP-трудной для рандомизированного сведе́ния.

Для контраста, известно, что эквивалентная задача для равномерных норм, является NP-трудной.

Алгоритмы для евклидовых норм

Для решения точной версии ЗКВ для евклидовой нормы известны несколько различных подходов, которые можно разбить на два класса — алгоритмы, требующие суперэкспоненциального времени ($2^{\omega (n)}$) и $\operatorname {poly} (n)$ памяти, и алгоритмы, требующие экспоненциального времени и памяти ($2^{\Theta (n)}$), от размерности решётки. В первом классе алгоритмов наиболее значимы алгоритмы перечисления решётки и алгоритмы сокращения случайных выборок, в то время как второй класс включает решеточное просеивание, вычисление ячеек Вороного на решётке и дискретные гауссовы распределения. Открытой проблемой является, существуют ли алгоритмы, решающие точную ЗКВ за обычное экспоненциальное время ($2^{O(n)}$) и требующие память, полиномиально зависящую от размерности решётки.

Для решения $\gamma$-приближённой версии ЗКВ_γ для $\gamma >1$ для евклидовой нормы лучший известный подход базируется на использовании редукции базиса решётки. Для больших $\gamma =2^{\Omega (n)}$ Алгоритм Ленстры — Ленстры — Ловаса редукции базиса решётки может найти решение за полиномиальное время от размерности решётки. Для малых значений $\gamma$ обычно используется блочный алгоритм Коркина — Золотарёва (БКЗ, англ. Block Korkine-Zolotarev algorithm, BKZ), где вход алгоритма (размер блока $\beta$) определяет временну́ю сложность и качество выхода — для больших аппроксимационных коэффициентов $\gamma$ достаточен малый размер блока $\beta$ и алгоритм завершается быстро. Для малых $\gamma$ требуется больший $\beta$, чтобы найти достаточно короткие вектора решётки, и алгоритм работает дольше. БКЗ-алгоритм внутри использует алгоритм точного ЗКВ в качестве подпрограммы (работающей на решётке размерности, не превосходящей $\beta$), и общая сложность тесно связана со стоимостью этих вызовов ЗКВ в размерности $\beta$.

GapSVP

Задача $GapSVP_{\beta }$ состоит в различении между вариантами ЗКВ, в которых ответ не превосходит 1 или больше $\beta$, где $\beta$ может быть фиксированной функцией от размерности решётки $n$. Если задан базис решётки, алгоритм должен решить, будет $\lambda (L)\leqslant 1$ или $\lambda (L)>\beta$. Подобно другим задачам с предусловиями, алгоритму разрешены ошибки во всех остальных случаях.

Другой версией задачи является $GapSVP_{\zeta ,\gamma }$ для некоторых функций $\zeta ,\gamma$. Входом алгоритма является базис $B$ и число $d$. Алгоритм обеспечивает, чтобы все вектора в ортогонализации Грама — Шмидта имели длину, не меньшую 1, чтобы $\lambda (L(B))\leqslant \zeta (n)$ и чтобы $1\leqslant d\leqslant \zeta (n)/\gamma (n)$, где $n$ — размерность. Алгоритм должен принять, если $\lambda (L(B))\leqslant d$ и отвергнуть, если $\lambda (L(B))\geqslant \gamma (n).d$. Для больших $\zeta$ ($\zeta (n)>2^{n/2}$) задача эквивалентна $GapSVP_{\gamma }$, поскольку препроцессорный шаг с помощью алгоритма ЛЛЛ делает второе условие (а следовательно, $\zeta$) лишним.

Задача нахождения ближайшего вектора (ЗБВ)

Иллюстрация задачи нахождения ближайшего вектора (базисные вектора показаны синим цветом, ближайший вектор показан красным, внешний вектор показан зелёным).

В ЗБВ (англ. Closest vector problem, CVP) для решётки L даны бaзис векторного пространства V и метрика M (часто L²), а также вектор v в V, но не обязательно в L. Требуется найти вектор в L, наиболее близкий к v (по мере M). В $\gamma$-приближённой версии ЗБВ_γ, нужно найти вектор решётки на расстоянии, не превосходящем $\gamma$.

Связь с ЗКВ

Задача нахождения ближайшего вектора является обобщением задачи нахождения кратчайшего вектора. Легко показать, что если задан предсказатель для ЗБВ_γ (определён ниже), можно решить ЗКВ_γ путём некоторых запросов предсказателю. Естественный метод поиска кратчайшего вектора путём запросов к предсказателю ЗБВ_γ, чтобы найти ближайший вектор, не работает, поскольку 0 является вектором решётки и алгоритм, потенциально, может вернуть 0.

Сведение от ЗКВ_γ к ЗБВ_γ следующее: Предположим, что входом задачи ЗКВ_γ является базис решётки $B=[b_{1},b_{2},\ldots ,b_{n}]$. Рассмотрим базис $B^{i}=[b_{1},\ldots ,2b_{i},\ldots ,b_{n}]$ и пусть $x_{i}$ будет вектором, который вернул алгоритм ЗБВ$\gamma (B^{i},b_{i})$. Утверждается, что кратчайший вектор в множестве $\{x_{i}-b_{i}\}$ является кратчайшим вектором в данной решётке.

Трудность

Голдрайх, Миссиансио, Сафра и Seifert показали, что из любой сложности ЗКВ вытекает такая же сложность для ЗБВ. Используя средства ВПД, Арора , Babai, Stern, Sweedyk показали, что ЗБВ трудна для аппроксимации до множителя $2^{\log ^{1-\epsilon }(n)}$, если только не $\operatorname {NP} \subseteq \operatorname {DTIME} (2^{poly(\log n)})$. Динур, Киндлер, Сафра усилили это, указав NP-трудность с $\epsilon =(\log \log n)^{c}$ для $c<1/2$.

Сферическое декодирование

Алгоритм для ЗБВ, особенно вариант Финке и Поста используется, например, для обнаружения данных в беспроводных системах связи с многоканальным входом/многоканальным выходом (MIMO) (для кодированных и раскодированных сигналов). В этом контексте он называется сферическим декодированием.

Алгоритм был применён в области целочисленного разрешения неоднозначности фазы несущей GNSS (GPS). В этой области это называется LAMBDA-методом.

GapCVP

Эта задача подобна задаче GapSVP. Для $GapCVP_{\beta }$, входом является базис решётки и вектор $v$, а алгоритм должен ответить, какое из условий выполняется

• существует вектор решётки, такой, что расстояние между ним и $v$ не превосходит 1.
• любой вектор решётки находится от $v$ на расстоянии, большем $\beta$.

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

Задача тривиально содержится в классе NP для любого коэффициента аппроксимации.

Клаус Шнорр в 1987 показал, что алгоритмы с детерминированным полиномиальным временем могут решить задачу для $\beta =2^{O(n(\log \log n)^{2}/\log n)}$. Айтаи, Кумар, Сивакумар показали, что вероятностные алгоритмы могут получить слегка более лучший аппроксимационный коэффициент $\beta =2^{O(n\log \log n/\log n)}$.

В 1993 Банашчик показал, что $GapCVP_{n}$ содержится в $NP\cap coNP$. В 2000 Голдрайх и Голдвассер показали, что $\beta ={\sqrt {n/\log n}}$ помещает задачу в классы как NP, так и coAM. В 2005 Ааронов и Реджев показали, что для некоторой константы $c$ задача с $\beta =c{\sqrt {n}}$ входит в $NP\cap coNP$.

Для нижних границ Динур, Киндлер и Сафра показали в 1998, что задача является NP-трудной для $\beta =n^{o(1/\log {\log {n}})}$.

Задача о кратчайших независимых векторах

Если дана решётка L размерности n, алгоритм должен выдать n линейно независимых векторов $v_{1},v_{2},\ldots ,v_{n}$, таких, что $\max \|v_{i}\|<\max _{B}\|b_{i}\|$, где правая часть состоит из всех базисов $B=\{b_{1},\ldots ,b_{n}\}$ решётки.

В $\gamma$-приближённой версии, если дана решётка L размерности n, алгоритм находит n линейно независимых векторов $v_{1},v_{2},\ldots ,v_{n}$ длины $\max ||v_{i}||\leqslant \gamma \lambda _{n}(L)$, где $\lambda _{n}(L)$ является $n$-ым последующим минимумом $L$.

Декодирование с ограниченным расстоянием

Эта задача подобна ЗБВ. Если дан вектор, такой, что его расстояние от решётки не превосходит $\lambda (L)/2$, алгоритм должен выдать ближайший вектор решётки.

Задача покрытия решётки радиусами

Если дан базис для решётки, алгоритм должен найти самое большое расстояние (или, в некоторых версиях, его аппроксимацию) от любого вектора до решётки.

Задача поиска кратчайшего базиса

Многие задачи становятся проще, если входной базис состоит из коротких векторов. Алгоритм, который решает задачу поиска кратчайшего базиса (ПКБ), должен по заданному базису решётки $B$ дать эквивалентный базис $B'$, такой, что длина самого длинного вектора в $B'$ настолько коротка, насколько возможно.

Аппроксимированная версия задачи ПКБ_γ заключается в поиске базиса, самый длинный вектор которого не превосходит по длине в $\gamma$ раз самого длинного вектора в кратчайшем базисе.

Использование в криптографии

Основная статья: Криптография на решётках

Трудность среднего случая задач образует базис для доказательства стойкости большинства криптографических схем. Однако экспериментальные данные наталкивают на предположение, что для большинства NP-трудных задач это свойство отсутствует — они трудны лишь в худшем случае. Для многих задач теории решёток было предположено или доказано, что они трудны в среднем, что делает их привлекательными для криптографических схем. Однако трудность в худшем случае некоторых задач теории решёток используется для создания схем стойкой криптографии. Использование трудности в худшем случае в таких схемах помещает их в класс очень немногих схем, которые, с большой долей вероятности, устойчивы даже для квантовых компьютеров.

Вышеприведённые задачи теории решёток легко решаются, если дан «хороший» базис. Цель алгоритмов редукции базиса по данному базису решётки выдать новый базис, состоящий из относительно коротких почти ортогональных векторов. Алгоритм Ленстры — Ленстры — Ловаса редукции базиса решётки (ЛЛЛ, англ. Lenstra–Lenstra–Lovász lattice basis reduction algorithm, LLL) был ранним эффективным алгоритмом для этой задачи, который может выдать редуцированный базис решётки за полиномиальное время. Этот алгоритм и его дальнейшие улучшения были использованы для взлома некоторых криптографических схем, что сформировало его статус как очень важного средства в криптографии. Успех ЛЛЛ на экспериментальных данных привел к вере, что редукция базиса решётки на практике может быть простой задачей. Однако эта вера была разрушена, когда в конце 1990s-х были получены новые результаты о трудности задач теории решёток, начиная с результатов Айтаи.

В своей основополагающей работе Айтаи показал, что ЗКВ был NP-трудным и обнаружил некоторые связи между сложностью в худшем случае и сложностью в среднем некоторых задач теории решёток. Основываясь на этих результатах, Айтаи и Дворк создали криптосистему с открытым ключом, секретность которой может быть доказана, используя лишь худший случай трудности определённой версии ЗКВ, что было первым результатом по созданию защищённых систем с использованием трудности в худшем случае.

См. также

• Обучение с ошибками

Литература для дальнейшего чтения

• Agrell E., Eriksson T., Vardy A., Zeger K. Closest Point Search in Lattices // IEEE Trans. Inform. Theory. — 2002. — Т. 48, вып. 8. — doi:10.1109/TIT.2002.800499.
• Daniele Micciancio. The Shortest Vector Problem is {NP}-hard to approximate to within some constant // SIAM Journal on Computing. — 2001. — Т. 30, вып. 6. — С. 2008–2035. — doi:10.1137/S0097539700373039.
• Phong Q. Nguyen, Jacques Stern. Lattice Reduction in Cryptology: An Update // Proceedings of the 4th International Symposium on Algorithmic Number Theory. — Springer-Verlag, 2000. — С. 85–112. — ISBN 3-540-67695-3.