# 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.