Quantum Computing Poses Security Threats to Cryptography

Article By : Maurizio Di Paolo Emilio

Quantum computing promises significant breakthroughs, but it also has the power to blow right through current cryptography systems...

Quantum computing promises significant breakthroughs in science, medicine, financial strategies, and more, but it also has the power to blow right through current cryptography systems, therefore becoming a potential risk for a whole range of technologies, from the IoT to technologies that are supposedly hack-proof, like blockchain.

Cryptography is everywhere — in messages from WhatsApp, online payments, eCommerce sites. Perhaps we cannot see it, but our data are transformed several times to avoid being tracked. “Simple” Wi-Fi is protected by the Wi-Fi Protected Access 2 (WPA2) protocol. Every credit card transaction is protected by the Advanced Encryption Standard (AES). These are different encryption methods with different mathematical problems to solve.

In order to keep ahead of potential security problems, the length of the encryption keys is gradually increasing, and the algorithms are gradually becoming more sophisticated. The general principle is that the longer the key length, the more difficult it is for a brute force to attack and break it. These are attacks in which cyber criminals make thousands of attempts to force keys until they find the right one.

All of this remains true with classic computers that operate with bits and bytes. If and when quantum computers that use qubits come into play, however, then the story changes. In the case of encryption keys, quantum computers are able to process an enormous number of potential results in parallel.

In an interview with EE Times, Jason Soroko, CTO of PKI, Sectigo, said “A traditional computer has two states: on and off, which is why we call them binary computers and often refer to ones and zeros that represent those on and off states. A quantum computer can also use a third state known as a superposition, which gives a quantum computer a unique capability.”

He added, “traditional computers measure their data in bits, but quantum computers utilize a ‘quantum bit’ or qubit. That unique capability enables a quantum computer to perform integer factorization very quickly, which is why current cryptographic algorithms that are based on factorization are potentially vulnerable in the future. A traditional binary computer solves that mathematical problem slowly, whereas a quantum computer with an efficient algorithm can solve that problem much more quickly.  That efficient algorithm known as ‘Shor’s Algorithm’, when coupled with a quantum computer with enough stable qubits, will theoretically be able to break current cryptographic algorithms such as RSA and Elliptic Curve (ECC).”

Progress in quantum computing would jeopardize the use of PKI X.509 (RSA, ECDSA) certificates used today for authentication and digital signature algorithms: all must be protected by new quantum-resistant algorithms to remain secure.

Quantum computing and security
Quantum computers are based on the idea of encoding the digital encoding value into a property of an elementary particle, called “quantum bit” or qubit. According to quantum mechanics, the operations in these quantum CPUs are performed by transforming the state of the elementary particles.

Above, Soroko referred to an algorithm that will probably be the thing that make quantum-era hacking so destabilizing. Named after its developer, Peter Shor, the algorithm allows the factorization of a whole number in polynomials; the second part speeds up the search for a value or a function inversion.

Asymmetric encryption provides a pair of public-private keys with an extremely complex mathematical relationship. The secret private key supports creating a digital signature that can be verified using the public key, protected by a mathematical principle called “unidirectional function.”

Shor’s algorithm solves the mathematical problem underlying many asymmetric encryption algorithms, or public-private key, such as the RSA algorithm.

The advent of quantum processors capable of performing the Shor’s algorithm would make asymmetric algorithms such as RSA, ECC, or all cryptographic algorithms based on integer factoring mathematical problems, discrete logarithms, and discrete logarithms on elliptical curves completely insecure.

Quantum cybersecurity
What is stopping quantum computers overcoming normal ones is that they are difficult to build and maintain stability. Any slight change in temperature or vibration can cause calculations to fail and force you to start again from scratch. That said, many companies, including Google and IBM, have made a lot of progress.

Before the quantum computing becomes common, everyone is advised to secure their data, because when a quantum computer falls into the hands of a cyber-criminal, it will take little time to decipher just about anyone’s data in an astonishingly brief amount of time.

The RSA and ECC algorithms are practically impossible to decipher with brute force methods on a traditional computer. But they’re not impossible to a quantum computer with sufficient stable qubits. Quantum computers can therefore threaten all communications, trade, and finance.

Companies and IT managers are working on protection quantum-based cybersecurity attacks. Learning and training are important factors to consider. We already have quantum-safe encryption algorithms, but they are not yet widely used. There are many reasons for this. First of all, these new algorithms are not yet standardized. It is an essential step so that everyone can refer to the same algorithm. The second reason is that it is necessary to inventory with extreme precision, where what and why encryption is used for existing platforms and services.

“Quantum-resistant cryptographic algorithms have been proposed and are currently undergoing a selection process by NIST, an authority dealing with certifications and standards. Quantum resistance comes from choosing a mathematical approach that is difficult for both traditional and quantum computers. Current cryptographic algorithms such as RSA and ECC are based on algebraic problems, whereas quantum-resistant algorithms are based on solving entirely different problems.  As an example, lattice-based cryptography uses a geometric, rather than algebraic approach, rendering a quantum computer’s special properties less effective. In other words, good cryptography requires a tough problem to solve, and lattice-based cryptography is tough for both classical and quantum computers to solve, making it a good candidate to be the basis of an approach for a post-quantum cryptographic algorithm,” said Soroko.

It is important to gain practical experience with the new post-quantum algorithms and to test the emission and use of safe quantum certificates. As the cryptographic community standardizes on quantum-safe algorithms, Soroko pointed out Sectigo has announced the release of ‘Sectigo Quantum Labs’ which combines a web resource meant to provide education on this subject, as well as a toolkit that enables the user to experiment with quantum-resistant algorithms and issue hybrid certificates. The solution includes the basic tools needed to create quantum-safe certificates for a variety of use cases, along with sample applications showing the use of quantum-safe algorithms (Figure 1).

Figure 1: One way to prepare for the quantum computing future is by using Hybrid Certificates that combine elements of both traditional safe certificates and new quantum safe certificates
Figure 1: One way to prepare for the quantum computing future is by using Hybrid Certificates that combine elements of both traditional safe certificates and new quantum-safe certificates. Click to enlarge the image. (Source: Sectigo)

New quantum secure schemes have been proposed in the literature. Most of them have a public key and signature size significantly larger than those used today. Although post-quantum signatures may work well for some use cases, there are concerns about their size and processing costs on technologies using X.509 certificates.

The X.509 standard defines as a digital certificate, an electronic document associated with a natural person or a computer service that certifies their identity; it consists of a public and a private key provided by the Certification Authority that awaits its validity. In general, being a certificate of identity, it is used in authentication systems based on public key infrastructure (PKI); moreover, it can be used to sign and encrypt e-mail messages.

“Quantum-safe certificates are x.509 based PKI certificates where the keypair is generated with a quantum-resistant algorithm. In the future, we will likely be living in a world where both traditional and post-quantum algorithms will be used at the same time because it will be difficult to rip and replace all of the PKI infrastructures in existence. Hybrid certificates will have both traditional and quantum-safe keys and signatures, which will help to bridge the gap between systems that have been designed to take advantage of the new algorithms, and those that cannot,” said Soroko.

Almost all the algorithms in use with public-private key and used daily for web browsing are subject to  Shor’s algorithm that makes them insecure. There is, therefore, the need to develop new algorithms in a so-called post-quantum phase, i.e. identify and create cryptographic algorithms that will remain secure after the advent of quantum processors. The researchers are proposing several post-quantum cryptographic algorithms with different approaches and based on different mathematical problems that would imply a high consumption of network resources.

Leave a comment