- Researchers develop a new quantum algorithm that uses fewer resources to perform code-breaking calculations.
- A 20-million-qubit quantum computer running on this algorithm would take only 8 hours to crack 2,048-bit RSA encryption.
It is certain that quantum computers will be able to crack existing encryption codes used to send secret messages. These encryption techniques have never been completely reliable. Instead, they depend on complex mathematical functions that work in only one direction, making it easy to encrypt information.
The security of such techniques is based on the time a classical computer takes to decrypt the information. Modern encryption techniques are almost unbreakable, as it would take thousands of years for today’s computers to decrypt their code.
However, quantum computers would be able to break these code with ease, and these machines are quite closer to the reality than expected.
Recently, researchers at Google and KTH Royal Institute of Technology in Sweden came up with a more efficient technique that quantum computers could use to decrypt secret messages. It would allow quantum computers to use fewer resources to perform code-breaking calculations.
Quantum Computers Are Becoming More Powerful
In 1994, an American mathematician Peter Shor developed a quantum algorithm for factoring large numbers exponentially faster than the best existing algorithms running on a classical computer. He suggested that a sufficiently powerful quantum machine could break modern encryption techniques with ease.
In the recent decade, a lot of advances has been made in quantum computing. In 2012, scientists were able to use a 4-qubit quantum computer to factor ‘143’. Two years later, they used a similar machine to factor ‘56153’.
Considering the rate of progress, quantum computers will soon be able to outperform today’s computers. At least this is what scientists had expected a few years ago.
It turns out factoring large numbers in quantum machines is much more difficult than anticipated. This is due to the significant noise in large quantum computers. The problem could be tackled by using error-correcting codes, which themselves require extra qubits.
Reference: arXiv:1905.09749 | MIT Technology Review
Taking this noise factor into account, a quantum computer would need one billion qubits to factor 2048-bit numbers (or to decrypt 2048-bit RSA encryption). However, today’s universal quantum computers feature only 70 qubits.
Modular Exponentiation
The new algorithm enables quantum computers to do these calculations with just 20 million qubits. In fact, researchers have shown that a quantum device running on this new algorithm would take only 8 hours to crack 2,048-bit RSA encryption.
“This means the worst case estimate of number of qubits required to factor 2048-bit RSA integers has dropped approximately two orders of magnitude.” – the research team.
Their method performs modular exponentiation — a type of exponentiation carried out over a modulus — in an efficient manner. This mathematical operation is computationally expensive in Shor’s algorithm.
Researchers have found different ways to optimize this operation, dramatically decreasing the resources required to run the algorithm.
Read: 5 Quantum Processors That Features New Computing Paradigm
Although a quantum computer with 20-million-qubit isn’t feasible in the near future, security experts have to think of a new form of encryption that even a powerful quantum computer will not be able to crack.
