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

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

Для всіх задач нижче припустимо, що нам дано (крім інших більш конкретних вхідних даних) базис для векторного простору V і норма N. Для норм зазвичай розглядається L². Однак інші норми, такі як L^p), також розглядаються і з'являються в різних результатах. Нижче в статті $\lambda (L)$ означає довжину найкоротшого вектора в ґратці L, тобто : $\lambda (L)=\min _{v\in L\setminus \{\mathbf {0} \}}\|v\|_{N}.$

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

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

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

В $\gamma$-наближеній версії ЗНВ_γ потрібно найти ненульовий вектор ґратці довжини, що не перевищує $\gamma \lambda (L)$.

Труднощі

Тільки точна версія задачі, як відомо, є NP-важкою для рандомізованого відомості .

Для контрасту, відомо, що еквівалентна задача для рівномірних норм, є NP-важкою .

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

Для вирішення точної версії ЗНВ для евклідової норми відомі кілька різних підходів, які можна розбити на два класи — алгоритми, що вимагають суперекспоненціального часу ($2^{\omega (n)}$) і $\operatorname {poly} (n)$ пам'яті, і алгоритми, що вимагають експоненціального часу і пам'яті ($2^{\Theta (n)}$), від розмірності ґратки($2^{\Theta (n)}$). У першому класі алгоритмів найбільш значимі алгоритми перерахування ґратки і алгоритми скорочення випадкових вибірок , в той час як другий клас включає ґраткову просіювання , обчислення осередків Вороного на ґратці і дискретні гаусові розподілу . Відкритою проблемою є, чи існують алгоритми, вирішальні точну ЗНВ за звичайне експоненціальне час ($2^{O(n)}$) і вимагають пам'яті, поліноміально залежить від розмірності ґратки .

Для вирішення $\gamma$-наближеною версії ЗНВ_γ для $\gamma >1$ для евклідової норми кращий відомий підхід базується на використанні редукції базису ґратки. Для великих $\gamma =2^{\Omega (n)}$ алгоритм Ленстра — Ленстра — Ловаш (алгоритм ЛЛЛ) редукції базису ґратки може знайти рішення за поліноміальний час від розмірності ґратки. Для малих значень $\gamma$ зазвичай використовується блоковий алгоритм Коркіна — Золотарьова (БКЗ, англ. Block Korkine-Zolotarev algorithm, BKZ), де вхід алгоритму (розмір блоку $\beta$) визначає часову складність і якість виходу — для великих аппроксимаціонних коефіцієнтам $\gamma$ достатній малий розмір блоку $\beta$ і алгоритм завершується швидко. Для малих $\gamma$ вимагається більший $\beta$, щоб знайти досить короткі вектора ґратки, і алгоритм працює довше. БКЗ-алгоритм всередині використовує алгоритм точного ЗНВ як підпрограми (працює на ґратці розмірності, не перевершує $\beta$), і загальна складність тісно пов'язана з вартістю цих викликів ЗНВ в розмірності $\beta$.

GapSVP

Задача $GapSVP_{\beta }$ полягає в розрізненні між варіантами ЗНВ, в яких відповідь не перевищує 1 або більше $\beta$ може бути фіксованою функцією від розмірності ґратки $n$. Якщо заданий базис ґратки, алгоритм повинен вирішити, буде $\lambda (L)\leqslant 1$ або $\lambda (L)>\beta$. Подібно до інших задач із передумовою, алгоритму дозволені помилки у всіх інших випадках.

Іншою версією задачі є $GapSVP_{\zeta ,\gamma }$ для деяких функцій $\zeta ,\gamma$. Входом алгоритму є базис $B$ і число $d$. Алгоритм забезпечує, щоб всі вектори в ортогоналізації Грама — Шмідта мали довжину, не меншу 1, щоб $\lambda (L(B))\leqslant \zeta (n)$ і щоб $1\leqslant d\leqslant \zeta (n)/\gamma (n)$, де $n$ — розмірність. Алгоритм повинен прийняти, якщо $\lambda (L(B))\leqslant d$ і відкинути, якщо $\lambda (L(B))\geqslant \gamma (n).d$. Для великих $\zeta$ ($\zeta (n)>2^{n/2}$) задача еквівалентна$GapSVP_{\gamma }$, оскільки препроцесорний крок за допомогою алгоритму ЛЛЛ робить другу умову (а отже, $\zeta$) зайвою.

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

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

У ЗНВ (англ. Closest vector problem, CVP) для ґратки L дані базис векторного простору V і метрика M (часто L²), а також вектор v в V, але не обов'язково в L. Вимагається знайти вектор в L, найбільш близький до v (у міру M). У $\gamma$-наближеній версії ЗНВ_γ, треба знайти вектор ґратки на відстані, що не перевершує $\gamma$.

