What’s the Deal with Quantum Computing: Simple Introduction

Introduction

Recently I suggested that the emergence of quantum internet connectivity and computation, expected sometime in the next decade, poses numerous new cryptography and cybersecurity challenges for 5G security. Let me explain.

MIT offers an explainer on the nascent status of powerful quantum computers, how they work, and where they might provide practical value first. While quantum computers are not expected to replace classical supercomputers for most tasks and problems, they will leverage the “almost-mystical” phenomena of quantum mechanics to produce amazing advances in certain fields such as cryptography, drug discovery, materials sciences, and artificial intelligence.

However, understanding quantum computing can be challenging due to its reliance on principles of quantum mechanics. The secret sauce of quantum computing, which even Einstein called “spooky,” is the ability to generate and manipulate quantum bits of data or qubits. Certain computational tasks can be executed exponentially faster on a quantum processor using qubits, than on a classical computer with 1s and 0s. A qubit can attain a third state of supeposition of 1s and 0s simultaneously, encode data into quantum mechanical properties by “entangling” pairs of qubits, manipulate that data and perform huge complex calculations very quickly. The fundamental challenge is to build a sufficiently high capacity processor capable of running quantum algorithms in an exponentially larger computational space.

Classical vs. Quantum Computing

To understand the differences between classical and quantum computing, let’s first understand how classical computers work. Classical computers use bits, which are the basic units of information and can be either 0 or 1. These bits are manipulated through a series of logical operations to perform calculations and solve problems. Classical computers execute these operations in a linear and predictable manner, processing one bit at a time.

Superposition

Quantum computers, on the other hand, use quantum bits or qubits. Unlike classical bits, qubits can exist in multiple states simultaneously thanks to a property called superposition. This means a qubit can be both 0 and 1 at the same time. This allows a quantum computer to process a vast number of possibilities at once. For example, with two qubits, you can represent four states simultaneously (00, 01, 10, and 11). As the number of qubits increases, the number of possible states grows exponentially. With 3 classical bits, we can represent 3 states. However, with 3 qubits we can represent 2 to the 3rd power states, or 8 states in total. And here lies the first challenge in trying to explain quantum computing. This is first of many non-intuitive concepts in quantum mechanics. Imagine the situation like a coin spinning in the air: instead of being just heads or tails, it’s in a state that represents both while it’s in the air. It’s only once it lands and measure the outcome that we can say it is head or tails. In quantum computing, we work with many coins while they are still up in the air. We use quantum algorithms to manipulate these qubits while they are still “in the air,” calculating the probabilities of different outcomes before measuring them to get a specific result.

Exponential Growth of States

One of the most mind-boggling aspects of quantum computing is the exponential growth of the number of states it can represent as the number of qubits increases. For instance, a quantum computer with 300 qubits can represent 2 to the 300th power states simultaneously, which is close to 1.5 times 10 to the 90th power. To put this into perspective, this number far exceeds the estimated number of atoms in the observable universe, which is around 10 to the 80th power. This exponential growth highlights the immense potential power of quantum computing, particularly for problems involving vast computational complexity.

Entanglement

Additionally, qubits can be entangled, a phenomenon where the state of one qubit is directly related to the state of another, no matter the distance between them. Continuing the above analogy, imagine you have two spinning coins that, once flipped, always land on same faces, no matter how far apart they are. They could be light years apart, and still always match the landing faces instantly. No, I cannot explain how they “communicate.” In quantum computing the entanglement is when two qubits become linked in such a way that the state of one qubit directly influences the state of the other, instantly and regardless of distance. This strong correlation between entangled qubits allows quantum computers to perform complex operations more efficiently in a way that classical computers cannot match.

The combination of superposition and entanglement allows quantum computers to explore many possible solutions at once, providing them with the potential to solve certain complex problems much faster than classical computers. However, it is important to note that quantum computing does not replace classical computing; instead, it complements it by handling specific types of problems more efficiently. But not all types of problems.

This is where quantum algorithms, such as Grover’s search algorithm, come into play. These algorithms are designed to maximize the probability of measuring the correct solution by manipulating the superposition and entanglement of qubits.

Grover’s Search Algorithm

