Postkvantová kryptografie

Postkvantová kryptografie (, zkráceně PQC), někdy také označovaná anglickým termínem Quantum-Safe (v doslovném překladu „kvantově bezpečná“), je oblast kryptografie zaměřující se na kryptografické algoritmy, které jsou odolné vůči útokům využívajícím kvantové počítače.

Přesněji, termín postkvantová kryptografie se používá v kontextu asymetrické kryptografie (neboli kryptografie s veřejným klíčem), jelikož bezpečnost všech prakticky používaných asymetrických algoritmů – jako RSA, (EC)DH a (EC)DSA – závisí na těžkosti faktorizace a diskrétního logaritmu. V kontextu postkvantové kryptografie je pro tyto kryptografické algoritmy používán termín „klasické (kryptografické) algoritmy“. Důvodem je, že útoky využívající kvantové počítače jsou právě efektivní vůči těmto klasickým algoritmům viz Motivace.

I u algoritmů postkvantové kryptografie (které mají různé fixní parametry) ale nelze vyloučit, že obsahují zadní vrátka.

Motivace Hlavní motivací pro vývoj postkvantových algoritmů je tzv. Shorův algoritmus vynalezen v roce 1994 Peterem Shorem. Shorův algoritmus je kvantový polynomiální algoritmus na řešení problémů faktorizace a diskrétního logaritmu. Oba tyto problémy jsou „těžké“ pro klasické počítače.

Nejefektivnější klasický algoritmus pro řešení problému faktorizace je General Number Field Sieve (GNFS), který má subexponenciální složitost. Nejefektivnější klasické algoritmy pro řešení problému diskrétního logaritmu nad konečným tělesem jsou Function Field Sieve (FFS) a modifikace General Number Field Sieve (GNFS). Oba tyto algoritmy mají subexponenciální složitost a vycházejí z algoritmu Index Calculus. Nejefektivnější klasické algoritmy pro řešení problému diskrétního logaritmu nad eliptickými křivkami je Pollardův rho algoritmus, což je generický algoritmus, který má exponenciální složitost.

Z toho plyne, že Shorův algoritmus je exponenciálně rychlejší než klasické algoritmy. Jeho polynomiální složitost znamená, že nelze jednoduše navýšit parametry klasických kryptografických algoritmů s veřejným klíčem, což bylo dosavadní řešení následků objevu subexponenciálních algoritmů a obecně zvyšujícího výpočetního výkonu klasických algoritmů. Je tedy nutné vynalézt zcela nové kryptografické algoritmy s veřejným klíčem, jejichž bezpečnost nesouvisí s faktorizací nebo diskrétním logaritmem.

Vývoj kvantových počítačů Důležitou otázkou je kdy a zdali vůbec bude existovat „dost výkonný“ kvantový počítač, který bude schopen spustit Shorův algoritmus se vstupem odpovídajícím standardním kryptografickým parametrům – například faktorizace 3072bitového modulu aktuálně používaného v RSA.

Kvantové počítače již existují, ale jejich výpočetní výkon je aktuálně daleko od výkonu, který je nutný na faktorizaci velkých čísel. Pro rozlišení aktuálních (málo výkonných) kvantových počítačů od „výkonných“ kvantových počítači se používá termín kryptograficky relevantní kvantový počítač (anglicky Cryptographically Relevant Quantum Computer, zkráceně CRQC). Tento termín není rigorózně definován, ale předpokládá se, že takový kvantový počítač musí disponovat 1000+ logickými qubity.

Nutno podotknout, že je rozdíl mezi tzv. logickým qubitem a fyzickým qubitem. Logický qubit je idealizovaný matematický model qubitu, který se používá při návrhu kvantových algoritmů apod. Naopak fyzický qubit je reálný fyzický objekt, který se používá pro konstrukci logického qubitu. Logické qubity jsou konstruovány pomocí tzv. kvantových samoopravných kódů. V praxi je potřeba 10-1000Toto rozpětí je velké, jelikož záleží i na dalších vlastnostech zkontruovaných qubitů jako jejich chybovost apod. fyzických qubitů pro konstrukci jednoho logického qubitu. Aktuálně se předpokládá, že na faktorizaci 2048bitového RSA modulu je potřeba okolo 1 milionu fyzických qubitů – je velice pravděpodobné, že toto číslo se v budoucnu změní.