Зв'язок із ЗНВ

Задача знаходження найближчого вектору є узагальненням задачі знаходження найкоротшого вектору. Легко показати, що якщо заданий провісник для ЗНВ_γ (визначений нижче)можна вирішити ЗНВ_γ шляхом деяких запитів провісникові. Природний метод пошуку найкоротшого вектору шляхом запитів до провісника ЗНВ_γ, щоб знайти найближчий вектор, не працює, оскільки 0 є вектором ґратки і алгоритм, потенційно, може повернути 0.

Зведення від ЗНВ_γ до ЗНВ_γ наступне: припустимо, що входом задачі ЗНВ_γ є базис ґратки $B=[b_{1},b_{2},\ldots ,b_{n}]$. Розглянемо базис $B^{i}=[b_{1},\ldots ,2b_{i},\ldots ,b_{n}]$ буде вектором, який повернув алгоритм ЗНВ$\gamma (B^{i},b_{i})$. Стверджується, що найкоротший вектор в множині $\{x_{i}-b_{i}\}$ є найкоротшим вектором в даній ґратці.

Труднощі

Голдрайх, Міссіансіо, Сафра і Сейферт показали, що з будь-якої складності ЗНВ витікає така ж складність для ЗНВ. Використовуючи засоби Арора, Бабаї, що перевіряється, Стерн, Свідік показали, що ЗНВ важка для апроксимації до множника $2^{\log ^{1-\epsilon }(n)}$, якщо тільки не $\operatorname {NP} \subseteq \operatorname {DTIME} (2^{poly(\log n)})$. Дінур, Кіндлер, Сафра посилили це, вказавши NP-трудність з $\epsilon =(\log \log n)^{c}$ для $c<1/2$.

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

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

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

GapSVP

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

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

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

Клаус Шнорр в 1987 показав, що алгоритми з детермінованим поліноміальним часом можуть розв'язати задачу $\beta =2^{O(n(\log \log n)^{2}/\log n)}$. Айтаі, Кумар, Сівакумар показали, що ймовірнісні алгоритми можуть отримати злегка більше кращий коефіцієнт апроксимації $\beta =2^{O(n\log \log n/\log n)}$.

У 1993 Банашчик показав, що $GapCVP_{n}$ міститься в $NP\cap coNP$. У 2000 Голдрайх і Голдвассер показали, що $\beta ={\sqrt {n/\log n}}$ поміщає задачу в класи як NP, так і coAM. У 2005 Ааронов і Реджев показали, що для деякої константи $c$ задача з $\beta =c{\sqrt {n}}$ входить в $NP\cap coNP$.

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

Якщо дані ґратки L розмірності n, алгоритм повинен видати n лінійно незалежних векторів $v_{1},v_{2},\ldots ,v_{n}$, таких, що $\max \|v_{i}\|<\max _{B}\|b_{i}\|$, де права частина складається з усіх базисів $B=\{b_{1},\ldots ,b_{n}\}$ ґратки.

У $\gamma$-приближенній версії, якщо дані ґратки L розмірності n, алгоритм знаходить n лінійно незалежних векторів $v1,v2,\ldots ,v_{n}$ довжини $\max ||v_{i}||\leqslant \gamma \lambda _{n}(L)$, де $\lambda _{n}(L)$ є $n$-м подальшим мінімумом $L$.

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

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

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

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

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

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

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

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

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

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

Література

