Квантова ґраткова криптографія: помилка в атаці Чена на LWE

TL;DR. Помилка в квантовому алгоритмі LWE Yilei Chen тимчасово відстрочує загрозу для криптографії на основі ґраток. Що це означає для CRYSTALS-Kyber, Dilithium та дорожньої карти PQC.

Points clés

Квантова дилема: переоцінка стандартизації постквантової криптографії NIST у світлі алгоритму Yilei Chen. Після моєї нещодавньої статті про [Виклики квантових алгоритмів для криптографії на основі ґраток][00], я змушений надати оновлення щодо останніх подій у [дослідженні Yilei Chen ⧉][01].
Помилка в квантовому алгоритмі Чена. Помилка була виявлена на кроці 9 алгоритму Чена, і він заявив, що не знає, як її виправити.
Наслідки для процесу стандартизації постквантової криптографії NIST. Дослідження Чена опосередковано викликало занепокоєння та сумніви щодо [процесу стандартизації постквантової криптографії (PQC) NIST ⧉][03] та вибору стійких до квантових атак криптографічних алгоритмів.
Майбутнє постквантової криптографії. Виявлення помилки в алгоритмі Чена підкреслює критичну роль рецензування в науковому процесі.

Квантова дилема: переоцінка стандартизації постквантової криптографії NIST у світлі алгоритму Yilei Chen

Після моєї нещодавньої статті про Виклики квантових алгоритмів для криптографії на основі ґраток, я змушений надати оновлення щодо останніх подій у дослідженні Yilei Chen ⧉.

У результаті несподіваного повороту подій Yilei Chen, доцент Інституту міждисциплінарних інформаційних наук (IIIS) Університету Цінхуа, повідомив, що його колеги-вчені Hongxun Wu та Thomas Vidick незалежно один від одного виявили помилку в його квантовому алгоритмі поліноміального часу, розробленому для розв'язання задачі навчання з помилками (LWE).

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

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

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

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

Але відповідно до сторінки Nigel Smart ⧉, запропонована квантова атака на LWE є помилковою і не ставить під загрозу схеми граткової криптографії, такі як Kyber ⧉, Dilithium ⧉, BGV ⧉ або TFHE ⧉.

Наслідки для процесу стандартизації постквантової криптографії NIST

Дослідження Чена опосередковано викликало занепокоєння та сумніви щодо процесу стандартизації постквантової криптографії (PQC) NIST ⧉ та вибору стійких до квантових атак криптографічних алгоритмів.

Схеми CRYSTALS-KYBER та CRYSTALS-Dilithium, які є одними з фіналістів у процесі стандартизації PQC від NIST, є прикладами криптографічних схем на основі ґраток, які пройшли ретельне тестування та оцінку на стійкість до квантових загроз. Проте вкрай важливо продовжувати тестування та вдосконалення цих схем для забезпечення їхньої довгострокової безпеки та життєздатності.

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

Майбутнє постквантової криптографії

Виявлення помилки в алгоритмі Чена підкреслює критичну роль рецензування в науковому процесі. Це також висвітлює потребу в миттєвому рецензуванні, зворотному зв'язку та дискусіях.

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

Процес стандартизації PQC від NIST є важливим кроком у цьому напрямку, але це лише початок. Помилка в алгоритмі Чена є яскравим нагадуванням про виклики та невизначеності, які чекають попереду, але вона також слугує закликом до дії для криптографічної спільноти подвоїти свої зусилля та розширити межі можливого.

Це захоплива подія в галузі постквантової криптографії, і буде цікаво спостерігати за тим, як розвиватиметься процес стандартизації PQC від NIST у відповідь на цю нову інформацію.

Висновок

Помилка, виявлена в квантовому алгоритмі Yilei Chen для розв'язання задачі LWE, є свідченням важливості ретельного наукового рецензування та співпраці у розробці квантово-стійкої криптографії.

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

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

Джерела

Sebastien Rousseau, (2024). Квантовий алгоритм кидає виклик криптографії на основі ґраток.
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-16.

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

Квантова ґраткова криптографія: помилка в атаці Чена на LWE — Sebastien Rousseau

Помилка в квантовому алгоритмі LWE Yilei Chen тимчасово відстрочує загрозу для криптографії на основі ґраток. Що це означає для CRYSTALS-Kyber, Dilithium та дорожньої карти PQC.

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

Квантова ґраткова криптографія: помилка в атаці Чена на LWE — Sebastien Rousseau

Помилка в квантовому алгоритмі LWE Yilei Chen тимчасово відстрочує загрозу для криптографії на основі ґраток. Що це означає для CRYSTALS-Kyber, Dilithium та дорожньої карти PQC.

Originally published at https://sebastienrousseau.com/uk/2024-04-22-pomylka-v-kvantovomu-alhorytmi-dlya-hratkovoyi-kryptohrafiyi/ by Sebastien Rousseau.
Licensed under CC-BY-4.0.

SEBASTIEN ROUSSEAU FOUNDER · ENGINEER