Проблема решетки

Задача оптимизации в информатике

В информатике решетчатые задачи представляют собой класс задач оптимизации , связанных с математическими объектами, называемыми решетками . Предполагаемая неразрешимость таких задач является центральной для построения безопасных криптосистем на основе решеток : решетчатые задачи являются примером NP-трудных задач, которые, как было показано, являются трудными в среднем случае , что является тестовым случаем для безопасности криптографических алгоритмов. Кроме того, некоторые решетчатые задачи, которые являются трудными в худшем случае, могут быть использованы в качестве основы для чрезвычайно безопасных криптографических схем. Использование трудности в худшем случае в таких схемах делает их одними из немногих схем, которые, скорее всего, безопасны даже против квантовых компьютеров . Для приложений в таких криптосистемах обычно рассматриваются решетки над векторными пространствами (часто ) или свободными модулями (часто ). ${\displaystyle \mathbb {Q} ^{n}}$ ${\displaystyle \mathbb {Z} ^{n}}$

Для всех задач ниже предположим, что нам даны (в дополнение к другим более конкретным входным данным) базис для векторного пространства V и норма N . Обычно рассматриваемая норма — это евклидова норма L 2 . Однако другие нормы (такие как L p ) также рассматриваются и появляются в различных результатах. ^[1]

В этой статье будем обозначать длину самого короткого ненулевого вектора в решетке L : то есть, ${\displaystyle \lambda (L)}$

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

Задача о кратчайшем векторе (SVP)

Это иллюстрация задачи о кратчайшем векторе (базисные векторы выделены синим цветом, кратчайший вектор — красным).

В SVP базис векторного пространства V и норма N (часто L 2 ) задаются для решетки L , и необходимо найти кратчайший ненулевой вектор в V , измеряемый N , в L . Другими словами, алгоритм должен выводить ненулевой вектор v такой, что ⁠ ⁠ ${\displaystyle \|v\|_{N}=\lambda (L)}$ .

В версии γ-приближения SVP _γ необходимо найти ненулевой вектор решетки длины не более для заданного ⁠ ⁠ . ${\displaystyle \gamma \cdot \lambda (L)}$ ${\displaystyle \gamma \geq 1}$

Результаты твердости

Известно, что точная версия проблемы является NP-трудной только для рандомизированных сокращений. ^{[2] [3]} Напротив, известно, что соответствующая проблема относительно равномерной нормы является NP-трудной . ^[4]

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

Для решения точной версии SVP в евклидовой норме известно несколько различных подходов, которые можно разделить на два класса: алгоритмы, требующие сверхэкспоненциального времени ( ) и памяти, и алгоритмы, требующие как экспоненциального времени, так и пространства ( ) в решетчатом измерении. Первый класс алгоритмов, в частности, включает решетчатое перечисление ^{[5] [6] [7]} и случайное сокращение выборки, ^{[8] [9],} в то время как последний включает решетчатое просеивание, ^{[10] [11] [12]} вычисление ячейки Вороного решетки, ^{[13] [14]} и дискретную гауссовскую выборку. ^[15] Открытая проблема заключается в том, существуют ли алгоритмы для решения точной SVP, работающие за одно экспоненциальное время ( ) и требующие полиномиального масштабирования памяти в решетчатом измерении. ^[16] ${\displaystyle 2^{\omega (n)}}$ ${\displaystyle \operatorname {poly} (n)}$ ${\displaystyle 2^{\Theta (n)}}$ ${\displaystyle 2^{O(n)}}$