• 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 L₂ 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. — 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.
• 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.
• Miklós Ajtai, Ravi Kumar, D. Sivakumar. A sieve algorithm for the shortest lattice vector problem // Proceedings of the thirty - third annual ACM symposium on Theory of computing. — Hersonissos, Greece : ACM, 2001.
• Banaszczyk W. New bounds in some transference theorems in the geometry of numbers // Math. Ann.. — 1993. — Т. 296, вип. 1. — DOI:10.1007/BF01445125.
• Dorit Aharonov, Oded Regev. Lattice problems in NP $\cap$ coNP // J. ACM. — 2005. — Т. 52, вип. 5. — DOI:10.1145/1089023.1089025.
• Ajtai M. Generating hard instances of lattice problems // Proceedings of the twenty - eighth annual ACM symposium on Theory of computing. — Philadelphia, Pennsylvania, United States : ACM, 1996.
• Miklós Ajtai, Cynthia Dwork. A public - key cryptosystem with worst - case/average - case equivalence // Proceedings of the twenty - ninth annual ACM symposium on Theory of computing. — El Paso, Texas, United States : ACM, 1997.
• Jin - Yi Cai. The Complexity of Some Lattice Problems // Algorithmic Number Theory.Lecture Notes in Computer Science. — 2000. — Т. 1838. — DOI:10.1007/10722028 1.
• Lenstra A. K., Lenstra H. W., Lovász L. Factoring polynomials with rational coefficients // Math. Ann.. — 1982. — Т. 261, вип. 4. — DOI:10.1007/BF01457454.
• Daniele Micciancio, Panagiotis Voulgaris. Faster Exponential Time Algorithms for the Shortest Vector Problem // Proceedings of the Twenty - first Annual ACM - SIAM Symposium on Discrete Algorithms. — Philadelphia, PA, USA : Society for Industrial and Applied Mathematics, 2010. — С. 1468-1480. — (SODA '10) — ISBN 9780898716986.
• Daniele Micciancio, Panagiotis Voulgaris. A Deterministic Single Exponential Time Algorithm for Most Lattice Problems Based on Voronoi Cell Computations // Proceedings of the Forty - second ACM Symposium on Theory of Computing. — New York, NY, USA : ACM, 2010a. — ISBN 9781450300506. — DOI:10.1145/1806689.1806739.
• Becker A., Ducas L., Gama N., Laarhoven T. Proceedings of the Twenty - Seventh Annual ACM - SIAM Symposium on Discrete Algorithms. — Society for Industrial and Applied Mathematics, 2015. — С. 10-24. — (Proceedings) — DOI:10.1137/1.9781611974331.ch2.
• Divesh Aggarwal, Daniel Dadush, Oded Regev, Noah Stephens - Davidowitz. Solving the Shortest Vector Problem in 2n Time Using Discrete Gaussian Sampling : Extended Abstract // Proceedings of the Forty - seventh Annual ACM Symposium on Theory of Computing. — New York, NY, USA : ACM, 2015. — (STOC) — ISBN 9781450335362. — DOI:10.1145/2746539.2746606.
• Daniele Micciancio. Lattice Cryptography - Shortest Vector Problem. — 2017.
• Schnorr C. P. A hierarchy of polynomial time lattice basis reduction algorithms // Theoretical Computer Science. — 1987. — Т. 53, вип. 2. — DOI:10.1016/0304-3975 (87) 90064-8.
• Schnorr C. P., Euchner M. Lattice basis reduction: Improved practical algorithms and solving subset sum problems // Mathematical Programming. — 1994. — Т. 66, вип. 1-3. — ISSN 0025-5610. — DOI:10.1007/bf01581144.
• Claus Peter Schnorr. Lattice Reduction by Random Sampling and Birthday Methods // 14 STACS. — Springer, Berlin, Heidelberg, 2003. — ISBN 3540364943. — DOI:10.1007/3-540-36494-3 14.
• Yuanmi Chen, Phong Q. Nguyen. 1 Advances in Cryptology - ASIACRYPT 2011. — Springer, Berlin, Heidelberg, 2011. — DOI:10.1007/978-3-642-25385-0 1.

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

• 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.
• Daniele Micciancio. The Shortest Vector Problem is \u007BNP\u007D- hard to approximate to within some constant // SIAM Journal on Computing. — 2001. — Т. 30, вип. 6. — С. 2008-2035. — DOI:10.1137/S0097539700373039.
• Phong Q. Nguyen, Jacques Stern. Lattice Reduction in Cryptology : An Update // Proceedings of the 4th International Symposium on Algorithmic Number Theory. — Springer - Verlag, 2000. — С. 85-112. — ISBN 3-540-67695-3.
• Ravi Kannan. Improved Algorithms for Integer Programming and Related Lattice Problems // Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing. — New York, NY, USA : ACM, 1983. — (STOC) — ISBN 0897910990. — DOI:10.1145/800061.808749.
• Nicolas Gama, Phong Q. Nguyen, Oded Regev. Lattice Enumeration Using Extreme Pruning // Advances in Cryptology - EUROCRYPT 2010. — Springer, Berlin, Heidelberg, 2010. — DOI:10.1007/978-3-642-13190-5 13.
• Yoshinori Aono, Phong Q. Nguyen. Random Sampling Revisited : Lattice Enumeration with Discrete Pruning // Advances in Cryptology - EUROCRYPT 2017. — Springer, Cham, 2017. — DOI:10.1007/978-3-319-56614-6 3.
• Daniele Micciancio, Panagiotis Voulgaris. Faster Exponential Time Algorithms for the Shortest Vector Problem // Id = 1873601.1873720  — (SODA '10)^{[недоступне посилання]}
• Daniele Micciancio, Panagiotis Voulgaris. A Deterministic Single Exponential Time Algorithm for Most Lattice Problems Based on Voronoi Cell Computations //
• Becker A., ​​Ducas L., Gama N., Laarhoven T. [1] Архівовано з джерела 19 січня 2022