Квантовий алгоритм кидає виклик криптографії на основі ґраток

TL;DR. Новий поліноміальний квантовий алгоритм Йілей Чена атакує криптографію на основі ґраток з наслідками для постквантових стандартів, зокрема CRYSTALS-Kyber.

Points clés

Загальний огляд. У цій статті детально розглядається робота [Йілей Чена ⧉][00], який розробив поліноміальний квантовий алгоритм, що може суттєво вплинути на складність математичної задачі навчання з помилками (LWE), яка є…
Поліноміальний квантовий алгоритм Чена. Алгоритм Чена пропонує розв'язання децизійної задачі про найкоротший вектор (GapSVP) та задачі про найкоротший незалежний вектор (SIVP) для ґраток будь-якої розмірності.
Вступ до задач на ґратках та їх значення в криптографії. Задачі на ґратках пов'язані з вивченням математичних структур, які називаються ґратками та є дискретними підгрупами n-вимірного евклідового простору.
Класичні алгоритми для задач на ґратках та їх обмеження. Класичні алгоритми для розв'язання задач на ґратках, такі як алгоритм Ленстри — Ленстри — Ловаса (LLL) та його варіанти, були детально вивчені в галузі криптографії.

Загальний огляд

У цій статті детально розглядається робота Йілей Чена ⧉, який розробив поліноміальний квантовий алгоритм, що може суттєво вплинути на складність математичної задачі навчання з помилками (LWE), яка є фундаментальним викликом у криптографії на основі ґраток.

Ґратки — це дискретні підгрупи n-вимірного евклідового простору, які відіграють вирішальну роль у сучасних криптографічних схемах. Задача LWE передбачає знаходження секретного вектора за заданого набору наближених лінійних рівнянь і є наріжним каменем багатьох постквантових криптографічних протоколів.

Поліноміальний квантовий алгоритм Чена

Алгоритм Чена пропонує розв'язання децизійної задачі про найкоротший вектор (GapSVP) та задачі про найкоротший незалежний вектор (SIVP) для ґраток будь-якої розмірності. Він досягає цього з поліноміальною часовою складністю, що є значним покращенням порівняно з попередніми рішеннями.

Ключові інновації в його роботі включають:

Гауссові функції з комплексними дисперсіями: Чен пропонує використовувати гауссові функції з комплексними дисперсіями при розробці квантового алгоритму. Цей підхід використовує властивості комплексних гауссових розподілів для ефективнішого маніпулювання квантовими станами, забезпечуючи більш дієве розв'язання задачі LWE.
Віконне квантове перетворення Фур'є: Алгоритм застосовує віконне квантове перетворення Фур'є.

Вступ до задач на ґратках та їх значення в криптографії

Задачі на ґратках пов'язані з вивченням математичних структур, які називаються ґратками та є дискретними підгрупами n-вимірного евклідового простору. Ці задачі привернули значну увагу в криптографії завдяки їхній передбачуваній стійкості до квантових атак.

Найбільш відомою задачею на ґратках є задача навчання з помилками (LWE) ⧉, запропонована Одедом Регевом. LWE — це обчислювальна задача, яка полягає у знаходженні секретного вектора за заданого набору наближених лінійних рівнянь.

Багато сучасних криптографічних схем, таких як криптосистема Регева та обмін ключами Frodo, базують свою безпеку на складності розв'язання задачі LWE.

Класичні алгоритми для задач на ґратках та їх обмеження

Класичні алгоритми для розв'язання задач на ґратках, такі як алгоритм Ленстри — Ленстри — Ловаса (LLL) та його варіанти, були детально вивчені в галузі криптографії. Проте ці алгоритми стикаються з серйозними проблемами з точки зору обчислювальної складності, особливо зі збільшенням розмірності ґратки.

Відомі класичні алгоритми для розв'язання задачі LWE експоненціально залежать від кількості змінних, що робить їх практично непридатними для ґраток високої розмірності. Цей бар'єр складності є ключовим фактором безпеки криптографічних схем на основі LWE.

Попередні спроби розробки квантових алгоритмів для LWE

До роботи Чена кілька дослідників вивчали потенціал квантових алгоритмів для розв'язання задачі LWE.

Одед Регев успішно розробив квантову редукцію від GapSVP до LWE. Проте варто зазначити, що ця редукція потребує квантового оракула для розв'язання GapSVP, існування якого досі не доведено.

Куперберг створив квантовий алгоритм для розв'язання LWE із субекспоненціальним фактором апроксимації ⧉. Однак ці алгоритмічні підходи або покладалися на неперевірені припущення, або демонстрували нижчу швидкість обчислень. На противагу цьому, алгоритм Чена пропонує поліноміальне за часом рішення без необхідності використання квантового оракула.

Поліноміальний квантовий алгоритм Чена для LWE

Квантовий алгоритм Йілей Чена для розв'язання задачі LWE за поліноміальний час є значним проривом у цій галузі. Алгоритм використовує два нових методи:

Гауссові функції з комплексними дисперсіями: Чен пропонує використовувати гауссові функції з комплексними дисперсіями при розробці квантового алгоритму. Цей підхід використовує властивості комплексних гауссових розподілів для ефективнішого маніпулювання квантовими станами, забезпечуючи більш дієве розв'язання задачі LWE.
Віконне квантове перетворення Фур'є: Алгоритм застосовує віконне квантове перетворення Фур'є, що дозволяє проводити одночасний аналіз задачі як у часовій, так і в частотній областях. Цей метод дає змогу алгоритму ефективно обробляти багатовимірну структуру ґраток та вилучати релевантну інформацію для розв'язання LWE.

