Beta

Slashdot: News for Nerds

×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Physicists Develop Quantum Public Key Encryption

CmdrTaco posted more than 3 years ago | from the with-the-power-of-atoms dept.

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."

cancel ×

45 comments

Um (1)

Toe, The (545098) | more than 3 years ago | (#35503616)

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? (4, Informative)

Tim C (15259) | more than 3 years ago | (#35503634)

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:Did even the submittor read the summary? (1)

bondsbw (888959) | more than 3 years ago | (#35503764)

So /. posts a story with content from the actual article, and you complain?

So harsh...

Re:Did even the submittor read the summary? (1)

stardaemon (834177) | more than 3 years ago | (#35503952)

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:Did even the submittor read the summary? (2)

Tim C (15259) | more than 3 years ago | (#35504012)

Heh - I'm complaining that the headline is sensationalist and not representative of the actual story.

Re:Did even the submittor read the summary? (1)

Kilrah_il (1692978) | more than 3 years ago | (#35514098)

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:Did even the submittor read the summary? (0)

Anonymous Coward | more than 3 years ago | (#35504200)

You were probably kidding, but editing should improve the article summary/title, not make it just as shitty or worse every time.

Re:Did even the submittor read the summary? (1)

Anonymous Coward | more than 3 years ago | (#35504174)

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 (3, Funny)

dakkon1024 (691790) | more than 3 years ago | (#35503684)

This seems nearly identical to the communication system my wife uses.

Re:Old news (0)

Anonymous Coward | more than 3 years ago | (#35504050)

If you don't have your wife's private key, you're doing it wrong.

Re:Old news (1)

Kilrah_il (1692978) | more than 3 years ago | (#35514108)

That's what I call Quantum Entanglement. Good luck, buddy.

Hmmm... (-1)

Anonymous Coward | more than 3 years ago | (#35503696)

Could this be used in some way to help fix CmdrTaco's micropeen? God I can't imagine how he could ever have sex with his wife when you combine that lard gut we saw yesterday with a 2mm fully erect penis. No wonder he has to be a bottom when he hangs out in the gay bathhouses and his wife is constantly sleeping around.

Short on details... (1)

siwelwerd (869956) | more than 3 years ago | (#35503726)

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 [arxiv.org]

Tag (0)

Grizzley9 (1407005) | more than 3 years ago | (#35503750)

Are slashdots tags meaningless? It seems there is always one that says "story". Is that even remotely useful?

Re:Tag (2)

snookerhog (1835110) | more than 3 years ago | (#35503840)

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:Tag (1)

Desler (1608317) | more than 3 years ago | (#35503852)

Yes, that "story" tag has been automatically added for quite some time. You just now noticed that?

Re:Tag (0)

Anonymous Coward | more than 3 years ago | (#35504000)

No, he just now asked about it.

Re:Tag (1)

gd2shoe (747932) | more than 3 years ago | (#35512330)

If I remember correctly, it's for running searches in the firehose. Articles that have been chosen and opened for comment are tagged "story" (I think others are tagged "submission"). There's an example in the help section somewhere that explains how to use it.

graph isomorphism is not hard! (4, Informative)

Tava (31002) | more than 3 years ago | (#35503788)

"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:graph isomorphism is not hard! (-1)

Anonymous Coward | more than 3 years ago | (#35504318)

Damned academics, and you had the gaul to cite Erdos, who probably actually understood the problem. Take it from someone with the common sense not to waste time on schooling... (I took courses-- just didn't waste my time)

To my knowledge there exists *NO* public key cryptosystem that is known to be NP complete.

Now, as you damned well should be aware--isomorphism is in NP. Period. Any counterexample algorithm you can cite only solves special cases--not the general one. Those special cases turn up surprisingly frequently in real world data.

The outright proof or rejection of many PKI schemes would either separate, or collapse P from NP.

But thanks for playing technobabble.

    "It is not known to be NP Complete either" Yeah shithead, you let me know when you find PKI that is so we can claim the millenium prize...

And of course, then there's your special "Expected polynomial time". Yeah, I saw the one that used infinite memory to do it. But of course, most expected algorithms are expected over the set of all possible ... whatever. It's kind of like saying the expected time to find a factor of a number is constant across the set of naturals (test for divisibility by two).

Just because some twit publishes it in a paper and it's factually true doesn't make that expected value practical in any sort of useful situation.

Re:graph isomorphism is not hard! (2)

Ambiguous Coward (205751) | more than 3 years ago | (#35504536)

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:graph isomorphism is not hard! (1)

sydneyfong (410107) | more than 3 years ago | (#35505452)

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:graph isomorphism is not hard! (0)

Anonymous Coward | more than 3 years ago | (#35505502)

Hahaha, you write like you know it and you are obnoxiously arrogant about it. But you get it wrong nonetheless. Life never gets better than that :)

The outright proof or rejection of many PKI schemes would either separate, or collapse P from NP.
The proof of validity of PKI would separate P from NP.
The rejection of PKI would do nothing, because as you affirmed the known PKI are not based on known NP Complete problems.

-- "It is not known to be NP Complete either" Yeah shithead, you let me know when you find PKI that is so we can claim the millenium prize...

Finding a PKI that is NP Complete will do nothing of earning the millenium prize, as it doesn't prove P=NP.

But thx for the technobabble, you made my day.

Hahahaha

Re:graph isomorphism is not hard! (2)

Tyler Durden (136036) | more than 3 years ago | (#35506262)

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.

Which, coincidentally is the exact same situation for integer factorization [wikipedia.org] . The current basis for public key encryption.

Re:graph isomorphism is not hard! (1)

Tava (31002) | more than 3 years ago | (#35508314)

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:graph isomorphism is not hard! (1)

Tyler Durden (136036) | more than 3 years ago | (#35508786)

So, if I understand it correctly, "expected polynomial time" is about average running time? That doesn't seem like it would make a difference as long as you pick the "hard" graph isomorphism problems for encryption.

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 to the integer factorization figure you gave (looks close), but it was no picnic dealing with that for my Master's [rit.edu] .

Re:graph isomorphism is not hard! (0)

Anonymous Coward | more than 3 years ago | (#35603880)

Sounds like they developed the photo"graph".
I could easily show you a graph of x = y + 1, and you could look at the graph and quickly solve it in "reverse". However if you were to compare 2 pictures, it would take "considerably longer" to compare.

But I suppose I just oversimplified their oversimplification and am wrong in some way, so take it as a joke I suppose :P

Pie-in-the-sky (0)

Anonymous Coward | more than 3 years ago | (#35503830)

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.

Re:Pie-in-the-sky (1)

TheEyes (1686556) | more than 3 years ago | (#35504220)

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.

Re:Pie-in-the-sky (0)

Anonymous Coward | more than 3 years ago | (#35505072)

The transistor was invented in the 1920s. [wikipedia.org]

so disarmament is our best chance to survive? (-1)

Anonymous Coward | more than 3 years ago | (#35503862)

what are our other options? stop eating/living. looks like #1?

if we stopped shooting etc, we would need FEWER digits to hide all those secrets, so that's good. as for the skeletons; there's not enough digits to hide behind anymore.

ALL MOMMYS GET YOUR BUTTS TO THE MIDDLE EAST, JAPAN, DC, NY, FL, LA,,, WE'RE DYING HERE. do the math. hurry if you can. thanks.

Re:so disarmament is our best chance to survive? (-1)

Anonymous Coward | more than 3 years ago | (#35504788)

If I had a quantum gun I would decrypt your head off.

Quantum Public Key? (1, Funny)

heptapod (243146) | more than 3 years ago | (#35503864)

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:Quantum Public Key? (1)

operagost (62405) | more than 3 years ago | (#35505106)

I don't know, but I'm sure the answer involves using the main deflector.

Re:Quantum Public Key? (0)

Anonymous Coward | more than 3 years ago | (#35505646)

And reversing the polarities. Don't forget to reverse the polarities.

oblig xkcd (0)

FunkyELF (609131) | more than 3 years ago | (#35504354)

Re:oblig xkcd (0)

Anonymous Coward | more than 3 years ago | (#35506478)

It's neither obligatory, nor applicable here.

Virtual xkcd comic (0)

Anonymous Coward | more than 3 years ago | (#35504506)

#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.

Accidents & "Social Engineering" (1)

BoRegardless (721219) | more than 3 years ago | (#35504510)

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:Accidents & "Social Engineering" (1)

PPH (736903) | more than 3 years ago | (#35505008)

or 'lady friend' who manages to get your key

Secure for Slashdotters then.

Re:Accidents & "Social Engineering" (1)

Darinbob (1142669) | more than 3 years ago | (#35506950)

Nonsense. I know plenty of ladies who wish to remain friends only.

Soooo... (0)

DarthVain (724186) | more than 3 years ago | (#35505014)

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 (1)

WaffleMonster (969671) | more than 3 years ago | (#35505436)

"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.

A Quantum Internet (0)

Anonymous Coward | more than 3 years ago | (#35505494)

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.

Wait, wait, wait... (1)

Patman64 (1622643) | more than 3 years ago | (#35506876)

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.

Check for New Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Create a Slashdot Account

Loading...