Using just a laptop, an encryption code designed to prevent a quantum computer attack was cracked in just 53 hours

Security in an age when quantum computing is about to explode is one of the major concerns for all of the protection systems the world over. (According to Jian-Wei Pan, the major expert in this scientific field in China, “the next quantum breakthrough will happen in five years.”) The National Institute of Standards and Technology (NIST) wanted to put seven encryption formulas to the test in order to determine their vulnerability to the new processing systems. Ward Beullens, from the IBM research center in Zurich, Switzerland, managed to crack an encrypted code in just 53 hours and with a simple laptop.

The challenge involved taking seven encryption models to the test bench. The plan was to create an impenetrable technique to develop invulnerable transmission formulas. NIST received 69 proposals, of which in the end there were only four encryption formulas and three secure signatures for the identification and execution of financial transactions.

One of the last of these three models was Rainbow, a signature system that has a secret key that is only known by the user and that can be verified by the recipient. Ward Beullens cracked the access system in a little less than a weekend and using only a laptop. This was the second time that Beullens has managed to do this. “I believe my previous attack was also fairly severe, and it was already clear that Rainbow would not be standardized.”

The researcher, who is the author of a study that was presented at the International Association for Cryptographic Research, explains: “Both attacks reduce the security level of Rainbow’s proposal below the requirements set by NIST. It would be possible to move to larger parameters to protect against the attacks at the cost of larger key sizes and signature sizes.”

Ray Perner and Daniel Smith-Tone, two math researchers involved in the standardization process of NIST, agree with the analysis. According to both of the scientists, before the current selection process “none of the parameters of Rainbow achieve their claimed security level,” but they admit that small changes are possible so that they can be reached.

However, Dustin Moody, also from NIST, believes that the “assault on Rainbow has been proven, and the method is now unlikely to be chosen as the final signature algorithm.”

Quantum computing is a race that is running in parallel to the security problems that it will generate. On the one hand, this science presents huge potential. According to Adán Cabello, a physicist from the University of Seville in Spain, “it will allow for quantum physics to be verified in regions that were inaccessible until now.” But it also represents a risk. For Mark Webber, from the University of Sussex and the main author of an investigation in AVS Quantum Science, “quantum computers are exponentially more powerful at breaking many encryption techniques than classical computers.”

Today, even the biggest supercomputer couldn’t represent a serious threat to Bitcoin

Mark Webber, from the University of Sussex

Webber warns that the encryption that Bitcoin uses will one day be vulnerable to a quantum computing attack, but he clarifies: “Today, even the biggest supercomputer couldn’t represent a serious threat.”

A conventional current computer uses a bit as a basic unit of information (this can have two different values). In a quantum computer, the basic unit is the quantic bit, or qubit, which possesses an infinite number of states. According to Webber, latest-generation quantic computers today only have between 50 and 100 qubits, and, according to his team’s research, would need up to 300 million physical qubits to break Bitcoin’s security.

While that may appear out of reach, the quantic investigator from Sussex warns that the future advances could reduce even more the requirements for improvements both of quantum algorithms as well as the error-correction protocols. “Four years ago, we estimated a trapped ion device would need a billion physical qubits to break RSA encryption, requiring a device with an area of 100-by-100 square meters,” says Webber. “Now, with improvements across the board, this could see a dramatic reduction to an area of just 2.5-by-2.5 square meters.”

This will also be a problem for Bitcoin. According to Webber, “the Bitcoin network could perform a ‘hard-fork’ onto a quantum-secure encryption technique, but this may result in network scaling issues due to an increased memory requirement.”

For Jian-Wei Pan, security has to be a significant aspect of the development of quantum computing, but believes that the latter should be the priority. “Building a practically useful fault-tolerant quantum computer is one of the great challenges for human beings,” he says. “I am more concerned about how and when we will build one. The most formidable challenge for building a large-scale universal quantum computer is the presence of noise and imperfections. We need to use quantum error correction and fault-tolerant operations to overcome the noise and scale up the system.”