Quantum-Safe Cryptography

- TODO
- TODO

- TODO

It is well known in computer science that **quantum computers will break some cryptographic algorithms**, especially the public-key cryptosystems like **RSA**, **ECC** and **ECDSA** that rely on the **IFP** (integer factorization problem), the **DLP** (discrete logarithms problem) and the **ECDLP** (elliptic-curve discrete logarithm problem). Quantum algorithms will not be the end of cryptography, because:

- Only some cryptosystems are
**quantum-unsafe**(like RSA, DHKE, ECC, ECDSA and ECDH). - Some cryptosystems are
**quantum-safe**and will be only slightly affected (like cryptographic hashes, MAC algorithms and symmetric key ciphers).

Let's discuss this in details.

Quantum-Safe and Quantum-Broken Crypto Algorithms

Most cryptographic **hashes** (like SHA2, SHA3, BLAKE2), **MAC** algorithms (like HMAC and CMAK), **key-derivation functions** (bcrypt, Scrypt, Argon2) are basically **quantum-safe** (only slightly affected by quantum computing).

- Use 384-bits or more to be quantum-safe (256-bits should be enough for long time)

- Use 256-bits or more as key length (don't use 128-bit AES)

Most popular **public-key cryptosystems** (like RSA, DSA, ECDSA, EdDSA, DHKE, ECDH, ElGamal) are **quantum-broken**!

- Most
**digital signature**algorithms (like RSA, ECDSA, EdDSA) are**quantum-broken**! **Quantum-safe signature**algorithms and public-key cryptosystems are already developed (e.g. lattice-based or hash-based signatures), but are not massively used, because of longer keys and longer signatures than ECC.

...

Quantum-Resistant Crypto Algorithms

...

ECC Cryptography and Most Digital Signatures are Quantum-Broken!

...

A **k**-bit number can be factored in time of order **O(k^3)** using a quantum computer of **5k+1 qubits** (using Shor's algorithm).

256-bit number (e.g. Bitcoin public key) can be factorized using 1281 qubits in 72*256^3 quantum operations.

- ~ 1.2 billion operations == ~ less than 1 second using good machine

ECDSA, DSA, RSA, ElGamal, DHKE, ECDH cryptosystems are all quantum-broken

Conclusion: publishing the signed transactions (like Ethereum does) is not quantum safe -> avoid revealing the ECC public key

Hashes are Quantum Safe

Cryptographic **hashes** (like SHA2, SHA3, BLAKE2) are considered **quantum-safe**:

- On traditional computer, finding a collision for 256-bit hash takes √2^256 steps (using the
**birthday attack**) -> SHA256 has 2^128 crypto-strength - Quantum computers might find hash collisions in ∛2^256 operations (see the BHT algorithm), but this is disputed (see [Bernstein 2009] - http://cr.yp.to/hash/collisioncost-20090823.pdf
- On theory it might take 2^85 quantum operations to find SHA256 / SHA3-256 collision, but in practice it may cost significantly more.

Conclusion: SHA256 / SHA3-256 are most probably quantum-safe

- SHA384, SHA512 and SHA3-384, SHA3-512 are quantum-safe

...

Symmetric Ciphers are Quantum Safe

...

Most symmetric ciphers (like AES and ChaCha20) are quantum-safe:

- [Grover's algorithm]([[[[[[https://en.wikipedia.org/wiki/Grover's_algorithm](https://en.wikipedia.org/wiki/Grover's_algorithm)](https://en.wikipedia.org/wiki/Grover's_algorithm](https://en.wikipedia.org/wiki/Grover's_algorithm))](https://en.wikipedia.org/wiki/Grover's_algorithm](https://en.wikipedia.org/wiki/Grover's_algorithm)](https://en.wikipedia.org/wiki/Grover's_algorithm](https://en.wikipedia.org/wiki/Grover's_algorithm)))](https://en.wikipedia.org/wiki/Grover's_algorithm](https://en.wikipedia.org/wiki/Grover's_algorithm)](https://en.wikipedia.org/wiki/Grover's_algorithm](https://en.wikipedia.org/wiki/Grover's_algorithm))](https://en.wikipedia.org/wiki/Grover's_algorithm](https://en.wikipedia.org/wiki/Grover's_algorithm)](https://en.wikipedia.org/wiki/Grover's_algorithm](https://en.wikipedia.org/wiki/Grover's_algorithm))))](https://en.wikipedia.org/wiki/Grover's_algorithm](https://en.wikipedia.org/wiki/Grover's_algorithm)](https://en.wikipedia.org/wiki/Grover's_algorithm](https://en.wikipedia.org/wiki/Grover's_algorithm))](https://en.wikipedia.org/wiki/Grover's_algorithm](https://en.wikipedia.org/wiki/Grover's_algorithm)](https://en.wikipedia.org/wiki/Grover's_algorithm](https://en.wikipedia.org/wiki/Grover's_algorithm)))](https://en.wikipedia.org/wiki/Grover's_algorithm](https://en.wikipedia.org/wiki/Grover's_algorithm)](https://en.wikipedia.org/wiki/Grover's_algorithm](https://en.wikipedia.org/wiki/Grover's_algorithm))](https://en.wikipedia.org/wiki/Grover's_algorithm](https://en.wikipedia.org/wiki/Grover's_algorithm)](https://en.wikipedia.org/wiki/Grover's_algorithm](https://en.wikipedia.org/wiki/Grover's_algorithm)))))](https://en.wikipedia.org/wiki/Grover's_algorithm]%28https://en.wikipedia.org/wiki/Grover's_algorithm%29]%28https://en.wikipedia.org/wiki/Grover's_algorithm]%28https://en.wikipedia.org/wiki/Grover's_algorithm%29%29]%28https://en.wikipedia.org/wiki/Grover's_algorithm]%28https://en.wikipedia.org/wiki/Grover's_algorithm%29]%28https://en.wikipedia.org/wiki/Grover's_algorithm]%28https://en.wikipedia.org/wiki/Grover's_algorithm%29%29%29]%28https://en.wikipedia.org/wiki/Grover's_algorithm]%28https://en.wikipedia.org/wiki/Grover's_algorithm%29]%28https://en.wikipedia.org/wiki/Grover's_algorithm]%28https://en.wikipedia.org/wiki/Grover's_algorithm%29%29]%28https://en.wikipedia.org/wiki/Grover's_algorithm]%28https://en.wikipedia.org/wiki/Grover's_algorithm%29]%28https://en.wikipedia.org/wiki/Grover's_algorithm]%28https://en.wikipedia.org/wiki/Grover's_algorithm%29%29%29%29]%28https://en.wikipedia.org/wiki/Grover's_algorithm]%28https://en.wikipedia.org/wiki/Grover's_algorithm%29]%28https://en.wikipedia.org/wiki/Grover's_algorithm]%28https://en.wikipedia.org/wiki/Grover's_algorithm%29%29]%28https://en.wikipedia.org/wiki/Grover's_algorithm]%28https://en.wikipedia.org/wiki/Grover's_algorithm%29]%28https://en.wikipedia.org/wiki/Grover's_algorithm]%28https://en.wikipedia.org/wiki/Grover's_algorithm%29%29%29]%28https://en.wikipedia.org/wiki/Grover's_algorithm]%28https://en.wikipedia.org/wiki/Grover's_algorithm%29]%28https://en.wikipedia.org/wiki/Grover's_algorithm]%28https://en.wikipedia.org/wiki/Grover's_algorithm%29%29]%28https://en.wikipedia.org/wiki/Grover's_algorithm]%28https://en.wikipedia.org/wiki/Grover's_algorithm%29]%28https://en.wikipedia.org/wiki/Grover's_algorithm]%28https://en.wikipedia.org/wiki/Grover's_algorithm%29%29%29%29%29)) finds AES secret key using √𝑁 quantum operations
- Quantum era will
**double the key size**of the symmetric ciphers, see [http://cr.yp.to/codes/grovercode-20100303.pdf](http://cr.yp.to/codes/grovercode-20100303.pdf%29%29)

AES-256 in the post-quantum era is like AES-128 before

- 128-bits or less symmetric ciphers are quantum-attackable

Conclusion: 256-bit symmetric ciphers are generally quantum safe

- AES-256, ChaCha20-256, Twofish-256, Camellia-256 are considered quantum-safe

Post-Quantum Cryptography

...

Post-quantum signature scheme XMSS:

- Post-quantum key agreement schemes McEliece and NewHope

Post-quantum signatures and key agreements (XMSS, McEliece, NewHope):
https://github.com/randombit/botan

Hash-Based Public-Key Cryptography

...

Code-Based Public-Key Cryptography

...

Lattice-Based Public-Key Cryptography

...

Zero-Knowledge Proof-Based

Multivariate-Quadratic-Equations Public-Key Cryptography

...

Quantum-Resistant Cryptography - Libraries

The quantum-safe cryptography is still emerging, not mature, and still not widely supported by the most crypto-libraries and tools like Web browsers, OpenSSL, OpenSSH, etc. This is a list of well developed quantum crypto algorithm libraries:

SPHINCS+ Signatures in Python

NewHope Key Exchange in Python

Last modified 7mo ago

Copy link

Contents

Quantum-Safe and Quantum-Broken Crypto Algorithms

ECC Cryptography and Most Digital Signatures are Quantum-Broken!

Hashes are Quantum Safe

Symmetric Ciphers are Quantum Safe

Post-Quantum Cryptography

Hash-Based Public-Key Cryptography

Code-Based Public-Key Cryptography

Lattice-Based Public-Key Cryptography

Zero-Knowledge Proof-Based

Multivariate-Quadratic-Equations Public-Key Cryptography

Quantum-Resistant Cryptography - Libraries

SPHINCS+ Signatures in Python

NewHope Key Exchange in Python