Для решения γ-аппроксимационной версии SVP _γ для для евклидовой нормы наиболее известные подходы основаны на использовании редукции базиса решетки . Для больших ⁠ ⁠ алгоритм Ленстры–Ленстры–Ловаса (LLL) может найти решение за время, полиномиальное по размерности решетки. Для меньших значений обычно используется алгоритм Блока Коркина-Золотарева (BKZ) ^{[17] [18] [19]} , где входные данные для алгоритма (размер блока ) определяют временную сложность и качество вывода: для больших факторов аппроксимации достаточно небольшого размера блока , и алгоритм быстро завершает работу. Для малых требуются большие для поиска достаточно коротких векторов решетки, и алгоритму требуется больше времени для поиска решения. Алгоритм BKZ внутренне использует точный алгоритм SVP в качестве подпрограммы (работающий в решетках размерности не более ), и его общая сложность тесно связана со стоимостью этих вызовов SVP в размерности ⁠ ⁠ . ${\displaystyle \gamma >1}$ ${\displaystyle \gamma =2^{\Omega (n)}}$ ${\displaystyle \gamma }$ ${\displaystyle \beta }$ ${\displaystyle \gamma }$ ${\displaystyle \beta }$ ${\displaystyle \gamma }$ ${\displaystyle \beta }$ ${\displaystyle \beta }$ ${\displaystyle \beta }$

GapSVP

Задача GapSVP _β состоит в различении случаев SVP, в которых длина самого короткого вектора не превышает ⁠ ⁠ , где может быть фиксированной функцией размерности решетки ⁠ ⁠ . При наличии основы для решетки алгоритм должен решить, или ⁠ ⁠ . Как и в других задачах обещаний , алгоритм может ошибаться во всех других случаях. ${\displaystyle 1}$ ${\displaystyle \beta }$ ${\displaystyle \beta }$ ${\displaystyle n}$ ${\displaystyle \lambda (L)\leq 1}$ ${\displaystyle \lambda (L)>\beta }$

Еще одна версия задачи — GapSVP _ζ,γ для некоторых функций ζ и γ. Входными данными для алгоритма являются базис и число . Гарантируется, что все векторы в ортогонализации Грама–Шмидта имеют длину не менее 1, и что и что ⁠ ⁠ , где — размерность. Алгоритм должен принимать , если ⁠ ⁠ , и отклонять , если ⁠ ⁠ . Для больших (т.е. ⁠ ​​⁠ ) задача эквивалентна GapSVP _γ , поскольку ^[20] предварительная обработка, выполненная с использованием алгоритма LLL, делает второе условие (и, следовательно, ⁠ ⁠ ) избыточным. ${\displaystyle B}$ ${\displaystyle d}$ ${\displaystyle \lambda (L(B))\leq \zeta (n)}$ ${\displaystyle 1\leq d\leq \zeta (n)/\gamma (n)}$ ${\displaystyle n}$ ${\displaystyle \lambda (L(B))\leq d}$ ${\displaystyle \lambda (L(B))\geq \gamma (n)\cdot d}$ ${\displaystyle \zeta }$ ${\displaystyle \zeta (n)>2^{n/2}}$ ${\displaystyle \zeta }$

Задача о ближайшем векторе (CVP)

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

В CVP базис векторного пространства V и метрика M (часто L 2 ) задаются для решетки L , а также вектор v в V , но не обязательно в L . Требуется найти вектор в L , ближайший к v (измеряемый M ). В версии CVP _γ с -приближением необходимо найти вектор решетки на расстоянии не более . ${\displaystyle \gamma }$ ${\displaystyle \gamma }$

Отношения со старшим вице-президентом

Задача о ближайшем векторе является обобщением задачи о кратчайшем векторе. Легко показать, что при наличии оракула для CVP _γ (определенного ниже) можно решить SVP _γ , сделав несколько запросов к оракулу. ^[21] Наивный метод поиска кратчайшего вектора путем вызова оракула CVP _γ для поиска ближайшего вектора к 0 не работает, поскольку 0 сам по себе является вектором решетки, и алгоритм потенциально может вывести 0.

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

Результаты твердости

Голдрайх и др. показали, что любая твердость SVP подразумевает такую ​​же твердость для CVP. ^[22] Используя инструменты PCP , Арора и др. показали, что CVP трудно аппроксимировать с точностью до множителя , если только . ^[23] Динур и др. усилили это, предоставив результат NP-твердости при . [ ^24] ${\displaystyle 2^{\log ^{1-\epsilon }(n)}}$ ${\displaystyle \operatorname {NP} \subseteq \operatorname {DTIME} (2^{\operatorname {poly} (\log n)})}$ ${\displaystyle \epsilon =(\log \log n)^{c}}$ ${\displaystyle c<1/2}$

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

