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 2n possible n-bit keys in 2n/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!

More from Artificial Intelligence

Machine Learning Applications in the Cybersecurity Space

3 min read - Machine learning is one of the hottest areas in data science. This subset of artificial intelligence allows a system to learn from data and make accurate predictions, identify anomalies or make recommendations using different techniques. Machine learning techniques extract information from vast amounts of data and transform it into valuable business knowledge. While most industries use these techniques, they are especially prominent in the finance, marketing, healthcare, retail and cybersecurity sectors. Machine learning can also address new cyber threats. There…

3 min read

Now Social Engineering Attackers Have AI. Do You? 

4 min read - Everybody in tech is talking about ChatGPT, the AI-based chatbot from Open AI that writes convincing prose and usable code. The trouble is malicious cyber attackers can use generative AI tools like ChatGPT to craft convincing prose and usable code just like everybody else. How does this powerful new category of tools affect the ability of criminals to launch cyberattacks, including social engineering attacks? When Every Social Engineering Attack Uses Perfect English ChatGPT is a public tool based on a…

4 min read

Can Large Language Models Boost Your Security Posture?

4 min read - The threat landscape is expanding, and regulatory requirements are multiplying. For the enterprise, the challenges just to keep up are only mounting. In addition, there’s the cybersecurity skills gap. According to the (ISC)2 2022 Cybersecurity Workforce Study, the global cybersecurity workforce gap has increased by 26.2%, which means 3.4 million more workers are needed to help protect data and prevent threats. Leveraging AI-based tools is unquestionably necessary for modern organizations. But how far can tools like ChatGPT take us with…

4 min read

Why Robot Vacuums Have Cameras (and What to Know About Them)

4 min read - Robot vacuum cleaner products are by far the largest category of consumer robots. They roll around on floors, hoovering up dust and dirt so we don’t have to, all while avoiding obstacles. The industry leader, iRobot, has been cleaning up the robot vacuum market for two decades. Over this time, the company has steadily gained fans and a sterling reputation, including around security and privacy. And then, something shocking happened. Someone posted on Facebook a picture of a woman sitting…

4 min read