Postkvantová kryptografie

Postkvantová kryptografie (anglicky Post-Quantum Cryptography, 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.

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 3072-bitové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í logických qubitů pomocí tzv. kvantových samoopravných kódů. V praxi je potřeba 10-1000 fyzických qubitů pro konstrukci jednoho logického qubitu. Aktuálně se předpokládá, že na faktorizaci 2048-bitového RSA modulu je potřeba okolo 1 milionu fyzických qubitů – je velice pravděpodobné, že toto číslo se v budoucnu změní.

Nikdo neví kdy, a jestli vůbec, tyto výkonné kvantové počítače budou vyvinuty. 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.

Můžeme 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.

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 již může provést tzv. „Ulož teď, dešifruj poté“ (anglicky Harvest now, decrypt later) útokovou strategii. Jde o to, že útočník aktuálně může začít nahrávat a ukládat šifrovanou komunikaci a vyč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ý) 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éma ML-DSA a FN-DSA závisí na těžkosti 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ť $\mathbf {s} \in \mathbb {Z} _{q}^{n}$ je vektor a ${\mathcal {X}}$ pravděpodobnostní distribuce nad $\mathbb {Z} _{q}^{n}$, pak tzv. LWE distribuce $A_{s,{\mathcal {X}}}$ je pravděpodobnostní distribuce nad množinou $\mathbb {Z} _{q}^{n}\times \mathbb {Z} _{q}$ definována tak, že rovnoměrně náhodně zvolíme vektor $\mathbf {a} \in \mathbb {Z} _{q}^{n}$ a zvolíme skalár $e\leftarrow {\mathcal {X}}$ a výstupem je pár $(\mathbf {a} ,b=\langle \mathbf {a} ,\mathbf {s} \rangle +e)$, kde $\langle \cdot ,\cdot \rangle$ značí skalární součin nad $\mathbb {Z} _{q}^{n}$ a součet je v $\mathbb {Z} _{q}^{n}$.

Hledací varianta LWE problému (Search-LWE) je následující: Je dáno $m\in \mathbb {N}$ nezávislých vzorků z distribuce $A_{s,{\mathcal {X}}}$ a úkolem je najít $\mathbf {s} \in \mathbb {Z} _{q}^{n}$.

Rozhodovací varianta LWE problému (Decision-LWE) je následující: Je dáno $m\in \mathbb {N}$ nezávislých vzorků z distribuce $A_{s,{\mathcal {X}}}$, nebo $m\in \mathbb {N}$ nezávislých vzorků z rovnoměrné distribuce nad $\mathbb {Z} _{q}^{n}\times \mathbb {Z} _{q}$. Ú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 $\mathbb {Z} _{q}$ se používá okruh $\mathbb {Z} _{q}[x]/(f(x))$, kde $f(x)\in \mathbb {Z} _{q}[x]$ je monický polynom stupně $d$, 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 $n=1$ (rank modulu). MLWE je totiž vlastně zobecnění LWE and RLWE.

• LWE z MLWE: $d=1,n>1$, neboli předpokládáme polynomy stupně 1, což jsou skaláry. Vzorek z LWE distribuce je pár $(\mathbf {a} ,b)$, kde $\mathbf {a} \in \mathbb {Z} _{q}^{n}$ (vektor délky $n$, s hodnotami v $\mathbb {Z} _{q}^{n}$,) a $b$ je skalár z $\mathbb {Z} _{q}$.
• RLWE z MLWE: $d>1,n=1$, neboli předpokládáme jeden polynom stupně $d>1$. Vzorek z MLWE distribuce je pár $(\mathbf {a} ,b)$, kde $\mathbf {a} \in (\mathbb {Z} _{q}[x]/(f(x)))^{n}$ (vektor polynomů stupně $d$ s koeficienty z $\mathbb {Z} _{q}$ délky $n$) a $b$ je polynom stupně $d$ s koeficienty z $\mathbb {Z} _{q}$.

Pozorujme, že související problémy mají následující vztahy:

• RLWE ≤ LWE, neboli pokud umím vyřešit LWE, tak umím vyřešit RLWE. Rovnice $a(x)\cdot s(x)+e(x)=b(x)\in \mathbb {Z} _{q}[x]/(f(x))$ se dá rozložit na $d$ LWE rovnic tvaru $\langle a,s\rangle +e=b\in \mathbb {Z} _{q}$. Celkem tedy na vyřešení RLWE s $m$ vzorky, potřebujeme umět řešit LWE s $m\cdot d$ vzorky. Nutnou podotknout, že LWE s $m\cdot d$ vzorky je lehčí než LWE s "jen" $m$ vzorky – struktura RLWE nám tedy dává "vzorky navíc".
• RLWE ≤ MLWE, neboli pokud umím vyřešit MLWE, tak umím vyřešit RLWE. Toto plyne z toho, že MLWE je generalizace RLWE.

Kryptosystémy

Na bázi mřížových problémů bylo vytvořeno mnoho kryptosystémů. Do této skupiny právě patří tři algoritmy vybrané pro standardizaci americkým NISTem: ML-KEM, ML-DSA a FN-DSA. "ML" v jejich názvu značí "Module Lattice" neboli "modulovou mříž". Modulové mříže korespondují s právě s problémem MLWE. FN-DSA není založený na LWE, ale na jiném mřížovém problému zvaném NTRU.

