Beta
×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Code-Breaking Quantum Algorithm On a Silicon Chip

Soulskill posted more than 5 years ago | from the one-small-chip-for-man dept.

Security 133

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

Sorry! There are no comments related to the filter you selected.

F1rst (-1, Offtopic)

Anonymous Coward | more than 5 years ago | (#29319229)

We're decrypting your /. too.

Is this really a big deal? (0)

Anonymous Coward | more than 5 years ago | (#29319239)

The last I heard, the largest number ever factored with Shor's algorithm was 15.

Re:Is this really a big deal? (4, Informative)

Trepidity (597) | more than 5 years ago | (#29319343)

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.

Version 2 (5, Funny)

epine (68316) | more than 5 years ago | (#29319419)


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:Version 2 (0)

Anonymous Coward | more than 5 years ago | (#29319943)

Go back and check your code. You forgot something important...

Re:Version 2 (1)

buswolley (591500) | more than 5 years ago | (#29320007)

im game. What?

Superposition? (0)

Anonymous Coward | more than 5 years ago | (#29320049)

I'm no expert in qbits, bit I thought it was supposed to work like this:

int input=15;
start=2;
end=truncate(sqrt(input)); /* =3 */
/* FAIL is a value that says no integer can be found to satisfy the condition */
/* magic qbit stuff goes here */
printf("15=2*FAIL, 15=3*5");

Re:Version 2 (-1, Offtopic)

shelly.green (1631649) | more than 5 years ago | (#29321467)

i can programming when i was in my high school.now i owned my self website http://www.igolfyoo.com/ [igolfyoo.com]

Re:Is this really a big deal? (4, Funny)

FloydTheDroid (1296743) | more than 5 years ago | (#29319945)

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

Re:Is this really a big deal? (0, Offtopic)

moon3 (1530265) | more than 5 years ago | (#29319519)

no deal until it runs crysis and downloads porn in 2s

Re:Is this really a big deal? (4, Informative)

Dyinobal (1427207) | more than 5 years ago | (#29319869)

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

Re:Is this really a big deal? (2, Insightful)

dfetter (2035) | more than 5 years ago | (#29320077)

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.

Re:Is this really a big deal? (4, Insightful)

CharlyFoxtrot (1607527) | more than 5 years ago | (#29320313)

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

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 this really a big deal? (0)

Anonymous Coward | more than 5 years ago | (#29320893)

Not to mention convincing the Japanese to attack the wrong place in order to destroy their fleets in the Pacific...

Can you even imagine the extent to which it would affect an asymmetric war if *either* side was able to accurately predict the movements of the other?

Re:Is this really a big deal? (1)

dfetter (2035) | more than 5 years ago | (#29321265)

Please to recall that the Manhattan Project was originally intended to be used in Europe, and that would have, sooner or later, ended the war. Nothing you've put out here makes me think the Axis might have won in the absence of the crypto stuff.

Re:Is this really a big deal? (1)

TheRaven64 (641858) | more than 5 years ago | (#29322087)

I've read analyses of the German nuclear program that claim that they were between six months and a year away from producing a nuclear bomb by the end of the war. They already had a delivery system, in the form of the V2, that could have hit London. If the USA hadn't had its injection of German scientists after D-Day, it's not at all certain which side would have built the first bomb. Given that they British firebombing of Dresden killed more people than either atomic bomb, it's not a stretch to assume that the Germans would have retaliated by destroying London.

Re:Is this really a big deal? (0)

Anonymous Coward | more than 5 years ago | (#29320329)

Midway Islands, June 1942. What if Yamamoto's plan had worked and he destroyed the US Pacific Fleet's remaining carriers?

Re:Is this really a big deal? (1)

FearForWings (1189605) | more than 5 years ago | (#29321559)

US naval based air-power would have been setback a few years*. Instead of relativity quickly recapturing the outer south pacific islands, we may have moved to further support Australia from threat of invasion, and in their fight in the Pacific. It should be remembered that Japan had been at war for five year prior to the Battle of Midway, and was experiencing shortages of resources and personnel. If Japan hadn't surrendered to the US (in this hypothetical case due a US loss at Midway) it may have faced invasion from the Soviet army, after the fall of Berlin.

*As Adm. Nimitz strongly believed in a carrier based battle group it would seem unlikely that he, or the Admirals in charge of the carriers, would (engage in)/(not disengage from) the battle if the entire carrier fleet was in imminent danger of being sunk; even if this meant sacrificing ships.

Re:Is this really a big deal? (3, Interesting)

Hal_Porter (817932) | more than 5 years ago | (#29320365)

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

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.

Re:Is this really a big deal? (1)

Goat Nutrition (720344) | more than 5 years ago | (#29321607)

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.

Part of the importance of keeping Enigma secret after WWII (up until the late seventies) was that the British circulated Type-X coding machines widely into colonial countries (and the US may have done similar things, I don't know). That enabled GCHQ to run decrypts against a very large number of governments, presumably including those in the post-colonial wars, Suez, etc, although this is (unsurprisingly) not publically well documented. That's a fair number of wars right there.

Even during the earlier stages of WWII, key areas such as North Africa were won with very significant help from decrypts, not to mention the Atlantic. Without that, and assuming that Purple had never been broken either, WWII would have probably ended in 1943. All the "men and materiel" is irrelevant if you're an ocean away from the enemy and can't engage them.

man - this is QUANTUM computing (1)

CFD339 (795926) | more than 5 years ago | (#29319919)

It won't run Crysis and Download generic porn. It will run whatever game you had in mind -- the one that most closely matches your mood -- and it will download porn that exactly fits your personal fetish tastes. Hell, all that's missing is some carbon nanotubes and "free hydrogen" and this could save the world!

Is that quantum computing (1)

davidwr (791652) | more than 5 years ago | (#29320113)

It won't run Crysis and Download generic porn. It will run whatever game you had in mind -- the one that most closely matches your mood -- and it will download porn that exactly fits your personal fetish tastes. Hell, all that's missing is some carbon nanotubes and "free hydrogen" and this could save the world!

Is that quantum computing or my latest acid trip? Sorry, I can't tell the difference.

For any future employer who sees this: The above is a joke post. I've never done LSD and unless a doctor prescribes it, I never will. If taking mind-altering drugs stronger than caffine or Microsoft products is a job requirement please disregard my resume.

Re:Is that quantum computing (0)

Anonymous Coward | more than 5 years ago | (#29321587)

If taking mind-altering drugs stronger than...Microsoft products is a job requirement please disregard my resume.

Good news, we have an opening for a methamphetamine product tester. Though you may experience withdraw symptoms from your previous MS usage.

Re:Is this really a big deal? (1)

marcansoft (727665) | more than 5 years ago | (#29320589)

To put things into perspective, you can factor RSA-384 in a few hours on a decent desktop computer. That's a number like 165375296535705386155571228848957419 6982006687461869497532793906938608837243 5801577531013884898737786797134855942291 (whose factors are 1845911360880639167287667999134101328853184774154263277561 and 8959005293559105489286020014804938358380924734239385853931, by the way). So although the algorithm is much more efficient in theory, they still have quite a ways to go before being an improvement over existing computers :)

wow (-1, Offtopic)

Anonymous Coward | more than 5 years ago | (#29319255)

asd

All your bases (0)

Anonymous Coward | more than 5 years ago | (#29319269)

are belong to us.

But seriously.. now NSA will have to come up with another algorithm that only they have the horsepower to break!

Re:All your bases (1)

mikael (484) | more than 5 years ago | (#29320351)

If arbitary sized integers are capable of being factorized, then it will be "All your primes are belong to us"

Phew (0)

Anonymous Coward | more than 5 years ago | (#29319281)

Although the new chip is only 26 mm long, it has to be surrounded by a whole table top of that equipment.

Not the end of RSA just yet!

Kind of cool that all they need is a way to quickly generate and detect photons though. Neat!

Interesting and a qustion (5, Interesting)

doublebackslash (702979) | more than 5 years ago | (#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)?

Re:Interesting and a qustion (4, Informative)

Trepidity (597) | more than 5 years ago | (#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.

Re:Interesting and a qustion (5, Insightful)

Brian Gordon (987471) | more than 5 years ago | (#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.

Re:Interesting and a qustion (5, Interesting)

doublebackslash (702979) | more than 5 years ago | (#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.

Re:Interesting and a qustion (5, Insightful)

maxume (22995) | more than 5 years ago | (#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).

Re:Interesting and a qustion (4, Informative)

SpazmodeusG (1334705) | more than 5 years ago | (#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.

Re:Interesting and a qustion (1)

PatrickThomson (712694) | more than 5 years ago | (#29322029)

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.

Re:Interesting and a qustion (2, Interesting)

mark-t (151149) | more than 5 years ago | (#29321087)

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.

Harder than it seems (4, Funny)

raftpeople (844215) | more than 5 years ago | (#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."

Re:Harder than it seems (0)

Anonymous Coward | more than 5 years ago | (#29321689)

The issue is whether it is |off>+|on> or |off>+i|on>

Re:Interesting and a qustion (1)

epee1221 (873140) | more than 5 years ago | (#29320019)

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?

Re:Interesting and a qustion (0)

Anonymous Coward | more than 5 years ago | (#29320449)

It gets us factoring in polynomial time, so yes.

Re:Interesting and a qustion (1)

blueg3 (192743) | more than 5 years ago | (#29320937)

Yes, also using Shor's algorithm.

Re:Interesting and a qustion (2, Informative)

doublebackslash (702979) | more than 5 years ago | (#29320949)

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

fight fire with fire (1)

davidwr (791652) | more than 5 years ago | (#29320241)

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 intermediaries, but at least it will work. 20 or 30 years from now you'll be able to send secure data from any city in the world to any other city, and, through trusted intermediaries, from anywhere in the world with a fiber-optic link to anywhere else with a fiber-optic link.

I say "trusted" intermediaries - if you don't trust your intermediaries then you should consider delivering the message in person.

Re:fight fire with fire (1)

doublebackslash (702979) | more than 5 years ago | (#29320969)

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 a system that provides 'end to end' security, since I don't like to trust third parties for security. Too much corruption.

Re:fight fire with fire (1)

mlts (1038732) | more than 5 years ago | (#29321075)

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 is able to be brute forced in 48, and you cascade it with one that hasn't been broken. Your data is still safe.

Re:Interesting and a qustion (3, Interesting)

wurp (51446) | more than 5 years ago | (#29321005)

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

Re:Interesting and a qustion (2, Informative)

Captain Segfault (686912) | more than 5 years ago | (#29319963)

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)

Re:Interesting and a qustion (1)

mikael (484) | more than 5 years ago | (#29320363)

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.

Re:Interesting and a qustion (1)

doublebackslash (702979) | more than 5 years ago | (#29320987)

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 operation bit counts in normal processors very easily, quantum breakthroughs are needed to even go to the next level of quantum computing. Though, if I had to place a bet I'd say it would follow a linear version of moore's law, since you have a qudratic level of complexity added to the problem, canceling out our honored tradition of quadratic computing growth.

Re:Interesting and a qustion (1)

beelsebob (529313) | more than 5 years ago | (#29321687)

Hate to point out to you, but doubling every year is *not* quadratic growth ;)

Re:Interesting and a qustion (0)

Anonymous Coward | more than 5 years ago | (#29322105)

"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..."
Some math knowledge and theoretical background about computing that you get during the first semesters of studying computer science is helpful. I wasn't a good student, but I signed up to participate in a quantum computing seminar and hold a lecture about quantum complexity anyway, because the topic seemed cool, although I had zero knowledge at that point. None of us students had. Took like 2 or 3 weeks from the 'I don't understand anything, I was crazy to sign up for this' to feel comfortable with the matter quantum computing and being able to work through the more difficult papers. After all it was a great experience. Think anyone with some good math education can get into this. It's just getting over the initial shock and being persistent, until you get used to how quantum computing works and have adapted your thinking to it.

Re:Interesting and a qustion (5, Informative)

Dc0der (783811) | more than 5 years ago | (#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.

Re:Interesting and a qustion (4, Funny)

JordanL (886154) | more than 5 years ago | (#29319749)

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

Re:Interesting and a qustion (5, Interesting)

Captain Segfault (686912) | more than 5 years ago | (#29319917)

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 (1)

wurp (51446) | more than 5 years ago | (#29321021)

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

Re:Interesting and a qustion (1)

RiotingPacifist (1228016) | more than 5 years ago | (#29319941)

Normal computers can solve it, just not efficiently!

Re:Interesting and a qustion (2, Interesting)

mckinleyn (1288586) | more than 5 years ago | (#29319983)

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 fixed distances between said points) are what we call np-complete. This means, in short, that the amount of time it takes to solve them goes up more and more for each item (point in TS, making the prime gigantic in crypto) you add. It's trivial to factor 15, as shown here, but non-trivial to factor (2 ^ 43112609 -1) * (2 ^ 42643801 -1).

So, yes, if it can solve the traveling salesman problem (in polynomial time. Solving it is easy, unless you consider that with enough nodes, it'll take until the heat death of the universe), it IS a big deal for modern crypto because it shows that np-complete problems (whose only REAL issue is that they are computationally difficult) can be solved in a realistic amount of time, and most modern crypto counts on the fact that it cannot.

Is factoring np-complete? (1)

davidwr (791652) | more than 5 years ago | (#29320087)

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.

Re:Is factoring np-complete? (5, Informative)

Trepidity (597) | more than 5 years ago | (#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).

Re:Is factoring np-complete? (0)

Anonymous Coward | more than 5 years ago | (#29321941)

It should be noted that integer factorization is solvable in sub-exponential runtime (but still super-polynomial - see, for example, Lenstra's elliptic curve algorithm). If it could be shown to be NP-complete, that would be a Big Deal, as we currently have no sub-exponential algorithms for any NP-complete problem. It seems probable that factorization is easier than any NP-complete problem.

Re:Interesting and a qustion (1)

SKJDot (1169063) | more than 5 years ago | (#29320163)

Why has this really been modded funny?

Re:Interesting and a qustion (1)

doublebackslash (702979) | more than 5 years ago | (#29321019)

THANK YOU!

That link was exactly what I was looking for.
Really thank you.

Re:Interesting and a qustion (0)

Anonymous Coward | more than 5 years ago | (#29319697)

Lattice-based public key algorithms are safe from quantum so far, but they are much less efficient (vs. currently used algorithms) with respect to key size and computation time. Until there is a significant breakthrough in the # of qubits, though, everything is safe from quantum.

RSA may sleep well... (2, Funny)

Vadim Makarov (529622) | more than 5 years ago | (#29319313)

they are still factorizing the number 15 :)

How many qubits? (3, Informative)

zapakh (1256518) | more than 5 years ago | (#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?

Re:How many qubits? (5, Insightful)

Trepidity (597) | more than 5 years ago | (#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 (5, Funny)

youn (1516637) | more than 5 years ago | (#29319329)

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

changing of the guard (2, Funny)

JackSpratts (660957) | more than 5 years ago | (#29319345)

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

Re:changing of the guard (5, Funny)

BungaDunga (801391) | more than 5 years ago | (#29319473)

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

Re:changing of the guard (1)

pdbaby (609052) | more than 5 years ago | (#29319641)

How did you know?! Dammit now I have to regenerate everything!

Re:changing of the guard (5, Funny)

sakdoctor (1087155) | more than 5 years ago | (#29319671)

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

Re:changing of the guard (1)

DoofusOfDeath (636671) | more than 5 years ago | (#29319891)

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

What kind of asshole would set his RSA factors to 1, 3, 5???

Re:changing of the guard (4, Funny)

DoofusOfDeath (636671) | more than 5 years ago | (#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

Re:changing of the guard (0)

Hurricane78 (562437) | more than 5 years ago | (#29320347)

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

Re:changing of the guard (0)

Anonymous Coward | more than 5 years ago | (#29320493)

Girlfriend? You must have the wrong guy.

Re:changing of the guard (0)

Anonymous Coward | more than 5 years ago | (#29321727)

Don't get uppity. Our records clearly show that he has a girlfriend who is currently driving towards his location at 65 miles per hour.

Re:changing of the guard (1)

Al Dimond (792444) | more than 5 years ago | (#29320737)

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

My darknet (1)

davidwr (791652) | more than 5 years ago | (#29320141)

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.

Can someone explain this... (1, Interesting)

Anonymous Coward | more than 5 years ago | (#29319363)

...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 one-by-one. I THINK this is made possible by superpositions of atoms not having a single state but all possible states simultaneously, whatever that means, and then somehow atoms are "entangled", manipulated, and the correct values are sussed out with a probability approaching 1.

If this is right, and I'm not saying it is, how do you do all this with a chip? The article says "Although the new chip is only 26 mm long, it has to be surrounded by a whole table top of that equipment.". I would think you'd need a ton of gear and rare materials to put atoms in superpositions and entangle them and all that... What does the chip do exactly... and how does this work?

If anyone could clarify, I'd be really interested. If this marks the beginning of the end of RSA... do we have a back up method that is more resistant to quantum computing? (And don't say quantum encryption, cuz I'm not sure people are going to have the gear on-hand when they want to send an email via GPG or do some online banking...)

Re:Can someone explain this... (1, Insightful)

Anonymous Coward | more than 5 years ago | (#29320445)

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 aren't a part of the system. This can screw things up pretty badly. It's a lot like Windows getting a BSOD when you decide to pick your nose.

That said... not all problems are instantly sped up just because you're working with qubits instead of normal bits. The problems that get a speedup all have a few common traits.

With a Quantum Computer, when you use a quantum logic gate, essentially every possible value is computed at once (in reality it's not that simple, but that's beyond the scope of this comment). However, when you attempt to measure the state of the qubits, it'll "snap" into any of the results, and this cannot be controlled. So you can perform "2*x" on 1..8, but the probability of actually getting the answer you want gets lower and lower as you take advantage of quantum parallelization more and more.

However, sometimes you don't want to know a specific answer, you want to know something about all of them. For these problems, Quantum Computers win. This is how Shor's Algorithm works.

Anyway, there are plenty of encryption methods that aren't vulnerable to Quantum Computers, like Lamport Signatures, for example.

Not "code" breaking (-1, Troll)

Anonymous Coward | more than 5 years ago | (#29319367)

RSA's a cipher, not a code. Please, learn the intricate details of everything before attempting to spread the word, even when everyone understands the meaning. :)

What about ECC? (1)

Stile 65 (722451) | more than 5 years ago | (#29319461)

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 do it. I'm working (very slowly) on an implementation of Chaumian anonymous crypto-cash, and in that application, all a government would need to do is break one key and an entire currency would go kaput. I need to include support for future-proof public key crypto algorithms as early as possible.

Re:What about ECC? (4, Informative)

Anonymous Coward | more than 5 years ago | (#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:What about ECC? (2, Insightful)

Stile 65 (722451) | more than 5 years ago | (#29320385)

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

Re:What about ECC? (1)

mysidia (191772) | more than 5 years ago | (#29319993)

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.

Re:What about ECC? (1)

Captain Segfault (686912) | more than 5 years ago | (#29320041)

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.

I, for one.... (1)

CFD339 (795926) | more than 5 years ago | (#29319999)

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

Is there any safe encryption? (1)

presidenteloco (659168) | more than 5 years ago | (#29320013)

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?

1-time pads are inherently unbreakable (2, Informative)

davidwr (791652) | more than 5 years ago | (#29320189)

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 collect Linux distros, then we can use the distros as one-time pads. Sharing a pad becomes as easy as saying "CentOS-5.3-x86_64-bin-4of7.iso start at byte 134,379,001 and wrap around" and poof, we've got ourselves a 629MB pad to play with. When that pad nears the end, one of our messages could be "ubuntu-8.04.1-dvd-i386.iso offset 1,423,783,047 backwards and wrap around" and that gives us another 3.9GB worth of pad. This relies on security through obscurity to work, which is notoriously fragile, which is one reason it's not a general-purpose solution.

Re:1-time pads are inherently unbreakable (1)

mikeee (137160) | more than 5 years ago | (#29320587)

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.

Re:1-time pads are inherently unbreakable (0)

Anonymous Coward | more than 5 years ago | (#29321131)

What you want is unpredictability rather than true randomness. If you took your CentOS ISO, and either compressed it, or ran it through some type of bit blender (perhaps AES with a key of zeroes and a random hash), an eavesdropper would have it almost impossible to decrypt the cyphertext.

This is the weakness of one time pads though. Use a PRNG with some type of period where numbers start repeating, and you're cooked. True, cryptographically strong random numbers are relatively slow to make (look how slow output from /dev/random is compared to /dev/urandom unless you have a hardware RNG).

Re:Is there any safe encryption? (0)

Anonymous Coward | more than 5 years ago | (#29320195)

As I understand it: Yes so long as a key hasn't passed across the network.

HOWEVER I would assume that given some information on the TYPE of encryption used, along with packet sniffing on the network, quantum cryptoanalysis would significantly speed up brute force decryption against large packet logs (Along the lines of those WEP cracking apps out there that given enough packets can reverse engineer the key.

1-time pad can't be brute forced (1)

davidwr (791652) | more than 5 years ago | (#29320211)

If the 1-time pad is truly random and the pad itself is never compromised, it's mathematically unbreakable. In my examples with Linux distros above, I forgot to mention a flaw: the distros do not contain random data. In some situations this can make an attack easier.

Depends on What Features You Want (2, Informative)

mdmkolbe (944892) | more than 5 years ago | (#29320417)

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 to date. Thus if quantum were to break all the public-key systems, it wouldn't necessarily kill all crypto, but it would make implementing crypto more expensive (e.g. couriers or quantum hard lines).

However, quantum might not break all public-key crypto. Public-key crypto only requires the existance of a function, f, such that f is easy to compute but the inverse, inv-f, is hard to compute. Usually "easy" is defined as "polynomial". Thus it is a trivial corollary that if someone can prove P=NP or that quantum can solve all NP in polynomial time. As far as I know no one has proven either so there is a glimmer of hope.

However, even if P=NP, I may still be possible to build a public-key crypto. While "n^100" time is technically polynomial, it really isn't computationally "easy". So even with P=NP there may exist functions that can be computed in a low-degree polynomial time (e.g. linear or quadratic) but who's inverse requires a high-degree polynomial.

All of this is a long winded way of saying "quantum breaks the public-key currently in common use but there is the theoretical possibility that someone may develop a public-key that won't be broken by quantum".

Re:Is there any safe encryption? (0)

Anonymous Coward | more than 5 years ago | (#29321609)

Encryption based on quantum entanglement [wikipedia.org] is possible. The basic idea is to create a one time pad by sending one of a pair of entangled photons to Alice and one to Bob. Any measurement from an eavesdropper will show up when Alice and Bob compare a sample of their keys. As long as the eavesdropper does not know what sample they will compare (and doesn't control the photon source, etc.), it is guaranteed by the laws of quantum mechanics that the eavesdropper cannot know the key.

Amazing (1, Funny)

jfern (115937) | more than 5 years ago | (#29320297)

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.

Re:Amazing (1)

maxwell demon (590494) | more than 5 years ago | (#29322017)

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!

...full text requires a subscription (1)

Prof.Phreak (584152) | more than 5 years ago | (#29321799)

I'm so glad these research publications are made widely available to all... err...

The crypto race (1)

Arancaytar (966377) | more than 5 years ago | (#29322065)

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 come up with something else.

It's still scary, however: In practice, the "something else" can take years or decades to invent, and in that time computers can't be networked securely without symmetric keys, and people can't talk without meeting in person first. Particularly worrisome is that this shifts the power toward those with vast material resources: Governments can securely transport planeloads of one-time pads and build great quantum computing arrays, while a few dissenting college students in Beijing or Teheran (or even Washington) would be left with no way to organize.

Swarm networks and steganography will grow vastly more important. Already, it is far harder to hide that you use encryption than to encrypt. Hiding information in plain sight, and relying on anonymous/decentralized distribution, may become the resource underdogs' weapons of choice.

Load More Comments
Slashdot Login

Need an Account?

Forgot your password?