# Quantum Computer May Crack Public-Key Encryption

LAKE WALES, Fla.—No shortage of encryption and decryption schemes exists, but for those schemes that merely depend on the difficulty of finding the factors of two large prime numbers multiplied together, their days may be numbered, according to a team of researchers.

Known as public-key encryption, this encryption method—the most notable example being the popular Rivest-Shamir-Adleman (RSA) scheme —appears to be doomed by quantum computing, according to Massachusetts Institute of Technology (MIT, Cambridge) theorists working with prototyping experts at the University of Innsbruck (Austria). Using an algorithm invented by MIT professor Peter Shor and made scalable by Professor Alexei Kitaev at the California Institute of Technology (CalTech, Pasadena), a quantum computer was built to prove the concept, as presented in the paper Realization of a Scalable Shor Algorithm.

RSA algorithms use a public key to encrypt messages, but require a private key (usually the product of two large prime numbers) to decrypt them. RSA is often beefed up by "padding"—adding nonsense phrases at the beginning of an encrypted message (such as its most famous example, the world wonders)—or "hashing"—a function that maps data of variable lengths to data of fixed lengths. However, the leader of the project at MIT—professor Isaac Chuang—believes that even padding and hashing added to public-key-encryption can be cracked by future quantum computers with a little extra work.

"Shor's quantum factoring algorithm would probably help with breaking schemes which employ padding and hashing, but it would not suffice by itself," Chuang told EE Times in an exclusive interview.

**[ Understanding the IoT Platform Wars: Technical Trade Offs at ESC Boston]**

Chuang, in fact, warns countries to use a different encryption scheme altogether to hide state secrets today, because when quantum computers become common in the future, it will be possible to uncover old state secrets that could still harm the national security of a sovereign state.

On the other hand, when quantum computers do become common, it will be possible to use quantum cryptography methods to produce uncrackable codes—even by others who have quantum computers.

"Quantum cryptography is a well-known scheme, which is uncrackable, as long as the laws of quantum physics are correct, as known today," Chuang told EE Times.

Even making Shor's initial algorithm into a bullet-proof executable that could be extended to any length decryption key was a feat many years in the making, since Shor's original "thought experiment" was presented back in 1994. Even so it will be many many years before this proof-of-concept quantum computer can be extended to a size to solve today's modern 128- and 256-bit codes.

Based on the University of Innsbruck prototype using Kitaev's approach that required 5-qubits (super cooled atoms in traps controlled by lasers) the MIT design was thus able to shave 6-qubits off the typical Shor-algorithm (that requires 7-qubits plus 4-qubits as a "cache"). Still, the biggest problem it could solve was the simplest of all factors of two prime numbers, namely 3 and 5 (the two smallest prime numbers) as the factors of 15 (with a confidence of 99 percent, unlike any high-school student who can solve the problem with 100 percent confidence). The importance of the scheme, however, is its scalability that can theoretically someday tackle the 128- and 256-bit codes used by RSA.

Chuang and colleagues admit that it would be prohibitively expensive today to use conventional components—super cooled atoms and lasers—to scale up to RSA sizes, but the point is that someday when tiny solid-state quantum computers are in general use they will be able to use this algorithm to crack today's commonly used codes—as well as to produce uncrackable codes using new quantum-mechanical methods.

Funding was supplied by the Intelligence Advanced Research Project Activity (IARPA), and the MIT-Harvard Center for Ultracold Atoms, a National Science Foundation Physics Frontier Center.

— R. Colin Johnson, Advanced Technology Editor, EE Times

**Related articles:**

- IBM Solves Quantum Computing
- Is D-Wave a Quantum Computer?
- Quantum Highway Frictionless
- Quantum Computing: Diode-like Breakthrough Surmounts Roadblock
- NIST Hits Quantum Teleport Key Out of the Park

*Article update: The headline now reads "Quantum Computer May Crack Public-Key Encryption" rather than the original title ("Quantum Computers Crack Public-Key Encryption"), which suggests more than one quantum computer and current widespread use. The article is about only one experimental quantum computer that was specifically built to prove a quantum computer could break public-key encryption.*

Author

R_Colin_Johnson 3/18/2016 5:19:17 PM

Author

Terry.Bollinger 3/14/2016 7:57:31 AM

In quantum computing those sinusoidals are the different momentum states of the electrons, allowing you in effect to process at one time an "infinite" range of unique electron momentum states in the same circuit, at the same time. (I should note that there is also a more exotic, more powerful, and completely non-classical aspect of quantum computing that involves time. That part of QC cannot be replicated by any type of classical system, pretty much by definition, since only quantum systems can in certain ways be indifferent to the flow of classical time.)

In the old days, pretty much the same idea of processing many electrons states at once was implmented much more robustly by having populations of electrons form classical (vs the much more delicate quantum) wave forms. We called those systems analog computers, and when set up properly they could converge with truly amazing speed to an approxmate result.

And that also is the rub: "approximate" doesn't work when you are trying to factor a very larger number. It has to be exact!

However, there are ways to be clever about all of this by dividing up the problem in ways where you use multiple approximations to build collectively build towards a single well-defined solution. So the problem you raise is very much valid, but not necessarily insurmountable. After all, even we humans with our slow, rather bizarre, and fully classical mix of analog and digital (yes, digital: we use pulse coding to preserve signal levels as they are transmitted along nerves) signal processing are capable at times of exquisite levels of precision through a combination of approximation and feedback that lets us converge to feats such as a precisely thrown major-league baseball. There is no fundamental reason why the larger tool set of quantum computing cannot be also be configured so that despite the approximations and limits on resolution at individual stages of processing, the final result can be very precise indeed.

Author

wave.forest 3/14/2016 6:05:15 AM

The Shor's algorithm works for ECC as well.

Neither RSA nor ECC is secure under quantum computing. We all know it is coming. The question is "When?"

Your article is very good to raise the awareness.

On the other hand, the "May" in "Quantum Computer May Crack Public-Key Encryption" is not accurate either (LOL). It is not "May" - it is "Will". Your articles shows the advance. This advance is well accepted and this is why we are on post-quantum cryptography.

But, please forgive my picky-ness. Thank you for this very good article.

Author

Navelpluis 3/14/2016 3:52:04 AM

You are ABSOLUTELY right. We should not sleep, but see the consequences when all our RSA secrets are on the streets in -perhaps- a couple of years from now. From government point of view this is a no-brainer: They certainly will invest in QC, depending of the regime you are living in -of course. Even for governmental critical communication: They should consider this fact too.

Author

R_Colin_Johnson 3/13/2016 4:59:55 PM

Author

traneus 3/13/2016 4:00:04 PM

Author

R_Colin_Johnson 3/13/2016 1:12:01 PM

Rookie

MortenC683 3/13/2016 5:35:52 AM

Author

R_Colin_Johnson 3/11/2016 11:50:17 AM

Author

wave.forest 3/11/2016 10:17:24 AM

The title is misleading. ;)