The race to build a large-scale quantum computer is one of the most exciting technology challenges today. New breakthroughs appear in the press almost every week as researchers move closer to succeeding. However, as we discuss in 'Quantum computing: Why qubits have consequences for IP', achieving this goal will have far-reaching consequences for communications security not only in the future, but also today.
Cryptographic protocols
If a quantum computer were to be achieved today, then virtually all internet communication would become insecure. Even though that technology probably won’t emerge for some years, the most worrying fact is that when it does it will be able to retrospectively decrypt most of the secret communications being made today.
Cryptographic protocols, such as Hypertext Transfer Protocol Secure (HTTPS), ensure that communication between two parties is authenticated and private. The building blocks of these protocols are various cryptographic algorithms, such as RSA encryption schemes. Many used today exploit the fact that certain mathematical problems are extremely hard to solve. By hiding a secret within the mathematical solution, the assumption has been that the solution, and therefore the secret, can only be known to those who hid the secret in the first place.
A great source of hard problems is a branch of mathematics called Number Theory, and many widely-used public key cryptographic schemes have been designed specifically based on the difficulty of finding the integer factors of very large integer numbers. Examples include RSA and Diffie-Hellman Key Exchange. However, quantum computers can easily solve these problems using Shor’s algorithm. The race is now on to develop new quantum-resistant cryptographic algorithms that even a quantum computer could not crack (known as ‘quantum-safe’ algorithms, or ‘post-quantum’ algorithms) to replace those we presently use.
In the USA, the National Institute of Standards and Technology (NIST) is in the process of selecting one or more quantum-safe public-key cryptographic algorithms through a public, competition-like process. The NIST ‘Post-Quantum Cryptography Standardization Process’ began in 2017 with 69 candidate algorithms. The first round ended in January 2019, when candidate algorithms were selected based on their security and performance characteristics. NIST then selected 26 algorithms to proceed to the second round for more analysis. In their recent report 'Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process', NIST identifies those selected to move forward to the third round of the competition. The third-round finalist algorithms are:
- Crystals-Kyber
- Saber
- Crystals-Dilithium
- Classic McEliece
- NTRU
- Falcon
- Rainbow
Lattice-based cryptography
Interestingly, a breakthrough in quantum-safe cryptography has been the development of new ‘lattice-based’ techniques that allow for extremely practical algorithms. Most of these finalists employ ‘lattice-based’ techniques. NIST’s current view is that these lattice schemes are the most promising general-purpose algorithms for public-key encryption and digital signature schemes.
Lattice-based cryptography has become one of the most fruitful approaches for constructing quantum-safe cryptographic algorithms. To understand the idea behind this, imagine a 2-D lattice as a regular grid of points – a bit like atoms in a crystal. A ‘lattice problem’ is the task of finding the one lattice point that is the closest to a predefined central point (the ‘origin’) in the space containing the lattice. You can imagine that this task would be easy for a 2-D lattice: just draw the lattice points on a sheet of paper and select the lattice point closest to the origin. However, the problem becomes extremely hard to solve as you increase the number of dimensions of the grid from space 2-D, beyond 3-D space to, say, 1000-D space. With these high dimensions, it is believed that even a quantum computer would fail to solve the problem. Indeed, there is no evidence that a quantum computer would be any better at handling the problem than the fastest conventional computers around today.
Lattice-based cryptography is considered by many to be able to easily adapt to future security needs while standing the test of time. In fact, not only are lattice-based techniques said to be able to replace essentially all of our currently endangered schemes, they may even allow for entirely new classes of extremely powerful cryptographic tools for which currently used techniques simply have no analogues.
A new chapter
As the aphorism goes: “necessity is the mother of invention” (Plato). It might just be that the urgency to find quantum-safe cryptographic algorithms has opened an exciting a new chapter in cryptographic innovation. We will closely monitor developments coming from NIST as its Post-Quantum Cryptography Standardization Process reaches its conclusion.
