If you're worried that quantum computers will crack your crypto, don't be – at least, not for a decade or so. Here's why

Special report Quantum computing has been portrayed as a threat to current encryption schemes, but the ability of finicky vaporware to overthrow the current security regime looks like it's massively overstated.

Richard Evers, cryptographer for a Canadian security biz called Kryptera, argues that media coverage and corporate pronouncements about quantum computing have left people with the impression that current encryption algorithms will soon become obsolete.

As an example, Evers points to remarks made by Arvind Krishna, director of IBM research, at The Churchill Club in San Francisco last May, that those interested in protecting data for at least ten years "should probably seriously consider whether they should start moving to alternate encryption techniques now."

In a post Evers penned recently with his business partner Alastair Sweeny, he contends, "The hard truth is that widespread beliefs about security and encryption may prove to be based on fantasy rather than fact."

And the reason for this, he suggests, is the desire for funding and fame.

Face the facts

There two commonly used forms of encryption: symmetric and asymmetric.

Symmetric involves a single private key to encrypt and decrypt data. Examples of symmetric algorithms include 3DES, AES, DES, QUAD and RC4 (not to mention ROT13). Asymmetric involves a public key and a private key. ECC, El Gamal, Diffie-Hellman, DSA and RSA are common asymmetric algorithms.

Assuming a suitably functional quantum computer can be built – a possibility that has been tens years away for the past decade – the hope and fear is that the device will be able to run Shor's algorithm to break asymmetric algorithms like RSA and Grover's algorithm to break symmetric algorithms.

For that to happen, quantum computers need to become orders of magnitude better at error correction. Quantum computers traffic in qubits that can represent values of 0, 1, or a superposition of both states, whereas the binary bits in conventional computers can be 0 or 1, and nothing else. And they need quite a few qubits to do anything useful. It's been estimated that 6,681 qubits [PDF] would be required to run use Grover's algorithm to break AES-256 bit encryption.

IBM's Q System gated quantum computer currently tops out at 20 qubits; it's been testing 50 qubit system. Intel has a 49 qubit machine and Google has a 72 qubit device.

D-Wave, another quantum computing biz, sells a different type of machine with 2,000 qubits that uses an approach called quantum annealing, though the different architectural approaches preclude qubit-to-qubit comparison. Regardless, none of these implement error correction.

As a recent research paper puts it, "Experimental quantum error correction and fault tolerance is still in its infancy, but several impressive results have been achieved."

Error errata

A US National Academies of Sciences, Engineering, and Medicine report on quantum computing last December said the average error rate of qubits "would need to be reduced by a factor of 10 to 100 before a computation could be robust enough to support error correction at scale."

And quantum computers would have to be designed to hold 100,000 times more physical qubits than they do now to support the logical qubits necessary for such error correction calculations. Logical qubits, used for computation, require multiple physical qubits, with redundancy compensating for their unreliability.

Evers acknowledges that there's worldwide effort to get a handle on quantum error detection and correction. "Once that occurs, it may prove feasible to create quantum computers with sufficient logical qubits to reliably run Shor's and Grover's algorithms," he says. "Unfortunately, no one really knows what will happen in the future."

The NASEM report says as much, noting that it's "highly unexpected" a quantum computer will be able to break RSA 2048-bit encryption within the next decade.

In an email to The Register, Matthew Green, associate professor of computer science at the Johns Hopkins Information Security Institute, agreed that quantum computers don't spell the end for encryption, though he allowed they could pose problems if they can run the right algorithms reliably enough.

"So far as we know, quantum computers seem to be theoretically possible, and building them is just a matter of very hard engineering," he said. "We know that if an appropriate quantum computer can be built, it could run Shor's algorithm and other variants that would break most public-key encryption we use today. Grover's algorithm can also generically break some symmetric encryption, but only if it uses relatively short keys. We can address that by using larger keys."

Green noted that the US government's National Institute of Standards and Technology (NIST) is currently running a contest to see which encryption algorithms might weather an attack from a future quantum system.