This post was originally published on BTQ's Blog on August 29th, 2023. Subscribe to the blog for my upcoming series diving deep into quantum security.

Imagine having a super-fast computer that could solve problems and crunch data faster than anything we've seen before. It can develop new medicine more quickly and cheaply, solve energy efficiency problems in batteries and solar panels, and create better materials to withstand heat and strain.

Sounds great, right? But, there's a catch. These super-fast computers, or quantum computers, could crack the security measures we use to keep our online information safe. This is the “quantum threat” – the potential for quantum computers to crack many of today's encryption schemes, which could result in a collapse of our modern-day cybersecurity infrastructure.
‍

Shor’s Algorithm

Our current encryption methods, which keep our digital communications safe, heavily rely on the assumption that certain mathematical problems are hard to solve with classical computers. RSA encryption is based on factoring large numbers, while elliptic curve cryptography (ECC) is based on finding the discrete logarithm of a random elliptic curve element. Both of these problems are computationally difficult for classical computers.

The concept of a 'quantum threat' gained significant attention after the proposal of Shor's algorithm by mathematician Peter Shor in 1994. Shor's algorithm was quantum’s killer app, being the first to demonstrate the potential power of a large-scale, fully functional quantum computer in the real world. This algorithm could unlock the digital 'locks' we currently use to secure our online world.

Shor’s algorithm can factor large numbers exponentially faster than the best-known algorithms running on classical computers. The implication for encryption is profound. If a large and error-corrected quantum computer could run Shor's algorithm, it could crack these encryption methods, posing a significant threat to digital security worldwide.

And how fast? Exponentially faster is very fast. Breaking a 2048-bit RSA key would take 1 billion years with a classical computer. A quantum computer could do it in 100 seconds.

The immediate focus on examining post-quantum security solutions is no longer optional. Ironically, ECC was recommended over RSA because it offered the same level of security but used shorter keys, resulting in faster computation and less demand for resources such as storage and bandwidth. This made ECC a more efficient and appealing choice for a broad range of applications, from securing web traffic to protecting sensitive government data. However, ECC is even more vulnerable to quantum computers than RSA, requiring even less qubits for the calculation.
‍

The Costs of a Vulnerable Post-Quantum Future

Some data are just valuable for a day, or less. Your job requires you to reset your password every 3 months. So, in the worst-case scenario, a large-scale coherent quantum computer will be released and every website will force us to reset our passwords, encrypted with a new cryptosystem. No big deal.

But what about data vital to national security that is being sent now with quantum-crackable encryption, and can jeopardize national security even in 50 or 100 years if released? What about Bitcoin, built on elliptic curve encryption as the foundation of all its transactions - and is very hard to change because of its trustless, distributed nature? Or was your social security number sent over the web using ECC? Your WorldCoin biometric identity? You can’t replace your iris.

These data breaches can devastate businesses, industries, and individuals. They can lead to a loss of consumer trust, damage to reputation, and significant financial loss. The Equifax breach in 2017 exposed the personal data of 143 million people, resulting in a settlement of $425 million just to help people affected by the breach. And that was not a fundamental encryption issue. What we could be facing is a data breach armageddon.
‍

When Will The Quantum Threat Arrive?

The impacts of a large quantum computer are profound on fundamental science. Trillions of dollars are being invested into quantum computing because of applications in materials, healthcare, and financial modeling. But with worldwide security at risk, the race to build a large-scale quantum computer is also highly funded by governments. China, Russia, the US, the UK, and many others are putting hundreds of billions into quantum technology. For instance, the US CHIPS Act provides roughly $280 billion in new funding to boost domestic research and manufacturing of semiconductors in the United States.

There is some disagreement on when the threat will arrive. As of mid-2023, we are in the era of Noisy Intermediate-Scale Quantum (NISQ) computers. NISQ devices are characterized by having just tens to a few hundred qubits (quantum bits, similar to bits, but are two-level quantum mechanical systems that can be prepared in a probability of a 0 or 1)  and noise in quantum operations that introduces calculation errors. These machines, while needing to scale up to break modern encryption, are growing rapidly. While there are scalability challenges to address in quantum hardware, quantum computers have been accelerating in qubit counts, while gate infidelity, or the error rates applying quantum circuits, have been decreasing.