Kdy, a jestli vůbec, tyto výkonné kvantové počítače budou vyvinuty není jasné. Německá bezpečnostní agentura BSI ve studii z roku 2025 předpokládá, že by mohly být vyvinuty do 16 let. Organizace Global Risk Institute každý rok oslovuje významné osobnosti v oboru vývoje kvantových počítačů a zveřejňuje jejich predikce. Například více než 60 % respondentů si myslí, že je aspoň 50% pravděpodobnost, že budou vyvinuty do 15 let.

Lze také extrapolovat postoje různých organizací dle jejich migračních plánů. USA plánuje do roku 2033 zmigrovat svou kritickou infrastrukturu na postkvantovou kryptografii. Velká Británie a Evropská unie plánují tyto migraci provést do roku 2035, přičemž kritickou infrastrukturu do roku 2030.

Ulož teď, dešifruj poté Jedním z hlavních důvodů proč se přechází na postkvantovou kryptografii před existencí kryptograficky relevantních kvantových počítačů, je fakt, že útočník může provést útočnou strategii „Ulož teď, dešifruj poté“ (anglicky Harvest now, decrypt later). V ní jde o to, že útočník může aktuálně začít nahrávat a ukládat šifrovanou komunikaci a počkat do budoucna, až bude mít přístup ke kryptograficky relevantnímu kvantovému počítači a následně dešifrovat nahranou komunikaci. Nutno podotknout, že tento útok se netýká digitálních podpisů, ale týká se asymetrických šifer a algoritmů na výměnu klíče jako RSA a Diffie-Hellman (DH) (i DH nad eliptickými křivkami).

Dále je nutno podotknout, že protokoly s vlastností dopředné bezpečnosti (anglicky forward secrecy) nejsou chráněny proti tomuto útoku. Dopředná bezpečnost pouze zaručuje, že v případě prozrazení dlouhodobého klíče, útočník není schopen dešifrovat předchozí komunikaci. Kvantový útočník ale může prolomit tzv. jednorázové (ephemerální) klíče, které jsou součástí nahrané komunikace.

Historie a standardizace První snahy o (vědomý)Algoritmy jako McEliece (1978) nebo NTRU (1998) jsou technicky postkvantové, ale nebyly vědomě vyvinuty jako odolné Shorovu algoritmu. vývoj postkvantových algoritmů se dají vysledovat do roku 2006, kdy se odehrála první PQCrypto konference zaměřující se na vývoj postkvantových algoritmů. V následující letech proběhly další ročníky PQCrypto konference a v roce 2009 vyšla kniha s názvem Post-Quantum Cryptography, která shrnuje poznatky o postkvantové kryptografii do roku 2009.

V roce 2016 Národní institut standardů a technologie (NIST) odstartoval proces, jehož cílem bylo vyvinout a standardizovat postkvantové algoritmy. Tento standardizační proces byl otevřený neboli každý mohl předložit svou konstrukci postkvantového algoritmu – NIST se specificky zajímal o digitální podpisová schémata, asymetrické šifry a tzv. mechanismy zapouzdření klíče (anglicky Key Encapsulation Mechanism, zkráceně KEM). Standardizační proces měl celkem 4 kola. Na začátku bylo celkem 69 postkvantových algoritmů. Během následujících kol byla většina algoritmů prolomena. Některé algoritmy sice nebyly prolomeny, ale byly vyřazeny z jiných důvodů jako například, že byly méně efektivní než jejich alternativy.

V roce 2022 skončilo 3. kolo a byly prioritně vybrány 4 algoritmy na standardizaci:

ML-KEM (Module-Lattice Key Encapsulation Mechanism, původní název CRYSTALS-Kyber) je KEM založený na strukturovaných mřížích, ML-DSA (Module-Lattice Digital Signature Algorithm, původní název CRYSTALS-Dilithium) je podpisové schéma založené na strukturovaných mřížích, FN-DSA (FFT-over-NTRU-Lattice-Based Digital Signature Algorithm, původní název Falcon) je podpisové schéma založené na strukturovaných mřížích. SLH-DSA (Stateless Hash-Based Digital Signature Algorithm, původní název SPHINCS+) je podpisové schéma založené na hašovacích funkcích.

Proces dodatečně pokračoval do 4. kola s cílem vybral alternativní KEM k algoritmu ML-KEM. Čtvrté kolo skončilo na jaře 2025 a byl dodatečně vybrán algoritmus HQC založený na samoopravných kódech.

V roce 2024 NIST vydal finální standardy pro ML-KEM (FIPS 203), ML-DSA (FIPS 204) a pro SLH-DSA (FIPS 205). Pro FN-DSA a HQC aktuálně neexistuje finální standard.

