Slashdot Mirror

← Back to Stories (view on slashdot.org)

Physicists Develop Quantum Public Key Encryption

Posted by CmdrTaco on from the with-the-power-of-atoms dept.

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

27 of 45 comments (clear)

  1. Um by Toe,+The · · 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.

  2. Did even the submittor read the summary? by Tim+C · · Score: 4, 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)

    --
    It's official. Most of you are morons.
    1. Re:Did even the submittor read the summary? by bondsbw · · Score: 1

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

      So harsh...

      --
      All my liberal friends think I'm a conservative, all my conservative friends think I'm a liberal.
    2. Re:Did even the submittor read the summary? by stardaemon · · 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.

      --
      The only way to stay sane in an insane world, is to be mad yourself...
    3. Re:Did even the submittor read the summary? by Tim+C · · Score: 2

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

      --
      It's official. Most of you are morons.
    4. Re:Did even the submittor read the summary? by Anonymous Coward · · 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.

    5. Re:Did even the submittor read the summary? by Kilrah_il · · Score: 1

      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.

      --
      Whenever in an argument, remember this.
  3. Old news by dakkon1024 · · Score: 3, Funny

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

    1. Re:Old news by Kilrah_il · · Score: 1

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

      --
      Whenever in an argument, remember this.
  4. Short on details... by siwelwerd · · Score: 1

    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

  5. graph isomorphism is not hard! by Tava · · 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.

    1. Re:graph isomorphism is not hard! by Ambiguous+Coward · · Score: 2

      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.

      --
      Their may be a grammatical error, misspeling, or evn a typo in this post.
    2. Re:graph isomorphism is not hard! by sydneyfong · · Score: 1

      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.

      --
      Don't quote me on this.
    3. Re:graph isomorphism is not hard! by Tyler+Durden · · Score: 2

      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. The current basis for public key encryption.

      --
      Happy people make bad consumers.
    4. Re:graph isomorphism is not hard! by Tava · · 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.

    5. Re:graph isomorphism is not hard! by Tyler+Durden · · Score: 1

      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.

      --
      Happy people make bad consumers.
  6. Re:Tag by snookerhog · · Score: 2

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

  7. Re:Tag by Desler · · Score: 1

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

  8. Quantum Public Key? by heptapod · · 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?

    1. Re:Quantum Public Key? by operagost · · Score: 1

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

      --

      Gamingmuseum.com: Give your 3D accelerator a rest.
  9. Re:Pie-in-the-sky by TheEyes · · Score: 1

    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.

  10. Accidents & "Social Engineering" by BoRegardless · · Score: 1

    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.

    1. Re:Accidents & "Social Engineering" by PPH · · Score: 1

      or 'lady friend' who manages to get your key

      Secure for Slashdotters then.

      --
      Have gnu, will travel.
    2. Re:Accidents & "Social Engineering" by Darinbob · · Score: 1

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

  11. Physicists should just stop by WaffleMonster · · 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 promised.

    Second there is nothing "quantum" about this algorithm... It seems unappropriate to apply this label at all to a graph searching problem.

  12. Wait, wait, wait... by Patman64 · · 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.

  13. Re:Tag by gd2shoe · · Score: 1

    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.

    --
    I won't join Slashcott. OTOH, If Beta goes live, I just won't be back until it's fixed. Sorry Dice.