Is quantum computing a threat to cybersecurity? (2)

7.052 0

by Josh Lake – Specialist in security, privacy and encryption

The Open Quantum Safe project

On top of NIST’s search for suitable algorithms, the Open Quantum Safe project has also been launched. As a collaboration between academics and the open source community, backed by industry funding, it aims to support the “development and prototyping of quantum-resistant cryptography”.

The Open Quantum Safe project is currently focusing on two main objectives:
– Developing liboqs – an open-source library for quantum-resistant cryptographic algorithms;
– Prototyping integrations of cryptographic algorithms into various protocols and applications.

Post-quantum public-key algorithms

At this stage, five main approaches for public-key algorithms are thought to be resistant to quantum-computing attacks. These are hash-based cryptography, lattice-based cryptography, supersingular elliptic-curve isogeny cryptography, multivariate cryptography, and code-based cryptography.

Research into their security and usability is ongoing, but it is hoped that at least one option based on these techniques will be suitable for the post-quantum cryptographic world.

Hash-based cryptography

These systems for digital signatures have been around since the 1970s, but fell out of favor because under these schemes, a private key can only be used to sign data a limited number of times. Because these mechanisms are hash-based, rather than number-theoretic like the signature schemes we currently use (RSA, DSA, ECDSA, etc.), they aren’t vulnerable to known quantum-computing attacks.

This resistance ignited new interest in their properties and potential applications. Hash-based cryptography keys would need to be 36,000 bits long to grant 128 bits of security and be able to sign one million messages.

Lattice-based cryptography

Lattice-based cryptography involves a range of different approaches that rely on the properties of lattices. There are a number of different lattice problems which make their underlying structure resistant to both classical computing and quantum computing attacks.

Lattice-based cryptographic systems such as NTRU seem like promising candidates. After rigorous study, no major security concerns have been found. A team of academics recommended a 6,130-bit public key and a 6,743-bit private key for 128 bits of security with the NTRU algorithm.

Supersingular elliptic-curve isogeny cryptography

This method involves using both supersingular isogeny graphs and supersingular elliptic-curves to create a public-key exchange that has perfect forward secrecy. It works similarly to the Diffie-Hellman key exchange and has been scrutinized quite heavily.

The latest research shows that a 3,073-bit public key can give 128 bits of security under this system. This is the smallest key size for any of the systems that have been evaluated so far, with a similar size-to-security ratio as RSA.

Multivariate cryptography

These schemes are based on the concept that multivariate equations are difficult to solve. There are a range of different systems, and the most prominent has the quirky name of Unbalanced Oil and Vinegar.

At this stage, these systems seem to be most effective for digital signatures, because they produce the shortest signatures. Current research suggests that they are less useful when it comes to encryption.

As an example, an analysis of the Rainbow algorithm showed that it could provide 128 bits of security with 424-bit digital signatures, but public keys would have to be 991,000 bits and private keys would have to be 640,000 bits for the same level.

Code-based cryptography

One of the most prominent examples of this type of cryptography is the McEliece algorithm, which relies on the difficulty of decoding a general linear code. It has been studied for over 30 years and is resistant to known quantum-computing attacks.
There are a number of potential ways to implement this system. The technique with the smallest key sizes would need a public key of 32,771 bits and a private key of 4,384 bits to provide 128-bit security.

Quantum computing & symmetric-key cryptography

Symmetric-key encryption is the type of cryptography that you are probably most familiar with. It uses the same key in both the encryption and decryption processes, and it appears in a wide variety of applications, from encrypting your hard drive, to locking down the information that is transmitted between your web browser and an HTTPS website.

This type of encryption is a fundamental part of keeping our communications safe. Without it, our data would be far more vulnerable to attackers and eavesdroppers. The good news is that symmetric-key encryption is far more resistant to known post-quantum computing attacks than public-key cryptography.

Grover’s algorithm

At this stage, Grover’s algorithm is the biggest quantum-computing threat that can be used against our commonly used symmetric-key encryption methods. Others may arise in the future, but so far, Grover’s algorithm is the biggest concern.

It was developed by Lov Grover in the 1990s and it has the capability of calculating the key that was used to encrypt data with a high likelihood of success. Attackers could, therefore, use it to obtain keys that were used to encrypt data, giving them free reign to access the contents.

Again, since the quantum computers of today are nowhere near capable of running such a complex attack, Grover’s algorithm is not currently considered a threat. Despite this, if quantum computers do emerge and fall into the hands of adversaries, they will be able to use the algorithm to brute force the keys of their targets.

The threat of Grover’s algorithm is nowhere near as severe as those that loom ahead of public-key cryptography. Practically speaking, Grover’s algorithm is only able to reduce the security of a cipher like AES by half. That means that against Grover’s algorithm, a 128-bit AES key would only have the practical security of a 64-bit key.
There is a relatively simple solution to this threat: doubling the key length.

If we wanted our data to have a security level of 128 bits against Grover’s algorithm, we would simply use a 256-bit AES key. Although the threat is certainly real, the countermeasures for protecting our symmetric-key algorithms are relatively simple, so cryptographers are not particularly worried about attacks based on Grover’s algorithm.

