Slashdot Mirror
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."
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
d41d8cd98f00b204e9800998ecf8427e
they are still factorizing the number 15 :)
17779 eligible voters in a district, 17779 'vote' as one. This is Russia.
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?
shortly after, secret service agencies worldwide have decided to make the day a holiday and call it man in the middle day (MIM)
Never antropomorphize computers, they do not like that
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):
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.
10 PRINT CHR$(205.5+RND(1)); : GOTO 10
my darknet effectively utilities rsa/blowfish. not for long apparently.
...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...)
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);
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.
I claim first use of "Error No. 0B" - or "No. 0B error." It'll be the new ID 10T!
You really don't understand the impact world wide reliable and fast code breaking has. Cryptology has won wars.
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!
The problem with quotes on the internet, is that nobody bothers to check their veracity. -- Abraham Lincoln
Anything above "4" is represented as "A Suffusion of Yellow"
....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.
The problem with quotes on the internet, is that nobody bothers to check their veracity. -- Abraham Lincoln
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?
Where are we going and why are we in a handbasket?
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.
What part of "A well regulated militia" do you not understand?
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.
Knowledge is how to play a game, intelligence is how to win, wisdom is knowing what game to play.
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.
Knowledge is how to play a game, intelligence is how to win, wisdom is knowing what game to play.
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.
Knowledge is how to play a game, intelligence is how to win, wisdom is knowing what game to play.
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.
Knowledge is how to play a game, intelligence is how to win, wisdom is knowing what game to play.
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.
Knowledge is how to play a game, intelligence is how to win, wisdom is knowing what game to play.
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.
Knowledge is how to play a game, intelligence is how to win, wisdom is knowing what game to play.
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.
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.
If all else fails, immortality can always be assured by spectacular error.
If arbitary sized integers are capable of being factorized, then it will be "All your primes are belong to us"
Vintage computer adverts: http://www.vintageadbrowser.com/computers-and-software-ads
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;
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".
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 :)
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.
What part of "A well regulated militia" do you not understand?
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."
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.
I don't know about angles, but it's fear that gives men wings. -Max Payne
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.
I'm so glad these research publications are made widely available to all... err...
"If anything can go wrong, it will." - Murphy
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.
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.
I am TheRaven on Soylent News
How about an gzip'ed ISO xor'd with the output of a fast halfway-decent pseudorandom-number generator. By "pseudorandom" I mean it won't show an easily discernible pattern until after you've done xor'ing - if the ISO is 4.3GB, the pattern shouldn't be discernable until after 4.4GB of output.
Knowledge is how to play a game, intelligence is how to win, wisdom is knowing what game to play.
what's the deal with 2048 bits keys?? 6 bits seems fine for the next 10 years at least
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.
Huh, I had actually never heard that, I just assumed that due to the mores of the times it was easier to bomb "yellow" people than europeans. Strategically it doesn't make a lot of sense to me though. It's hard to image post WW2 being a cold war after bombing the russian backyard with WMD and sentiment in occupied europe might have swung more pro-german after a couple of mushroom clouds. Of course (luckily) we'll never know any of this for sure.
If all else fails, immortality can always be assured by spectacular error.
It's more something like this :
int a = 0..65535
int b = 0..65535
a*b = 15
printf("a = %d, b = %d", a, b);
(btw, this is not how it -currently- works, it's something that might, theoretically, someday be possible. You cannot just say a*b is 15, but you must find a way to amplify the a and b registers based on the desired outcome)
(oh, and you'll have to repeat the execution a few thousand times, since the chance for a wrong answer will be nonzero. Small, but nonzero. Also there might be multiple distinct answers)
(and btw, this is assuming it's possible at all. Yes, the current theory's equations predict this will work, but it has not actually been experimentally verified in non-trivial cases. E.g. the physician Gerard 't Hoofd, who carried a significant part of the work that led to the standard model (and got a Nobel prize for it) seems to think it won't work. More generally speaking, if any of the hidden-variable theories turn out to be true, this won't work)
(the algorithm "really works" by repeating a specifc calculation "infinite" number of times in one step. It allows one to find the period of the permuation that is created by (a^x mod N), or the order r of a in Z(N). If a is well chosen (it must not be 0, 1, or -1 mod N, and must divide ), then N can be factored into a^(r/2) - 1 and a^(r/2) + 1 (both mod N, so they can be very different numbers). The public key of an rsa key can be the input, and it will give you either p or q, making the other one trivial to compute)
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 will all have access to genetic engineering technology (why write a Windows virus when you can write a real one?) and to cheap quantum computers as well, we are back to square one. Pardon me as I insert a Quantum encrypted nano-virus developed from embryonic (suck my dick you Christian mofos) stem cells up your ass.
This is the theme for the movie Sneakers: http://www.imdb.com/title/tt0105435/