Quantum-safe Cryptography

Most of the public-key cryptographic algorithms we use today rely on one of three hard mathematical problems:

1. The integer factorization problem
2. The discrete logarithm problem
3. The elliptic-curve discrete logarithm problem

Some quantum algorithms — particularly Shor’s — can be used to speed up attack against current public-key cryptographic algorithms.

Another quantum algorithm — Grover’s — can be used to speed up attacks against most common symmetric algorithms & hash functions we use today.

Even though none of the current publicly known (with a huge emphasis on publicly known) quantum computers have the processing power to actually break any currently used cryptographic algorithms, the how-tos are already there, and it’s more matter of “when” then “how”.

The situation with the symmetric cryptography is much better than with the public-key one — as it possible to render Grover’s algorithm practically useless by doubling the key size.

Currently, there are 6 major approaches in post-quantum cryptography research:

1. Symmetric with increased key sizes
   Assuming that symmetric key cryptographic systems (f.e. AES) and key management systems that use symmetric cryptography (f.e. Kerberos) instead of public-key one are already safe if using sufficiently large key sizes.
2. Lattice-based cryptography
   Relies on the intractability of the Lattice problem, which appears to be resistant to quantum attacks.
3. Multivariate cryptography
   Relies on the difficulty of solving systems of Multivariate equations.
4. Hash-based cryptography
   Relies on the security of hash functions.
5. Code-based cryptography
   Relies on error-correcting codes.
6. Supersingular elliptic curve isogeny cryptography
   Relies on the properties of supersingular elliptic curves.