Задачи теории решёток
— это класс
задач оптимизации
на
решётках
(то есть дискретных аддитивных подгруппах, заданных на множестве
). Гипотетическая плохая разрешимость таких задач является центральным местом для построения стойких
криптосистем
на решётках
. Для приложений в таких криптосистемах обычно рассматриваются решётки на векторных пространствах (часто
) или свободных модулях (часто
).
Для всех задач ниже допустим, что нам даны (кроме других более конкретных входных данных) базис для векторного пространства
V
и
норма
N
. Для норм обычно рассматривается
L
2
. Однако другие нормы, такие как
L
p
), также рассматриваются и появляются в различных результатах
. Ниже в статье
означает длину самого короткого вектора в решётке
L
, то есть
В
ЗКВ
(
англ.
Shortest vector problem
, SVP), для решётки
L
даны
базис
векторного пространства
V
и
норма
N
(часто
L
2
) и нужно найти ненулевой вектор минимальной длины в
V
по норме
N
в решётке
L
. Другими словами, выходом алгоритма должен быть ненулевой вектор
v
, такой, что
.
В
-приближённой версии
ЗКВ
γ
нужно найти ненулевой вектор решётки длины, не превосходящий
.
Трудность
Только точная версия задачи, как известно, является
NP-трудной
для рандомизированного сведе́ния
.
Для решения точной версии ЗКВ для евклидовой нормы известны несколько различных подходов, которые можно разбить на два класса — алгоритмы, требующие суперэкспоненциального времени (
) и
памяти, и алгоритмы, требующие экспоненциального времени и памяти (
), от размерности решётки.
В первом классе алгоритмов наиболее значимы алгоритмы перечисления решётки
и алгоритмы сокращения случайных выборок
, в то время как второй класс включает решеточное просеивание
, вычисление ячеек Вороного на решётке
и дискретные гауссовы распределения
. Открытой проблемой является, существуют ли алгоритмы, решающие точную ЗКВ за обычное экспоненциальное время (
) и требующие память, полиномиально зависящую от размерности решётки
.
Для решения
-приближённой версии
ЗКВ
γ
для
для евклидовой нормы лучший известный подход базируется на использовании
.
Для больших
Алгоритм Ленстры — Ленстры — Ловаса редукции базиса решётки
может найти решение за полиномиальное время от размерности решётки. Для малых значений
обычно используется блочный алгоритм Коркина — Золотарёва (БКЗ,
англ.
Block Korkine-Zolotarev algorithm
, BKZ)
, где вход алгоритма (размер блока
) определяет временну́ю сложность и качество выхода — для больших аппроксимационных коэффициентов
достаточен малый размер блока
и алгоритм завершается быстро.
Для малых
требуется больший
, чтобы найти достаточно короткие вектора решётки, и алгоритм работает дольше. БКЗ-алгоритм внутри использует алгоритм точного ЗКВ в качестве подпрограммы (работающей на решётке размерности, не превосходящей
), и общая сложность тесно связана со стоимостью этих вызовов ЗКВ в размерности
.
GapSVP
Задача
состоит в различении между вариантами ЗКВ, в которых ответ не превосходит 1 или больше
, где
может быть фиксированной функцией от размерности решётки
. Если задан базис решётки, алгоритм должен решить, будет
или
. Подобно другим
, алгоритму разрешены ошибки во всех остальных случаях.
Другой версией задачи является
для некоторых функций
. Входом алгоритма является базис
и число
. Алгоритм обеспечивает, чтобы все вектора в
ортогонализации Грама — Шмидта
имели длину, не меньшую 1, чтобы
и чтобы
, где
— размерность. Алгоритм должен принять, если
и отвергнуть, если
. Для больших
(
) задача эквивалентна
, поскольку
препроцессорный шаг с помощью
алгоритма ЛЛЛ
делает второе условие (а следовательно,
) лишним.
В ЗБВ (
англ.
Closest vector problem
, CVP) для решётки
L
даны бaзис векторного пространства
V
и
метрика
M
(часто
L
2
), а также вектор
v
в
V
, но не обязательно в
L
. Требуется найти вектор в
L
, наиболее близкий к
v
(по мере
M
). В
-приближённой версии
ЗБВ
γ
, нужно найти вектор решётки на расстоянии, не превосходящем
.
Связь с ЗКВ
Задача нахождения ближайшего вектора является обобщением задачи нахождения кратчайшего вектора. Легко показать, что если задан предсказатель для
ЗБВ
γ
(определён ниже), можно
решить
ЗКВ
γ
путём некоторых запросов предсказателю
. Естественный метод поиска кратчайшего вектора путём запросов к предсказателю
ЗБВ
γ
, чтобы найти ближайший вектор, не работает, поскольку 0 является вектором решётки и алгоритм, потенциально, может вернуть 0.
Сведение от
ЗКВ
γ
к
ЗБВ
γ
следующее: Предположим, что входом задачи
ЗКВ
γ
является базис решётки
. Рассмотрим базис
и пусть
будет вектором, который вернул алгоритм
ЗБВ
. Утверждается, что кратчайший вектор в множестве
является кратчайшим вектором в данной решётке.
Трудность
Голдрайх, Миссиансио, Сафра и Seifert показали, что из любой сложности ЗКВ вытекает такая же сложность для
ЗБВ
. Используя средства
, Арора , Babai,
Stern
, Sweedyk показали, что
ЗБВ
трудна для аппроксимации до множителя
, если только не
. Динур, Киндлер, Сафра усилили это, указав NP-трудность с
для
.
Сферическое декодирование
Алгоритм для
ЗБВ
, особенно вариант Финке и Поста
используется, например, для обнаружения данных в беспроводных системах связи с многоканальным входом/многоканальным выходом (
MIMO
) (для кодированных и раскодированных сигналов)
. В этом контексте он называется
сферическим декодированием
.
Алгоритм был применён в области целочисленного разрешения неоднозначности фазы несущей
GNSS
(
GPS
)
. В этой области это называется
LAMBDA-методом
.
GapCVP
Эта задача подобна задаче GapSVP. Для
, входом является базис решётки и вектор
, а алгоритм должен ответить, какое из условий выполняется
существует вектор решётки, такой, что расстояние между ним и
не превосходит 1.
любой вектор решётки находится от
на расстоянии, большем
.
Известные результаты
Задача тривиально содержится в классе
NP
для любого коэффициента аппроксимации.
в 1987 показал, что алгоритмы с детерминированным полиномиальным временем могут решить задачу для
. Айтаи, Кумар, Сивакумар показали, что
вероятностные алгоритмы
могут получить слегка более лучший аппроксимационный коэффициент
.
В 1993 Банашчик показал, что
содержится в
. В 2000 Голдрайх и Голдвассер показали, что
помещает задачу в классы как NP, так и
. В 2005 Ааронов и Реджев показали, что для некоторой константы
задача с
входит в
.
Для нижних границ Динур, Киндлер и Сафра показали в 1998, что задача является NP-трудной для
.
Задача о кратчайших независимых векторах
Если дана решётка L размерности n, алгоритм должен выдать n
линейно независимых
векторов
, таких, что
, где правая часть состоит из всех базисов
решётки.
В
-приближённой версии, если дана решётка L размерности n, алгоритм находит n
линейно независимых
векторов
длины
, где
является
-ым последующим минимумом
.
Декодирование с ограниченным расстоянием
Эта задача подобна ЗБВ. Если дан вектор, такой, что его расстояние от решётки не превосходит
, алгоритм должен выдать ближайший вектор решётки.
Задача покрытия решётки радиусами
Если дан базис для решётки, алгоритм должен найти самое большое расстояние (или, в некоторых версиях, его аппроксимацию) от любого вектора до решётки.
Задача поиска кратчайшего базиса
Многие задачи становятся проще, если входной базис состоит из коротких векторов. Алгоритм, который решает задачу поиска кратчайшего базиса (ПКБ), должен по заданному базису решётки
дать эквивалентный базис
, такой, что длина самого длинного вектора в
настолько коротка, насколько возможно.
Аппроксимированная версия задачи
ПКБ
γ
заключается в поиске базиса, самый длинный вектор которого не превосходит по длине в
раз самого длинного вектора в кратчайшем базисе.
Использование в криптографии
Трудность
задач образует базис для доказательства стойкости большинства криптографических схем. Однако экспериментальные данные наталкивают на предположение, что для большинства NP-трудных задач это свойство отсутствует — они трудны лишь в худшем случае. Для многих задач теории решёток было предположено или доказано, что они трудны в среднем, что делает их привлекательными для криптографических схем. Однако трудность в худшем случае некоторых задач теории решёток используется для создания схем стойкой криптографии. Использование трудности в худшем случае в таких схемах помещает их в класс очень немногих схем, которые, с большой долей вероятности, устойчивы даже для
квантовых компьютеров
.
Вышеприведённые задачи теории решёток легко решаются, если дан «хороший» базис. Цель алгоритмов
по данному базису решётки выдать новый базис, состоящий из относительно коротких почти
ортогональных
векторов.
Алгоритм Ленстры — Ленстры — Ловаса
редукции базиса решётки (ЛЛЛ,
англ.
Lenstra–Lenstra–Lovász lattice basis reduction algorithm
, LLL) был ранним эффективным алгоритмом для этой задачи, который может выдать редуцированный базис решётки за полиномиальное время
. Этот алгоритм и его дальнейшие улучшения были использованы для взлома некоторых криптографических схем, что сформировало его статус как очень важного средства в криптографии. Успех ЛЛЛ на экспериментальных данных привел к вере, что редукция базиса решётки на практике может быть простой задачей. Однако эта вера была разрушена, когда в конце 1990s-х были получены новые результаты о трудности задач теории решёток, начиная с результатов Айтаи
.
В своей основополагающей работе Айтаи показал, что
ЗКВ
был NP-трудным и обнаружил некоторые связи между сложностью в худшем случае и
сложностью в среднем
некоторых задач теории решёток
. Основываясь на этих результатах, Айтаи и Дворк создали
криптосистему с открытым ключом
, секретность которой может быть доказана, используя лишь худший случай трудности определённой версии ЗКВ
, что было первым результатом по созданию защищённых систем с использованием трудности в худшем случае
.
Subhash Khot.
Hardness of approximating the shortest vector problem in lattices // J. ACM. — 2005. —
Т. 52
,
вып. 5
. —
doi
:
.
Miklós Ajtai.
// Proceedings of the thirtieth annual ACM symposium on Theory of computing. — Dallas, Texas, United States: ACM, 1998.
Peter van Emde Boas.
. Technical Report 8104. — University of Amsterdam, Department of Mathematics, Netherlands, 1981.
Chris Peikert.
// Proceedings of the 41st annual ACM symposium on Theory of Computing. — Bethesda, MD, USA: ACM, 2009.
Daniele Micciancio, Shafi Goldwasser.
Complexity of Lattice Problems: A Cryptographic Perspective. — 2002. — Т. 671. — (Kluwer International Series in Engineering and Computer Science). —
ISBN 0792376889
.
Daniele Micciancio, Shafi Goldwasser.
Complexity of Lattice Problems: A Cryptographic Perspective. — Springer US, 2011. — (The Springer International Series in Engineering and Computer Science). —
ISBN 9781461508984
.
Goldreich O., Micciancio D., Safra S., Seifert J. -p.
Approximating shortest lattice vectors is not harder than approximating closest lattice vectors // Inf. Process. Lett.. — 1999. —
Т. 71
,
вып. 2
. —
doi
:
.
Oded Goldreich, Shafi Goldwasser.
// Proceedings of the thirtieth annual ACM symposium on Theory of computing. — Dallas, Texas, United States: ACM, 1998.
Sanjeev Arora, László Babai, Jacques Stern, Z. Sweedyk.
The hardness of approximate optima in lattices, codes, and systems of linear equations // J. Comput. Syst. Sci.. — 1997. —
Т. 54
,
вып. 2
. —
doi
:
.
Dinur I., Kindler G., Safra S.
Approximating CVP to Within Almost-Polynomial Factors is NP-Hard // Combinatorica. — 2003. —
Т. 23
,
вып. 2
. —
doi
:
.
Dinur I., Kindler G., Safra S.
// Proceedings of the 39th Annual Symposium on Foundations of Computer Science. — IEEE Computer Society, 1998. —
ISBN 0-8186-9172-7
.
Fincke U., Pohst M.
Improved Methods for Calculating Vectors of Short Length in a Lattice, Including a Complexity Analysis // Math. Comp.. — 1985. —
Т. 44
,
вып. 170
. —
doi
:
.
Biglieri E., Calderbank R., Constantinides A., Goldsmith A., Paulraj A., Poor H. V.
MIMO Wireless Communications. — Cambridge: Cambridge U. P., 2007.
Ping Wang, Tho Le-Ngoc.
A List Sphere Decoding Algorithm with Improved Radius Setting Strategies // Wireless Personal Communications. — 2011. —
Т. 61
,
вып. 1
. —
doi
:
.
Hassibi A., Boyd S.
Integer Parameter Estimation in Linear Models with Applications to GPS // IEEE Trans. Sig. Proc.. — 1998. —
Т. 46
,
вып. 11
. —
doi
:
.
Miklós Ajtai, Ravi Kumar, D. Sivakumar.
// Proceedings of the thirty-third annual ACM symposium on Theory of computing. — Hersonissos, Greece: ACM, 2001.
Banaszczyk W.
New bounds in some transference theorems in the geometry of numbers //
Math. Ann.
. — 1993. —
Т. 296
,
вып. 1
. —
doi
:
.
Dorit Aharonov, Oded Regev.
Lattice problems in NP
coNP // J. ACM. — 2005. —
Т. 52
,
вып. 5
. —
doi
:
.
Ajtai M.
// Proceedings of the twenty-eighth annual ACM symposium on Theory of computing. — Philadelphia, Pennsylvania, United States: ACM, 1996.
Miklós Ajtai, Cynthia Dwork.
// Proceedings of the twenty-ninth annual ACM symposium on Theory of computing. — El Paso, Texas, United States: ACM, 1997.
Jin-Yi Cai.
The Complexity of Some Lattice Problems
// Algorithmic Number Theory. — 2000. — Т. 1838. —
doi
:
.
Lenstra A. K., Lenstra H. W., Lovász L.
Factoring polynomials with rational coefficients //
Math. Ann.
. — 1982. —
Т. 261
,
вып. 4
. —
doi
:
.
Ravi Kannan.
Improved Algorithms for Integer Programming and Related Lattice Problems
//
. — New York, NY, USA: ACM, 1983. — (STOC). —
ISBN 0897910990
. —
doi
:
.
Nicolas Gama, Phong Q. Nguyen, Oded Regev.
Lattice Enumeration Using Extreme Pruning
//
. — Springer, Berlin, Heidelberg, 2010. —
doi
:
.
Yoshinori Aono, Phong Q. Nguyen.
Random Sampling Revisited: Lattice Enumeration with Discrete Pruning
//
. — Springer, Cham, 2017. —
doi
:
.
Daniele Micciancio, Panagiotis Voulgaris.
Faster Exponential Time Algorithms for the Shortest Vector Problem
//
. — Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, 2010. — С. 1468–1480. — (SODA '10). —
ISBN 9780898716986
.
Daniele Micciancio, Panagiotis Voulgaris.
A Deterministic Single Exponential Time Algorithm for Most Lattice Problems Based on Voronoi Cell Computations
//
. — New York, NY, USA: ACM, 2010a. —
ISBN 9781450300506
. —
doi
:
.
Becker A., Ducas L., Gama N., Laarhoven T.
. — Society for Industrial and Applied Mathematics, 2015. — С. 10–24. — (Proceedings). —
doi
:
.
Divesh Aggarwal, Daniel Dadush, Oded Regev, Noah Stephens-Davidowitz.
Solving the Shortest Vector Problem in 2N Time Using Discrete Gaussian Sampling: Extended Abstract
//
. — New York, NY, USA: ACM, 2015. — (STOC). —
ISBN 9781450335362
. —
doi
:
.
Daniele Micciancio.
. — 2017.
Schnorr C. P.
// Theoretical Computer Science. — 1987. — Vol. 53. —
Вып. 2
. —
doi
:
.
Schnorr C. P., Euchner M.
// Mathematical Programming. — 1994. —
Т. 66
,
вып. 1-3
. —
ISSN
. —
doi
:
.
Claus Peter Schnorr.
Lattice Reduction by Random Sampling and Birthday Methods
//
. — Springer, Berlin, Heidelberg, 2003. —
ISBN 3540364943
. —
doi
:
.
Schnorr C. P.
Factoring integers and computing
via diophantine approximation
// . — 1993. — Т. 13. — С. 171-181.. — (AMS DIMACS series in Disc. Math, and Theoretical Comp. Science).
Agrell E., Eriksson T., Vardy A., Zeger K.
Closest Point Search in Lattices // IEEE Trans. Inform. Theory. — 2002. —
Т. 48
,
вып. 8
. —
doi
:
.
Daniele Micciancio.
// SIAM Journal on Computing. — 2001. —
Т. 30
,
вып. 6
. —
С. 2008–2035
. —
doi
:
.
Phong Q. Nguyen, Jacques Stern.
// Proceedings of the 4th International Symposium on Algorithmic Number Theory. — Springer-Verlag, 2000. — С. 85–112. —
ISBN 3-540-67695-3
.