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.
The block diagram for the quantum computer expandable to any number of RSA encryption sizes, such as 128- or 256-bits.
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.
Only the 3 and 5 results from the quantum computer match on the truth table by both existing on the intersecting factor lines.
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
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.