The effort to build a fully functional quantum computer is one of the most exciting engineering challenges today. We hear of a new potential breakthrough almost every week that gets researchers closer to achieving this goal. But with every new breakthrough comes the question of how quantum technology will affect security.

There are certainly reasons for concern. If a quantum computer were to appear today, virtually all internet communication would become insecure. Even if the technology emerges some years from now, it will still be able to open the secret communications of today. No matter how you cut it, quantum computing will have a profound effect on today’s security infrastructure, and organizations of all kinds would be wise to consider the security implications before it’s too late.

Protocols and Primitives

Cryptographic protocols, such as Secure Sockets Layer (SSL), Transport Layer Security (TLS) and Hypertext Transfer Protocol Secure (HTTPS), ensure that communication between two parties is authenticated and private. The building blocks of these protocols are various cryptographic primitives, such as authentication schemes (e.g., keyed-hash message authentication code, or HMAC), block ciphers (e.g., advanced encryption standard, or AES), digital signatures (e.g., Digital Signature Algorithm, or DSA) and encryption schemes (e.g., RSA). For the most part, protocols are constructed from primitives in a modular way. Therefore, if the primitives satisfy their respective security properties, so will the protocols.

Cryptographic primitives can be divided into two classes: symmetric and asymmetric. The latter is often referred to as public key. Symmetric primitives assume the parties have a preshared secret key before beginning communication, whereas asymmetric primitives assume the parties begin with no common secret information.

Most protocols employ the hybrid approach. The communicating parties first use public key primitives to secretly exchange a string before it switches over to the much faster symmetric key primitives, using this common string as the secret key.

An Existential Threat?

Quantum computers will affect symmetric and asymmetric primitives differently. According to Grover’s algorithm, quantum computers are able to brute-force search all 2ⁿ possible n-bit keys in 2^n/2 time, which would require us to double the key sizes to maintain the same level of security. For the most part, this is all quantum computers can do against the symmetric primitives in use today. While certainly notable, this by itself does not pose an existential threat to symmetric cryptography.

Public key primitives are a different story. Virtually all public key primitives used today require that either factoring large integers or finding discrete logarithms in finite groups is a hard problem. However, quantum computers can easily solve these problems using Shor’s algorithm.

In other words, the bad news is that quantum computers break public key primitives. The good news is that the only primitives that really need fixing are digital signatures and public key encryption, because these are enough to construct virtually every critical internet security protocol. Once these primitives are in place, all the important protocols can be made quantum-safe.

Constructing Quantum-Safe Primitives

As it turns out, public key encryption and digital signature schemes that we believe to be quantum-safe have existed since the late 1970s, even before people were aware of the potential problems quantum computing would pose to cryptography. The problem with these constructions, however, is that they are very inefficient. Keys and/or messages are on the order of megabytes.

One of the real breakthroughs in the field of quantum-safe cryptography in the past decade has been the development of new techniques that allow for extremely practical constructions. Lattice-based cryptography has become one of the most fruitful approaches for constructing primitives.

Lattice-Based Cryptography

Lattice-based cryptography is rooted in linear algebra. Suppose that one is given a square, full-rank matrix A and a value b=Ax mod p where x is a vector with 0/1 coefficients and p is a small (e.g., 10-bit) prime. One is then tasked with finding x. This problem has a unique solution, x, which is actually quite easy to find using Gaussian elimination.

On the other hand, if one is given a slightly noisy version of Ax, that is Ax+e mod p, where e is some random vector with 0/1 coefficients, then for matrices of large-enough dimension (say, around 512), this problem becomes surprisingly difficult. This type of problem is related to both the subset sum and the learning parity with noise problems that have been widely studied since the 1980s and have not succumbed to any algorithmic attacks, either classical or quantum.

Exciting Progress

Much of the past decade’s research focused on increasing our understanding of different versions of the problem described above and building schemes based on their presumed hardness. In my view, this research line has been a great success. Performancewise, the most efficient lattice-based encryption and signature schemes are much faster than those based on RSA, and have key and output lengths of a similar size.

Researchers have also made exciting progress toward building cryptographic primitives, such as fully homomorphic encryption, which allows for evaluation of encrypted data whose only instantiations are based on the same linear-algebraic assumptions. Lattice-based cryptography provides fast, quantum-safe, fundamental primitives and allows for constructions of primitives that were previously thought impossible. This combination has established lattice-based cryptography as one of the most fascinating research fields with potential to become the backbone of real-world cryptography in the near future.

Today’s Solution to Tomorrow’s Problem

Can quantum-safe cryptography be used today? The short answer is yes. Lattice-based primitives are efficient and have already been successfully plugged into the TLS and Internet Key Exchange (IKE) protocols. But since quantum computers are not yet here, few security professionals are likely to abandon today’s cryptography for a different approach. After all, any new technology comes with growing pains, and IT professionals cannot afford to make even the smallest mistake when dealing with information security. A slow migration towards lattice cryptography is probably the best bet.

An organization looking to future-proof its data should first use lattice cryptography in tandem with traditional primitives. This approach should secure the organization’s data as long as at least one of these constructions is secure. This would remove all the risk of introducing a new technology. If implemented correctly, all communication will be quantum-safe. All it takes is a couple of extra kilobytes of data per communication session.

In short, quantum computers may be coming sooner than you think, so be ready!