Задачі теорії ґраток

Зада́чі тео́рії ґра́ток — це клас задач оптимізації на ґратках (тобто дискретних адитивних підгрупах, заданих на множині ). Труднощі при розв'язуванні таких задач є центральним місцем для побудови стійких криптосистем на ґратках. Для додатків в таких криптосистемах зазвичай розглядаються ґратки на векторних просторах (часто ) або вільних модулях (часто ).

Для всіх задач нижче припустимо, що нам дано (крім інших більш конкретних вхідних даних) базис для векторного простору V і норма N. Для норм зазвичай розглядається L2. Однак інші норми, такі як Lp), також розглядаються і з'являються в різних результатах. Нижче в статті означає довжину найкоротшого вектора в ґратці L, тобто :

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

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

У ЗНВ (англ. Shortest vector problem, SVP), для ґратки L дані базис векторного простору V і норма N (часто L2) і потрібно знайти ненульовий вектор мінімальної довжини в V за нормою N в ґратці L. Іншими словами, виходом алгоритму повинен бути ненульовий вектор v, такий, що .

В -наближеній версії ЗНВγ потрібно найти ненульовий вектор ґратці довжини, що не перевищує .

Труднощі

Тільки точна версія задачі, як відомо, є NP-важкою для рандомізованого відомості [1] [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.

Зведення від ЗНВγ до ЗНВγ наступне: припустимо, що входом задачі ЗНВγ є базис ґратки . Розглянемо базис буде вектором, який повернув алгоритм ЗНВ. Стверджується, що найкоротший вектор в множині є найкоротшим вектором в даній ґратці.

Труднощі

Голдрайх, Міссіансіо, Сафра і Сейферт показали, що з будь-якої складності ЗНВ витікає така ж складність для ЗНВ[21]. Використовуючи засоби Арора, Бабаї, що перевіряється, Стерн, Свідік показали, що ЗНВ важка для апроксимації до множника , якщо тільки не [22]. Дінур, Кіндлер, Сафра посилили це, вказавши NP-трудність з для [23].

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

Алгоритм для ЗНВ, особливо варіант Фінці і Поста[24] використовується, наприклад, для виявлення даних у безпровідних системах зв'язку з багатоканальним входом/багатоканальним виходом (MIMO) (для кодованих і розкодованих сигналів) [25][26]. У цьому контексті він називається сферичним декодуванням[27].

Алгоритм був застосований в області цілочисельного дозволу неоднозначності фази такою, що несе GNSS (GPS)[28]. У цій області це називається LAMBDA-методом.

GapSVP

Ця задача подібна до задачі GapSVP. Для , входом є базис ґратки і вектор , а алгоритм повинен відповісти, яка з умов виконується існує вектор ґратки, такий, що відстань між ним і не перевершує 1. Будь-який вектор ґратки знаходиться від на відстані, більшому .

Відомі результати

Задача тривіально міститься в класі NP для будь-якого коефіцієнта апроксимації.

Клаус Шнорр в 1987 показав, що алгоритми з детермінованим поліноміальним часом можуть розв'язати задачу [29]. Айтаі, Кумар, Сівакумар показали, що ймовірнісні алгоритми можуть отримати злегка більше кращий коефіцієнт апроксимації [30].


У 1993 Банашчик показав, що міститься в [31]. У 2000 Голдрайх і Голдвассер показали, що поміщає задачу в класи як NP, так і coAM[32]. У 2005 Ааронов і Реджев показали, що для деякої константи задача з входить в [33].

Задача про найкоротші незалежні вектори

Якщо дані ґратки L розмірності n, алгоритм повинен видати n лінійно незалежних векторів , таких, що , де права частина складається з усіх базисів ґратки.

У -приближенній версії, якщо дані ґратки L розмірності n, алгоритм знаходить n лінійно незалежних векторів довжини , де є -м подальшим мінімумом .

Декодування з обмеженою відстанню

Це задача подібна до ЗНВ. Якщо даний вектор, такий, що його відстань від ґратки не перевершує , алгоритм повинен видати найближчий вектор ґратки.

Задача покриття ґратки радіусами

Якщо даний базис для ґратки, алгоритм повинен знайти найбільшу відстань (чи, в деяких версіях, його апроксимацію) від будь-якого вектору до ґратки.

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

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

Апроксимована версія задачі ПКБγ полягає в пошуку базису, щонайдовший вектор якого не перевершує по довжині в раз щонайдовшого вектору в найкоротшому базисі.

Використання в криптографії

Складність середнього випадку задач утворює базис для доведення стійкості більшості криптографічних схем. Проте експериментальні дані наштовхують на припущення, що для більшості NP-складних заданч ця властивість відсутня — вони лише важкі у гіршому разі. Для багатьох задач теорії ґраток припустило або доведено, що вони важкі в середньому, що робить їх привабливими для криптографічних схем. Проте складність у гіршому разі деяких задач теорії ґраток використовується для створення схем стійкої криптографії. Використання трудності у гіршому разі в таких схемах поміщає їх в клас дуже небагатьох схем, які, з великою часткою вірогідності, стійкі навіть для квантових комп'ютерів.

Наведені вище задачі теорії ґраток легко вирішуються, якщо даний «хороший» базис. Мету алгоритмів редукції базису по цьому базису ґратки видати новий базис, що полягає їх відносно коротких майже ортогональних векторів. Алгоритм Ленстри — Ленстри — Ловаша редукції базису ґратки був раннім ефективним алгоритмом для цієї задачі, який може видати зредукований базис ґратки за поліноміальний час [34]. Цей алгоритм і його подальші поліпшення були використані для злому деяких криптографічних схем, що сформувало його статус як дуже важливий засіб в криптографії. Успіх ЛЛЛ на експериментальних даних привів до віри, що редукція базису ґратки на практиці може бути простою задачею. Проте ця віра була зруйнована, коли у кінці 1990s-х були отримані нові результати про складність задач теорії ґраток, починаючи з результатів Айтаі[35]. У своїй засадничій роботі Айтаі показав, що ЗНВ був NP-важким і виявив деякі зв'язки між складністю у гіршому разі і складністю в середньому деяких задач теорії ґраток[36]. Ґрунтуючись на цих результатах, Айтаі і Дворк створили криптосистему з відкритим ключем, секретність якої може бути доведена, використовуючи лише гірший випадок трудності певної версії ЗНВ[37], що було першим результатом по створенню захищених систем з використанням трудності у гіршому разі[38].

Примітки

Література

  • Subhash Khot. Hardness of approximating the shortest vector problem in lattices // J. ACM.  2005. Т. 52, вип. 5. DOI:10.1145/1089023.1089027.
  • 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.
  • 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.
  • 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:10.1090/S0025 - 5718-1985-0777278-8.
  • 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:10.1007/s11277 - 010-0018-4.
  • Hassibi A., Boyd S. Integer Parameter Estimation in Linear Models with Applications to GPS // IEEE Trans. Sig. Proc..  1998. Т. 46, вип. 11. DOI:10.1109/78.726808.
  • Banaszczyk W. New bounds in some transference theorems in the geometry of numbers // Math. Ann..  1993. Т. 296, вип. 1. DOI:10.1007/BF01445125.


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

  • Agrell E., Eriksson T., Vardy A., Zeger K. Closest Point Search in Lattices // IEEE Trans. Inform. Theory.  2002. Т. 48, вип. 8. DOI:10.1109/TIT.2002.800499.
    This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.