Grover’s algorithm is an excellent example of how quantum computing can outperform classical computing for specific tasks. It provides a quadratic speedup for unstructured search problems. The algorithm starts by initializing all qubits to an equal superposition of all possible states. Then, a special function called an oracle marks the correct solution by flipping its phase. Grover’s algorithm uses a series of quantum operations to amplify the probability of the marked state, making it more likely to be observed upon measurement. After enough iterations, the correct solution’s probability is maximized, and the algorithm can find the solution with high likelihood.

Related to cybersecurity, Grover’s search algorithm presents significant risks to cryptographic systems, particularly those relying on symmetric key encryption and hashing. This algorithm provides a quadratic speedup for searching unsorted databases and can be used to break symmetric encryption by effectively reducing the key length needed to brute-force a cipher. For example, symmetric encryption methods, such as AES (Advanced Encryption Standard), rely on the length of the key to ensure security. AES-256 is designed to provide 256 bits of security, which is computationally infeasible to break with classical computers. Grover’s algorithm can search through possible keys in square root of N steps, where N is the number of possible keys. For AES-256, this reduces the effective key length to 128 bits, making it more vulnerable to attack.

Types of Problems Suitable for Quantum Computing

Quantum computers excel at solving specific types of problems more efficiently than classical computers. One of the most notable examples is factoring large numbers. Shor’s algorithm, a quantum algorithm, can factor large integers exponentially faster than classical algorithms. This has significant implications for cryptography, as many encryption schemes, like RSA, rely on the difficulty of factoring large numbers.

Another area where quantum computing shines is in search problems. Grover’s algorithm provides a quadratic speedup for unstructured search problems, making it much faster than classical search algorithms. This can be incredibly useful for database searches and other applications requiring efficient search capabilities.

Quantum simulations are another promising application of quantum computing. Quantum computers can efficiently simulate quantum systems, which is extremely challenging for classical computers. This capability can lead to breakthroughs in fields such as chemistry, materials science, and biology, enabling the discovery of new drugs, materials, and a deeper understanding of biological processes.

Optimization problems also benefit from quantum computing. Algorithms like the Quantum Approximate Optimization Algorithm (QAOA) and Quantum Annealing can find optimal or near-optimal solutions to complex optimization problems much faster than classical algorithms. This is particularly valuable in logistics, finance, and machine learning.

Additionally, quantum computing has the potential to revolutionize machine learning. Quantum machine learning algorithms, such as quantum support vector machines and quantum neural networks, can offer significant speedups for certain tasks, especially those involving large datasets and complex models.

In the field of cryptography, quantum computing not only poses a threat to current encryption methods but also offers new possibilities. Quantum cryptographic protocols, like quantum key distribution, leverage the principles of quantum mechanics to create theoretically unbreakable encryption, ensuring secure communication in the age of quantum computing.

Problems Not Suitable for Quantum Computing

While quantum computers have immense potential, they are not universally better for all problems. For everyday computing tasks like word processing, web browsing, and basic arithmetic, classical computers remain the best choice. These tasks do not benefit from the unique properties of quantum computing and are efficiently handled by classical methods.

Large-scale data storage and retrieval are also not suitable for quantum computers. Quantum computers are not designed for data storage or retrieval on a large scale, and classical databases and data storage solutions are more practical for handling large volumes of data.

Tasks that can be easily parallelized and distributed across many classical processors, such as many types of numerical simulations, may not see significant benefits from quantum computing. Classical supercomputers are often more efficient for these tasks.

Moreover, many problems do not have known quantum algorithms that provide a significant speedup over the best classical algorithms. For such problems, classical computers remain the preferred choice.

Finally, non-computational tasks, such as physical manipulation, manual labor, or creative processes like art and writing, are beyond the scope of quantum computers. These tasks do not involve computation in the traditional sense and therefore do not benefit from the capabilities of quantum computing.

Problem for Cybersecurity

