Bench Talk

Quantum computers will easily hack today's cryptography keys, leaving critical data exposed to cybercriminals. To counter this threat, scientists and engineers have been working on new algorithms that even powerful quantum machines will find impossible to break.

(Source: Maxim Borbut / stock.adobe.com; generated with AI)

Decades ago, Y2K symbolized the fear that computers would fail over due to the date change at the turn of the millennium, but that turned out to be anticlimactic. Now, Y2Q represents a new computing dilemma that could be globally disruptive. Y2Q, or “Q-Day,” describes a future date when current cryptographic algorithms will be vulnerable to quantum computing attacks. Quantum computers will easily be able to crack today's standard algorithms that protect the cryptographic keys providing access to much of the encrypted data passing through the internet.

Most contemporary public keys are generated using mathematical algorithms such as the integer factorization problem, the discrete logarithm problem, or the elliptic-curve discrete logarithm problem. Cybercriminals using even the most powerful conventional computers would need years to break open encryption keys based on these algorithms, making hacking impractical. For tomorrow's quantum computers, however, cyberattacks would be a breeze.

The Quantum Threat

Quantum computers gain their advantage by substituting the bits (0s or 1s) of digital machines for data units called qubits. Qubits exploit the quantum mechanical characteristic of superposition, whereby a stored unit of information can exist in multiple states at once. Such a characteristic not only allows a quantum computer to tackle much harder problems than today's computers, but it also allows it to solve them at lightning speed.

The software able to crack many of today's cryptography keys has been around for 30 years. In 1994, an American mathematician, Peter Shor, developed an algorithm that a quantum computer could use to find the prime factors of an integer. Integer factorization is a very common technique for generating public cryptographic keys. However, even armed with Shor's algorithm, today's quantum computers remain too feeble to break contemporary keys. The problem is an accumulation of errors that can only be resolved by dramatically increasing the number of qubits—something that's beyond current technology.

But the research and development dollars being invested in quantum computers is supercharging their progress. Their progress is accelerating to the point that, according to Physics World , the US National Institute of Standards and Technology (NIST) says that quantum computers will be able to break existing keys, like 128-bit AES encryption, by 2029. ^[1] This type of encryption is widely used to protect sensitive information sent over the internet.

Despite the lack of an immediate threat, there's not a minute to lose. Hackers are already harvesting and storing encrypted data in anticipation of a future quantum breakthrough that would render the information readable. Engineers are countering these threats by working hard on post-quantum cryptography (PQC), also referred to as quantum-proof, -safe, or -resistant cryptography.

Building PQC Algorithms

PQC describes a class of public-key cryptographic algorithms designed to be secure against attack by a quantum computer. While some work was completed previously, efforts to develop the software really got going in 2016 when NIST invited cryptographers to submit ideas for PQC algorithms. Since then, this initiative to develop and standardize the algorithms has seen international cryptographers review proposals, crack some algorithms, and gain confidence in the security of others.

In July 2022, NIST announced the first four PQC algorithms selected for standardization. For secure access to websites, the organization has selected the “CRYSTALS-Kyber” algorithm, which made the grade in part because it quickly produces comparatively small encryption keys that two parties can exchange easily. For digital signatures—used to verify identities during a digital transaction or to remotely sign a document—NIST selected “CRYSTALS-Dilithium,” “FALCON,” and “SPHINCS+.” The first three PQC algorithms are based on the math of structured lattices, while SPHINCS+ uses hash functions.

Structured Lattices and Hash Functions

A lattice is a collection of points used to define a structure. Any point in the lattice can be expressed as a combination of a few special points within the structure and that forms the basis of the cryptography key. The PQC algorithms based on lattice math can only be cracked by solving a lattice problem. The algorithms gain their security because it takes an inordinate amount of computing power to solve such a problem, making it impractical even for a quantum machine.

A hash function is any function that can be used to map data of an arbitrary size to fixed-size values. Hash-based cryptography constructs cryptographic primitives—low-level cryptographic algorithms that can be used to build PQC protocols for computer security systems. 

Challenges to Introducing PQC

Collaborative research and an extensive standardization process will mean that establishing PQC algorithms is not going to be quick. Previous experience with existing cryptographic algorithms has shown it can take up to 15 years after the publication of the standard before a full implementation is complete. Worse yet, with the complexity of PQC public-key standards, they are likely to be even more difficult to implement than classic cryptographic algorithms.

And even when the details of the algorithm are ironed out, introducing a new algorithm can’t happen until all the parts of a computer system are able to deal with the new software. This process is disruptive and can take many years and lots of dollars. These inevitable delays mean we can’t relax our efforts to develop, standardize, and implement PQC cryptographic algorithms for even a second.

The good news is that once PQC security is in place, it will sustain global security for many years because a leap beyond quantum computers will be many decades in the future. A more capable computer will happen one day, but for now, scientists and engineers have little idea of ​​what anything more powerful than a fully-fledged quantum machine would even look like.  

Conclusion

We've got used to the routine encryption and protection of our internet data. Sure, there are still frequent data breaches, but generally, the good guys have remained one step ahead of the hackers and world commerce moves serenely forward. But there's zero room for complacency. Already, cybercriminals are cramming their servers full of encrypted data, waiting for Y2Q when quantum computers will make mincemeat of today's cryptography protection.

Concerted efforts coordinated by NIST since 2016 are bearing fruit, with four PQC algorithms moving forward in the standardization process. But it's important that the momentum continues, because while a quantum computer capable of cracking current cryptography technology is still years in the future, so is standardized PQC security and the infrastructure to support it.

Sources

[1]   https://physicsworld.com/a/when-will-quantum-computers-finally-break-into-the-market/.