According to ABC News, a Canadian company, D-Wave, says that it will be unveiling a quantum computer today. Now I just happen to know a physicist who has done lots of horribly hard maths and stuff on this subject, he happens to write a blog too, so I've just asked him for his opinion.
He said let's "wait and see" but also pointed to the scientist Dave Bacon's blog where he isn't that convinced. If quantum computing is a reality it will make most current encryption a complete waste of time. What's worse is that the Canuks have it! Oh wait, they're part of the Commonwealth! Score!
Update: I should add, if this is indeed true, then Canada will find itself elevated to the top tables in the global pecking order of things.
Hat Tip: Martine Martin
12 comments:
A general Quantum Computer will, indeed, break public-key encryption. This machine appears to be claiming to perform something like Grover's search algorithm, however, which 'only' provides a 'quadratic speedup' which means that in the limit of large searches, you get a square root speedup. That's not useless, but it won't make breaking public key easy; for that, they'd have to execute Shor's algorithm. Search is the believed (although not proven, I don't think) to be the best possible way to solve a class of problems called 'NP Complete' (a class which includes the famous 'travelling salesman' problem) and it is known (from a paper by Beals, Buhrman, Cleve, Mosca and DeWolf) that quadratic speedup is the best that you can do for something like blind search. Grover's search is a genuinely quantum algorithm; IF they can do it, it'll be very interesting. More interesting, of course, if their methods scale.
As an aside, it's not known for sure that cracking public key encryption is even 'hard' on a classical computer; it's believed to be the case, and no one has published a classical algorithm to break public key encyption (which is based on factoring the product of two large primes), but it's not yet been shown for sure.
The only provably secure method of communication is 'one-time pad' and there you have the problem of communicating the one-time pad in the first place. Quantum communications can, however, solve that problem because, executed suitably sensitively, they'll tell you if an eavesdropper has been grabbing your one-time cypher when you communicate it.
*nods in faux agreement*
*looks dazzled*
I know nothing about quantum computers, but one thing I am certain of ....
if it's any good, the yanks will buy the rights to it!
A quantum computer breaks some public key encryption, not all algorithms...
Anything based on factorisation is susceptible to attack with Shor's algorithm, I believe. I don't know enough about public key algorithms to know if they are ALL based on factorisation.
Shor's algorithm, incidentally, peforms the task of period-finding. Presumably, any method that is open to attacks based on period finding (which includes factorisation) will be vulnerable, in principle, to a quantum computer executing shor's algorithm.
Not all public key algorithms are based on factorisation - you also have elliptical curve crypto. I am sure there are others.
I agree with Adam's first comment - you may notice that current public keys are much larger than the supposedly equivalent security symmetric keys - for example this comment box is using a 256 bit AES symmetric key exchanged using (what looks like) 1024 bit RSA. This is necessary because the phase space of the standard public key algorithms is much more sparse than the symmetric algorithms. That is to say, nearly all 256-bit numbers are valid 256-bit AES keys (although some would be a bit daft). Far fewer such keys are valid for RSA, ECC or other PK algorithms.
A functioning quantum computer, and the D-Wave one appears to be a step that way if not the whole way, will collapse the phase space therefore allowing you to search against a much smaller space (and as the space gets even sparser as you increase the length - at least for factorisation based systems, that doesn't help :)
To Stan's point, how exactly do you know that the NSA don't have one of these running already? They are hardly going to tell people, are they?
S-E
Breaking Elliptical Curve Cryptography would require a quantum algorithm to solve a version of the Hidden Subgroup Problem, wouldn't it? Some cases of HSG are crackable already (I think that factorisation can be rephrased as an HSG problem and the abelian case is also soluble quantumly); it's not (and never was) my area of QIT so I don't know if the considerable effort put into HSG is driven by hope or a general feeling that the problem is quantumly soluble.
It would be some feat to have made a quantum computer in public, let alone secretly. If it's happened, though, you are damn right that telling us all would be highly unlikely.
It may be that Elliptic Curve Cryptography is quantumly crackable already, actually. I did some algorithm stuff early on, but didn't touch this, so I can't say much more than that.
I liked assure all my readers that I understand everything that they are talking about.
I was lost as soon as Adam started with A general ,I have to go now my head hurts.
Post a Comment