Originally published on CSO
While scientists may rejoice at the idea of large-scale quantum computing, CISOs are right to feel nervous.
The advent of large-scale quantum computing promises huge advances in multiple fields, as certain difficult problems become much easier to solve. While progress in developing quantum computers moves in fits and starts (and some well-respected experts doubt we will ever see a large-scale implementation), the prospect of a sudden breakthrough cannot be taken lightly.
While scientists may rejoice at this idea, CISOs are right to feel nervous. Computer networks are only secure because today’s computers can’t solve certain mathematical problems. Once quantum computers arrive, the game will change and some of our existing defenses will be worthless. It’s possible we won’t even know when they arrive. Given what a valuable asset they would be for intelligence services and governments, their debut may be kept quiet.
How do quantum computers affect cryptography?
In 1994, Peter Shor published a quantum algorithm that solves a historically intractable problem: finding the prime factors of very large numbers. Unfortunately, the RSA public-key cryptosystem is dependent on prime factorization being too difficult for computers to do.
Using Shor’s algorithm, quantum computers will render RSA obsolete, allowing attackers to calculate a private key based on public data. With the private key, attackers can masquerade as the victim by signing documents or decrypting confidential messages encrypted under the victim’s public key.
To illustrate the scale of the problem, a 2048-bit RSA key is estimated to take hundreds or thousands of years to break on a modern computer. To gain the same level of security against a large quantum computer, the key would need to be around a million times larger (in the gigabyte range). At this size, one TLS handshake per hour would be optimistic.
Traditional elliptic curve cryptography fares even worse, requiring less-powerful quantum computers to break it. A modified version of Shor’s algorithm can solve the discrete logarithm problem, which underpins schemes like ECDSA and Diffie-Hellman key exchange. In short, asymmetric cryptography as we know it today is doomed.
Fortunately, it’s not all gloomy news. Hash functions are still safe, although we need to double the size of the output to protect against a Grover search. The same is true for symmetric cryptography, using ciphers such as AES. If we double the key size (e.g. to 512 bits), we are assured of safety.
What does this mean for business?
In August, Gartner published a report warning organizations to “plan now for quantum computing.” In the week that followed, the inboxes of CISOs worldwide were likely filled with emails asking what steps are being taken to address the threat of large-scale quantum computing becoming a reality.
To understand how to react to the threat of quantum computing, we must consider the impact of breaking today’s cryptosystems.
Trust and identity
Once public key cryptosystems are broken, it will be impossible to determine if an RSA or ECDSA signature was made by the legitimate owner of the key. Even though new signatures can be made with quantum-safe algorithms (a topic I’ll discuss later), a plethora of previously signed data will still be out there. Which begs the questions: how do we cope with that scenario? Can we trust it?
One approach would be to notarize signed data using quantum-safe algorithms, before we believe quantum computing is available. By embedding a time stamp in a quantum-safe signature, we can assert that the classical signature was valid at the time of inspection, prior to the advent of quantum computing.
Whether this is necessary depends upon the lifespan of your data. Perhaps in the field of law or finance, data must be stored and trusted long enough to make this process a worthwhile endeavor. In other environments, provided a transition to quantum-safe algorithms is conducted within the next decade, signed data will expire before quantum algorithms invalidate it.
In my next blog, I’ll discuss why the lifespan of IoT devices further complicates quantum security (and what to do about it) and quantum computing’s impact on data confidentiality (and what to do about it). I’ll then dive into some of the more promising initiatives centered around mitigating the quantum security threat.