Moving towards Post Quantum Cryptography

Cryptography is the foundation of IT security.

It ensures confidentiality, integrity and non-repudiation of the information protected by it.

Due to its complexity it is often misused by development teams. We often encountered situations of incorrect use of cryptographic primitives, the use of outdated algorithms or an inept attempt to interfere with the proven cryptographic protocols, or the creation of their own faulty cryptographic protocols.

If flawed cryptography is used in our software, in most cases other protections, although strong, may become useless.

This entry is the beginning of a series on cryptology, in which we will try to highlight how cryptography is a key component of any system.

Finite based field cryptography

Currently, almost all cryptographic protocols used in the commercial market are based on computationally difficult problems that are solved in finite bodies

Due to this computational difficulty, breaking a protocol is as complicated as solving a computationally complex problem.

Algorithms that are employed to solve these problems include the Generalized sieve over number bodies, the elliptic curves method, and Pohlig-Hellman reduction.

However, these algorithms are not very efficient and even the use of supercomputers, given sufficient key lengths have little to no effect. These problems are usually NP-hard problems and there are not known efficient algorithms that deal with them in a simple and fast way.

But are they really?

In the previous sentence I said that there are no algorithms that break current cryptographic protocols. This is true, however it applies to algorithms running on classical computers.

However there are quantum algorithms which in polynomial time (efficiently) solve computationally difficult problems unsolvable on classical computers.

The canonical, most popular algorithm cited in the literature is Shor's algorithm or Grover's algorithm. To harness these algorithms, however, a quantum computer is necessary.

Officially on the day when I'm writing this entry (26.07.2021) the most powerful quantum computer has capacity of 64 cubits[1]

Such a computer is still too feeble to break the keys of the length used today. However we remember how fast classical computers from x computers became x computers

It is also worth remembering that these data concern unclassified, commercially used, quantum computer projects. Military classified projects, probably already have quantum computers with more power.

Symmetric, block algorithms built on architectures based on confusion and diffusion layers are resistant to the quantum computer as long as we will be able to double the length of keys used in these algorithms.

However, we need to radically change our approach when it comes to asymmetric cryptography, digital signatures or key exchange protocols. This will be a very problematic migration as almost all currently used systems including banking systems, communication protocols or even blockchain networks are based on classical cryptography.

Given the rapid technological development, we must think slowly about moving to post-quantum cryptographic protocols that are resistant to these attacks.

Post-quantum cryptography

The mathematical problems underlying post-quantum algorithms in which cryptologists see the greatest potential are based on longest vector or nearest vector problems.

These are lattice problems, which in standardization contests regarding post-quantum cryptology[2] cryptologists evaluate best and probably will be a new standard of cryptography

Examples of such algorithms are RLWE based New Hope[3], or SVP based NTRU[4]. These algorithms so far perform well against both classical and quantum computers.

As of today, the third round of the NIST standardization competition has ended, in which new standards for modern cryptography are selected. These algorithms will be the next standard for asymmetric cryptography including encryption, key exchange and digital signatures.

Summary

In the coming years we will definitely have to stop using algorithms like Finite Fields based RSA, DH or ECDH and start using Lattice Based method.

Unless we want hackers to know what we do, who we communicate with using spoofing or MITMs attacks on our deprecated cryptography.

Sources

[1] https://www.honeywell.com/us/en/news/2020/06/the-worlds-highest-performing-quantum-computer-is-here

[2] https://www.honeywell.com/us/en/news/2020/06/the-worlds-highest-performing-quantum-computer-is-here

[3] https://www.honeywell.com/us/en/news/2020/06/the-worlds-highest-performing-quantum-computer-is-here

[4] https://www.honeywell.com/us/en/news/2020/06/the-worlds-highest-performing-quantum-computer-is-here