Slashdot Mirror

← Back to Stories (view on slashdot.org)

Code-Breaking Quantum Algorithm On a Silicon Chip

Posted by Soulskill on 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."

5 of 133 comments (clear)

  1. Interesting and a qustion by doublebackslash · · Score: 5, Interesting

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

    --
    md5sum /boot/vmlinuz
    d41d8cd98f00b204e9800998ecf8427e /boot/vmlinuz
    1. Re:Interesting and a qustion by doublebackslash · · Score: 5, Interesting

      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.

      --
      md5sum /boot/vmlinuz
      d41d8cd98f00b204e9800998ecf8427e /boot/vmlinuz
    2. Re:Interesting and a qustion by Captain+Segfault · · Score: 5, Interesting

      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.

    3. Re:Interesting and a qustion by wurp · · Score: 3, Interesting

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

  2. Re:Is this really a big deal? by Hal_Porter · · Score: 3, Interesting

    http://en.wikipedia.org/wiki/Ultra#Battle_of_the_Atlantic

    It is commonly claimed that breaking of German Naval Enigma shortened the war by a year, but given its effects on the Second Battle of the Atlantic alone, that might be an underestimate.

    An exhibit in 2003 on "Secret War" at the Imperial War Museum, in London, quoted British Prime Minister Winston Churchill telling King George VI, "It was thanks to Ultra that we won the war." Churchill's greatest fear, even after Hitler had suspended Operation Sealion and invaded the Soviet Union, was that the German submarine wolf packs would succeed in strangling sea-locked Britain. He would later write, in Their Finest Hour (1949), "The only thing that ever really frightened me during the war was the U-boat peril." A major factor that averted Britain's defeat in the Battle of the Atlantic was her regained mastery of Naval Enigma decryption.

    --
    echo -e 'global _start\n _start:\n mov eax, 2\n int 80h\n jmp _start' > a.asm; nasm a.asm -f elf; ld a.o -o a;