Quantum Computing may sound like science fiction, but this week Google announced their plan to build a ‘useful’ quantum computer by 2029.  So how do Quantum Computers work, and why should they be on the radar of Security Managers today?

Selecting keys and Moore’s Law

Before we dive into Quantum Computers, we need to circle back a think about today’s conventional CPU and Moore’s law – and how this impacts security and cryptography today.

When picking a symmetric key or password, we are used to thinking of the strength of the key in terms of ‘how many years would it take to brute force guess.’   Provided it takes longer (i.e. costs more) to break the encryption or brute force the password than the protected data is worth then we have picked a key of the right length.  Provided that is, we remember about Moore’s Law: that is the processing power of a CPU doubles about every two years.  So, when it comes to encrypting data that a business has to retain for ten years before deleting it, we need to ensure that the key chosen will withstand the predicted CPU power that will be available in 8 or 9 years time, not just the power of today’s processors.

Computer systems and software often remain in service for much longer than the original authors and designers expect.  The millennium bug happened because no-one believed the code they were writing in the 1980s would still be in use two decades later.

It is a similar thought process when it comes to quantum computing – 2029 is not very far away and systems being designed today may well still be in use in 2029 when the availability of quantum computers could significantly affect the strength of encryption.  For this reason, Security Managers need to be aware of the threat of quantum computers to today’s encryption technologies – as quantum computers are likely to be a reality within the lifetime of today’s information systems.

What is a quantum computer?

Conventional CPU are made from millions of tiny transistors.  A Pentium II CPU from 1999 contained about 27 million, and a 2017 28-Core Xeon chip had about 8 billion. The Apple M1 chip has about 16 billion transistors, whereas an AMD Epyc Rome CPU has just under 40 billion.  The number of transistors governs how many binary operations a CPU can perform per second.

Quantum Computers do not use transistors, instead they are based on qubits – quantum bits.  There is no real correlation between transistor counts and qubit counts other than the principle that the more there are, the ‘faster’ problems can be solved.

In the spring of 2021, current quantum computers are using less then 100 qubits.  Unlike traditional binary CPU which work with bits that have either a state of 0 or 1, qubits take advantage of quantum superposition to exist as both a 1 and 0 at the same time. (No wonder Einstein called quantum mechanics ‘spooky.’)  This means that a quantum computer sees an exponential increase in processing power as more qubits are added as each pair of qubits that can exist as either 0 or 1 can actually embody four possible states. So, three qubits can embody 8 possible states while three hundred qubits can embody more possible states than there are atoms in the whole Universe.   Google is aiming to eventually construct a quantum computer with a million qubits.  As for progress so far, Google claims their current working quantum computer can complete a calculation in 200 seconds that would take a traditional supercomputer 10,000 years. (Although IBM’s quantum research team disputes this result)

In 1994, MIT Professor Peter Shor discovered Shor’s algorithm which allows quantum computers to ‘easily’ discover prime factors.  The supposed fact that finding prime factors is very, very difficult is the foundation of most public key cryptography schemes such as RSA.  The problem is, finding prime factors is computationally intractable on traditional silicon but quite possible for a quantum computer. IBM proved this in 2001 when it validated Shor’s algorithm using a 7 qubit system. In fact, the three hard math problems that underpin PKI (integer factorisation, discrete logarithm problem and the elliptic-curve discrete logarithm problem) are all susceptible to quantum computers and Shor’s algorithm.

When it comes to symmetric key encryption, the news is a little better.  It is thought that most current symmetric encryption algorithms and hash functions are relatively secure to quantum computer powered attacks.  In the symmetric encryption world, it is Grovers algorithm that is used by quantum computers to discover the encryption key and its effect is the equivalent of halving the key length.  So if a 128 bit key is considered strong enough today for your symmetric encryption needs, a 256 bit key should provide the same level of protection against a quantum computer powered attack.

What should security managers do today to prepare for quantum computing tomorrow?

Both the NCSC and NIST have helpful resources for today’s security managers listed below.  In summary their guidance is: be aware of the risk of quantum computing, but it is too early for most organisations to invest in quantum cryptography yet.

NCSC says in their whitepaper Preparing for Quantum-Safe Cryptography that today’s quantum computers are not a threat to Public Key Cryptography, but data encrypted today could be decrypted in the future and so there is “a relevant threat now to organisations that need to provide long-term cryptographic protection of {very high value} data.”

NIST is expected to publish standards for quantum-safe cryptography sometime in 2022-24 and the NCSC is waiting to see those recommendations rather than producing their own.

The NCSC further advises:

Large organisations should factor the threat of quantum computer attacks into their long-term roadmaps. But for now, todays normal cyber-security best practices should be followed until standards emerge for quantum-safe cryptography.  Long term plans should factor in the need to transition today’s public-key systems to quantum safe technology at some point in the future with attention paid to those parts of the infrastructure that use certificates with expiry dates far in the future that may be hardest to replace. For symmetric encryption, consider when to double key lengths to protect against Grovers-based quantum attacks.

Early adoption of non-standardised Quantum-Safe Cryptography is not recommended.  Wait for the NIST standards to be published.  If you adopt quantum technology today you risk picking a system which later proves not to be truly secure or is not compatible with the industry standards when they finally emerge.

Further Reading

NCSC Preparing for Quantum-Safe Cryptography

NCSC White Paper on Quantum Security Technologies

NIST Getting ready for post-quantum cryptography

ETSI Migration strategies and recommendations to Quantum Safe schemes