By Quantum algorithm offers faster way to hack internet encryption
In 1994, Peter Shor created one of the first practical uses for a quantum computer: hacking the internet. Shor, an applied mathematician at the Massachusetts Institute of Technology (MIT), showed how a quantum computer could be exponentially faster than a classical computer at finding the prime number factors of large numbers. Those primes are used as the secret keys that secure most of the encrypted information sent over the internet.
For 30 years, Shor’s algorithm has endured as an example of the promise of quantum computers—although the devices are not yet big or reliable enough to implement it for large numbers. But now, a computer scientist has revealed a new quantum algorithm that might be better than Shor’s. In a preprint first posted to the arXiv server on 12 August, Oded Regev of New York University proposes a scheme that could greatly reduce the number of gates, or logical steps, needed to factor very large numbers. In principle, it could enable a smaller quantum computer to ferret out the secret encryption keys or a bigger machine to decode them faster. “Is this actually going to have any effect?” Regev asks. “My feeling is that yes, it might have a chance.”
Independent cryptographers who have evaluated the work are intrigued, too. Vinod Vaikuntanathan, a computer scientist at MIT, expects a packed house there next month when Regev will give a colloquium talk on his new algorithm. “In the world of quantum computing, essentially two or three new ideas have appeared so far in the last 30 years since Shor,” Vaikuntanathan says. “You don’t see these new ideas every day, and that makes us hope.” Kenneth Brown, a quantum computing researcher at Duke University, agrees. “Because everybody has studied Shor’s algorithm for a long time, this result is surprising and super cool.”
Like all quantum algorithms, Shor’s algorithm relies on the mysterious properties of quantum bits, or qubits, which can be set to values of not only 0 and 1, but also a “superposition” of 0 and 1 at the same time. Small numbers of these qubits can be stitched together into gates, which carry out the logical operations of an algorithm. To factor a number n bits long, Shor’s algorithm requires a quantum circuit of n2 gates.
Most internet encryption now relies on numbers of at least 2048 bits, which equate to decimal numbers 617 digits long. Finding their prime factors with Shor’s algorithm would therefore require quantum computers with at least 4 million gates. But the biggest quantum computers to date only have a few hundred qubits. “None of them are anywhere near the size we need to factor numbers that we’d care about,” Brown says.
Making things worse, environmental noise often destroys qubits’ delicate superposition states, ruining the operation. The noise can be addressed with error correction, but that requires even more qubits—millions or even billions of them, Vaikuntanathan says. “It really blows up because of error correction,” he says. “That’s why we are pretty far from actually being able to factor 1000-digit numbers.” Improving error correction would help—but so would improving on Shor’s algorithm.
Regev saw a way to do that. Shor’s algorithm is 1D. It searches for the prime factors by raising a single number to high powers. Many big numbers must be multiplied together before a result is reached. Regev realized he could multiply several numbers in different dimensions. The powers for any one number don’t get nearly as high. Although the two algorithms require about the same total number of multiplications, the multidimensional character of Regev’s means the multiplied numbers don’t get nearly as large before a result is reached.
In the end, he found he would need only n1.5 gates to factor an n-bit integer. It’s the first substantial improvement on Shor’s algorithm in 30 years, Vaikuntanathan says. “Nobody has really succeeded beyond shaving off a little bit.”
But Regev’s algorithm also comes with drawbacks, says Martin Ekerå, a quantum computing researcher with the Swedish government whom
Regev consulted with while trying to understand the practical implications of his work. Its structure seems to require quantum memory to store intermediate values during the computation, and that means a need for more of those finicky qubits. “This drives up the cost of the algorithm,” Ekerå says. Regev acknowledges the concern about memory requirements, but says the algorithm still could end up having value—“maybe when memory is cheaper and we instead worry about the number of operations.”
By the time quantum computers are ready to find prime factors by implementing either Regev or Shor’s algorithm, internet encryption may have moved on. Federal agencies and security leaders are already shifting to alternatives, including so-called “lattice cryptography,” which would be immune to quantum hacking. Even so, algorithms like Regev and Shor’s could be applied retroactively, to decrypt recorded traffic from the present and recent past, Ekerå says.
Regardless, Brown believes the sheer novelty of Regev’s work is likely to inspire and generate other new ideas in quantum cryptography, which has struggled for significant breakthroughs. “I am myself trying to think about ways to push this further,” he says.
Source: Science
