Code-Breaking Quantum Algorithm On a Silicon Chip 133
Urchin writes "Shor's quantum algorithm, which offers a way to crack the commonly-used RSA encryption algorithm, has been demonstrated on a silicon chip for the first time. The algorithm was first demonstrated on large tabletop arrays 3 years ago, but the photonic quantum circuit can now be printed relatively easily onto a silicon chip just 26 mm long. You can see the abstract from the team's academic paper in the journal Science; the full text requires a subscription."
Interesting and a qustion (Score:5, Interesting)
Side question: Which asymmetrical encryption algorithms are safe(er) against quantum algorithms (Some algorithms do not benefit from a tremendous quantum speedup, only a large one)?
Can someone explain this... (Score:1, Interesting)
...in more human-understandable terms?
Here's my understanding of it, which is probably wrong but I'd love some clarification-- basically one benefit of a quantum computer is that it allows you to factor gigantic numbers into component primes super-fast. So for example, those distributed computing contests where you'd crack RSA keys by searching a keyspace in 10 years or 50 or 50 million years or whatever goes out the window, because a quantum computer can find all possible primes simultaneously rather than one-by-one. I THINK this is made possible by superpositions of atoms not having a single state but all possible states simultaneously, whatever that means, and then somehow atoms are "entangled", manipulated, and the correct values are sussed out with a probability approaching 1.
If this is right, and I'm not saying it is, how do you do all this with a chip? The article says "Although the new chip is only 26 mm long, it has to be surrounded by a whole table top of that equipment.". I would think you'd need a ton of gear and rare materials to put atoms in superpositions and entangle them and all that... What does the chip do exactly... and how does this work?
If anyone could clarify, I'd be really interested. If this marks the beginning of the end of RSA... do we have a back up method that is more resistant to quantum computing? (And don't say quantum encryption, cuz I'm not sure people are going to have the gear on-hand when they want to send an email via GPG or do some online banking...)
Re:Interesting and a qustion (Score:5, Interesting)
I'm a bit of a crypto nerd (more of a fan, not exactly up to sratch on designing the algorithms, but I've read EXTENSIVELY on their proper use) and if you get a large quantum computer working, things go titsup for any of our currently viable public key crypto schemes. The short of it is this: you can no longer trust any key exchange system that relies on public keys. SSH is no longer secure, SSL is trash, the list goes on. Any time you need to exchange secure data without having previously encountered the far end securely first, game over.
That's frightening. I know that there are some proposed algorithms that only allow for a polynomial speedup in quantum computers, but I couldn't find them between when I posted initially and now.
So yeah, fear it, but in terms of cracking larger numbers this is not even a proverbial "smoke in the building" scenario. It looks like their technique does not employ error checking, making large numbers of qbits near impossible to work with.
Re:Interesting and a qustion (Score:5, Interesting)
I think the real question is whether or not quantum computing can solve the Travelling Salesman problem.
It can not.
There is no reason to believe QBP contains NP. (We might be wrong, but then we might be wrong about P != NP!)
Any approach along the lines of "do everything quantumly in parallel and somehow select the interesting results" will do no better than a Grover search, which is a quadratic speedup.
Re:Interesting and a qustion (Score:2, Interesting)
Problems like factoring products of primes (This is a big deal in crypto, but the explanation of why is hard if you haven't taken a university number theory course) and the above-mentioned Traveling Salesman Problem (The question of how I can most efficiently reach each of a given set of points, after given fixed distances between said points) are what we call np-complete. This means, in short, that the amount of time it takes to solve them goes up more and more for each item (point in TS, making the prime gigantic in crypto) you add. It's trivial to factor 15, as shown here, but non-trivial to factor (2 ^ 43112609 -1) * (2 ^ 42643801 -1).
So, yes, if it can solve the traveling salesman problem (in polynomial time. Solving it is easy, unless you consider that with enough nodes, it'll take until the heat death of the universe), it IS a big deal for modern crypto because it shows that np-complete problems (whose only REAL issue is that they are computationally difficult) can be solved in a realistic amount of time, and most modern crypto counts on the fact that it cannot.
Re:Is this really a big deal? (Score:3, Interesting)
http://en.wikipedia.org/wiki/Ultra#Battle_of_the_Atlantic [wikipedia.org]
It is commonly claimed that breaking of German Naval Enigma shortened the war by a year, but given its effects on the Second Battle of the Atlantic alone, that might be an underestimate.
An exhibit in 2003 on "Secret War" at the Imperial War Museum, in London, quoted British Prime Minister Winston Churchill telling King George VI, "It was thanks to Ultra that we won the war." Churchill's greatest fear, even after Hitler had suspended Operation Sealion and invaded the Soviet Union, was that the German submarine wolf packs would succeed in strangling sea-locked Britain. He would later write, in Their Finest Hour (1949), "The only thing that ever really frightened me during the war was the U-boat peril." A major factor that averted Britain's defeat in the Battle of the Atlantic was her regained mastery of Naval Enigma decryption.
Re:Interesting and a qustion (Score:4, Interesting)
As far as I know, the "only" crypto applications of QC that would give an exponential speed-up are for factoring (Shor's algorithm). I realize that that's essentially all currently used asymmetric (public/private key) encryption, but afaik elliptical encryption, which is also usable for asymmetric encryption, isn't impacted.
Of course, no one knows if elliptical encryption will fall to some quantum algorithm, and you can always get a O^0.5 speed up using Grover's algorithm, but O^0.5 just requires double the key length rather than making encryption impractical.
Scott Aaronson [scottaaronson.com], a quantum algorithm complexity researcher at MIT, believes that quantum computing does not in general give an exponential speed-up to algorithms, and I believe him...
Re:Interesting and a qustion (Score:3, Interesting)
So not anytime soon... the refrigeration units required to produce the temperatures at which quantum computing is viable are not likely to be within a typical consumer's budget (or likely to fit in their apartment, for that matter) for the forseeable future.