Physicists Develop Quantum Public Key Encryption 45
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."
Um (Score:1)
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.
Did even the submittor read the summary? (Score:5, Informative)
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)
Re: (Score:2)
So /. posts a story with content from the actual article, and you complain?
So harsh...
Re: (Score:1)
So /. posts a story with content from the actual article, and you complain?
So harsh...
And herein lies the problem. Here on /. we do not read the articles before commenting on them.
At least it appears to be bad form.
Re: (Score:3)
Heh - I'm complaining that the headline is sensationalist and not representative of the actual story.
Re: (Score:2)
Look at the bright side, you are reading the one site on the entire Internet where "Physicists Develop Quantum Public Key Encryption" could be considered sensationalist. On any other site it would be a sound-pretty-cool headline, at best.
Re: (Score:1)
That kind trivializes the discovery. For all conventional pk crypto's might, it comes to factoring primes. Without the math problem, there is no encryption since decryption become so ridiculously easy. These guys found a math problem that quantum computer won't be good at. This is a pre-req for any kind of encryption scheme involving quantum computers.
Old news (Score:3, Funny)
Re: (Score:2)
That's what I call Quantum Entanglement. Good luck, buddy.
Short on details... (Score:2)
Tag (Score:1)
Re: (Score:3)
It seems there is always one that says "story". Is that even remotely useful?
It is only useful if there is also one that says "garbage".
Re: (Score:1)
Yes, that "story" tag has been automatically added for quite some time. You just now noticed that?
Re: (Score:2)
graph isomorphism is not hard! (Score:4, Informative)
"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.
Re: (Score:3)
Wow, your post might have been interesting or even insightful, but you you write like an asshole and any useful information you may have had was lost in the noise.
Re: (Score:2)
And of course, then there's your special "Expected polynomial time". Yeah, I saw the one that used infinite memory to do it.
You're going to claim the millenium prize by showing us all idiots how to use up infinite memory in expected polynomial time.
Re: (Score:3)
Which, coincidentally is the exact same situation for integer factorization [wikipedia.org]. The current basis for public key encryption.
Re: (Score:1)
No it is not. While integer factorization is not known to be NPcomplete, there is no known expected polynomial time algorithm to solve it (polynomial in the number of digits (not in the magnitude of the integer).
To my knowledge the best result is exp[(1+o(1))sqrt(log n)(sqrt(log log n)], where n in the number to be factorized and consequently log n is the number of digits.
Re: (Score:2)
After all, there are several cases of large integers that are simple to factor. Public key encryption works simply by avoiding them when creating the key.
The current worst-case running-time for graph isomorphism is listed as 2^O(sqrt (n * log n)) in Wikipedia. Not sure how that compares
Re: (Score:2)
And before the transistor was invented in the 1950s I bet everyone thought that widespread computing was pie-in-the-sky. Just because we haven't discovered something yet doesn't mean it's impossible.
Quantum Public Key? (Score:1, Funny)
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?
Re: (Score:1)
oblig xkcd (Score:1)
http://xkcd.com/538/ [xkcd.com]
Accidents & "Social Engineering" (Score:2)
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.
Re: (Score:2)
or 'lady friend' who manages to get your key
Secure for Slashdotters then.
Re: (Score:2)
Nonsense. I know plenty of ladies who wish to remain friends only.
Soooo... (Score:1)
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!
Physicists should just stop (Score:1)
"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 prom
Wait, wait, wait... (Score:1)
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.