Forgot your password?
typodupeerror
Security Science Technology

Code-Breaking Quantum Algorithm On a Silicon Chip 133

Posted by Soulskill
from the one-small-chip-for-man dept.
Urchin writes "Shor's quantum algorithm, which offers a way to crack the commonly-used RSA encryption algorithm, has been demonstrated on a silicon chip for the first time. The algorithm was first demonstrated on large tabletop arrays 3 years ago, but the photonic quantum circuit can now be printed relatively easily onto a silicon chip just 26 mm long. You can see the abstract from the team's academic paper in the journal Science; the full text requires a subscription."
This discussion has been archived. No new comments can be posted.

Code-Breaking Quantum Algorithm On a Silicon Chip

Comments Filter:
  • by doublebackslash (702979) <doublebackslash@gmail.com> on Friday September 04, 2009 @08:18PM (#29319311)
    So, this is really impressive. I'd also like to know how many (useful, as opposed to error checking) qbits they can manipulate in total using this technique, and traditional techniques, for that matter. Those are the big limiting factors in this technique's use.

    Side question: Which asymmetrical encryption algorithms are safe(er) against quantum algorithms (Some algorithms do not benefit from a tremendous quantum speedup, only a large one)?
    • by Trepidity (597) <delirium-slashdo ... org minus author> on Friday September 04, 2009 @08:33PM (#29319421)

      Currently, they and the traditional techniques can each manipulate 4 non-error-checking qubits. =]

      The article argues that their approach is more promising for scaling up, though, and has fewer inherent limits to doing so. That of course is still to be demonstrated, but the result still seems interesting--- basically, here's proof-of-concept of a new method that at least works as well as previous methods, along with some reasons to believe it might scale up better.

    • by Brian Gordon (987471) on Friday September 04, 2009 @08:33PM (#29319431)

      My guess is that miniaturizing a optical processor into silicon is probably going to be less powerful than normal optical processors. They should be factoring numbers larger than 15 before trying to fit it on a chip.

      Quantum computing is extraordinarily difficult though, even just in theory, so I guess I understand why its development is so slow.

      I wonder what the curve is for how much education you need to be terrified of the Shor's algorithm article rather than just mystified, and then how much more you need to master it. I'm deep into nightmare territory.

      • by doublebackslash (702979) <doublebackslash@gmail.com> on Friday September 04, 2009 @08:59PM (#29319661)
        As far as being terrified by it, that's fairly easy.

        I'm a bit of a crypto nerd (more of a fan, not exactly up to sratch on designing the algorithms, but I've read EXTENSIVELY on their proper use) and if you get a large quantum computer working, things go titsup for any of our currently viable public key crypto schemes. The short of it is this: you can no longer trust any key exchange system that relies on public keys. SSH is no longer secure, SSL is trash, the list goes on. Any time you need to exchange secure data without having previously encountered the far end securely first, game over.

        That's frightening. I know that there are some proposed algorithms that only allow for a polynomial speedup in quantum computers, but I couldn't find them between when I posted initially and now.

        So yeah, fear it, but in terms of cracking larger numbers this is not even a proverbial "smoke in the building" scenario. It looks like their technique does not employ error checking, making large numbers of qbits near impossible to work with.
        • by maxume (22995) on Friday September 04, 2009 @09:27PM (#29319849)

          It's only frightening when operating a quantum computer becomes trivial. Until then, it really isn't that big a deal to send your credit card details to Amazon.com. So when there are 5 powerful quantum computers running, there will probably still be a year or two to fix things. Even then, I'm not sure people will be running quantum computers against the vast majority of communication (so it really only sucks for the people who are trying to secure something worth getting at, us gmail https users aren't out much).

          • by SpazmodeusG (1334705) on Saturday September 05, 2009 @12:28AM (#29320779)
            No it is frightening now if you transmit anything that still has to be secret in the future. After all someone might simply record both sides of the encrypted conversation now for later reference.
            This is why government agencies want secure quantum links now. As even though there is no way for someone to decrypt their plans right now there's still a chance of the plans getting out once quantum computers do come about.

            I have a feeling a lot of criminals will find themselves being arrested for past crimes once quantum computers do come about as all their past recorded conversations, no matter how encrypted, suddenly become decryptable.
            • It's a certainty that various large nation's defense/intelligence agencies have been pushing the boundaries of QC as applied to breaking crypto, far far beyond what's been published (and not just from accelerated science, but from effective censorship/buying research.) It's also a safe assumption for each of these countries that other nations have similar programs. I don't have any insider knowledge, it's just human nature that such things are inevitable.

            • by ultranova (717540)

              I have a feeling a lot of innocent people will find themselves being arrested for past communication their government or some big corporation disapproves of once quantum computers do come about as all their past recorded conversations, no matter how encrypted, suddenly become decryptable.

              Fixed that for you.

              It's frightening how corporations and governments seem to be in a race to see who can cause the most harm in the least amount of time. Breaking secure communications at this point in history is a very wo

          • Re: (Score:3, Interesting)

            by mark-t (151149)

            It's only frightening when operating a quantum computer becomes trivial.

            So not anytime soon... the refrigeration units required to produce the temperatures at which quantum computing is viable are not likely to be within a typical consumer's budget (or likely to fit in their apartment, for that matter) for the forseeable future.

          • by raftpeople (844215) on Saturday September 05, 2009 @02:31AM (#29321299)
            It's only frightening when operating a quantum computer becomes trivial.

            "Congratulations on your purchase. To begin using your quantum computer, set the power switch to both off and on simultaneously."
            • "Congratulations on your purchase. To begin using your quantum computer, set the power switch to both off and on simultaneously."

              More like, "Your computer may appear to be both on and off at the same time. Don't worry, this is normal. To turn the computer off, you don't have to do anything. Likewise, to turn it on, you don't have to do anything."

        • by epee1221 (873140)

          The short of it is this: you can no longer trust any key exchange system that relies on public keys.

          So does quantum computing get us discrete logs too?

          • by blueg3 (192743)

            Yes, also using Shor's algorithm.

          • Re: (Score:3, Informative)

            A very insightful question. Mod parent up.

            In short, yes: Wiki [wikipedia.org] see also (with more math than I can handle) Berkley article [74.125.95.132]

            So, yeah. Quantum computers of reasonable size get us discrete logarithms. This means that the Diffie Hellman key exchange can be reversed after the exchange if the attacker has a powerful enough quantum computer. The computer to break DH key exchanges would be powerful enough to also break the encapsulating RSA or similar exchange (even assuming RSA encryption AND signatures was
        • If quantum physics will be the undoing of public key cryptography, perhaps quantum physics can give us a means to communicate securely with our bank.

          Imagine it's maybe 10 years from now and every major city has a "quantum wire" to other major cities within a few hundred kilometers. This means if I'm in New York I can send a secure message to Washington, D. C. or Chicago.

          Granted, at first sending such secure messages won't be cheap, and sending them long distances will require relays by trusted intermediari

          • A very fine point you make about trusted intermediaries. Quantum key exchange only works 'point to point' not 'end to end' that means that for every link in the chain there is a weak point to be exploited. That is unacceptable for some uses and users.

            The wiki article has really good information, but please research this in depth (learn the lingo, do some google searches if you want to know more) [wikipedia.org] http://en.wikipedia.org/wiki/Quantum_cryptography [wikipedia.org] .

            Good insights Davidwr, but I hope we can come up with
          • by mlts (1038732) *

            All you need is a link fast enough to transmit the key for bulk encryption, then dump the rest of the data via a normal pipe encrypted via either AES, or a cascade [1]. Quantum computers are not useful against symmetric encryption such as DES, AES, Serpent, or IDEA.

            [1]: If you have two algorithms each 256 bit, cascading them only gives you 257 bit security (256 + 256), but the reason one would do this is to deal with a possible algorithm breakage of either algorithm. Say some algorithm that is 256 bits i

            • [1]: If you have two algorithms each 256 bit, cascading them only gives you 257 bit security (256 + 256)

              I think this is wrong. If you use the same key for both then it's still just 256 bit. If you use different keys then that's 2^256 * 2^256 giving you 512 bit. Right?

              • by mlts (1038732) *

                In a perfect world, you would have 512 bit security provided you used different keys for both cyphers. However, there are a number of attacks like birthday and meet in the middle attacks which would reduce the effective amount of bits from 512 down, such as how double-DES is pointless instead of triple DES. They may not be as effective because of the use of two different algorithms, but they may be possible.

                If the attacker knows anything about the text between the two algorithms, the 512 bits drops to 257

        • by wurp (51446) on Saturday September 05, 2009 @01:18AM (#29321005) Homepage

          As far as I know, the "only" crypto applications of QC that would give an exponential speed-up are for factoring (Shor's algorithm). I realize that that's essentially all currently used asymmetric (public/private key) encryption, but afaik elliptical encryption, which is also usable for asymmetric encryption, isn't impacted.

          Of course, no one knows if elliptical encryption will fall to some quantum algorithm, and you can always get a O^0.5 speed up using Grover's algorithm, but O^0.5 just requires double the key length rather than making encryption impractical.

          Scott Aaronson [scottaaronson.com], a quantum algorithm complexity researcher at MIT, believes that quantum computing does not in general give an exponential speed-up to algorithms, and I believe him...

          • afaik elliptical encryption, which is also usable for asymmetric encryption, isn't impacted.

            It is impacted. There are also quantum algorithms to break elliptic curve cryptography.
            See, e.g., http://arxiv.org/abs/quant-ph/0301141 [arxiv.org]

            • by wurp (51446)

              Bummer. Thanks for the info!

              This is the danger of QC to crypto - it's still so new. No one knows if factoring can be done in polynomial time using classical algorithms, but we know people have been trying forever and failing. I don't think we even have a good handle on what is hard with QC and what's not. There are lots of other asymmetric algorithms (unfortunately none that I know of that have anywhere near the kind of analysis that's been applied to factoring), but who knows if QC will make inverting

        • I wasn't talking about being terrified of the ramifications of QC. I was talking about being terrified of the math.

      • Re: (Score:2, Informative)

        My guess is that miniaturizing a optical processor into silicon is probably going to be less powerful than normal optical processors.

        The power of a quantum computer, at this early stage, is limited by the number of qbits. The point of putting it onto silicon is that silicon fabrication is the easiest way, right now, to make large numbers of interesting small structures. (in this case qbits and controlling infrastructure)

      • by mikael (484)

        They have two directions to go in; (1) make the hardware smaller and more compact, and (2) make the hardware support huge integers. Getting a quantum processing unit into a single chip proves that it can be done. They will follow the path of CPU's and GPU's: move all the way from 4-bit computing to 64-bits and beyond.

        • There is a limitation that quantum computing has to deal with that normal computing does not. That is the problem of decoherence. Think of it as noise, but worse. Quantum computers need to operate on all of their bits at the same time. This introduces problems once you scale up, since you can't just compartmentalize the problem. You have to add error correction, but that adds more complexity, and therefore more bits. It starts to spiral out of control very quickly.

          So, though we jump to higher per operati
    • by Dc0der (783811) on Friday September 04, 2009 @08:57PM (#29319651)
      There are a few algorithms resistant against quantum computers, based on alternative problems. A good reference of the main, usable ones, is at http://pqcrypto.org/ [pqcrypto.org]. Quantum computers can also speed up exhaustive searches (see Grover's algorithm) and collision searches, but this is easily mitigated by increasing symmetric key sizes to e.g. 256 bits up from 128.
      • by JordanL (886154) <jordan.ledoux@nospAM.gmail.com> on Friday September 04, 2009 @09:12PM (#29319749) Homepage
        I think the real question is whether or not quantum computing can solve the Travelling Salesman problem. :)
        • by Captain Segfault (686912) on Friday September 04, 2009 @09:37PM (#29319917) Homepage Journal

          I think the real question is whether or not quantum computing can solve the Travelling Salesman problem.

          It can not.

          There is no reason to believe QBP contains NP. (We might be wrong, but then we might be wrong about P != NP!)

          Any approach along the lines of "do everything quantumly in parallel and somehow select the interesting results" will do no better than a Grover search, which is a quadratic speedup.

          • by wurp (51446)

            Any approach along the lines of "do everything quantumly in parallel and somehow select the interesting results" will do no better than a Grover search, which is a quadratic speedup.

            I agree with the sentiment, but this bold statement is just not true. The Deutch-Jozsa algorithm [wikipedia.org] solves a problem which is provably O(e^n) using the best classical algorithm in O(1) with a quantum algorithm (in fact, in one step).

        • Normal computers can solve it, just not efficiently!

        • Re: (Score:2, Interesting)

          by mckinleyn (1288586)
          With a 6-digit UID, I'm sure you know this, but for those who might not have taken a university level computing class (or who took one a long time ago), I'm going to elaborate briefly on your post.

          Problems like factoring products of primes (This is a big deal in crypto, but the explanation of why is hard if you haven't taken a university number theory course) and the above-mentioned Traveling Salesman Problem (The question of how I can most efficiently reach each of a given set of points, after given fix
          • I read something recently that claimed that factoring the products of primes is non-polynomial but it may or may not be NP-complete. In other words, it might be slightly easier than the traveling salesman problem. By "slightly" I mean only that just because you can factor products of primes doesn't mean you can do the traveling salesman problem.

            • by Trepidity (597) <delirium-slashdo ... org minus author> on Saturday September 05, 2009 @12:29AM (#29320781)

              You're right, it isn't currently known either way.

              To review briefly,

              P problems are those solvable in polynomial time on a regular computer.

              NP problems are (one definition) those verifiable in polynomial time on regular computers. That is, if you gave the answer to the problem, in polynomial time I could tell you if it was the correct one.

              QBP problems are those solvable in polynomial time on a quantum computer.

              It is not known whether any of these classes are equivalent. However, the possibilities are constrained by,

              NP-complete, which are problems in NP to which all other NP problems can be reduced (provably!) in polynomial time.

              Traveling salesman is NP-complete. Therefore, if we found a polynomial-time algorithm on regular computers, P = NP. If we found a polynomial-time algorithm on quantum computers, QBP = NP.

              Integer factorization is in NP, but not known to be either NP-complete or in P. Therefore, a polynomial-time algorithm on regular computers could exist without P = NP--- but we don't know of one. Shor's algorithm (the subject of this article) is a polynomial-time algorithm for quantum computers, so integer factorization is in QBP. However, since integer factorization isn't NP-complete, this doesn't have any implications for whether QBP = NP or not.

              So it's not provably known that integer factorization is easier than traveling salesman on any kind of computer. But on quantum computers, the fastest known integer factorization algorithm is polynomial, while the only way we could do that for traveling salesman is if QBP = NP. On regular computers, no polynomial algorithm is known for either problem. But in a sense it'd be more surprising if one were found for traveling salesman, because that would imply P = NP... while finding one for integer factorization wouldn't have such wide-ranging implications on other problems (though it might have implications for other not-yet-known-to-be-in-P problems, if the technique were transferable).

          • Factoring primes is not NP-complete. just NP and EXP. See http://en.wikipedia.org/wiki/List_of_NP-complete_problems [wikipedia.org]
        • by ultranova (717540)

          I think the real question is whether or not quantum computing can solve the Travelling Salesman problem. :)

          Assuming that quantum computer is Turing complete, of course it can: simply enumerate every route and keep track of which is the shortest this far, and at the end of the enumeration you have the shortest one. Now, whether a quantum computer (or a normal computer, for that matter) can do this in a faster time than O(n!), that's the question.

      • THANK YOU!

        That link was exactly what I was looking for.
        Really thank you.
  • by Vadim Makarov (529622) <makarov@vad1.com> on Friday September 04, 2009 @08:18PM (#29319313) Homepage
    they are still factorizing the number 15 :)
  • How many qubits? (Score:3, Informative)

    by zapakh (1256518) on Friday September 04, 2009 @08:20PM (#29319325)
    The IBM test-tube quantum computer from a while back used the spins of several atoms in a specially-crafted molecule as qubits. This one is "an integrated waveguide silica-on-silicon chip that guides four single-photon qubits through the computation". Does this approach scale better to larger numbers of qubits than do designer molecules?
    • by Trepidity (597) <delirium-slashdo ... org minus author> on Friday September 04, 2009 @08:30PM (#29319403)

      That's their claim. The full version of the article says of previous implementations, "these approaches cannot be scaled to a large number of qubits because of purity, size, and stability limitations of these systems". And of theirs: "Although it currently uses an inefficient single photon source and modest efficiency detectors, ongoing progress to address heralded gates and efficient sources and detectors combined with the results presented here will allow large-scale quantum circuits on many qubits to be implemented".

  • MIM day (Score:5, Funny)

    by youn (1516637) on Friday September 04, 2009 @08:21PM (#29319329) Homepage

    shortly after, secret service agencies worldwide have decided to make the day a holiday and call it man in the middle day (MIM)

  • by JackSpratts (660957) on Friday September 04, 2009 @08:23PM (#29319345) Homepage
    my darknet effectively utilities rsa/blowfish. not for long apparently.
    • by BungaDunga (801391) on Friday September 04, 2009 @08:36PM (#29319473)

      Unless you're using 3 and 5 for your factors, I think you're safe for now...

    • by DoofusOfDeath (636671) on Friday September 04, 2009 @09:32PM (#29319887)

      my darknet effectively utilities rsa/blowfish. not for long apparently.

      No worries. We'll change it for you, Steve O'Connel from 42 Elmwood Ave., Chicago. You should take the night off - you're girlfriend will be ordering out for burritos. Bad news though, she's renting a chick flick.

      Thanks,
      NSA

      • He's a girlfriend named Steve? That is really bad news... ;P

      • by Al Dimond (792444)

        There is no Elmwood Ave. in Chicago, and anyway, all Chicago addresses need a directional prefix. There are Elmwood Aves. in Evanston and Oak Park; for the latter you'll also need a directional prefix.

        Thanks,
        Richard M. Daley, Mayor

        • Re: (Score:3, Funny)

          by Ant P. (974313)

          That's the problem with these quantum computers - you can't be certain which universe they're decrypting data from.

    • My darknet is truly dark. It's also very energy efficient, drawing zero watts from the mains. Unfortunately, it's hard to use since it's so dark. But it is quiet, and it runs cool.

      I must admit though, it is of limited practical value. It's utility seems limited to providing a flat surface for me to rest books on. Books I can't read because it's so dark.

  • by Anonymous Coward

    ...in more human-understandable terms?

    Here's my understanding of it, which is probably wrong but I'd love some clarification-- basically one benefit of a quantum computer is that it allows you to factor gigantic numbers into component primes super-fast. So for example, those distributed computing contests where you'd crack RSA keys by searching a keyspace in 10 years or 50 or 50 million years or whatever goes out the window, because a quantum computer can find all possible primes simultaneously rather than

    • Re: (Score:1, Insightful)

      by Anonymous Coward

      Quantum Entanglement isn't some esoteric, exotic process we can only observe in a laboratory, it pervades the universe continuously. Most of the particles in your body are probably entangled with most of the particles in your keyboard right now.

      We don't need rare materials and expensive equipment, entanglement sortof just happens on its own. The tricky part is shielding them from what's called decoherence: The qubits we're trying to do computations with tend to want to become entangled with particles that a

      • But.. if you're right, then that would imply that there are a zillion different "clones" of myself running around in different "branches" of the universe.

        I don't want to believe that, so I'm going to invent a spontaneous collapse of the wavefunction that prevents it. Maybe caused by humans observing it.. yeah, that's the ticket.

  • They're still pretty far from being able to do this at a scale practical for breaking RSA... ...but when scientists have reached the scale for breaking RSA, are there quantum algorithms that would work for breaking ECC? What about D-H? Are there any public key schemes that will still work when quantum computing is available?

    It doesn't really matter to me whether it'll only ever be practical for labs to break - the government can afford that kind of muscle. If it's physically possible, they'll be able to

    • Re:What about ECC? (Score:4, Informative)

      by Anonymous Coward on Friday September 04, 2009 @08:46PM (#29319545)

      All Discrete-Logarithm and Factoring based public key algorithms are vulnerable.

      THe current known safe alternatives are hash-based (Merkle), code based (e.g. McEliece), lattice based (NTRU) or multivariate equation based (HFE). All of them have quite the disadvantages and comparatively less research on them.

      • Re: (Score:3, Insightful)

        by Stile 65 (722451)

        Sweet, thanks for the awesome pointers. You've given me a whole lot of stuff to look over as a research starting point.

    • by mysidia (191772)

      For all we know, they've already done it, have an army of massive fully operational quantum computers, and are laughing real hard right now at private researchers trying to catch up.

    • ECC's hardness is based upon a generalization of discrete log to elliptic curves.

      The same algorithm that breaks discrete log on integers mod N breaks the elliptic curve generalization.

  • ....welcome our new all-sharing open society based on freely sharing information, technology, knowledge, and of course funding. The complete dissolution of the banking, monetary, privacy, security, and authentication systems forced on us by our repressive secret society will finally be over! -- or they'll just have to move to some prime numbers other than 3 and 5. Whichever.

  • Does anyone know if there is any practical and non-quantum
    ENCRYPTION method that is potentially safe from quantum
    cryptanalysis?

    Are one-time pads (assuming they could be copied around safely)
    proof against these techniques?

    • Well, a truly random 1-time pad that is used properly and never compromised is mathematically unbreakable.

      PRACTICAL one-time pads suffer two vulnerabilities: 1) If stored in the clear or encrypted with a defeatable algorithm, they can be compromised, and 2) if re-used they can be compromised. They are useful for sharing small amounts of data, such as passphrases.

      One way to make one-time pads more practical for certain applications is to use shortcuts to describe the pads. For example, if you and I both c

      • by mikeee (137160)

        Well, that's just a book cypher, though, and is plausibly crackable (I'd maybe gzip it first and then work from that, but it's still not random); it's only a 1-time pad if your pad is *RANDOM*. And really, really random, not pseudo-random, or randomish.

    • The short answer is "It depends". It depends on what features you want. (Some crypto systems provide security but not authentication. Others do the opposite. Still others provide neither but give plausible deny-ability or even it's opposite, non-reputability.) It depends on what resources you have. (Do you have couriers to hand deliver your new keys?)

      The reason quantum is scary is because it breaks a large number of public key systems. Public-key systems have been the most economical systems developed

    • by kasperd (592156)

      Does anyone know if there is any practical and non-quantum ENCRYPTION method that is potentially safe from quantum cryptanalysis?

      There is research going on in that area. I haven't been following it, but I know about one article that touches the subject. I haven't read the article, but if you are interested in that kind of stuff, you could read it and tell us what you think. http://eprint.iacr.org/2009/391.pdf [iacr.org]

      Are one-time pads (assuming they could be copied around safely) proof against these techniques?

      They

    • Any private-key encryption, of which OTPs are an example, don't have much to worry about from quantum computing at this time. The problem is that private-key exchange is hard to do between two entities who are unknown to each other.
  • Amazing (Score:1, Funny)

    by jfern (115937)

    15=3*5, just like 8 years ago when it was last factored on a quantum computer. Maybe in a few years someone will factor 21. I wonder what its factors are.

    • Well, it's always valuable to re-test basic truths. After all, imagine the equation 15=3*5 would stop to be true. It would completely change our world view!

    • by martas (1439879)

      Maybe in a few years someone will factor 21. I wonder what its factors are.

      I think a few years ago someone proved that 21's factors are between 1 and 20... Can't find the article, though.

      • by Trouvist (958280)
        Actually, I read somewhere that we know, with 100% certainty, that ONE of the factors is BELOW the square root of 21, so, roughly between 1 and 5. That means the OTHER factor can be anywhere between 5 and 21! You only have to find half!
  • I'm so glad these research publications are made widely available to all... err...

  • It's not the end of the world: Public key cryptography has been around for only a few decades. Before then (even after the invention of the somewhat impractical one-time pad) the winner (cryptographer or cryptanalyst) was determined by who had more computing power and the more ingenuous ideas.

    Basic statistics were death to the ROT13 and the Caesar shift, digital computers were death to Enigma, and now quantum computing will be death to assymetric keys that depend on non-polynomial prime factorization. We'll

  • what's the deal with 2048 bits keys?? 6 bits seems fine for the next 10 years at least
  • Any past or future communication is known to this theoretical quantum future, and so all sinners are known, as are their communications. Since we must also assume that the brain will be profoundly understood and its language decoded this too will become interceptable and interpretable. Therefore all your thoughts past and future will be known to those with the proper computing and communications devices. Since our brains will be jacked into the networks this would seem to present a problem. But since we w
  • This is the theme for the movie Sneakers: http://www.imdb.com/title/tt0105435/ [imdb.com]

"All my life I wanted to be someone; I guess I should have been more specific." -- Jane Wagner

Working...