Quantum computing: More than just a security threat

At this stage of the article, you might be beginning to think that quantum computing is all bad news when it comes to internet security and cryptography. Despite the complications that quantum computing may bring to these fields, there could also be some benefits.

The unique properties of quantum mechanics open up a world of new opportunities when it comes to secure communication. Some of these, such as quantum key-distribution, are already being used. Potential quantum mechanisms for the future include Kak’s three stage protocol and quantum digital-signatures, among other possibilities.

Quantum key-distribution

Quantum key-distribution is much like any other key exchange protocol. It allows two parties to securely establish a symmetric key which they can use to encrypt their future communications. The main difference is that it leverages the unique properties of quantum mechanics, allowing the two parties to detect if an attacker is eavesdropping on the messages.

This is made possible because of one of the fundamental principles of quantum mechanics: Any attempt to measure a quantum system will alter it. Since intercepting data is, in essence, a form of measurement, a quantum key-distribution scheme will detect any anomalies that come from an attacker eavesdropping and abort the connection.

If the system does not detect any eavesdropping, the connection will proceed, and the parties can be certain that the key they have developed is secure, as long as adequate authentication has taken place.

Quantum key-distribution is currently used in certain situations where the need for security is high, such as banking and voting. It is still relatively expensive and cannot be used over large distances, which has prevented further adoption.

Kak’s three-stage protocol

Subhash Kak’s three-stage protocol is a proposed mechanism for using quantum cryptography to encrypt data. It requires the two parties in the connection to first be authenticated, but can theoretically provide a way to continuously encrypt data in a way that is unbreakable.

Although it could be used to establish keys, it differs from quantum key-distribution because it can also be used to encrypt the data. Quantum key-distribution only uses quantum properties to establish the key–the data itself is encrypted using classical cryptography.

Kak’s three-stage protocol relies on random polarization rotations of photons. This method allows the two parties to securely send data over an unsafe channel. The analogy that is usually used to describe the structure is to picture two people, Alice and Bob. Alice has a secret that she wants to send to Bob, but she does not have a safe communication channel over which to do so. To securely send her secret over an insecure channel, Alice puts her secret in a box, then locks the box with a chain around the outside. She then sends the box to Bob, who locks the box with his own chain as well.

Bob then sends the box back to Alice, who takes off her lock. She then returns the box to Bob. Since the box now only has Bob’s lock protecting it, he can unlock it and access the secret data.

This method allows Alice to send Bob a secret without any third party being able to access it. This is because the box has at least one person’s lock on it each time it is sent across the insecure channel.

Quantum digital signatures

Quantum computing threatens our commonly used digital signature schemes, since they rely on public-key ciphers that are vulnerable to Shor’s algorithm. However, the new technology also opens the door to quantum digital signatures, which would be resistant to these attacks.

Quantum digital signatures would work just like normal digital signatures, and could authenticate data, check its integrity and provide non-repudiation. The difference is that they would rely on the properties of quantum mechanics, rather than on mathematical problems that are difficult to reverse, which is what the systems we currently use are based on.

There are two different approaches to quantum digital signatures:
– A classical bit string is used for the private key, and a public quantum key is derived from it.
– A quantum bit string is used for the private key, and a public quantum key is derived from it.
Both of these types of quantum digital signatures differ from classical digital signatures, because they use one-way quantum functions. These functions would be impossible to reverse, while classical one-way functions are just incredibly difficult to reverse.

Quantum computing: Should you be worried?

Practical quantum computing is still on the distant horizon and there is a lot that we don’t know about it. Its harshest critics think that quantum computing will never be useful, while some of the companies involved in its development estimate its commercial arrival at some point in the next five to 15 years.

At this stage, significant challenges lay ahead for scientists. Current machines aren’t powerful enough, and the issues surrounding quantum decoherence need to be resolved.

While these factors seem to be keeping our current cryptographic systems safe for now, there is still the risk that new algorithms, techniques, and attacks will be discovered. If quantum computing does finally arrive, these could pose far greater risks than anyone anticipated.

Despite these unknowns, a lot of money is being thrown into quantum computing and the study of its ramifications on security. Industries, government bodies, and academics are all working to prepare for a post-quantum future which may never arrive, just in case.

This is important, because the risks are great and the areas that need to be studied are extensive. On top of this, it takes years to develop, analyze and standardize new cryptosystems.

While quantum computing is still years away, if we weren’t already starting to work on precautionary measures now, a worst case scenario could lead to quantum computing falling into the hands of attackers before the appropriate defense mechanisms are in place. This would be catastrophic for all of our digital communications.

The risks are real and there is the slight possibility of things turning disastrous. However, a realistic analysis of the development of quantum computing and the precautionary measures that are being studied alongside it indicates that the world is on track to manage these risks effectively.

If practical quantum computing arrives, it is likely that it will disrupt some of our currently used cryptographic systems. Despite this, alternatives that are assumed to be secure are already in the pipeline.

As long as we continue along our current path and no sudden surprises emerge, the potential arrival of practical quantum computing should not cause any major disruptions or upheaval. For now, there’s nothing to worry about – the scientists seem to have everything under control.

yogaesoteric
April 26, 2020