Algoritmy založené na samoopravných kódech

Z teorie samoopravných kódů pocházejí těžké problémy, které jsou i těžké pro kvantové počítače. Jedním takovým problémem je tzv. problém dekódování syndromu (anglicky Syndrome Decoding problem, zkráceně SDP).

SDP je definován následovně. Nechť $n,k,t\in \mathbb {N}$, $H\in \mathbb {F} _{2}^{n-k\times n}$ je kontrolní matice (binárního) kódu (kód je délky $n$ and dimenze $k$ ) a $c\in \mathbb {F} _{2}^{n-k}$ ($c$ se nazývá syndrom), najdi takové $e\in \mathbb {F} _{2}^{n}$, že jeho Hammingova váha je maximálně $t$, neboli ($wt(e)\leq t$), a $He=c$.

Sice je SDP je NP-těžký problém, ale to nám neříká nic o tom jak je těžká náhodná instance tohoto problému. Na rozdíl od LWE, pro SDP není znám důkaz redukující průměrnou instanci tohoto problému na nejtěžší instanci.

Classic McEliece je kryptosystém, který používá tzv. Goppa kód, u kterého se předpokládá, že pro náhodný Goppa kód je SDP těžký problém. Nutno podotknout, že Classic McEliece vychází z kryptosystémů McEliece a Niederreiter – Classic McEliece je v podstatě vylepšený Niederreiter s Goppa kódem, co byl použitý právě v původním McEliece kryposystému.

HQC a BIKE jsou další kryptosystémy založené na samoopravných kódech.

HQC byl vybrán pro standardizaci NISTem jako alternativní KEM k mřížovému ML-KEM. Classic McEliece sice nebyl vybrán NISTem, ale byl vybrán pro standardizaci organizací ISO.

Algoritmy založené na hašovacích funkcích

Existují také postkvantové algoritmy, jejichž bezpečnost pouze závisí na bezpečnosti hašovací funkce. Jedním takovým příkladem je SLH-DSA, což je digitální podpis standardizovaný NISTem.

Algoritmy založené na rovnicích o více proměnných

Těžkým problémem pro kvantové počítače je také řešení soustavy kvadratických rovnic o více proměnných nad konečným tělesem. Kandidáti na standardizaci z této kategorie se v původním NIST standardizaci nedostali do třetího kola. Například podpisové schéma Rainbow bylo favorit na standardizaci, ale bylo následně prolomeno.

Aktuálně jsou v procesu dodatečné standardizace NISTem 4 podpisová schémata z této kategorie: MAYO, QR-UOV, SNOVA a UOV.

Algoritmy založené na izogeniích mezi eliptickými křivkami

Další kategorie těžkých problémů pro kvantové počítače pochází z teorie eliptických křivek. Izogenie (anglicky isogeny) je zobrazení mezi eliptickými křivkami. Těžkým problémem je nalézt toto zobrazení (splňující různé požadavky) mezi dvěma eliptickými křivkami.

Nutno podotknout, že některé klasické kryptosystémy jsou také spojené s teorií eliptických křivek, ale jde o fundamentálně jiný problém – jedná se o diskrétní logaritmus nad grupou bodů eliptické křivky. Tento problém se dá řešit Shorovým algoritmem, na rozdíl od problémů související s izogeniemi.

Nejznámější kryptosystém z této kategorie je (byl) SIKE. Tento kryptosystém byl prolomen (klasicky) v roce 2022. SIKE byl založen na trochu modifikovaném problému hledání izogenie, který byl právě ukázán, že není těžký. Původní problém ale stále zůstává těžký.

Alternativou k SIKE je kryptosystém CSIDH. U CSIDH se ukázalo, že navržené parametry nedosahují dostatečné bezpečnosti. V případě více bezpečných parametrů ale CSIDH není moc kompetitivní.

V roce 2025 byla navržena alternativa k CSIDH/SIKE jménem PEGASIS.

Existuje také podpisové schéma SQISign, které je aktuálně v procesu dodatečné standardizace NISTem.

Přechod na postkvantovou kryptografii

Přechod (migrace) na postkvantovou kryptografii aktuálně probíhá. Zde je seznam technologií, které aktuálně používají postkvantovou kryptografii:

• Prohlížeče Google Chrome a Firefox podporují postkvantovou výměnu klíče v protokolu TLS (specificky hybrid složený z klasického ECDSA a postkvantového ML-KEM). Postkvantová výměna klíče je také od verze 3.5 podporována TLS knihovnou OpenSSL. Aktuálně 50 % internetové provozu je postkvantově zabezpečeno.
• Komunikační aplikace Signal nebo iMessage používají postkvantovou výměnu klíče.
• VPN software Mullvad podporuje postkvantovou výměnu klíče.
• Postkvantová kryptografie je součástí knihoven kryptografických Botan, BouncyCastle a OpenSSL.

Související články

• Kvantová kryptografie
• Kryptografie
• Kryptoanalýza
• Šifrování dat

Externí odkazy

• Post-Quantum Cryptography Neural Network