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."
The last I heard, the largest number ever factored with Shor's algorithm was 15.
are belong to us.
But seriously.. now NSA will have to come up with another algorithm that only they have the horsepower to break!
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!
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
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!
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
....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?
I'm no expert in qbits, bit I thought it was supposed to work like this:
/* =3 */
int input=15;
start=2;
end=truncate(sqrt(input));
/* 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");
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.
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".
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."
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.
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
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/