Проблема с решеткой

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

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

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

Кратчайшая векторная задача (SVP) [ править ]

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

В СВП, А базис из векторного пространства V и нормой N (часто L ² ) приведены для решетки L и необходимо найти кратчайший ненулевой вектор в V , как измерено с помощью N , в L . Другими словами, алгоритм должен вывести ненулевой вектор v такой, что .${\ Displaystyle N (v) = \ 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]${\ Displaystyle 2 ^ {\ omega (п)}}$${\ Displaystyle \ OperatorName {поли} (п)}$${\displaystyle 2^{\Theta (n)}}$Открытая проблема заключается в том, существуют ли алгоритмы для решения точного SVP, работающие за одно экспоненциальное время ( ) и требующие полиномиального масштабирования памяти в размерности решетки. ^[16]${\displaystyle 2^{O(n)}}$

Наиболее известные подходы для решения варианта γ-приближения SVP _γ для евклидовой нормы основаны на использовании редукции базиса решетки . Для больших , то Ленстра-Ленстра-Lovász алгоритм (LLL) можно найти решение в полиномиальное время в решетке размерности. Для меньших значений обычно используется алгоритм Блока Коркина-Золотарева (BKZ) ^{[17] [18] [19]} , где входные данные алгоритма (размер блока ) определяют временную сложность и качество вывода: для больших коэффициентов аппроксимации a достаточно небольшого размера блока , и алгоритм быстро завершается. Для маленьких , больших${\displaystyle \gamma >1}$${\displaystyle \gamma =2^{\Omega (n)}}$${\displaystyle \gamma }$${\displaystyle \beta }$${\displaystyle \gamma }$${\displaystyle \beta }$${\displaystyle \gamma }$${\displaystyle \beta }$необходимы для поиска достаточно коротких векторов решетки, и алгоритм требует больше времени, чтобы найти решение. Алгоритм BKZ внутренне использует точный алгоритм SVP в качестве подпрограммы (работающий в решетках размерности не более ), и его общая сложность тесно связана со стоимостью этих вызовов SVP в размерности .${\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, и что и что где - размерность. Алгоритм должен принимать, если и отклонять, если . Для large ( ) проблема эквивалентна GapSVP _γ, поскольку ^[20] предварительная обработка, выполняемая с использованием алгоритма LLL, делает второе условие (и, следовательно, ) избыточным.${\displaystyle \zeta ,\gamma }$${\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).d}$${\displaystyle \zeta }$${\displaystyle \zeta (n)>2^{n/2}}$${\displaystyle \zeta }$

Ближайшая векторная проблема (CVP) [ править ]

В ЦВД, базис векторного пространства V и метрики М (часто 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}\}}$

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

Goldreich et al. показали, что любая твердость SVP подразумевает такую ​​же твердость для CVP. ^[22] Используя инструменты PCP , Arora et al. показал, что CVP трудно аппроксимировать в пределах фактора, если . ^[23] Dinur et al. усилил это, дав результат NP-твердости с for . ^[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, особенно вариант Fincke и Pohst ^[6] , использовались для обнаружения данных в системах беспроводной связи с множеством входов и множеством выходов ( MIMO ) (для кодированных и некодированных сигналов). ^{[25] [13]} В этом контексте это называется сферическим декодированием из-за внутреннего радиуса, используемого во многих решениях CVP. ^[26]

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

GapCVP [ править ]

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

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

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

Известные результаты [ править ]

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

Шнорр в 1987 году показал, что детерминированные алгоритмы с полиномиальным временем могут решить эту проблему для . ^[28] Ajtai et al. показал, что вероятностные алгоритмы могут достичь немного лучшего коэффициента приближения, равного . ^[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}}}$

Для оценки снизу Dinur et al. в 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-сложных задач не хватает этого свойства: они, вероятно, только в худшем случае. Были выдвинуты гипотезы или доказано, что многие решеточные задачи являются сложными для среднего случая, что делает их привлекательным классом задач для построения криптографических схем. Более того, для создания безопасных криптографических схем использовалась жесткость наихудшего случая некоторых решеточных задач. Использование в таких схемах жесткости наихудшего случая делает их одними из очень немногих схем, которые, скорее всего, безопасны даже против квантовых компьютеров .

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

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

См. Также [ править ]

• Обучение с ошибками
• Краткое целочисленное решение задачи

Ссылки [ править ]

Дальнейшее чтение [ править ]

• Agrell, E .; Eriksson, T .; Варди, А .; Зегер, К. (2002). «Поиск ближайшей точки в решетках» . IEEE Trans. Инф. Теория . 48 (8): 2201–2214. DOI : 10.1109 / TIT.2002.800499 .
• Микчанчо, Даниэле (2001). «Задачу кратчайшего вектора {NP} трудно аппроксимировать с точностью до некоторой константы» . SIAM Journal on Computing . 30 (6): 2008–2035. CiteSeerX  10.1.1.93.6646 . DOI : 10,1137 / S0097539700373039 .
• Nguyen, Phong Q .; Стерн, Жак (2000). «Сокращение решетки в криптологии: обновление» . Материалы 4-го Международного симпозиума по алгоритмической теории чисел . Springer-Verlag. С. 85–112. ISBN 978-3-540-67695-9.