A new paper by researchers from the encryption-focused Canadian company Kryptera says that it could take decades for quantum computers to break encryption. However, the time to produce alternatives for existing encryption algorithms may be now.
Delaying the Crypto-pocalypse
Richard Evers and Alastair Sweeny from Kryptera said that some of the companies that have been working on quantum computers, such as IBM, have been exaggerating the threat of quantum computers to encryption. The Director of IBM Research, Arvind Krishna, recently said that quantum computers could start breaking common encryption algorithms within the next decade as quantum computers gain an “advantage” over classical computers.
There are two main forms of encryption used by software and internet services today: symmetric and asymmetric. Quantum computers that are powerful enough could potentially break both forms, but not in the same way.
For instance, we only have one algorithm, called “Grover,” that could break an encryption key in quadratic time. That means that a quantum computer could break a 128-bit symmetric encryption key in the time it takes classical computers to break a 64-bit symmetric encryption key (several hundred CPU cores could do it in a year).
According to the Kryptera researchers, breaking AES-128 encryption should require a quantum computer with 2,953 logical qubits, while breaking AES-256 would need 6,681 qubits.
Then there is the “Shor” algorithm, which can break asymmetric encryption with twice as many qubits as the key size. For instance, breaking a 2048-bit RSA key would require a 4096-qubit quantum computer.
Difference between Logical and Physical Qubits
The Kryptera researchers said that so far neither Google, nor IBM, nor Rigetti have built quantum computers with error-correcting logical qubits. When error correcting code is used in a quantum computer, many more physical qubits are needed to create a logical qubit.
According to the Kryptera paper, creating a universal quantum computer with 1,000 qubits would require millions of physical qubits. Even if the number of qubits in a quantum computer could double every year, we’d still need to wait roughly two more decades before we get to the one million qubit mark.
However, it’s possible, or even likely, that progress in quantum computers will not be linear, and that we could see an explosion in the performance of quantum computers in the next decade as large companies begin to take quantum computers more seriously or start running sophisticated machine learning algorithms on them.
One breakthrough in quantum computing could make it so that you would need much fewer physical qubits per logical qubit, for instance, which would dramatically accelerate the progress of quantum computers, making it much more likely that encryption algorithms would be broken soon.
Quantum-Resistant Algorithms Are Still Needed Now
Even though the Kryptera researchers don’t think current efforts in quantum computers justify the worry about all encryption being broken soon, that doesn’t mean we shouldn’t start producing new post-quantum encryption algorithms already. It takes many years to invent a new encryption algorithm, many years to test it in competitions or in real-world programs, and many years still to see it deployed in most applications.
The National Institute of Standards and Technology (NIST) has started a competition for quantum-resistant algorithms and has recently announced phase 2 of this competition. The agency has selected 26 of the initial 69 algorithms for phase two.
Considering that most of these algorithms use new forms of cryptography (lattice-based, code-based, etc.), NIST is expected to select several of the candidates as the finalists. The sooner these finalists will begin to be tested in the wild, the sooner we’ll know which will be best suited to survive the powerful million-qubit quantum computers of the future.
