В информатике , решетчатые проблемы представляют собой класс оптимизационных задач , связанных с математическими объектами , называемых решетками . Предполагаемая неразрешимость таких проблем играет центральную роль в построении защищенных криптосистем на основе решеток : решетчатые проблемы являются примером NP-сложных проблем, которые, как было показано, являются сложными для среднего случая, обеспечивая контрольный пример безопасности криптографических алгоритмов. Кроме того, некоторые проблемы решетки, которые в наихудшем случае трудны, могут быть использованы в качестве основы для чрезвычайно безопасных криптографических схем. Использование в таких схемах жесткости наихудшего случая делает их одними из очень немногих схем, которые, скорее всего, защищены даже отквантовые компьютеры . Для приложений в таких криптосистемах решетки над векторным пространством (часто) или бесплатные модули (часто) обычно считаются.
Для всех приведенных ниже проблем, предположит , что нам дано (в дополнении к другим , более конкретным материалам) в основе для векторного пространства V и нормы N . Обычно рассматриваемой нормой является евклидова норма L 2 . Однако другие нормы (например, L p ) также учитываются и отражаются во множестве результатов. [1] Пустьобозначим длину кратчайшего ненулевого вектора в решетке L , т. е.
Кратчайшая векторная задача (SVP)
В СВП, А базис из векторного пространства V и нормой N (часто L 2 ) приведены для решетки L и необходимо найти кратчайший ненулевой вектор в V , как измерено с помощью N , в L . Другими словами, алгоритм должен вывести ненулевой вектор v такой, что.
В варианте γ-приближения SVP γ необходимо найти ненулевой вектор решетки длины не более для данного .
Результаты твердости
Точная версия проблемы известна только как NP-трудная для рандомизированных редукций. [2] [3]
Напротив, соответствующая задача относительно равномерной нормы, как известно, NP-трудна . [4]
Алгоритмы для евклидовой нормы
Для решения точной версии SVP при евклидовой норме известно несколько различных подходов, которые можно разделить на два класса: алгоритмы, требующие сверхэкспоненциального времени () а также память и алгоритмы, требующие как экспоненциального времени, так и пространства () в размерности решетки. Первый класс алгоритмов, в первую очередь, включает решетчатую нумерацию [5] [6] [7] и сокращение случайной выборки, [8] [9], в то время как последний включает решетчатое просеивание, [10] [11] [12] вычисление ячейки Вороного решетки, [13] [14] и дискретной гауссовой выборкой. [15] Открытая проблема заключается в том, существуют ли алгоритмы для решения точных SVP, работающие за одно экспоненциальное время () и требует полиномиального масштабирования памяти по размерности решетки. [16]
Решить вариант γ-приближения SVP γ длядля евклидовой нормы наиболее известные подходы основаны на использовании редукции базиса решетки . Для больших, алгоритм Ленстры – Ленстры – Ловаса (LLL) может найти решение за время, полиномиальное по размерности решетки. Для меньших значений, обычно используется блочный алгоритм Коркина-Золотарева (БКЗ) [17] [18] [19] , где вход в алгоритм (размер блока) определяет временную сложность и качество вывода: для больших коэффициентов аппроксимации , небольшой размер блока достаточно, и алгоритм быстро завершается. Для малых, больше необходимы для поиска достаточно коротких векторов решетки, и алгоритм требует больше времени, чтобы найти решение. Алгоритм BKZ внутренне использует точный алгоритм SVP в качестве подпрограммы (работающий в решетках размерности не более), и его общая сложность тесно связана со стоимостью этих вызовов SVP в измерении .
GapSVP
Задача GapSVP β состоит в различении экземпляров SVP, в которых длина кратчайшего вектора не превышает или больше чем , где может быть фиксированной функцией размера решетки . Учитывая основу решетки, алгоритм должен решить, будет ли или же . Как и другие проблемы с обещаниями , алгоритм может допускать ошибки во всех остальных случаях.
Еще один вариант проблемы - GapSVP ζ, γ для некоторых функций. Вход в алгоритм - это основа и ряд . Гарантируется, что все векторы в ортогонализации Грама – Шмидта имеют длину не менее 1 и что и это где это измерение. Алгоритм должен принять, если, и отклонить, если . Для больших () проблема эквивалентна GapSVP γ, поскольку [20] предварительная обработка, выполняемая с использованием алгоритма LLL, выполняет второе условие (и, следовательно,) избыточный.
Проблема ближайшего вектора (CVP)
В ЦВД, базис векторного пространства V и метрики М (часто L 2 ) приведены для решетки L , а также в качестве вектора V в V , но не обязательно в L . Желательно найти вектор в L, ближайший к v (измеренный с помощью M ). в-приближенной версии CVP γ необходимо найти вектор решетки на расстоянии не более.
Отношения со старшим вице-президентом
Ближайшая векторная задача является обобщением самой короткой векторной задачи. Легко показать, что с помощью оракула для CVP γ (определенного ниже) можно решить SVP γ , сделав несколько запросов к оракулу. [21] Наивный метод поиска кратчайшего вектора путем вызова оракула CVP γ для нахождения вектора, ближайшего к 0, не работает, потому что 0 сам является вектором решетки, и алгоритм потенциально может вывести 0.
Сведение от SVP γ к CVP γ выглядит следующим образом: предположим, что исходные данные для задачи SVP γ являются базисом для решетки. Рассмотрим основу и разреши быть вектором, возвращаемым CVP γ (B i , b i ). Утверждается, что кратчайший вектор в наборе - кратчайший вектор в данной решетке.
Результаты твердости
Goldreich et al. показали, что любая твердость SVP подразумевает такую же твердость для CVP. [22] Используя инструменты PCP , Arora et al. показали, что ЦВД трудно аппроксимировать в пределах фактора пока не . [23] Dinur et al. усилили это, дав результат NP-твердости с для . [24]
Расшифровка сферы
Алгоритмы для CVP, особенно вариант Fincke и Pohst [6] , использовались для обнаружения данных в системах беспроводной связи с множеством входов и множеством выходов ( MIMO ) (для кодированных и некодированных сигналов). [25] [13] В этом контексте это называется сферическим декодированием из-за внутреннего радиуса, используемого во многих решениях CVP. [26]
Он был применен в области разрешения целочисленной неоднозначности несущей GNSS (GPS). [27] В этой области это называется методом LAMBDA . В той же области общая проблема CVP упоминается как целочисленные наименьшие квадраты .
GapCVP
Эта проблема аналогична проблеме GapSVP. Для GapSVP β вход состоит из базиса решетки и вектора и алгоритм должен ответить, выполняется ли одно из следующих условий:
- существует такой вектор решетки, что расстояние между ним и не больше 1.
- каждый вектор решетки находится на расстоянии больше, чем далеко от .
Противоположное условие - ближайший вектор решетки находится на расстоянии , отсюда и название Gap CVP.
Известные результаты
Проблема тривиально содержится в NP для любого фактора приближения.
Шнорр в 1987 году показал, что детерминированные алгоритмы с полиномиальным временем могут решить проблему для. [28] Ajtai et al. показали, что вероятностные алгоритмы могут достичь немного лучшего коэффициента аппроксимации. [10]
В 1993 году Банащик показал, что GapCVP n находится в. [29] В 2000 году Голдрайх и Гольдвассер показали, чтоставит проблему как в NP, так и в coAM . [30] В 2005 году Ааронов и Регев показали, что для некоторой постоянной, проблема с в . [31]
Для оценки снизу Dinur et al. показал в 1998 году, что проблема NP-трудна для. [32]
Задача кратчайших независимых векторов (SIVP)
Для решетки L размерности n алгоритм должен выводить n линейно независимых чтобы где правая часть учитывает все основания решетки.
в -приближенный вариант, заданный решеткой L размерности n , найти n линейно независимых векторов длины , где это -й последовательный минимум .
Декодирование с ограниченным расстоянием
Эта проблема похожа на CVP. Для вектора, расстояние от решетки которого не превышает, алгоритм должен вывести ближайший к нему вектор решетки.
Проблема радиуса покрытия
Имея основу для решетки, алгоритм должен найти наибольшее расстояние (или, в некоторых версиях, его приближение) от любого вектора до решетки.
Кратчайшая проблема базиса
Многие проблемы становятся проще, если исходная база состоит из коротких векторов. Алгоритм, который решает задачу кратчайшего базиса (SBP), должен, учитывая базис решетки, вывести эквивалентный базис такая, что длина самого длинного вектора в как можно короче.
Задача SBP γ приближенного варианта состоит в нахождении базиса, самый длинный вектор которого не превосходит раз больше, чем самый длинный вектор в самом коротком базисе.
Использование в криптографии
Средняя степень сложности задач является основой для доказательств безопасности для большинства криптографических схем. Однако экспериментальные данные свидетельствуют о том, что большинству NP-сложных задач не хватает этого свойства: они, вероятно, только в худшем случае. Были выдвинуты гипотезы или доказано, что многие решеточные задачи являются сложными для среднего случая, что делает их привлекательным классом задач для построения криптографических схем. Более того, для создания безопасных криптографических схем использовалась жесткость наихудшего случая некоторых решеточных задач. Использование в таких схемах жесткости наихудшего случая делает их одними из очень немногих схем, которые, скорее всего, защищены даже от квантовых компьютеров .
Приведенные выше решеточные задачи легко решить, если у алгоритма есть «хорошая» база. Алгоритмы сокращения решетки стремятся, учитывая основу для решетки, вывести новый базис, состоящий из относительно коротких, почти ортогональных векторов. В Ленстр-Ленстр-Lovász решетчатого алгоритм редукции базиса (LLL) был одним из первых эффективного алгоритма для этой проблемы , которые могли бы выход почти уменьшенные решетки базиса в полиномиальное время. [33] Этот алгоритм и его дальнейшие усовершенствования были использованы для взлома нескольких криптографических схем, что сделало его очень важным инструментом в криптоанализе. Успех LLL на экспериментальных данных привел к убеждению, что сокращение решетки может быть простой проблемой на практике. Однако это убеждение было оспорено, когда в конце 1990-х годов было получено несколько новых результатов о сложности решеточных задач, начиная с результата Аджтаи . [2]
В своих основополагающих статьях Аджтай показал, что проблема SVP является NP-сложной, и обнаружил некоторые связи между сложностью наихудшего случая и сложностью среднего случая некоторых решеточных задач. [2] [3] Основываясь на этих результатах, Аджтай и Дворк создали криптосистему с открытым ключом , безопасность которой может быть доказана с использованием только наихудшего случая жесткости определенной версии SVP, [34], таким образом, сделав ее первым результатом, который использовал наихудший случай создания безопасных систем. [35]
Смотрите также
- Обучение с ошибками
- Краткое целочисленное решение задачи
Рекомендации
- ^ Хот, Subhash (2005). «Трудность аппроксимации кратчайшей векторной задачи в решетках». J. ACM . 52 (5): 789–808. DOI : 10.1145 / 1089023.1089027 . S2CID 13438130 .
- ^ а б в Айтай, М. (1996). «Создание сложных экземпляров решетчатых задач» . Материалы двадцать восьмого ежегодного симпозиума ACM по теории вычислений . Филадельфия, Пенсильвания, США: ACM. С. 99–108.
- ^ а б Айтай, Миклош (1998). «Самый короткий вектор проблема в L 2 является NP -Жесткий для рандомизированных сокращений» . Материалы тридцатого ежегодного симпозиума ACM по теории вычислений . Даллас, Техас, США: ACM. С. 10–19.
- ^ ван Эмде Боас, Питер (1981). «Еще одна NP-полная проблема и сложность вычисления коротких векторов в решетке» . Технический отчет 8104 . Амстердамский университет, факультет математики, Нидерланды.
- ^ Каннан, Рави (1983). «Улучшенные алгоритмы для целочисленного программирования и связанных задач решетки». Материалы пятнадцатого ежегодного симпозиума ACM по теории вычислений - STOC '83 . Материалы пятнадцатого ежегодного симпозиума ACM по теории вычислений . СТОК '83. Нью-Йорк, Нью-Йорк, США: ACM. С. 193–206. DOI : 10.1145 / 800061.808749 . ISBN 978-0897910996. S2CID 18181112 .
- ^ а б Fincke, U .; Похст, М. (1985). «Усовершенствованные методы расчета векторов малой длины в решетке, включая анализ сложности» . Математика. Комп . 44 (170): 463–471. DOI : 10.1090 / S0025-5718-1985-0777278-8 .
- ^ Гама, Николас; Nguyen, Phong Q .; Регев, Одед (30 мая 2010 г.). Перечисление решетки с использованием экстремального отсечения . Достижения в криптологии - EUROCRYPT 2010 . Конспект лекций по информатике. 6110 . Шпрингер, Берлин, Гейдельберг. С. 257–278. DOI : 10.1007 / 978-3-642-13190-5_13 . ISBN 978-3-642-13189-9.
- ^ Шнорр, Клаус Питер (27 февраля 2003 г.). «Редукция решетки методами случайной выборки и рождения». Стакс 2003 . Конспект лекций по информатике. 2607 . Шпрингер, Берлин, Гейдельберг. С. 145–156. CiteSeerX 10.1.1.137.4293 . DOI : 10.1007 / 3-540-36494-3_14 . ISBN 978-3540364948. Отсутствует или пусто
|title=
( справка ) - ^ Аоно, Ёсинори; Нгуен, Фонг К. (30 апреля 2017 г.). Возвращение к случайной выборке: решеточное перечисление с дискретным отсечением (PDF) . Достижения в криптологии - EUROCRYPT 2017 . Конспект лекций по информатике. 10211 . Спрингер, Чам. С. 65–102. DOI : 10.1007 / 978-3-319-56614-6_3 . ISBN 978-3-319-56613-9.
- ^ а б Айтай, Миклош; Кумар, Рави; Сивакумар, Д. (2001). «Решетчатый алгоритм для кратчайшей векторной задачи на решетке» . Материалы тридцать третьего ежегодного симпозиума ACM по теории вычислений . Херсониссос, Греция: ACM. С. 601–610.
- ^ Микчанчо, Даниэле; Вулгарис, Панайотис (2010). Более быстрые экспоненциальные алгоритмы времени для задачи наикратчайших векторов . Труды двадцать первого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . SODA '10. Филадельфия, Пенсильвания, США: Общество промышленной и прикладной математики. С. 1468–1480. DOI : 10.1137 / 1.9781611973075.119 . ISBN 9780898716986. S2CID 90084 .
- ^ Беккер, А .; Ducas, L .; Gama, N .; Лаарховен, Т. (21 декабря 2015 г.). «Новые направления поиска ближайшего соседа с приложениями для решетчатого просеивания». Материалы двадцать седьмого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . Ход работы. Общество промышленной и прикладной математики. С. 10–24. DOI : 10.1137 / 1.9781611974331.ch2 . ISBN 978-1-61197-433-1.
- ^ а б Agrell, E .; Eriksson, T .; Варди, А .; Зегер, К. (2002). «Поиск ближайшей точки в решетках» . IEEE Trans. Инф. Теория . 48 (8): 2201–2214. DOI : 10.1109 / TIT.2002.800499 .
- ^ Микчанчо, Даниэле; Вулгарис, Панайотис (2010). Детерминированный одноэкспоненциальный временной алгоритм для большинства задач на решетке, основанный на вычислениях ячейки Вороного . Материалы сорок второго симпозиума ACM по теории вычислений . СТОК '10. Нью-Йорк, Нью-Йорк, США: ACM. С. 351–358. CiteSeerX 10.1.1.705.3304 . DOI : 10.1145 / 1806689.1806739 . ISBN 9781450300506. S2CID 2449948 .
- ^ Аггарвал, Дивеш; Дадуш, Даниил; Регев, Одед; Стивенс-Давидовиц, Ноа (2015). Решение задачи о кратчайшем векторе за 2N времени с использованием дискретной гауссовой выборки: расширенная аннотация . Материалы сорок седьмого ежегодного симпозиума ACM по теории вычислений . СТОК '15. Нью-Йорк, Нью-Йорк, США: ACM. С. 733–742. DOI : 10.1145 / 2746539.2746606 . ISBN 9781450335362. S2CID 10214330 .
- ^ Миччансио, Даниэле (2017-07-01). «Решеточная криптография - задача кратчайшего вектора» .
- ^ Шнорр, КП (1987-01-01). «Иерархия алгоритмов редукции базиса полиномиальной решетки» . Теоретическая информатика . 53 (2): 201–224. DOI : 10.1016 / 0304-3975 (87) 90064-8 .
- ^ Шнорр, CP; Евхнер, М. (1994-08-01). «Сокращение базиса решетки: улучшенные практические алгоритмы и решение задач суммы подмножеств» (PDF) . Математическое программирование . 66 (1–3): 181–199. DOI : 10.1007 / bf01581144 . ISSN 0025-5610 . S2CID 15386054 .
- ^ Чен, Юаньми; Нгуен, Фонг К. (2011-12-04). BKZ 2.0: лучшие оценки безопасности решетки . Достижения в криптологии - ASIACRYPT 2011 . Конспект лекций по информатике. 7073 . Шпрингер, Берлин, Гейдельберг. С. 1–20. DOI : 10.1007 / 978-3-642-25385-0_1 . ISBN 978-3-642-25384-3.
- ^ Пайкерт, Крис (2009). «Криптосистемы с открытым ключом из наихудшей задачи кратчайшего вектора: расширенная аннотация» . Материалы 41-го ежегодного симпозиума ACM по теории вычислений . Бетесда, Мэриленд, США: ACM. С. 333–342.
- ^ Микчанчо, Даниэле; Гольдвассер, Шафи (2002). Сложность решеточных задач . Springer.
- ^ Goldreich, O .; и другие. (1999). «Приближение кратчайших векторов решетки не сложнее, чем приближение ближайших векторов решетки». Инф. Процесс. Lett . 71 (2): 55–61. DOI : 10.1016 / S0020-0190 (99) 00083-6 .
- ^ Арора, Санджив; и другие. (1997). «Трудность приближенных оптимумов в решетках, кодах и системах линейных уравнений». Труды 1993 IEEE тридцать четвёртой ежегодной Основы информатики . J. Comput. Syst. Sci . 54 . С. 317–331. DOI : 10.1109 / SFCS.1993.366815 . ISBN 978-0-8186-4370-5. S2CID 44988406 .
- ^ Динур, I .; и другие. (2003). «Приближение CVP с точностью до почти полиномиальных множителей является NP-трудным». Combinatorica . 23 (2): 205–243. DOI : 10.1007 / s00493-003-0019-у . S2CID 45754954 .
- ^ Biglieri, E .; Calderbank, R .; Константинидес, Энтони Г .; Goldsmith, A .; Paulraj, A .; Бедный, HV (2007). Беспроводная связь MIMO . Кембридж: Cambridge UP
- ^ Ван, Пинг; Ле-Нгок, То (2011). «Алгоритм декодирования сферы списка с улучшенными стратегиями установки радиуса». Беспроводная персональная связь . 61 (1): 189–200. DOI : 10.1007 / s11277-010-0018-4 . S2CID 30919872 .
- ^ Hassibi, A .; Бойд, С. (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 .
- ^ Шнорр, CP "Факторинг целых чисел и вычисление дискретных логарифмов через диофантово приближение". Достижения в криптологии: материалы Eurocrypt '91 .
- ^ Banaszczyk, W. (1993). «Новые оценки некоторых теорем переноса в геометрии чисел». Математика. Аня. 296 (1): 625–635. DOI : 10.1007 / BF01445125 . S2CID 13921988 .
- ^ Гольдрайх, Одед; Гольдвассер, Шафи (1998). «О пределах неприближаемости решеточных задач» . Материалы тридцатого ежегодного симпозиума ACM по теории вычислений . Даллас, Техас, США: ACM. С. 1–9.
- ^ Ааронов, Дорит; Одед Регев (2005). «Решеточные задачи в НПcoNP ". J. ACM . 52 (5): 749–765. CiteSeerX 10.1.1.205.3730 . doi : 10.1145 / 1089023.1089025 . S2CID 1669286 .
- ^ Динур, I .; Киндлер, G .; Сафра, С. (1998). «Приближение CVP с точностью до почти полиномиальных множителей является NP-трудным» . Материалы 39-го ежегодного симпозиума по основам информатики . Компьютерное общество IEEE. п. 99. ISBN 978-0-8186-9172-0.
- ^ Ленстра, АК; Lenstra, HW, Jr .; Ловас, Л. (1982). «Факторизация многочленов с рациональными коэффициентами» (PDF) . Математика. Аня. 261 (4): 515–534. DOI : 10.1007 / BF01457454 . S2CID 5701340 . Архивировано из оригинального (PDF) 17 июля 2011 года.
- ^ Айтай, Миклош; Дворк, Синтия (1997). «Криптосистема с открытым ключом с эквивалентностью наихудшего и среднего случая» . Материалы двадцать девятого ежегодного симпозиума ACM по теории вычислений . Эль-Пасо, Техас, США: ACM. С. 284–293.
- ^ Цай, Цзинь-И (2000). «Сложность некоторых решеточных задач». Алгоритмическая теория чисел . Конспект лекций по информатике. 1838 . С. 1–32. DOI : 10.1007 / 10722028_1 . ISBN 978-3-540-67695-9.
дальнейшее чтение
- 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.