Що таке постквантова криптографія (Post-Quantum Cryptography)?

Постквантова криптографія (PQC) — це напрям криптографії, що займається розробкою алгоритмів, стійких до атак квантових комп’ютерів. Актуальність підходу зумовлена тим, що потужні квантові комп’ютери зможуть легко зламувати більшість сучасних методів шифрування: вони здатні дуже швидко виконувати обчислення, непосильні для класичних комп’ютерів. 

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

Чому квантові комп’ютери загрожують сучасній криптографії?

Більшість широко використовуваних криптосистем (RSA, алгоритми на еліптичних кривих тощо) спираються на математичні задачі факторизації великих чисел чи дискретного логарифмування, які звичайним комп’ютерам розв’язати вкрай важко.

Квантові комп’ютери здатні розв’язувати такі задачі набагато швидше, підриваючи стійкість класичних алгоритмів шифрування. Зокрема, відомий алгоритм Шора для квантової машини дозволяє ефективно розкладати велетенські числа на прості множники, фактично зламуючи RSA‐шифрування. Аналогічно, квантовий алгоритм для дискретного логарифму ставить під загрозу алгоритми на еліптичних кривих (ECDSA, ECC).

Крім асиметричних схем, квантові обчислення впливають і на симетричні алгоритми (AES, SHA тощо). Хоча симетричні шифри вважаються більш стійкими, алгоритм Гровера на квантовому комп’ютері може прискорити перебір ключа, фактично зменшуючи ефективну довжину ключа вдвічі. Тобто 256-бітний ключ забезпечуватиме такий рівень безпеки, як 128-бітний у класичній моделі. Відповідно, щоб зберегти надійність, довжину ключів симетричних алгоритмів необхідно збільшувати (наприклад, перейти з 128-бітних ключів AES на 256-бітні).

Принципи та напрямки постквантової криптографії

Постквантові алгоритми базуються на задачах, які вважаються складними як для класичних, так і для квантових комп’ютерів. Криптографи досліджують різні математичні основи, що не піддаються прискоренню за допомогою відомих квантових алгоритмів. Серед основних підходів, на яких ґрунтуються постквантові криптосистеми:

• Алгоритми на геш-функціях. Використовують властивості криптографічних гешів (хешів). Класичний приклад — підписи Меркла, що побудовані на дереві геш-функцій. Такі хеш-підписи дуже стійкі до квантових атак (адже стійкість геш-функцій підривається квантово лише частково, через алгоритм Гровера), проте мають недолік: обмежену кількість підписів від одного ключа і великі розміри відкритих ключів. Попри це, сучасні реалізації (наприклад, SPHINCS+) усувають деякі обмеження і вже стандартизовані для використання.
  
• Алгоритми на кодах виправлення помилок. Ґрунтуються на складності декодування зашифрованих повідомлень, використовуючи теорію коректувальних кодів. Найвідоміший представник — шифрування МакЕліса (McEliece), розроблене ще у 1970-х. Воно досі не зламане ні класичними, ні квантовими методами, хоча має дуже великий розмір публічного ключа (сотні кілобайт). Кодові алгоритми розглядаються як перспективні кандидати для шифрування і обміну ключами. Наприклад, у 2025 році алгоритм HQC (Hamming Quasi-Cyclic), що базується на кодах, був обраний як резервний стандарт для постквантового шифрування.
  
• Алгоритми на ґратках (латтисна криптографія). Використовують задачі з геометрії чисел — пошук векторів у багатовимірних ґратках (решітках). Це один із найбільш досліджених і перспективних напрямків PQC. Приклади: алгоритми на задачі пошуку найближчого вектора чи розв’язку «шумових» рівнянь (Learning With Errors). Саме до цього класу належать багато фіналістів конкурсів постквантових алгоритмів: CRYSTALS-Kyber (шифрування) та CRYSTALS-Dilithium (цифровий підпис) побудовані на решітках і показали відмінне поєднання швидкості та відносно невеликого розміру ключів. Інші приклади решіткових схем — NTRU, SABER, FrodoKEM тощо. Перевага решіткових алгоритмів — висока швидкість та компактність (Kyber шифрує швидше за RSA і має набагато менший ключ, порядку кількох сотень байт). Недолік — доведена стійкість ґраткових задач поки не така сильна, як факторизації, і можливі нові математичні атаки; також деякі реалізації вимогливі до ресурсів (потрібно багато операцій лінійної алгебри).
  
