Postkvantová kryptografie

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 č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]

PříkladyEditovat

Například algoritmus NTRU založený na celočíselných mřížích odolá kvantovým počítačům.[4]

Dále je to RLWE-KEX (Ring-Learning with Errors), UOV (Unbalanced Oil and Vinegar), McEliece (či Niederreiter), supersingulární eliptické křivky a další.

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).

Po průlomové publikaci v roce 2014 bylo zjištěno, že algoritmy potřebují modifikaci (například NTRU Prime).[5]

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

StandardizaceEditovat

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

  • 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)

Výběr by mohl být ukončen v roce 2022.

ReferenceEditovat

  1. https://arstechnica.com/information-technology/2015/08/nsa-preps-quantum-resistant-algorithms-to-head-off-crypto-apocolypse/ - NSA preps quantum-resistant algorithms to head off crypto-apocalypse
  2. https://techxplore.com/news/2016-07-software-post-quantum-cryptography-chrome.html - Software engineer announces experiment with post-quantum cryptography in Chrome
  3. https://openquantumsafe.org/ - OPEN QUANTUM SAFE - software for prototyping quantum-resistant cryptography
  4. http://tbuktu.github.io/ntru/ - NTRU Quantum-resistant cryptography (anglicky)
  5. https://eprint.iacr.org/2016/461.pdf - Bernstein: NTRU Prime
  6. https://csrc.nist.gov/publications/detail/nistir/8309/final - Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process