Post-Quantum Cryptography

Hanno Böck

1982

CC by-sa 3.0, Tamiko Thiel, Wikimedia Commons

1994

CC sa 1.0, Peter Shor, Wikimedia Commons

Public key cryptography

Quantum computers break all mainstream public key algorithms.

RSA, DSA, Diffie-Hellman, ElGamal, ECDSA, ECDH, X25519, Ed25519, ...

Symmetric cryptography (block/stream-ciphers, hashes) mostly not affected.

Quantum computers

Well understood theory, but hard to engineer.

Some researchers give timeframes of 10-15 years for scalable quantum computers.

Post-Quantum Cryptography

Algorithms that we believe to be resistant to quantum attacks.

Code-based cryptography

McEliece, McBits

Pro: Old, probably secure

Con: Large keys (~ 1 Megabyte).

Lattices

Ntru, Ring-Learning-With-Errors, New Hope

Pro: Practical, fast, small keys

Con: Patents, DJB thinks security analysis is inadequate (discussion)

Supersingular Isogenies of Elliptic Curves

SIDH

Pro: Very similar workflow to Diffie Hellman, small keys

Con: Not that fast, very experimental

Hash-based signatures

XMSS, SPHINCS

Pro: Likely very secure

Con: Either stateful (easy to mess up) or large signatures (~ 40 Kilobytes)

Google uses New Hope

Google deployed New Hope (lattice-based algorithm) key exchange in Chrome/BoringSSL and on some servers.

Hybrid key exchange with X25519: In case New Hope breaks it still has the security of X25519.

PSA 1: D-Wave

The D-Wave quantum computer can't run Shor's algorithm.

PSA 2: Quantum Cryptography

If anyone tells you that Quantum Cryptography or Quantum Key Distribution solves the problem of Quantum attacks or wants to build a Quantum Internet: This is utter nonsense. If you don't believe me please talk to me later.

Image public domain, Wikimedia Commons