Forgot your password?
typodupeerror
Encryption Japan Science

Physicists Develop Quantum Public Key Encryption 45

Posted by CmdrTaco
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."
This discussion has been archived. No new comments can be posted.

Physicists Develop Quantum Public Key Encryption

Comments Filter:
  • by Toe, The (545098)

    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.

  • by Tim C (15259) on Wednesday March 16, 2011 @10:27AM (#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)

    • by bondsbw (888959)

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

      So harsh...

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

      • by Tim C (15259)

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

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

    • by Anonymous Coward

      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)

    by dakkon1024 (691790) on Wednesday March 16, 2011 @10:32AM (#35503684)
    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 [arxiv.org]
  • Are slashdots tags meaningless? It seems there is always one that says "story". Is that even remotely useful?
    • 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".

    • by Desler (1608317)

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

    • by gd2shoe (747932)
      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.
  • by Tava (31002) on Wednesday March 16, 2011 @10:42AM (#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.

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

      • by Tava (31002)

        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.

        • 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
  • 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?

  • 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 prom

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

"The value of marriage is not that adults produce children, but that children produce adults." -- Peter De Vries

Working...