• Алгоритми на багатовимірних поліномних системах. Ця категорія охоплює схеми, що базуються на складності розв’язання систем нелінійних багатовимірних рівнянь (як правило, квадратичних). Приклад — криптосистема Rainbow (багатовимірні сигнатури), яка свого часу була кандидатом на стандарт. Ідея полягає в тому, що знаходження ключа з набору поліноміальних рівнянь є вкрай складною задачею. Хоча деякі такі схеми були зламані або ослаблені криптоаналітиками (той же Rainbow піддалась успішній атаці на класичному комп’ютері у 2022 році), напрямок Multivariate все ще розвивається.
  
• Алгоритми на ізогеніях еліптичних кривих. Досить вузький, але цікавий напрям: використовуються так звані суперсингулярні ізогенії — особливі відображення між еліптичними кривими. Схеми на ізогеніях, як-от SIKE (Supersingular Isogeny Key Exchange), пропонували компактні ключі і були багатообіцяючими для обміну ключами. На жаль, у 2022 році алгоритм SIKE був зламаний класичним методом (математичну лазівку знайшли до появи квантових комп’ютерів). Попри це, дослідження ізогеній тривають, і вони залишаються альтернативним підходом для побудови квантовостійких протоколів.

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

Стандартизація та приклади постквантових алгоритмів

У 2016 році Національний інститут стандартів і технологій США (NIST) оголосив відкритий конкурс на квантовистійкі алгоритми. Протягом кількох раундів було розглянуто десятки кандидатів з усього світу. У липні 2022 року NIST оголосив перших переможців цього шестирічного відбору. До списку увійшли:

• CRYSTALS-Kyber — алгоритм шифрування та обміну ключами (Key Encapsulation Mechanism), оснований на решітках. Забезпечує секретний обмін ключами між сторонами.
• CRYSTALS-Dilithium — схема цифрового підпису на решітках. Забезпечує підтвердження автентичності та цілісності даних.
• FALCON — ще один алгоритм цифрового підпису на ґратках (використовує NTRU-решітки та швидке перетворення Фур’є).
• SPHINCS+ — схема цифрового підпису на основі геш-функцій (статична багаторазова версія геш-підписів Меркла).

Kyber і Dilithium наразі вважаються основними стандартами для постквантового шифрування та підписів відповідно. NIST у серпні 2024 року випустив фінальні стандарти для цих алгоритмів: Kyber отримав офіційну назву ML-KEM (Module-Lattice Key Encapsulation Mechanism), а Dilithium — ML-DSA (Module-Lattice Digital Signature Algorithm). Одночасно стандартом став і SPHINCS+ як резервний алгоритм підпису (в стандарті його назвали SLH-DSA, Stateless Hash-based DSA) — він базується на зовсім іншій математичній ідеї (геш-дерев), щоб підстрахувати випадок, якщо основний решітковий підпис раптом виявиться вразливим. Таким чином, вперше затверджено набір постквантових алгоритмів на державному рівні.

У 2025 році NIST додатково обрав HQC (Hamming Quasi-Cyclic) — алгоритм на кодах — в якості резервного стандарту для шифрування. HQC має слугувати запасним варіантом на випадок, якщо згодом будуть виявлені слабкі місця у головного алгоритму (Kyber) на ґратковій основі. Це відображає стратегію диверсифікації криптографії: використовувати різні математичні підходи паралельно/

Перспективи та виклики впровадження

Нові алгоритми потрібно не лише стандартизувати, а й реалізувати у безлічі протоколів і пристроїв: від веб-браузерів і серверів до банкоматів, смарт-карт і блокчейн-гаманців. Виклики впровадження включають сумісність (наприклад, старі пристрої можуть не підтримувати великі ключі), оптимізацію продуктивності (деякі PQC-алгоритми повільніші чи споживають більше пам’яті) та управління ключами.

Експерти з безпеки наголошують: щоб уникнути катастрофічних наслідків, готуватися до квантового переходу треба вже зараз. За рекомендаціями NIST, упродовж найближчих років слід поступово відмовитися від уразливих алгоритмів: до 2030 року припинити їх використання у нових системах, а до 2035 року повністю замінити на квантовостійкі стандарти. Масова міграція на квантовостійкі алгоритми вимагатиме злагоджених зусиль стандартизаторів, розробників програмного забезпечення і апаратних виробників. Ідеальний сценарій полягає в тому, що через декілька років постквантові методи шифрування стануть невидимим стандартом всюди — від веб-сайтів до банкових систем — і користувачі будуть захищені від квантових атак, навіть не задумуючись про це.

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