Postkvantová kryptografie

Postkvantová kryptografie (Post-quantum cryptography, PQC) je 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í.[1] 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.[2] Roku 2016 odstartoval projekt Open Quantum Safe, který zpřístupňuje otevřené knihovny.[3] Speciální hardware (například RISC-V) může být bezpečnější a rychlejší než softwarová implementace kryptografie.[4] 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[5] 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ř. NTRU Prime[6]. 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).[7]

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:[8]

  • 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:[9]

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

Standardy NIST pravděpodobně přijme i EU.[10] Další algoritmy pro digitální podpisy se ale budou ještě vybírat.[11]

V roce 2024 byla standardizace dokončena vydáním příslušných standardů FIPS (Federal Information Processing Standards).[12] Šifrování je zdarma i pro komerční účely a v USA budou pro vládní účely povinné od roku 2030.[13]

Reference

  1. ↑ GOODIN, Dan. NSA preps quantum-resistant algorithms to head off crypto-apocalypse. Ars Technica [online]. 2015-08-21 [cit. 2024-08-29]. Dostupné online. (anglicky) 
  2. ↑ OWANO, Nancy; XPLORE, Tech. Software engineer announces experiment with post-quantum cryptography in Chrome. techxplore.com [online]. [cit. 2024-08-29]. Dostupné online. (anglicky) 
  3. ↑ https://openquantumsafe.org/ - OPEN QUANTUM SAFE - software for prototyping quantum-resistant cryptography
  4. ↑ MUNICH, Technical University. Chip with secure encryption will help in fight against hackers. techxplore.com [online]. [cit. 2024-08-29]. Dostupné online. (anglicky) 
  5. ↑ http://tbuktu.github.io/ntru/ - NTRU Quantum-resistant cryptography (anglicky)
  6. ↑ https://eprint.iacr.org/2016/461.pdf - Bernstein: NTRU Prime
  7. ↑ Vytvořit kryptosystém založený na NP-těžkém problému ještě nestačí. www.itbiz.cz [online]. [cit. 2023-11-27]. Dostupné online. 
  8. ↑ https://csrc.nist.gov/publications/detail/nistir/8309/final - Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process
  9. ↑ https://www.nist.gov/news-events/news/2022/07/nist-announces-first-four-quantum-resistant-cryptographic-algorithms - NIST Announces First Four Quantum-Resistant Cryptographic Algorithms
  10. ↑ https://techxplore.com/news/2022-07-future-encryption.html - The future of encryption
  11. ↑ NIST Announces Additional Digital Signature Candidates for the PQC Standardization Process [online]. [cit. 2023-07-24]. Dostupné online. 
  12. ↑ Postřehy z bezpečnosti: kvantové šifrování, rekordní DDoS útoky a nové zranitelnosti. www.root.cz [online]. [cit. 2024-08-19]. Dostupné online. 
  13. ↑ Qubity: Standardy pro post-kvantové šifrování, PQC přinese velký byznys, test kvantové inerciální navigace. www.lupa.cz [online]. [cit. 2024-08-19]. Dostupné online. 

Související články

Externí odkazy

  • Stochastické blokové šifrování počítačových souborů neuronovou sítí
  • Kvantová hrozba a kvantově odolná kryptografie