A new study by Google has found that quantum computers could break present-day encryption standards sooner than previously thought, raising security concerns and causing unease among cryptocurrency investors.
In 2019, researchers at Google had estimated that a quantum computer would need to be powered by 20 million qubits in order to crack the encryption standards that make WhatsApp chats secure and protect Bitcoin transactions.
However, in a new paper published on May 21, the same researchers have found that the 2048-bit Rivest–Shamir–Adleman (RSA) encryption standard could theoretically be cracked by a quantum computer with one million qubits running for one week.
“This is a 20-fold decrease in the number of qubits from our previous estimate, published in 2019,” Google researchers Craig Gidney and Sophie Schmieg wrote in a blog post on May 23.
Understanding the theoretical size and performance of future quantum computers capable of breaking encryption standards could help guide the transition towards post-quantum cryptography or PQC.
However, the researchers have also noted that existing quantum computers with relevant error rates are currently powered by 100 to 1,000 qubits. This suggests that building a quantum computer with one million qubits will require overcoming technical challenges and is still some years away.
Why did Google revise its 2019 estimate?
The codes used to encrypt data and secure messages rely on ‘trapdoor’ mathematical functions that work easily in one direction but are much harder to do in reverse. Hence, these functions make it easier to encrypt data, but decoding them is extremely difficult without a special key.
Story continues below this ad
It is practically impossible for a classical computer to factor numbers that are longer than 2048 bits. However, quantum computers can perform code-breaking calculations at a much faster rate than classical computers.
In 1994, American mathematician Peter Shor came up with an algorithm which showed that a quantum computer scaled up to a certain capability can solve trapdoor functions with ease, and hence crack any system with RSA encryption. Since then, the number of qubits needed to run such a quantum computer has steadily declined, according to Google.
In 2012, it was estimated that a 2048-bit RSA key could be broken by a quantum computer with a billion physical qubits. Seven years later, Google lowered that figure to 20 million physical qubits.
What is behind the reduction in physical qubit count?
Qubits are the building blocks of quantum computers. They serve as the basic unit of information with encoded data. Google has attributed the revision of qubit estimates to better algorithms and error correction techniques.
Story continues below this ad
Since physical qubits exist in multiple states, they lead to multiple outcomes. Getting the desirable outcome is a challenge as disturbances caused in any qubit can result in errors in calculations. Detecting and correcting these errors require algorithms which require extra qubits (logical qubits).
What are the implications of the new study?
Asymmetric algorithms such as RSA are used for encrypting data in transit. They form the basis of messaging services like WhatsApp. The Elliptic Curve Diffie-Hellman algorithm, which is also based on asymmetric cryptography, is used to secure Bitcoin transactions with public and private keys.
Google said asymmetric encryption standards need to be urgently replaced with post-quantum encryption standards “due to the fact that an adversary can collect ciphertexts, and later decrypt them once a quantum computer is available, known as a “store now, decrypt later” attack.”
Without specifically naming bitcoin or any other cryptocurrencies, Google said that signature keys need to be equipped with post-quantum cryptographic standards as they are “harder to replace and much more attractive targets to attack, especially when compute time on a quantum computer is a limited resource.”
Story continues below this ad
Last year, a study by University of Kent’s School of Computing found that Bitcoin would have to go offline for 300 days in order to be updated with a PQC protocol that would make the cryptocurrency immune to quantum computing-based attacks.
Google said it has been working with the US National Institute of Standards and Technology (NIST) and others in government, industry, and academia to develop and transition to PQC.
“NIST recently concluded a PQC competition that resulted in the first set of PQC standards. These algorithms can already be deployed to defend against quantum computers well before a working cryptographically relevant quantum computer is built,” it said.