While we still have time before the quantum threat,  the scaling and error issue is being attacked from multiple sides. Researchers are focused on manufacturing techniques for superconducting hardware to scale on qubit count and fidelity, new modalities are emerging, like photonic-based quantum computers, and theorists are working on new error correction algorithms to reduce the number of supporting qubits. In the last few years, co-designed application-specific processors became the most viable path to quantum advantage to reduce qubit count and error correction needed to scale.

Microsoft Research has calculated around 2500 qubits are needed to compute elliptic curve discrete logarithms to crack a standard 256-bit key. Around 4000 qubits are needed for 2048-bit RSA. While these are logical qubits, not physical (logical qubits will require additional physical qubits for error correction), the resource estimates keep decreasing.

10 years ago, John Preskills’s lecture noted you would need 10 million physical qubits to break RSA cryptography. In 2023, a PRL paper, "Performance Analysis of a Repetition Cat Code Architecture: Computing 256-bit Elliptic Curve Logarithm in 9 Hours with 126 133 Cat Qubits” was released showing two orders of magnitude reduction in qubit counts. Assuming a similar pace of two orders of magnitude reduction of qubit counts in the next 10 years, we may only need ~2000 qubits to break RSA encryption. BTQ’s QByte Quantum Risk Calculator tracks qubit counts and quantum infidelity.  Even pessimistic estimates place that threshold by 2030, without any advances in error correction or fabrication.
‍

What can we do?

Given the potential vulnerabilities, there is a growing consensus on the need for preemptive action. This involves adopting post-quantum cryptography algorithms that are resistant to quantum attacks. While there's uncertainty about when a quantum computer capable of breaking current cryptography will exist, the risk is significant enough to warrant immediate action.

Industry and academia are closely collaborating to advance post-quantum security. For instance, NIST's Post-Quantum Cryptography Standardization project involves both academic and industry players in the development and evaluation of new cryptographic systems. BTQ’s post-quantum cryptography scheme, Preon, was recently selected by NIST as a candidate for the Post-Quantum Cryptography Standard.

Post-quantum cryptographic algorithms are designed to resist attacks by classical and quantum computers. These include lattice-based, hash-based, code-based, multivariate polynomial, and isogeny-based cryptographic algorithms. Each approach has pros and cons regarding security, performance, and key and ciphertext sizes.

While post-quantum cryptographic algorithms are still being studied, evaluations show promise in their resistance against known quantum attacks. However, more research is needed to identify unknown vulnerabilities and thoroughly assess their security.

Even though the standard has not yet been released, large tech companies, including Google, Microsoft, and IBM, are testing post-quantum algorithms, and some have already started implementing post-quantum security in their products and services. Blockchains, like QRL and Nexus, are being built “quantum-first” to protect against the risks of large-scale quantum computers.
‍

New Standards, New Post-Quantum Future

As post-quantum cryptographic standards emerge, organizations may need to comply with new regulatory requirements that take adequate measures to secure data against quantum threats.

While the new standards and cryptosystems are open source, cryptography isn’t enough for this new, unknown world where crypto agility is critical. Vendors approved by government players as post-quantum solutions will have a head start - especially since national security is a crucial priority and holder of a lot of long-term data. The transition to post-quantum cryptography will be more complex for companies in regulated industries like finance or healthcare. These companies will need to balance the adoption of new technologies with compliance with existing and emerging regulations.

The advent of quantum computing is a double-edged sword, bringing immense promise, but significant threats to digital security. It's crucial for governments, industries, and academia to work together to develop, implement, and scale the adoption of robust post-quantum cryptographic algorithms. Although the active quantum threat is still a future concern, the time to act is now.

‍