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

Перейти к навигацииПерейти к поиску

Задачи теории решёток — это класс задач оптимизации на решётках (то есть дискретных аддитивных подгруппах, заданных на множестве ). Гипотетическая плохая разрешимость таких задач является центральным местом для построения стойких криптосистем на решётках. Для приложений в таких криптосистемах обычно рассматриваются решётки на векторных пространствах (часто ) или свободных модулях (часто ).

Для всех задач ниже допустим, что нам даны (кроме других более конкретных входных данных) базис для векторного пространства V и норма N. Для норм обычно рассматривается L2. Однако другие нормы, такие как Lp), также рассматриваются и появляются в различных результатах[1]. Ниже в статье означает длину самого короткого вектора в решётке L, то есть

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

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

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

В -приближённой версии ЗКВγ нужно найти ненулевой вектор решётки длины, не превосходящий .

Трудность

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

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

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

Для решения точной версии ЗКВ для евклидовой нормы известны несколько различных подходов, которые можно разбить на два класса — алгоритмы, требующие суперэкспоненциального времени () и памяти, и алгоритмы, требующие экспоненциального времени и памяти (), от размерности решётки. В первом классе алгоритмов наиболее значимы алгоритмы перечисления решётки[4][5][6] и алгоритмы сокращения случайных выборок[7][8], в то время как второй класс включает решеточное просеивание[9][10][11], вычисление ячеек Вороного на решётке[12][13] и дискретные гауссовы распределения[14]. Открытой проблемой является, существуют ли алгоритмы, решающие точную ЗКВ за обычное экспоненциальное время () и требующие память, полиномиально зависящую от размерности решётки[15].

Для решения -приближённой версии ЗКВγ для для евклидовой нормы лучший известный подход базируется на использовании редукции базиса решётки[англ.]. Для больших Алгоритм Ленстры — Ленстры — Ловаса редукции базиса решётки может найти решение за полиномиальное время от размерности решётки. Для малых значений обычно используется блочный алгоритм Коркина — Золотарёва (БКЗ, англ. Block Korkine-Zolotarev algorithm, BKZ)[16][17][18], где вход алгоритма (размер блока ) определяет временну́ю сложность и качество выхода — для больших аппроксимационных коэффициентов достаточен малый размер блока и алгоритм завершается быстро. Для малых требуется больший , чтобы найти достаточно короткие вектора решётки, и алгоритм работает дольше. БКЗ-алгоритм внутри использует алгоритм точного ЗКВ в качестве подпрограммы (работающей на решётке размерности, не превосходящей ), и общая сложность тесно связана со стоимостью этих вызовов ЗКВ в размерности .

GapSVP

Задача состоит в различении между вариантами ЗКВ, в которых ответ не превосходит 1 или больше , где может быть фиксированной функцией от размерности решётки . Если задан базис решётки, алгоритм должен решить, будет или . Подобно другим задачам с предусловиями[англ.], алгоритму разрешены ошибки во всех остальных случаях.

Другой версией задачи является для некоторых функций . Входом алгоритма является базис и число . Алгоритм обеспечивает, чтобы все вектора в ортогонализации Грама — Шмидта имели длину, не меньшую 1, чтобы и чтобы , где — размерность. Алгоритм должен принять, если и отвергнуть, если . Для больших () задача эквивалентна , поскольку[19] препроцессорный шаг с помощью алгоритма ЛЛЛ делает второе условие (а следовательно, ) лишним.

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

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

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

Связь с ЗКВ

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

Сведение от ЗКВγ к ЗБВγ следующее: Предположим, что входом задачи ЗКВγ является базис решётки . Рассмотрим базис и пусть будет вектором, который вернул алгоритм ЗБВ. Утверждается, что кратчайший вектор в множестве является кратчайшим вектором в данной решётке.

Трудность

Голдрайх, Миссиансио, Сафра и Seifert показали, что из любой сложности ЗКВ вытекает такая же сложность для ЗБВ[21]. Используя средства ВПД[англ.], Арора , Babai, Stern, Sweedyk показали, что ЗБВ трудна для аппроксимации до множителя , если только не [22]. Динур, Киндлер, Сафра усилили это, указав NP-трудность с для [23].

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

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

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

GapCVP

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

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

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

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

Клаус Шнорр[англ.] в 1987 показал, что алгоритмы с детерминированным полиномиальным временем могут решить задачу для [27]. Айтаи, Кумар, Сивакумар показали, что вероятностные алгоритмы могут получить слегка более лучший аппроксимационный коэффициент [9].

В 1993 Банашчик показал, что содержится в [28]. В 2000 Голдрайх и Голдвассер показали, что помещает задачу в классы как NP, так и coAM[29]. В 2005 Ааронов и Реджев показали, что для некоторой константы задача с входит в [30].

Для нижних границ Динур, Киндлер и Сафра показали в 1998, что задача является NP-трудной для [31].

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

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

В -приближённой версии, если дана решётка L размерности n, алгоритм находит n линейно независимых векторов длины , где является -ым последующим минимумом .

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

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

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

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

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

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

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

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

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

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

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

См. также

Примечания

Литература

  • Subhash Khot. Hardness of approximating the shortest vector problem in lattices // J. ACM. — 2005. — Т. 52, вып. 5. — doi:10.1145/1089023.1089027.
  • Miklós Ajtai. The shortest vector problem in L2 is NP-hard for randomized reductions // Proceedings of the thirtieth annual ACM symposium on Theory of computing. — Dallas, Texas, United States: ACM, 1998.
  • Peter van Emde Boas. Another NP-complete problem and the complexity of computing short vectors in a lattice. Technical Report 8104. — University of Amsterdam, Department of Mathematics, Netherlands, 1981.
  • Chris Peikert. Public-key cryptosystems from the worst-case shortest vector problem: extended abstract // 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:10.1016/S0020-0190(99)00083-6.
  • Oded Goldreich, Shafi Goldwasser. On the limits of non-approximability of lattice problems // 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:10.1109/SFCS.1993.366815.
  • Dinur I., Kindler G., Safra S. Approximating CVP to Within Almost-Polynomial Factors is NP-Hard // Combinatorica. — 2003. — Т. 23, вып. 2. — doi:10.1007/s00493-003-0019-y.
  • Dinur I., Kindler G., Safra S. Approximating-CVP to within Almost-Polynomial Factors is NP-Hard // Proceedings of the 39th Annual Symposium on Foundations of Computer Science. — IEEE Computer Society, 1998. — ISBN 0-8186-9172-7.

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