Алгоритмы для CVP, особенно вариант Финке и Поста, ^[6] использовались для обнаружения данных в беспроводных системах связи с множественными входами и множественными выходами ( MIMO ) (для кодированных и некодированных сигналов). ^{[25] [13]} В этом контексте это называется сферическим декодированием из-за радиуса, используемого внутри многих решений CVP. ^[26]

Он был применен в области разрешения целочисленной неоднозначности фазовой несущей GNSS (GPS). ^[27] В этой области он называется методом LAMBDA . В той же области общая задача CVP называется Integer Least Squares .

GapCVP

Эта проблема похожа на проблему GapSVP. Для GapSVP _β входные данные состоят из базиса решетки и вектора , а алгоритм должен ответить, выполняется ли одно из следующих условий: ${\displaystyle v}$

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

Противоположным условием является то, что ближайший вектор решетки находится на расстоянии , отсюда и название Gap CVP. ${\displaystyle 1<\lambda (L)\leq \beta }$

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

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

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

В 1993 году Банащик показал, что GapCVP _n находится в . ^[29] В 2000 году Голдрайх и Голдвассер показали, что помещает проблему как в NP, так и в coAM . ^[30] В 2005 году Ааронов и Регев показали, что для некоторой константы проблема с находится в . ^[31] ${\displaystyle {\mathsf {NP\cap coNP}}}$ ${\displaystyle \beta ={\sqrt {n/\log n}}}$ ${\displaystyle c}$ ${\displaystyle \beta =c{\sqrt {n}}}$ ${\displaystyle {\mathsf {NP\cap coNP}}}$

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

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

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

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

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

Эта задача похожа на CVP. Если задан вектор, расстояние от которого до решетки не превышает , алгоритм должен вывести ближайший к нему вектор решетки. ${\displaystyle \lambda (L)/2}$

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

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

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

Многие проблемы становятся проще, если входной базис состоит из коротких векторов. Алгоритм, который решает задачу кратчайшего базиса (SBP), должен, учитывая решетчатый базис ⁠ ⁠ ${\displaystyle B}$ , выводить эквивалентный базис таким образом, чтобы длина самого длинного вектора в была как можно короче. ${\displaystyle B'}$ ${\displaystyle B'}$

Аппроксимационная версия задачи SBP _γ состоит в нахождении базиса, самый длинный вектор которого в максимальное количество раз длиннее самого длинного вектора в самом коротком базисе. ${\displaystyle \gamma }$

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

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

Вышеуказанные проблемы с решеткой легко решить, если алгоритму предоставлен «хороший» базис. Алгоритмы редукции решетки направлены на то, чтобы, имея базис для решетки, вывести новый базис, состоящий из относительно коротких, почти ортогональных векторов. Алгоритм редукции решеточной базы Ленстры–Ленстры–Ловаса (LLL) был ранним эффективным алгоритмом для этой задачи, который мог выводить почти редуцированный базис решетки за полиномиальное время. ^[33] Этот алгоритм и его дальнейшие усовершенствования использовались для взлома нескольких криптографических схем, что установило его статус очень важного инструмента в криптоанализе. Успех LLL на экспериментальных данных привел к убеждению, что редукцию решетки можно легко решить на практике; однако это убеждение было подвергнуто сомнению в конце 1990-х годов, когда было получено несколько новых результатов о сложности проблем с решеткой, начиная с результата Аджтая . ^[2]

В своих основополагающих работах Аджтай показал, что задача SVP является NP-трудной, и обнаружил некоторые связи между сложностью в худшем случае и сложностью в среднем случае некоторых задач на решетке. ^{[2] [3]} Основываясь на этих результатах, Аджтай и Дворк создали криптосистему с открытым ключом , безопасность которой можно было доказать, используя только сложность в худшем случае определенной версии SVP, ^[34] таким образом, сделав ее первым результатом, в котором использовалась сложность в худшем случае для создания защищенных систем. ^[35]