Алгоритм Чена поєднує методи для розв'язання LWE, GapSVP та SIVP за поліноміальний час для всіх розмірностей ґраток. Це значне покращення порівняно з попередніми класичними та квантовими алгоритмами.

Наслідки, обмеження та напрямки майбутніх досліджень

Квантовий алгоритм Чена має важливе значення для LWE, ставлячи під сумнів уявлення про те, що квантові атаки не можуть зламати LWE та подібні задачі на основі ґраток. Це припущення лежить в основі багатьох нових криптографічних схем. Проте вкрай важливо розуміти обмеження алгоритму та його потенційний вплив на існуючі системи шифрування на основі LWE.

Ключова проблема з алгоритмом Чена полягає в тому, що він працює оптимально, коли розмір задачі значно перевищує допустиму похибку. У практичних криптографічних схемах на основі LWE відношення модуля до шуму зазвичай підтримується низьким з міркувань безпеки. Навпаки, алгоритм Чена вимагає більшого відношення для досягнення поліноміального часу роботи.

Це обмеження вказує на те, що існуючі схеми шифрування на основі LWE з меншим відношенням модуля до шуму можуть залишатися безпечними проти поточного варіанта алгоритму Чена. Таким чином, хоча цей алгоритм є значним теоретичним проривом, він не становить безпосередньої загрози для безпеки всіх криптографічних систем на основі LWE.

Його робота підкреслює необхідність подальших досліджень у напрямку розробки квантово-стійких криптографічних примітивів.

Потенційні сфери застосування та стимули

Розробка ефективних квантових алгоритмів для задач на ґратках має далекосяжні наслідки для всіх секторів, які залежать від безпечного цифрового зв'язку та зберігання даних. Алгоритм Чена підкреслює загальну потребу в квантово-стійкому шифруванні.

Сюди належать такі галузі, як:

Кібербезпека: Надійні, квантово-стійкі методи шифрування є критично важливими для захисту конфіденційної інформації в еру квантових обчислень.
Державний сектор та оборона: Державні органи можуть використовувати ці досягнення для підвищення безпеки критичної інфраструктури та засекреченого зв'язку, мінімізуючи потенційні загрози, пов'язані з квантовими можливостями супротивників.
Фінансові послуги: Фінансовий сектор значною мірою покладається на безпечні канали зв'язку для проведення транзакцій та захисту даних. Квантово-стійкі криптографічні примітиви на основі задач на ґратках можуть допомогти забезпечити довгострокову безпеку фінансових систем.
Охорона здоров'я: Оскільки дані про охорону здоров'я стають все більш оцифрованими, забезпечення їхньої конфіденційності та цілісності має першорядне значення. Квантово-безпечні методи шифрування, отримані на основі роботи Чена, можуть допомогти захистити чутливу інформацію пацієнтів від майбутніх квантових атак.
Хмарні обчислення: Зі зростанням популярності хмарних послуг безпека даних, що зберігаються та обробляються в хмарі, викликає серйозне занепокоєння. Квантово-стійкі схеми шифрування на основі задач на ґратках можуть забезпечити додатковий рівень захисту хмарних додатків та сховищ даних.

Висновок

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

Розробка квантово-стійкої криптографії є не лише технічним викликом, але й стратегічним імперативом як для бізнесу, так і для урядів. Інвестиції в дослідження та розробки в цій галузі можуть принести значні довгострокові вигоди з точки зору безпеки та конфіденційності даних.

Джерела

Chen, Y. (2024). Квантові алгоритми для задач на ґратках: нова ера в криптографії ⧉. Journal of Quantum Computing and Cryptography, 7(4), 112-135.

Regev, O. (2005). Про ґратки, навчання з помилками, випадкові лінійні коди та криптографію. ⧉ In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (pp. 84-93).

Kuperberg, G. (2005). Субекспоненціальний квантовий алгоритм для діедральної проблеми прихованої підгрупи. ⧉ SIAM Journal on Computing, 35(1), 170-188.

Останній перегляд: 2026-06-23.

Останній перегляд 2026-07-02.

Перевидати цю статтю

Квантовий алгоритм кидає виклик криптографії на основі ґраток — Sebastien Rousseau

Новий поліноміальний квантовий алгоритм Йілей Чена атакує криптографію на основі ґраток з наслідками для постквантових стандартів, зокрема CRYSTALS-Kyber.

Ця стаття поширюється за ліцензією Creative Commons Attribution 4.0 International. Перевидання вимагає посилання на канонічну URL-адресу.

Квантовий алгоритм кидає виклик криптографії на основі ґраток — Sebastien Rousseau

Новий поліноміальний квантовий алгоритм Йілей Чена атакує криптографію на основі ґраток з наслідками для постквантових стандартів, зокрема CRYSTALS-Kyber.

Originally published at https://sebastienrousseau.com/uk/2024-04-15-kvantovyy-alhorytm-kydaye-vyklyk-hratkovii-kryptohrafiyi/ by Sebastien Rousseau.
Licensed under CC-BY-4.0.

SEBASTIEN ROUSSEAU FOUNDER · ENGINEER

Квантовий алгоритм кидає виклик криптографії на основі ґраток

Загальний огляд

Поліноміальний квантовий алгоритм Чена

Вступ до задач на ґратках та їх значення в криптографії

Класичні алгоритми для задач на ґратках та їх обмеження

Попередні спроби розробки квантових алгоритмів для LWE

Поліноміальний квантовий алгоритм Чена для LWE

Наслідки, обмеження та напрямки майбутніх досліджень

Потенційні сфери застосування та стимули

Висновок

Джерела

Скопіювати формат для Medium

Скопіювати формат для Mastodon

Копіювати відформатоване для LinkedIn

BibTeX

RIS

Vancouver

Chicago

APA

Перевидати цю статтю