chapter fourteen

14. Post-quantum cryptography

 

This chapter covers:

  • Quantum computers and how they impact today’s cryptographic algorithms.
  • Post-quantum cryptography and this new field’s attempt at providing algorithms that can resist quantum computers.
  • The post-quantum algorithms that you can use today, and the ones that you might use in the future.

In the middle of 2015, the National Security Agency (NSA) took everybody by surprise after announcing their plans to transition to quantum resistant algorithms in their Commercial National Security Algorithm Suite (CNSA Suite, previously known as "Suite B") of approved cryptographic algorithms (a requirement for protecting government-related documents and applications).

 

For those partners and vendors that have not yet made the transition to Suite B elliptic curve algorithms, we recommend not making a significant expenditure to do so at this point but instead to prepare for the upcoming quantum resistant algorithm transition. […] Unfortunately, the growth of elliptic curve use has bumped up against the fact of continued progress in the research on quantum computing, which has made it clear that elliptic curve cryptography is not the long term solution many once hoped it would be. Thus, we have been obligated to update our strategy.

  
  -- National Security Agency Cryptography Today (2015)

14.1 What are quantum computers and why are they scaring cryptographers?

14.1.1 Quantum mechanics, the study of the small

14.1.2 From the birth of quantum computers to quantum supremacy

14.1.3 The impact of Grover and Shor’s algorithms on cryptography

14.1.4 Post-quantum cryptography, the defense against quantum computers

14.2 Hash-based signatures: don’t need anything but a hash function

14.2.1 One-time signatures (OTS) with Lamport signatures

14.2.2 Smaller keys with Winternitz one-time signatures (WOTS)

14.2.3 Many-times signatures with XMSS and SPHINCS+

14.3 Achieving shorter communication with lattice-based cryptography

14.3.1 What’s a lattice?

14.3.2 Learning with errors (LWE), a basis for cryptography?

14.3.3 Kyber, a lattice-based key exchange

14.3.4 Dilithium, a lattice-based signature scheme

14.4 Code-based cryptography and other post-quantum candidates

14.5 Do I need to panic?

14.6 Summary