# Quantum what?

Quantum computing, quantum cryptography, and post-quantum cryptography: these terms are confusing. This post attempts to clarify them and draws the relationship between them.

*Quantum computing* is the set of technologies that use quantum-mechanical phenomena to
perform computing. Quantum computing uses
qubits rather than bits. Where one bit of
conventional computing has one of the two possible states “0” or “1”, a qubit has
a set of independent states simultaneously via superposition. Furthermore, entangled qubits behave together
in non-conventional ways (for instance, immediate synchronization independent
from the distance separating the two qubits).

These properties allow solving some classes of problems, many orders faster than conventional computing. In 1994, Peter Shor published “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer” [1]. His algorithm solves the prime factorization and discrete logarithm hard problems. Prime factorization is the foundation of cryptosystems such as Diffie Hellman (DH) and RSA. Discrete logarithms are the foundation of elliptic curve cryptosystems (ECC). In 1996, Lov Grover published “A fast quantum mechanical algorithm for database search” [2]. His algorithm inverts one-way functions in time. It applies to symmetric ciphers and cryptographic hashes.

Whenever quantum computing is operational, accurate, and with enough qubits, these algorithms and their enhancements will impact traditional cryptography. To mitigate Grover’s algorithm, the size of symmetric keys and hashes has to increase. For instance, AES will need at least 256-bit keys. Shor’s algorithm annihilates the security of prime factorization or discrete logarithm-based cryptosystems. In other words, DH, RSA, and ECC will not be secure anymore.

*Post-quantum cryptography* encompasses the algorithms that are allegedly immune against quantum
computing. There are mainly four categories
of algorithms.

- Hash-based signatures; It uses the current hash algorithms, and its security is well understood. The size of the public key is far larger and usable only once.
- Code-based encryption; It uses sophisticated error-correcting codes. The McEliece’s scheme was first proposed in 1978 [3] and has not been broken since.
- Lattice-based encryption is the most efficient and promising solution. It allows encryption, digital signatures, and fully homomorphic encryption.
- Multi-variate Quadratic Equations seem the less promising path. All proposed schemes are currently broken.

It is wise to strengthen post-quantum cryptography to be ready whenever this threat is active. NIST estimates that a 1 billion $ quantum computer may break RSA 2048 keys in a matter of hours. A future post will explore more in detail post-quantum cryptography.

*Quantum cryptography* or Quantum Key Distribution (QKD) sends over information, including
a secret key, using photons over a line between Alice and Bob. Once Bob received the secret key, Alice and
Bob use it to encrypt and decrypt via traditional symmetric cryptosystems their
messages. This key distribution is very
similar to many current systems. Nevertheless, due to the Heisenberg’s
principle, if Eve eavesdrops the QKD, she alters the secret key. Thus, Alice and Bob know they are
eavesdropped, offering higher security. The
obvious limitation is that it can only be used in point to point
communications. The first QKDs were
designed in the 80s.

Hoping that this post shed some light, I wish you a happy new year.

# References

[1] P.
W. Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete
Logarithms on a Quantum Computer,” *SIAM J. Comput.*, vol. 26, no. 5, pp.
1484–1509, Oct. 1997, doi: 10.1137/S0097539795293172.

[2] L. K. Grover, “A fast quantum
mechanical algorithm for database search,” *ArXivquant-Ph9605043*, Nov.
1996.

[3] R. McEliece, “A public-key cryptosystem based on algebraic coding theory,” NASA, DSN 42-44, 1978.

Pingback: NIST reduced the number of candidates for post-quantum cryptography | The blog of content protection

Pingback: IS RSA2048 broken? | The blog of content protection