Hanno Böck

https://hboeck.de

Richard Feynman presents idea of a quantum computer

Peter Show shows quantum computers could break public key cryptography

Well understood theory, but hard to engineer.

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

Algorithms that we believe to be resistant to quantum attacks.

Development still in early stages.

Hash functions (SHA-2, SHA-3) and symmetric encryption (AES) are the easy part.

Just use larger keys (256 bit is fine).

- Encryption with separate public and private key
- Signatures
- Key exchanges

- Factoring-based (RSA)
- Discrete-logarithm-based (Diffie Hellman, DSA, ElGamal)
- Elliptic-curve-based (ECDSA, ECDH, X25519, Ed25519)

Quantum computers break all three.

Almost every crypto software and protocol today uses these algorithms.

TLS/SSL, SSH, OpenPGP/GnuPG, Signal, Whatsapp, OTR, OMEMO, ...

Quantum computers break practically everything using crypto.

Code-based cryptography

Lattice-based cryptography

Isogeny-based cryptography

Hash-based signatures

Multivariate cryptography

McBits: Variant of McEliece.

Good: old, well researched, bad: large keys (~1 MB)

SPHINCS: Hash-based signatures

Good: as secure as the hash function, bad: large signatures (~42 KB)

Not practical for many use cases (TLS!)

(based on EU PQCRYPTO recommendations)

Ntru, Ring-Learning-With-Errors, New Hope, Ntru prime, BLISS, Tesla#.

Pro: Practical, fast, relatively small keys

Con: Patents, conflicts over security estimates.

Most likely candidate for early deployments.

SIDH - Diffie-Hellman-alike key exchange.

Pro: Very similar workflow to Diffie Hellman, small keys

Con: Not that fast, very experimental

We have the choice between very impractical and experimental algorithms.

Logjam, FREAK, DROWN, SWEET32

It often takes decades to deprecate old crypto. Windows-XP-compatibility is still a concern for some.

If quantum computers come in 10-15 years then the transition will be rough.

Secure algorithms can be used in insecure ways.

October 2016: Three research papers on potential backdoors and security issues with Diffie Hellman.

If we don't even know how to use the oldest public key algorithm safely, how should we know how to use entirely new algorithms?

Attackers could store large amounts of encrypted communication today and decrypt it once a quantum computer is available.

Strong argument for fast deployment.

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.

Similar plan by Tor.

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

It's not clear if D-Wave quantum computers can do anything useful. But they are almost certainly irrelevant for cryptography.

Quantum computing: Using quantum effects to solve mathematical problems that can't efficiently be solved on normal computers.

Post-Quantum cryptography: Cryptography that resists attacks with quantum computers.

Quantum cryptography / quantum key distribution: Using physical channels to exchange cryptographic keys.

Idea: cryptography that is secure based on the laws of physics.

Send single particles with polarized encoding, exchange polarization filter configuration.

This has major drawbacks and solves nothing.

Very likely limited distances (tens or hundreds of kilometers).

Or maybe this is good?

Source: EU Quantum Manifesto

QKD needs a physical connection between endpoints.

- No Wifi
- No mobile Internet

All QKD systems need an authenticated channel.

QKD depends on the cryptography its proponents claim it should replace.

This limitation is rarely mentioned, but it's significant. It means QKD can't solve the problems created by quantum computers.

Quantum cryptography provides perfect security.

However regularly commercial QKD devices get broken.

How's that even possible?

The big argument for QKD: It's perfectly secure - based on the laws of physics!

However that's only true for an idealized version of QKD, not for any real system.

If you have a bug in your encryption software you can install an update (hopefully).

If you have a bug in your encryption hardware you need to buy new hardware.

Extremely overhyped with outragerous claims ("Quantum Internet").

Entirely unclear which problems it should solve.

Definitely not a solution for the problems created by quantum computers. That solution is Post-Quantum cryptography.

Quantum computers may come pretty soon (or not at all). We need to be prepared.

Post-Quantum cryptography is still in its early stages. We're already too late.

Be wary of overhyped claims about quantum cryptography, which likely won't solve anything

- pqcrypto.org
- pqcrypto.eu.org - EU PQCRYPTO research project
- csrc.nist.gov/groups/ST/post-quantum-crypto/ - NIST standardization effort

Questions?