Researchers have created a new and potentially dangerous encryption-breaking quantum algorithm
Some cryptography researchers see the claim as misleading, others see it as a potential warning signBy Jimmy Pezzone 23 comments
In a nutshell: Researchers at China's Tsinghua University believe they have discovered a quantum-based algorithm capable of breaking today's most complex encryption standards. The team claims that the algorithm can be run using currently available quantum technologies, too. If true, the lifespan of today's encryption could be drastically reduced to nothing in a handful of years.
Tsinghua University professor Long Guili and his team claim to have developed a new, qubit-saving factorization algorithm that could spell trouble for cryptographic security standards in the not-so-distant future. The algorithm, called sublinear-resource quantum integer factorization (SQIF), claims to optimize the quantum calculation process by reducing the number of qubits required to conduct the code-breaking calculations. The work is based on an algorithm developed in 2013 by German researcher Claus Schnorr.
What does that mean to someone who isn't overly familiar with quantum computing? If successful, the algorithm would increase the chances of breaking today's strongest encryption using currently available quantum technologies, and sooner than originally expected.
Must read: We Cannot Live Without Cryptography!
Created by the National Security Agency (NSA) in 2001, SHA-256 is a cryptographic hashing function that transforms data into an encrypted string of 256 characters. The encrypted output is unreadable unless a recipient has the proper key to decrypt the message.
These decryption keys are also comprised of complex mathematical strings related to the SHA-256 hash, making an encrypted message extremely difficult to decrypt without the proper keys. For example, the time to crack an RSA-2048 bit encryption key using today's most powerful traditional computing resources is estimated around the 300-trillion-year mark.
300 trillion sounds like a nice, safe number that no one should have to worry about. That is, at least until quantum computers are brought into the equation. According to cryptography and quantum experts, a properly sized quantum computer could complete the same algorithm-breaking operation in just under eight hours. This is where Guili's equation raises the alarm bells.
If the SQIF algorithm scales and effectively reduces the quantum computing resources required to run the calculations, then the wait for quantum technology to mature enough to run the calculations could be reduced from a few decades to just a few years.
IBM's Osprey is currently the largest quantum processor in the world, weighing in at 433 qubits. The company's quantum roadmap depicts plans to pursue larger processors ranging from 1,100 qubits in 2023 to more than 4,100 qubits in 2025. By comparison, the SQIF algorithm claims to bring the practical required scale of a quantum computer down to 372 qubits.
Currently the Tsinghua team has not yet proven the ability to break the 2048-bit encryption barrier. They have, however, successfully demonstrated SQIF's feasibility by breaking a 48-bit-length encryption key with a tiny 10-qubit superconductive quantum computer. Though the breakthrough may be nothing to worry about yet, it's definitely a development that security and cryptography experts will continue to monitor.