I don't usually nitpick spelling of posters, but when the slashdot article itself spells weird as "wierd" I have to wonder if there exist any good spell-checkers for linux. I use ispell.
Hey, that's not fair! We academics know there is a denial of service attack and that it's a problem. At least some of us do. There are situations where it isn't that bad though. If a company is communicating with a branch office through a fiber and the denial of service happens, you just send the police out to see who dug up your fiber. Problem solved.
One definitely does need a secure authentication scheme for quantum key exchange to work.
Fortunately, secure authentication schemes exist even without quantum mechanics. For example, suppose you and I each already have a 20 bit key. I just ask you what it is and if you can tell me I know it was you. Obviously this is secure (up to a one in a million chance). Of course, there are two unavoidable problems with this. One, you may have handed over your key to someone else at gunpoint. Two, we'd better not use that same key again because Eve could have listened to it.
Problem one cannot be solved. Problem two is solved by not reusing the key, but instead using new key that we exchange using the quantum key distribution. This makes denial of service attacks particulary annoying, since if we have to wait and try again later we'd better authenticate again using a new key and we might run out before we get to use quantum key exchange to make some more. Doh!
The real situation is more complicated than this because I don't need to juse verify that I am talking to you at the start of the conversation, but rather must authenticate each bit of our conversation, without using up more key than we can get back by the quantum key distribution. This is also possible with a little more complexity.
I'll have to read up on NP-complete cryptosystems and see if I think they are broken by quantum computeres. It is always possible that the cryptosystems are all broken without actually sovling the NP-complete problem itself. One possibility is that there is no PK crypto if there are quantum computers. I don't think we know.
As for Grover's algorithm being optimal: It is optimal for finding a single marked item in a list of N elements, which it does in square root of N time. But an NP problem may have more structure than simply being a random element in a list. So I believe the jury is still out on if quantum computers can solve NP-complete problems in polynomial time.
Let me try to clarify the situation with regards to factoring as an NP problem. I believe the situation is this (I'm a physicist working on quantum information, rather than a computer scientist, so the classical computer sciencey stuff you should take with a grain of salt):
Polynomial problems are said to be in NP since they are a subset of NP, so it is not right to say factoring is not in NP, since all polynomial problems are "in" NP. There are also problems that are NP hard but not NP complete, meaning they are harder than polynomial, but that a fast solution to one of them doesn't solve all other NP problems.
Factoring is known to NOT be NP-complete.
Factoring might be NP hard, or might be polynomial.
P might be the same as NP.
So fast factoring on a quantum computer doesn't mean all NP problems are easy.
It is not known if quantum computers can solve NP complete problems in polynomial time. Most people doubt it.
Computer scientists certainly are working to try to understand the new complexity classes which result from the presence of quantum computers. I'm not quite sure if they have a class which is NP hard to a quantum computer, but even harder to a classical computer as Kreep suggests, but I am sure people think about such things.
I am not aware of crypto systems based on NP complete problems. Even these might turn out to be breakable, if P=NP or if P=NP when you have a quantum computer. If anyone knows of a crypto system based on an NP complete problem (rather than just one that is NP hard) I'd like to take a look at it.
Nearly all the papers in the field come out first on the web at quant-phys.
Slashdot Mirror
I don't usually nitpick spelling of posters, but when the slashdot article itself spells weird as "wierd" I have to wonder if there exist any good spell-checkers for linux. I use ispell.
Hey, that's not fair! We academics know there is a denial of service attack and that it's a problem. At least some of us do. There are situations where it isn't that bad though. If a company is communicating with a branch office through a fiber and the denial of service happens, you just send the police out to see who dug up your fiber. Problem solved.
Fortunately, secure authentication schemes exist even without quantum mechanics. For example, suppose you and I each already have a 20 bit key. I just ask you what it is and if you can tell me I know it was you. Obviously this is secure (up to a one in a million chance). Of course, there are two unavoidable problems with this. One, you may have handed over your key to someone else at gunpoint. Two, we'd better not use that same key again because Eve could have listened to it.
Problem one cannot be solved. Problem two is solved by not reusing the key, but instead using new key that we exchange using the quantum key distribution. This makes denial of service attacks particulary annoying, since if we have to wait and try again later we'd better authenticate again using a new key and we might run out before we get to use quantum key exchange to make some more. Doh!
The real situation is more complicated than this because I don't need to juse verify that I am talking to you at the start of the conversation, but rather must authenticate each bit of our conversation, without using up more key than we can get back by the quantum key distribution. This is also possible with a little more complexity.
Quantum computers do solve discrete log.
Also, factoring becomes polynomial time,
but not (necessarily) linear.
As for Grover's algorithm being optimal: It is optimal for finding a single marked item in a list of N elements, which it does in square root of N time. But an NP problem may have more structure than simply being a random element in a list. So I believe the jury is still out on if quantum computers can solve NP-complete problems in polynomial time.
John
Polynomial problems are said to be in NP since they are a subset of NP, so it is not right to say factoring is not in NP, since all polynomial problems are "in" NP. There are also problems that are NP hard but not NP complete, meaning they are harder than polynomial, but that a fast solution to one of them doesn't solve all other NP problems.
Factoring is known to NOT be NP-complete.
Factoring might be NP hard, or might be polynomial.
P might be the same as NP.
So fast factoring on a quantum computer doesn't mean all NP problems are easy.
It is not known if quantum computers can solve NP complete problems in polynomial time. Most people doubt it.
Computer scientists certainly are working to try to understand the new complexity classes which result from the presence of quantum computers. I'm not quite sure if they have a class which is NP hard to a quantum computer, but even harder to a classical computer as Kreep suggests, but I am sure people think about such things.
I am not aware of crypto systems based on NP complete problems. Even these might turn out to be breakable, if P=NP or if P=NP when you have a quantum computer. If anyone knows of a crypto system based on an NP complete problem (rather than just one that is NP hard) I'd like to take a look at it.
Nearly all the papers in the field come out first on the web at quant-phys.
John