Slashdot Mirror
Physicists Develop Quantum Public Key Encryption
KentuckyFC writes "Public key cryptography allows anybody to encrypt a message using a public key but only those with another private key can decrypt the message. That's possible because of certain mathematical functions that are easy to perform in one direction but hard to do in reverse. The most famous example is multiplication. It's easy to multiply two numbers together to get a third but hard to start with the third number and work out its factors. Now Japanese researchers have discovered a quantum problem that is hard to solve in one direction but easy to do in reverse. This asymmetry, they say, could form the basis of a new kind of quantum public key cryptography. Their system is based on the problem of distinguishing between two ensembles of quantum states. This is similar to the problem of determining whether two graphs are identical, ie whether they correspond vertex-for-vertex and edge-for-edge. Increasing the complexity of the graph can always make this problem practically impossible for a quantum computer to solve in a reasonable time. But knowing the structure of a subset of the graph makes this problem easy, so this acts as a kind of private key for decrypting messages."
From the article:
But don't expect to see this any time soon. We'll need a quantum internet first.
Hm. I'll get right on that.
Headline: "Physicists Develop Quantum Public Key Encryption"
Summary: "...This asymmetry, they say, could form the basis of a new kind of quantum public key cryptography."
So, they've not developed quantum public key encryption, they've discovered an effect that could let someone develop it one day.
(Yes, I know that's also the headline of TFA; that's no excuse)
It's official. Most of you are morons.
This seems nearly identical to the communication system my wife uses.
Article is short on details, but at least they include a link to the paper on the arxiv: http://arxiv.org/abs/quant-ph/0403069
Are slashdots tags meaningless? It seems there is always one that says "story". Is that even remotely useful?
"This is similar to the problem of determining whether two graphs are identical".
I think these guys should read: Babai, L., Erdös, P., and Selkow, S.M. Random Graph Isomorphism. In Proceedings of SIAM J. Comput.. 1980, 628-635.
In fact graph isomorphism is a relatively easy problem, while it is not known to be in P, it is not known to be NPcomplete either and is considered to be in a class of its own between the two. Further, it is in general easy as there exist several algorithms that solve it in expected polynomial time. all this without resorting to quantum computation.
You know any story with the words quantum and encryption in the title was going to make the front page, regardless of the fact that 50 years from now I guarantee you we have absolutely nothing like this working in the real world.
Aw man, that's going to be a pain in the ass checking with the recipient of my message if their cat is dead too. Have these scientsists developed any security measures to prevent positron sniffing over entanglement networks?
http://xkcd.com/538/
#1
Bob: with this $10 billion quantum encryption no one will be able to eaves drop on us!
/
Alice: in your face, Eve! Now we can communicate freely!
#2
Eve uses a scissor to cut the line with an evil grin
#3
Bob: "hello? hello?"
/
Alice: "hello? hello?"
Moral of the story: if you spend billions of dollars to communicate your keys securely - your adversary might just op to not let you communicate at all.
Unbreakable key encription is fine, but most "break-ins" seem to be accidental release or finding of a key or your friend or 'lady friend' who manages to get your key some clever subterfuge and access your files.
Maybe the Key exists or maybe not and sometimes the Key both exists and doesn't at the same time depending on observation? I could read the article I suppose.... nah!
"information-theoretically" secure...yawn... yea like how many supposedly "unbreakable" secure quantum crypto systems have already been hacked?
Oh .. thats right... key agreement is not worth a hill of beans unless you can *classically* prove who is on the other end of the fibre.
First and foremost there is no progress of any kind in developing real quantum computers and we still don't even know if it is even possible. "Topological" quantum computers have zero ability to factor huge numbers instantly as promised.
Second there is nothing "quantum" about this algorithm... It seems unappropriate to apply this label at all to a graph searching problem.
The real issue is the security of the keys used to encode and decrypt the data.
If you use quantum qryptography to send the decryption key (public key) to someone, the bizzarre properties allow you to see if someone has been evesdropping in on your communication (thus recieving the public key also), if so you can decide NOT to send the information and to re-encrypt using a different private and public key. Then go through the process again.
But of course you'd need a quantum connection to your ISP, and a quantum internet.
Wouldn't you encrypt your data with the PRIVATE key and whoever you are sending it to would decrypt it with their PUBLIC key? Because if you are sending out your private key, that doesn't seem very private to me.