Code-Breaking Quantum Algorithm On a Silicon Chip

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

Comments

Interesting and a qustion

[doublebackslash]

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

Re:Interesting and a qustion

[Trepidity]

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.

Re:Interesting and a qustion

[Brian Gordon]

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.

Re:Interesting and a qustion

[Dc0der]

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

Re:Interesting and a qustion

[doublebackslash]

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.

Re:Interesting and a qustion

[JordanL]

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

Re:Interesting and a qustion

[maxume]

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

Re:Interesting and a qustion

[Captain Segfault]

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.

Re:Interesting and a qustion

[SpazmodeusG]

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.

MIM day

[youn]

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

Re:Is this really a big deal?

[Trepidity]

They only factored the number 15 here as well--- in fact what they implemented was a version of the algorithm compiled to a specialized implementation for the input "15". Their claim from why it's an improvement is (from the full article):

[P]roof-of-principle demonstrations of Shor's algorithm have so far only been possible with liquid-state nuclear magnetic resonance and bulk optical implementations of simplified logic gates, owing to the need for several logic gates operating on several qubits, even for small-scale compiled versions. However, these approaches cannot be scaled to a large number of qubits because of purity, size, and stability limitations of these systems. We demonstrate a compiled version of Shor's algorithm operating on four qubits in which the processing occurs in a photonic circuit of several one- and two-qubit gates fabricated from integrated optical waveguides on a silica-on-silicon chip.

Essentially they claim that, while their demonstration here is as small-scale as the previous ones, it's at least plausible that it might scale up, while the previous demonstrations have inherent limitations that prevent them from scaling up.

Re:How many qubits?

[Trepidity]

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

Version 2

[epine]

int a = 0, b = 0;
if (x == 14) { a = 2; b = 7; }
else
if (x == 15) { a = 3; b = 5; }
if (a == 0)
    printf ("%s\n", "more funds required");
else
    printf ("%d, %d\n", a, b);

Re:changing of the guard

[BungaDunga]

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

Re:What about ECC?

[Anonymous Coward]

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:changing of the guard

[sakdoctor]

That's the kinda factors an idiot would have on his luggage.

Re:Is this really a big deal?

[Dyinobal]

You really don't understand the impact world wide reliable and fast code breaking has. Cryptology has won wars.

Re:changing of the guard

[DoofusOfDeath]

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

Re:Is this really a big deal?

[FloydTheDroid]

Anything above "4" is represented as "A Suffusion of Yellow"

Re:Is this really a big deal?

[CharlyFoxtrot]

Outside of science fiction novels, where did it do that? If you're thinking of WWII, the Allies had a gigantically larger industrial base than the Axis could ever summon, and basically won by throwing enough men and materiel at the problem. At most, crypto might have shortened that war, but even that's not crystal clear.

Breaking Enigma helped get those men and materiel past the U-boats. If they hadn't D-day wouldn't have happened (and it was almost a failure even with the resource there) and the Germans wouldn't have been caught in a pincer between the allies and the soviets. I wouldn't discount its influence.

Re:Is factoring np-complete?

[Trepidity]

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

Harder than it seems

[raftpeople]

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