Смотрите также

• Обучение на ошибках
• Задача с коротким целым числом

Ссылки

1. Хот, Субхаш (2005). «Трудность аппроксимации задачи о кратчайшем векторе в решетках». J. ACM . 52 (5): 789–808. doi :10.1145/1089023.1089027. S2CID  13438130.
2. Ajtai, M. (1996). "Generating hard instances of grill problems". Труды Двадцать восьмого ежегодного симпозиума ACM по теории вычислений . Филадельфия, Пенсильвания, США: ACM. стр. 99–108. doi :10.1145/237814.237838. ISBN 978-0-89791-785-8. S2CID  6864824.
3. Ajtai, Miklós (1998). "Проблема кратчайшего вектора в L2 является NP-трудной для рандомизированных сокращений". Труды тридцатого ежегодного симпозиума ACM по теории вычислений . Даллас, Техас, США: ACM. стр. 10–19. doi :10.1145/276698.276705. ISBN 978-0-89791-962-3. S2CID  4503998.
4. ван Эмде Боас, Питер (1981). «Еще одна NP-полная задача и сложность вычисления коротких векторов в решетке». Технический отчет 8104. Амстердамский университет, математический факультет, Нидерланды.
5. Каннан, Рави (1983). «Улучшенные алгоритмы для целочисленного программирования и связанных с ними решетчатых задач». Труды пятнадцатого ежегодного симпозиума ACM по теории вычислений — STOC '83 . Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 193–206. doi :10.1145/800061.808749. ISBN 978-0-89791-099-6. S2CID  18181112.
6. Fincke, U.; Pohst, M. (1985). «Улучшенные методы вычисления векторов короткой длины в решетке, включая анализ сложности». Math. Comp . 44 (170): 463–471. doi : 10.1090/S0025-5718-1985-0777278-8 .
7. Гама, Николас; Нгуен, Фонг К.; Регев, Одед (2010-05-30). «Перечисление решеток с использованием экстремального отсечения». Достижения в криптологии – EUROCRYPT 2010. Конспект лекций по информатике. Том 6110. Springer, Берлин, Гейдельберг. С. 257–278. doi :10.1007/978-3-642-13190-5_13. ISBN 978-3-642-13189-9. S2CID  1938519.
8. Шнорр, Клаус Питер (27.02.2003). «Редукция решетки случайной выборкой и методами дней рождения». Stacs 2003. Конспект лекций по информатике. Том 2607. Springer, Берлин, Гейдельберг. С. 145–156. CiteSeerX 10.1.1.137.4293 . doi :10.1007/3-540-36494-3_14. ISBN  978-3-540-36494-8.
9. Aono, Yoshinori; Nguyen, Phong Q. (2017-04-30). "Random Sampling Revisited: Lattice Enumeration with Discrete Pruning". Advances in Cryptology – EUROCRYPT 2017 (PDF) . Lecture Notes in Computer Science. Vol. 10211. Springer, Cham. pp. 65–102. doi :10.1007/978-3-319-56614-6_3. ISBN 978-3-319-56613-9. S2CID  39082279.
10. Ajtai, Miklós; Kumar, Ravi; Sivakumar, D. (2001). "Алгоритм решета для задачи о кратчайшем векторе решетки". Труды тридцать третьего ежегодного симпозиума ACM по теории вычислений . Херсониссос, Греция: ACM. стр. 601–610. doi :10.1145/380752.380857. ISBN 1-58113-349-9. S2CID  14982298.
11. Micciancio, Daniele; Voulgaris, Panagiotis (2010). "Быстрые экспоненциальные алгоритмы для задачи поиска кратчайших векторов". Труды двадцать первого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . SODA '10. Филадельфия, Пенсильвания, США: Общество промышленной и прикладной математики. стр. 1468–1480. doi : 10.1137/1.9781611973075.119 . ISBN 978-0-89871-698-6. S2CID  90084.
12. Беккер, А.; Дукас, Л.; Гама, Н.; Лаарховен, Т. (2015-12-21). «Новые направления в поиске ближайшего соседа с приложениями к решеточному просеиванию». Труды двадцать седьмого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам. Общество промышленной и прикладной математики. стр. 10–24. doi :10.1137/1.9781611974331.ch2. ISBN 978-1-61197-433-1.
13. Агрелл, Э.; Эрикссон, Т.; Варди, А.; Зегер, К. (2002). «Поиск ближайшей точки в решетках» (PDF) . IEEE Trans. Inf. Theory . 48 (8): 2201–2214. doi :10.1109/TIT.2002.800499.
14. Micciancio, Daniele; Voulgaris, Panagiotis (2010). "Детерминированный алгоритм с одним экспоненциальным временем для большинства решеточных задач на основе вычислений ячеек Вороного". Труды сорок второго симпозиума ACM по теории вычислений . STOC '10. Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 351–358. CiteSeerX 10.1.1.705.3304 . doi :10.1145/1806689.1806739. ISBN  978-1-4503-0050-6. S2CID  2449948.
15. Аггарвал, Дивиш; Дадуш, Даниэль; Регев, Одед; Стивенс-Давидовиц, Ноа (2015). «Решение задачи поиска кратчайшего вектора за 2 ⁿ времени с использованием дискретной гауссовой выборки». Труды сорок седьмого ежегодного симпозиума ACM по теории вычислений. STOC '15. Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 733–742. doi :10.1145/2746539.2746606. ISBN 978-1-4503-3536-2. S2CID  10214330.
16. Micciancio, Daniele (2017-07-01). «Криптография на решетке – задача о кратчайшем векторе».
17. Шнорр, CP (1987-01-01). "Иерархия алгоритмов редукции базиса решетки за полиномиальное время". Теоретическая информатика . 53 (2): 201–224. doi : 10.1016/0304-3975(87)90064-8 .
18. Шнорр, К. П.; Эухнер, М. (1994-08-01). "Редукция базиса решетки: улучшенные практические алгоритмы и решение задач на сумму подмножеств" (PDF) . Математическое программирование . 66 (1–3): 181–199. doi :10.1007/bf01581144. ISSN  0025-5610. S2CID  15386054.
19. Чен, Юаньми; Нгуен, Фонг К. (2011-12-04). "BKZ 2.0: Лучшая оценка безопасности решеток". Достижения в криптологии – ASIACRYPT 2011. Конспект лекций по информатике. Том 7073. Springer, Берлин, Гейдельберг. С. 1–20. doi :10.1007/978-3-642-25385-0_1. ISBN 978-3-642-25384-3.
20. Peikert, Chris (2009). "Public-key cryptosystems from the worst-case shortest vector problem: extended abstract". Труды 41-го ежегодного симпозиума ACM по теории вычислений. Бетесда, Мэриленд, США: ACM. стр. 333–342. doi :10.1145/1536414.1536461. ISBN 978-1-60558-506-2. S2CID  1864880.
21. Миччанчо, Даниэле; Гольдвассер, Шафи (2002). Сложность решеточных задач . Спрингер.
22. Goldreich, O.; et al. (1999). «Аппроксимация кратчайших векторов решетки не сложнее, чем аппроксимация ближайших векторов решетки». Inf. Process. Lett . 71 (2): 55–61. doi :10.1016/S0020-0190(99)00083-6.
23. Арора, Санджив и др. (1993). «Труды 34-й ежегодной конференции IEEE 1993 года по основам компьютерной науки». J. Comput. Syst. Sci . Vol. 54. pp. 317–331. doi :10.1109/SFCS.1993.366815. ISBN 978-0-8186-4370-5. S2CID  44988406.
24. Динур, И.; и др. (2003). «Аппроксимация CVP с точностью до почти полиномиальных факторов является NP-трудной». Combinatorica . 23 (2): 205–243. doi :10.1007/s00493-003-0019-y. S2CID  45754954.
25. Biglieri, E.; Calderbank, R.; Constantinides, Anthony G .; Goldsmith, A.; Paulraj, A.; Poor, HV (2007). Беспроводная связь MIMO . Кембридж: Cambridge UP
26. Ван, Пин; Ле-Нгок, Тхо (2011). «Алгоритм декодирования сферы списка с улучшенными стратегиями установки радиуса». Беспроводная персональная связь . 61 (1): 189–200. doi :10.1007/s11277-010-0018-4. S2CID  30919872.
27. Хассиби, А.; Бойд, С. (1998). «Оценка целочисленных параметров в линейных моделях с приложениями к GPS». IEEE Trans. Sig. Proc . 46 (11): 2938–2952. Bibcode : 1998ITSP...46.2938H. CiteSeerX 10.1.1.114.7246 . doi : 10.1109/78.726808. 
28. Шнорр, CP "Разложение целых чисел на множители и вычисление дискретных логарифмов с помощью диофантовых приближений". Advances in Cryptology – Proceedings of Eurocrypt '91 .
29. Банащик, В. (1993). «Новые границы в некоторых теоремах переноса в геометрии чисел». Math. Ann. 296 (1): 625–635. doi :10.1007/BF01445125. S2CID  13921988.
30. Goldreich, Oded; Goldwasser, Shafi (1998). "О пределах неаппроксимируемости решеточных задач". Труды тридцатого ежегодного симпозиума ACM по теории вычислений . Даллас, Техас, США: ACM. стр. 1–9. doi :10.1145/276698.276704. ISBN 0-89791-962-9. S2CID  3051993.
31. Ааронов, Дорит; Одед Регев (2005). «Решеточные задачи в NP coNP». Дж. АКМ . 52 (5): 749–765. CiteSeerX 10.1.1.205.3730 . дои : 10.1145/1089023.1089025. S2CID  1669286. ${\displaystyle \cap }$ 
32. Динур, И.; Киндлер, Г.; Сафра, С. (1998). «Аппроксимация CVP с точностью до почти полиномиальных факторов является NP-трудной». Труды 39-го ежегодного симпозиума по основам компьютерной науки . IEEE Computer Society. стр. 99. ISBN 978-0-8186-9172-0.
33. Lenstra, AK; Lenstra, HW Jr.; Lovász, L. (1982). «Разложение многочленов с рациональными коэффициентами» (PDF) . Math. Ann. 261 (4): 515–534. doi :10.1007/BF01457454. S2CID  5701340. Архивировано из оригинала (PDF) 2011-07-17.
34. Ajtai, Miklós; Dwork, Cynthia (1997). "Криптосистема с открытым ключом и эквивалентностью в худшем и среднем случае". Труды Двадцать девятого ежегодного симпозиума ACM по теории вычислений . Эль-Пасо, Техас, США: ACM. стр. 284–293. doi :10.1145/258533.258604. ISBN 0-89791-888-6. S2CID  9918417.
35. Cai, Jin-Yi (2000). «Сложность некоторых решеточных задач». Алгоритмическая теория чисел . Конспект лекций по информатике. Том 1838. С. 1–32. doi :10.1007/10722028_1. ISBN 978-3-540-67695-9.

Дальнейшее чтение

• Агрелл, Э.; Эрикссон, Т.; Варди, А.; Зегер, К. (2002). «Поиск ближайшей точки в решетках» (PDF) . IEEE Trans. Inf. Theory . 48 (8): 2201–2214. doi :10.1109/TIT.2002.800499.
• Micciancio, Daniele (2001). «Проблема кратчайшего вектора {NP}-трудна для приближения с точностью до некоторой константы». SIAM Journal on Computing . 30 (6): 2008–2035. CiteSeerX  10.1.1.93.6646 . doi :10.1137/S0097539700373039. S2CID  42794945.
• Нгуен, Фонг К.; Стерн, Жак (2000). «Редукция решетки в криптологии: обновление». Труды 4-го Международного симпозиума по алгоритмической теории чисел . Springer-Verlag. С. 85–112. ISBN 978-3-540-67695-9.