IT MIGHT seem like an esoteric achievement of interest to only a handful of computer scientists, but the advent of quantum computers that can run a routine called Shor’s algorithm could have profound consequences. It means the most dangerous threat posed by quantum computing - the ability to break the codes that protect our banking, business and e-commerce data - is now a step nearer reality.
Adding to the worry is the fact that this feat has been performed by not one but two research groups, independently of each other. One team is led by Andrew White at the University of Queensland in Brisbane, Australia, and the other by Chao-Yang Lu of the University of Science and Technology of China, in Hefei. Both groups have built rudimentary laser-based quantum computers that can implement Shor’s algorithm - a mathematical routine capable of defeating today’s most common encryption systems, such as RSA.
RSA is an example of public key cryptography, in which a user holds a pair of mathematically related strings of data, known as a public key and a private key. The public key is widely distributed and used to encrypt messages, while the private key is kept secret and used to decrypt them. An attacker who does not have the private key needs to work out the two very large prime numbers which, multiplied together, make up the public key. Find those factors and you can work out the private key. RSA’s security rests on the extreme difficulty of doing this: today’s digital computers are just not powerful enough to find the factors of a large key in any practical length of time.
For instance, to find the prime factors of a 10-digit public key, approximately 100,000 calculations are needed; for a 50-digit number about 10 trillion trillion are required. IBM’s Blue Gene supercomputer would take a fraction of a second to crack a 10-digit key, but about 100 years for a 50-digit key. And keys are now much longer than 50 digits. In 1994, mathematician Peter Shor at Bell Labs in New Jersey developed a routine that radically reduces the time required to make those calculations. There was just one rather large catch: it could only run on a computer that exploits quantum mechanics.
Shor’s algorithm provides a short cut to finding prime factors by looking for telltale patterns in remainders when a key is divided by a prime factor. Because of the vast number of possible factors for a long key, Shor’s algorithm needs to perform a huge number of mathematical operations in parallel - an ability only offered by the quantum bits, or qubits, that carry information in a quantum computer. Thanks to quantum superposition, qubits can inhabit multiple logical states simultaneously, whereas a digital bit can only exist in one state at a time.
The difficulty now is building a quantum computer big enough to carry out the calculations in a reasonable time. Approaches currently being researched include lasers, superconductors, ion traps and quantum dots.
The first implementation of Shor’s algorithm was achieved in 2001, when an IBM-led team built a quantum computer using nuclear magnetic resonance (NMR) to run calculations in fluorocarbon molecules. The five fluorine nuclei and two carbon nuclei in a molecule acted as seven qubits: the magnetic spin of each nucleus represented the qubit’s state - say, up for 1 and down for 0. Because spin is a quantum property the researchers reckoned the nuclei could be “entangled” into a state that is a mix of both spin up and spin down at the same time - allowing the quantum computer to make calculations in parallel.
Using NMR, the researchers manipulated nuclear spins and coaxed the qubits through Shor’s algorithm. As they had hoped, it gave the correct prime factors for 15 as 3 and 5, but doubts emerged over the experiment’s quantum credentials. “The NMR was valuable early work. But it is not clear that there was any quantum entanglement in it,” White says, and Lu agrees. And there is another problem with NMR: the technology does not scale up. “As the number of NMR qubits increases, the signal disappears in thermal noise,” says Carl Williams, of the US National Institute of Standards and Technology in Gaithersburg, Maryland.
Instead of manipulating nuclear spin, both White and Lu’s teams plumped for photonic quantum computers. Both used femtosecond lasers to generate photon pairs, which they passed through polarising bismuth borate crystals to create entangled qubits. Using optical devices such as filters, they manipulated the qubits to cajole them into running Shor’s algorithm - once again factorising 15 into its constituent primes and reading the results using polarisers and single photon detectors.
Despite the fact that both teams have, like the IBM-led NMR group, only factored the number 15, California-based IT security specialist Bruce Schneier says the way the scientists have done it - with standard lab optics - means problems for encryption may not be far away. Scaling up to solve bigger problems “is now more or less an engineering problem”, he says.
“There is no need to panic right now,” Schneier says, as cryptography would survive even if RSA was cracked. “RSA has lived with the possibility of being cracked for many years. There are lots of other algorithms, and we’ll shift to those.”
Computers like White and Lu’s are not powerful enough to pose a threat to the world’s data, but that may not last. “If we could perform calculations for much larger numbers, then fundamental changes would be needed in cryptography,” says White. “And there are paths to a fully scalable quantum computer.”
So what does he expect to become of the RSA system when such a quantum computer is finally built?
“It will go overnight,” he says.
"This article is posted on this site to give advance access to other authorised media who may wish to report on this story, or quote extracts as part of fair dealing with this copyrighted material. Full attribution is required, and if reporting online a link to www.newscientist.com is also required. This story posted here is the EXACT text used in New Scientist magazine, therefore advance permission is required before any and every reproduction of each article in full. Please contact claire.bowles@rbi.co.uk. Please note that all material is copyright of Reed Business Information Limited and we reserve the right to take such action as we consider appropriate to protect such copyright."
THIS ARTICLE APPEARS IN NEW SCIENTIST MAGAZINE ISSUE: 15 SEPTEMBER 2007. EMBARGOED UNTIL WEDNESDAY 12 SEPTEMBER 2007, 13:00 HRS ET US.
EDITOR’S NOTE: PRIOR PERMISSION IS REQUIRED BEFORE ANY REPRODUCTION OF THIS STORY IN FULL
Author: Saswato Das, Freelance writer, New York
IF REPORTING ON THIS STORY, PLEASE MENTION NEW SCIENTIST AS THE SOURCE AND, IF REPORTING ONLINE, PLEASE CARRY A LINK TO: http://www.newscientist.com
US CONTACT – New Scientist Boston office:
Tel: +1 617 386 2190 or email jill.heselton@reedbusiness.com