V roce 2022 NIST také spustil nový nezávislý proces na dodatečnou standardizaci postkvantových podpisových schémat. Důvodem pro tento dodatečný proces je to, že podpisová schémata vybraná během původního procesu nejsou dostatečně diverzifikovaná z pohledu bezpečnostních předpokladů. Bezpečnost obou schémat ML-DSA a FN-DSA závisí na obtížnosti problémů souvisejících se strukturovanými mřížemi. Bezpečnost schématu SLH-DSA sice závisí na jiném těžkém problému (odolnost hašovací funkce vůči získání jiné předlohy, anglicky second pre-image resistance), ale toto schéma nemá univerzální výkonnostní profil – malé veřejné klíče (32-64 bytů), ale veliké podpisy (7856-49856 bytů). V roce 2024 začalo druhé kolo této dodatečné standardizace, do kterého postoupilo celkem 14 podpisových schémat.

Postkvantové algoritmy Postkvantové algoritmy se dají rozdělit do kategorií podle oblasti matematiky, ze které pochází těžký problém, na kterém bezpečnost daného schématu závisí. Hlavní kategorie postkvantových algoritmů jsou mřížové, kódové, multivarietní, hašovací a izogenní.

Algoritmy ze stejné kategorie mají typicky podobný výkonnostní profil. Například mřížové algoritmy jsou obvykle rychlé, ale jejich veřejné klíče jsou velké (nižší tisíce bytů), naopak například izogenní algoritmy jsou obvykle pomalé, ale jejich veřejné klíče jsou malé (desítky nebo nižší stovky bytů).

Algoritmy založené na mřížích Základní těžký problém pro postkvantovou kryptografii založenou na mřížích je hledání nejkratšího vektoru v mříži (anglicky Shortest Vector Problem, zkráceně SVP). Existují různé další varianty tohoto problému jako hledání nejbližšího vektoru v mříži (anglicky Closest Vector Problem, zkráceně CVP) nebo uvolněné varianty těchto problému, kde nejde o to najít ten nejkratší/nejbližší vektor, ale nějaký který je mu "dost blízko"; tyto problémy poté mají předponu "Gap" (GapSVP, GapCVP, etc.).

Learning With Errors (LWE) Dalším významným problémem souvisejícím s mřížemi je tzv. učení s chybami (anglicky Learning With Errors, zkráceně LWE). Tento problém je významný pro kryptografické konstrukce, jelikož existuje důkaz, že průměrné instance tohoto problému jsou aspoň tak těžké jako ty nejtěžší instance GapSVP. Tento fakt je důležitý pro kryptografické konstrukce, jelikož umožňuje jednoduše generovat instance tohoto problému, které jsou prokazatelně těžké. V klasické kryptografii je tato vlastnost také důležitá. Například v případě problému faktorizace (RSA) je vysoce pravděpodobné, že součin dvou velkých náhodných prvočísel je faktorizovat, ale existují instance, kde je to lehké – například když daná prvočísla jsou příliš blízko u sebe.

LWE problém je definován následovně. Nechť je vektor a pravděpodobnostní distribuce nad , pak tzv. LWE distribuce je pravděpodobnostní distribuce nad množinou definována tak, že rovnoměrně náhodně zvolíme vektor a zvolíme skalár a výstupem je pár , kde značí skalární součin nad a součet je v .

Hledací varianta LWE problému (Search-LWE) je následující: Je dáno nezávislých vzorků z distribuce a úkolem je najít .

Rozhodovací varianta LWE problému (Decision-LWE) je následující: Je dáno nezávislých vzorků z distribuce , nebo nezávislých vzorků z rovnoměrné distribuce nad . Úkolem je rozhodnout z jaké distribuce (LWE distribuce, nebo rovnoměrné) vzorky jsou.

Module Learning With Errors (MLWE) Module Learning With Errors (MLWE) je zobecnění LWE problému. Je definován obdobně jako klasický LWE, akorát že místo se používá okruh , kde je monický polynom stupně , a místo skalárního součinu se používá součin v okruhu (násobení polynomů). Tato modifikace také znamená, že MLWE se neredukuje na SVP problém nad celočíselnými mřížemi, ale na SVP nad modulovými mřížemi.

Dalším blízkým problémem k LWE and MLWE je tzv. RLWE (Ring-LWE). Ten je definován obdobně jako MLWE, akorát že (rank modulu). MLWE je totiž vlastně zobecnění LWE and RLWE. LWE z MLWE: , neboli předpokládáme polynomy stupně 1, což jsou skaláry. Vzorek z LWE distribuce je pár , kde (vektor délky , s hodnotami v ,) a je skalár z .