It is anticipated that quantum computers will be capable of breaking 99% of the encryption used to protect today’s enterprises, financial systems and governments. Encryption in wide use today is unbreakable only because of the massive amounts of time, measured in hundreds or thousands or billions of years, that it would take existing supercomputers to break the underlying mathematical codes. Problems that are computationally infeasible for classical computers can be efficiently solved by quantum computers, rendering many traditional cryptographic methods vulnerable. Primarily this comes from the incredible multiple processing capabilities which enable quantum computers to use algorithm’s and mathematical formulae such as Shor’s algorithm to break down current cryptographic protocols.

The security of hundreds of billions of dollars in e-commerce transactions is at stake. This security vulnerability also applies to data stored on a digital blockchain. Even more importantly, the integrity of communication controlling critical infrastructure cyber-physical systems could be threatened with resulting impacts potentially threatening lives, well-being and the environment. In practical terms, this also means that encrypted data stored today could be decrypted in the future when quantum computers become more powerful and accessible. For instance, sensitive information such as bank account numbers, personal identity information, and military secrets could be at risk of exposure, leading to potentially severe consequences.

In short, now that the consensus is that quantum computing is definitely arriving, albeit at some unspecified time in the future, the following statement is unequivocally true: from now on, without quantum-safe encryption, everything stored or transmitted over any network is vulnerable to eavesdropping. You must assume that every email, file, and login used today and from today onwards will be exposed at some point in the future, whether in 5 years or 15 years.

A May 2019 study by a Google researcher in California and one at the KTH Royal Institute of Technology in Sweden, shows that quantum technology will catch up with today’s encryption standards faster than expected and should greatly concern any public or private organization that needs to store data securely for 25 years or more.

The impending arrival of quantum code breaking capability means that nation states and their military operations, as well as business enterprises, will need to upgrade to quantum-resistant hardware and cryptography to safeguard their data before full-scale quantum computers become available.

Pervasiveness of Quantum-Vulnerable Cryptography in Current Systems

Classical public key algorithms like RSA and ECC are ubiquitously used in various security protocols and applications to provide essential security services. The potential threat posed by quantum computing to these algorithms and their pervasive usage are putting a number of systems at risk. Below is just a subset of solutions that rely on these vulnerable cryptographic implementations:

Public Key Infrastructure (PKI)

Public Key Infrastructure (PKI) is a fundamental system that supports the use of public key cryptography across different platforms. At the heart of PKI is the Certificate Authority (CA), an entity that vouches for the authenticity of public keys by issuing digital certificates. This process ensures that communication between two parties is authentic and secure. These root certificates are embedded in web browsers and mobile devices, allowing users to trust the authenticity of websites they visit. Websites use SSL certificates, typically containing RSA public keys of at least 2048 bits, to establish secure connections. Certificates use RSA or ECC keys.

Secure Software Distribution

Secure software distribution is often ensured through public key-based digital signatures. Important data is signed with a private key, and the signature is appended to the data, allowing recipients to verify its authenticity with the corresponding public key. For example, mobile operating system updates are signed by the manufacturer to ensure the software has not been tampered with. This process prevents unauthorized modifications and ensures that only legitimate updates are installed. Companies like Apple and Microsoft issue developers code signing certificates containing RSA public keys to authenticate software updates.

Single Sign-On (SSO)

Single sign-on (SSO), enables users to log in once and gain access to multiple systems without re-entering credentials. This system relies heavily on cryptographic mechanisms to ensure secure and seamless access across different platforms. Quantum-vulnerable public key cryptography plays a crucial role in securing the tokens and assertions used in SSO protocols.

Key Exchange over a Public Channel

Key exchange protocols allow two parties to securely agree on a shared secret key over a public channel. This shared key is then used for encrypting subsequent communications. Protocols such as SSL/TLS, SSH, and IKE/IPsec rely extensively on RSA, DH, or ECC for secure key exchange. These protocols form the backbone of secure internet communications, protecting data during transmission.

Secure Email (S/MIME)

Secure/Multipurpose Internet Mail Extensions (S/MIME) is widely used within government entities and regulated industries to ensure the confidentiality and authenticity of email communications. S/MIME certificates often contain RSA public keys, facilitating secure email encryption and digital signatures. This ensures that sensitive email content remains confidential and untampered.

Virtual Private Networks (VPNs)

