Follow Slashdot blog updates by subscribing to our blog RSS feed

 



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 Tim C (15259) on Wednesday March 16, 2011 @09: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 Tava (31002) on Wednesday March 16, 2011 @09: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.

Economists state their GNP growth projections to the nearest tenth of a percentage point to prove they have a sense of humor. -- Edgar R. Fiedler

Working...