Postkvantová kryptografie

Technology

12 hours ago

Author

Postkvantová kryptografie je klasická kryptografie, která je odolná vůči případným útokům kvantových počítačů. Znamená to takový způsob šifrování, že není znám algoritmus pro kvantový počítač, který by snížil složitost úlohy oproti klasickému algoritmu. Například kvantový Shorův algoritmus je schopen snížit složitost pro běžné problémy (viz jednosměrná funkce s padacími dvířky) jako je diskrétní logaritmus, faktorizace či kryptografie nad eliptickými křivkami. Roku 2015 NSA vyzvala americké instituce a společnosti k přípravě přechodu na odolné šifrování. Společnost Google tak již testuje její využití, protože se tak zabrání po letech zpětnému odkrytí komunikace, když bude současná kryptografie prolomena. Roku 2016 odstartoval projekt Open Quantum Safe, který zpřístupňuje otevřené knihovny. Speciální hardware (například RISC-V) může být bezpečnější a rychlejší než softwarová implementace kryptografie. I u algoritmů postkvantové kryptografie (které mají různé fixní parametry) nelze vyloučit, že obsahují zadní vrátka.

Příklady

Například algoritmus NTRU z roku 2009 založený na celočíselných mřížích odolá kvantovým počítačům, stejně jako RLWE-KEX (Ring-Learning with Errors), UOV (Unbalanced Oil and Vinegar), McEliece (Niederreiter), či supersingulární eliptické křivky a další. Po průlomové publikaci v roce 2014 bylo zjištěno, že algoritmy potřebují modifikaci, např. +more NTRU Prime. Pro 128bitovou bezpečnost algoritmy potřebují klíče délky jednotek tisíců bitů (NTRU, RLWE, supersingulární eliptické křivky) až po milióny bitů (McEliece).

NP těžký problém ale nemusí být zárukou NP těžkého prolomení (například Ajtai-Dwork či GGH).

Dalším příkladem mohou být prostředky umělé inteligence, jako jsou neuronové sítě, pracující na odlišných principech, něž na jakých pracují běžné šifrovací algoritmy založené na problémech teorie čísel.

Standardizace

NIST v druhém kole výběru kandidátských algoritmů roku 2020 vybral do třetího kola:

* pro šifrování: CRYSTALS-KYBER, NTRU, SABER (tyto založeny na mřížích) a Classic McEliece (Goppa code) * pro digitální podpisy: CRYSTALS-DILITHIUM, FALCON (tyto založeny na mřížích) a Rainbow (unbalanced oil and vinegar)

(Do třetího kola dále postupuje několik „alternativích“ kandidátů s tím, že pravděpodobnost úspěšného dokončení kola a následné standardizace je nízká: BIKE, FrodoKEM, HQC, NTRU Prime, SIKE, GeMSS, Picnic, and SPHINCS+.)

Roku 2022 bylo vybráno:

* pro šifrování: CRYSTALS-Kyber * pro digitální podpisy: CRYSTALS-Dilithium, FALCON a SPHINCS+

Proces standardizace bude dokončen v roce 2023. Standardy NIST pravděpodobně přijme i EU. Další algoritmy pro digitální podpisy se ale budou ještě vybírat.