Virtual Private Networks (VPNs) use cryptographic protocols to create secure tunnels over the internet. VPNs, commonly employed by enterprises and individuals in restrictive environments, rely on protocols like IKE or mobileIKE for key establishment. These protocols typically use RSA or ECC to set up secure network tunnels, ensuring that data transmitted over the VPN remains confidential and secure.

Secure Web Browsing (SSL/TLS)

SSL/TLS protocols are integral to secure web browsing, indicated by the lock icon displayed in web browsers when visiting SSL-enabled websites. Websites that handle sensitive information, such as credit card details or personal data, use SSL/TLS to encrypt communications, ensuring data privacy and security. Most SSL/TLS certificates contain RSA keys for authentication, although the use of ECC for key exchange is increasing. Despite the growth of ECC, RSA remains prevalent due to its widespread acceptance and established trust.

Blockchain Technologies

Blockchain and cryptocurrencies rely heavily on cryptographic algorithms to ensure the integrity and security of transactions. Bitcoin, for instance, uses the elliptic curve digital signature algorithm (ECDSA) for signing transactions. If quantum computers can break ECDSA, the security of Bitcoin and other cryptocurrencies that use similar cryptographic methods would be compromised.

Payment Systems

Many payment systems and financial transactions depend on secure key exchanges and digital signatures to authenticate transactions and ensure privacy. Algorithms like RSA and ECC are commonly used in these systems. The widespread use of smart cards, contactless payments, and online banking relies on these quantum-vulnerable cryptographic methods.

Smart Grids

Smart grids rely on cryptographic algorithms to ensure secure communication between various components of the electrical grid. RSA and ECC are commonly used to authenticate devices and encrypt communications, ensuring the integrity and security of the grid.

Industrial Control Systems (ICS)

Industrial Control Systems, used in manufacturing, energy production, and other critical infrastructure, often employ cryptographic algorithms for secure communication and authentication. These systems use protocols like OPC UA, which rely on RSA and ECC to ensure secure data transmission and control.

Wireless Communication

Protocols like Wi-Fi Protected Access (WPA) and mobile communication standards such as 4G LTE and 5G use RSA and ECC for secure key exchange and authentication. These cryptographic methods ensure secure communication between devices and network infrastructure.

Others

All of the above examples rely on asymmetric cryptography (like RSA and ECC) which will be completely broken by quantum computers. However, symmetric cryptography and hashing algorithms will also be significantly weakened. For example:

Symmetric Cryptography

Symmetric key algorithms like AES (Advanced Encryption Standard) are generally considered more resilient against quantum attacks, but they are not immune. Grover’s algorithm can perform a brute-force search quadratically faster than classical algorithms. This means that the effective security of a symmetric key algorithm is halved. For instance, AES-128, which is currently considered secure with 128-bit keys, would only offer the equivalent security of a 64-bit key against a quantum attack.

Hashing Algorithms

Hash functions, such as SHA-256 and SHA-3, will also be affected by quantum computing. Grover’s algorithm can reduce the effective security of these hash functions by half. For instance, SHA-256, which provides 256-bit security against classical attacks, would only offer 128-bit security against quantum attacks.

And there are thousands of examples of those two cryptographic categories as well.

Conclusion

Quantum computing holds the potential to revolutionize fields where classical computers struggle, particularly in areas involving complex quantum systems, large-scale optimization, and cryptography. The power of quantum computing lies in its ability to leverage the principles of quantum mechanics—superposition and entanglement—to perform certain types of calculations much more efficiently than classical computers.

However, for many everyday tasks and problems that are efficiently solved by classical methods, quantum computers do not offer significant advantages. The future will likely see a hybrid approach, leveraging the strengths of both quantum and classical computing to solve a wide range of problems.

The problem from our perspective as cyber defenders is that along with exciting new capabilities that will serve humanity in general, quantum computing also ushers in an era of expanded risks to businesses trying to protect their commercial data, and to governments trying to protect their civilian databases and military secrets. Quantum hacking threats will drive a whole new level of digital IT security measures, including post-quantum encryption, authentication and data hygiene among those who are smart and proactive enough to embrace them. And those who haven’t yet considered the issue or haven’t planned out their path to quantum-proof cryptographic protocols implementation may find themselves caught with their proverbial pants down.