Slashdot Mirror
1978 Cryptosystem Resists Quantum Attack
KentuckyFC writes "In 1978, the CalTech mathematician Robert McEliece developed a cryptosystem based on the (then) new idea of using asymmetric mathematical functions to create different keys for encrypting and decrypting information. The security of these systems relies on mathematical steps that are easy to make in one direction but hard to do in the other. Today, popular encryption systems such as the RSA algorithm use exactly this idea. But in 1994, the mathematician Peter Shor dreamt up a quantum algorithm that could factorise much faster than any classical counterpart and so can break these codes. As soon as the first decent-sized quantum computer is switched on, these codes will become breakable. Since then, cryptographers have been hunting for encryption systems that will be safe in the post quantum world. Now a group of mathematicians have shown that the McEliece encryption system is safe against attack by Shor's algorithm and all other known quantum algorithms. That's because it does not depend on factorisation but gets its security from another asymmetric conundrum known as the hidden subgroup problem which they show is immune to all known quantum attacks."
Don't start feeling too secure about the so-called McEliece encryption system - a candidate for the security of Internet traffic in the age of the quantum computer (2008 article)
When the foot seeks the place of the head, the line is crossed. Know your place. Keep your place. Be a shoe.
If it can be engineered, it can be reverse-engineered.
Living With a Nerd
It is worth noting that solving hidden subgroup problem is a subfield of quantum computing that has been active for a while. Although we can't figure out how to solve it in general, we can solve specific instances of it; for example, I think that factorizing is one such instance.
Thus, I suspect that we will eventually figure out a way to break this encryption. Even if we do, though, these mathematicians still get credit for giving us a new instance of the hidden subgroup problem to try and solve, which may give us additional insight into the extent to which the general problem can be solved by a quantum computer.
Snarkiness is inversely proportional to wisdom because it emphasizes feeling right rather than being right.
I see
Would ElGamal also be immune since it's based on Discrete Logarithms?
"Can be broken" is a red herring. It is a simple matter to design log-in systems that prevent iterative attempts to test passwords that have been "broken".
The simplest form of security, "security by obscurity" remains effective despite quantum computers and server farms.
It is a mathematical exercise to determine time to "decrypt" a secure area or volume based on iterative password tests.
Even something as crude as a visual word input prior to a Slashdot anon post serves even this hacker-rich community.
Just anon, not coward.
I wonder if "THEY" already have one of these quantum computers and are keeping a lid on it so they can snoop on the PGP of our enemies. Would it be possible to develop one of these in secrecy?
Quantum computing needs exponential space. :)
Send a bunch of encrypted e-mails containing questionable content and see if anyone comes knocking at your door. And be sure to not send any questionable content unencrypted, or to give any other reasons for them to show up.
You can lead a horse to water, but you can't make it dissolve.
Symmetric algorithms are at least in their second generation (DES/Lucifer now AES) of production use, with decades of study and close analysis by a lot of good minds.
Asymmetric algorithms are still essentially the first generation. Take RSA. It has been out for so long that its patent has expired more than 15 years ago. Even elliptic curve cryptography has been out at least 20 years, because the NeXT had it in NeXTStep 3.0 (and ended up getting pulled out of the OS due to ITAR).
Even cryptographic hashes have been through a number of iterations. We had MD4, then MD5, then SHA-1, then SHA-256, now are looking for something to replace SHA, similar to how Rijndael replaced 3DES and DES.
Maybe it is time to have a contest to have a standard asymmetric algorithm to replace RSA, DSS, and ElGamal? Something fundamentally designed to resist quantum computer attack as well as other threats.
Thus, I suspect that we will eventually figure out a way to break this encryption. Even if we do, though, these mathematicians still get credit for giving us a new instance of the hidden subgroup problem to try and solve, which may give us additional insight into the extent to which the general problem can be solved by a quantum computer.
From TFA:
However, it's worth pointing out that while the new work guanratees safety against all known quantum attacks, it does nothing of the sort for future quantum attacks. It's perfectly possible that somebody will develop a quantum algorithm that will tear it apart as easily as Shor's can with the RSA algorithm. "Our results do not rule out other quantum (or classical) attacks," says Dinh and co.
"I don't care about the Constitution!" --Bill O'Reilly, November 17, 2009
Seriously, Slashdot gets it wrong EVERY TIME. Next time, would it kill the editor to go to http://www.caltech.edu/ and, you know, read any of the words on the page?
I think you are too optimistic. I do not mean that "THEY" have one (I do not know/not answer). The issue is that the statement should read:
After all, why limit it to only "ours" enemies after spending so much on it?
Why can't
torn off of a "one time" pad.
Anyone can transmit the page ID age the encrypted text in the clear and be assured of totally secure communication between the two parties who have both the encryption key and the decryption keys.
The algorithm consists of something non-computable.
In my case my the WEP2 key on my wireless LAN consists of my own unique way with keys (like I was going to tell you my idiosyncratic keying algorithm,) and an entire paragraph from a book on my shelf of selections from my favorite author (like I was going to tell you who that really was.)
Now extent that of a whole pad of keys...
Unbreakable is a phrase that comes unbidden to my lips.
MSBPodcast.com The opinions expressed here are my own. If you don't like 'em... Think up your own stuff.
Another article that is over the head of 90% of the people who post here but that won't stop them from acting like they know something
*pfft* I just broke the McEliece encryption on my iPad. There's an app on iTunes called iDecrypt...
this is not really news worthy.
quantum computers will kill cryptography (as they are now) because of the ability to perform many computations at the same time. Factoring and algorithms to "break" a crypto system is about finding a shortcut, so that brute force can be avoided. But with quantum computers, brute force will be a more viable method.
especially, as with most computers and tech, the speed of quantum computers will only increase exponentially (once the first working one is stable and commerical), thus making brute force more and more viable. Increasing the key size will not be a viable solution unless we are willing to increase the key size exponentially as well.
so once quantum computers come out and get more refined, no pure mathematical crypto system will be safe.
A sociological observation is that Shor was an undergrad at Caltech when McEliece was a professor there formulating the cryptosystem that would resist the quantum algorithm that Shor would develop years later. I wonder if knew each other.
The only encryption method I've heard about that has not been found to be breakable is the one time pad. This method has the problem of exchanging the pads beforehand.
All of the major encryption machines used during WWII appear to have been broken. The new encryption methods are currently much harder to break, but the spooks are likely to discover some innovative method to break such algorithms.
Current methods using large prime numbers sounds like they are soon (next few decades) to be broken. If we got into a war where breaking these methods became important, I'm sure that quantum computers would soon become available, if they aren't already. Even if quantum algorithms aren't available, someone might come up with a way to calculate prime factors using a bacteria colony through DNA molecules. A method may cost a million dollars per factor found, but sometimes that is small change for the information gained.
I'm sure that there are groups looking for the next level of encryption. Something that isn't compatible with quantum methods, or requires it to reverse the encrypted data. Making it take longer and be more expensive to break is the goal of encryption.
Who would win this election: Andrew Weiner vs Andrew Weiner's weiner.
I happen to work at [CENSORED] and I must assure you that there's no need to worry, our research clearly indicates that making such computers is impossible.
Hey, you know that girlfriend of yours that sends you those pictures? She's hot!
In the simplest of terms
I thought the whole point of the quantum computer was was it did the equivalent of brute forcing every single possible answer simultaneously
instead of checking a password say from
a ..z ..az ..bz
b
c
aa
ab
ac
ba
bb
bc
so a one letter password (normal computer) can be checked in 26 steps, and a 2 letter password in 676 steps..
each once then proceeding,
and on a quantum computer, I thought it threw the equivalent of the OED (all possible answers, all possible combinations) at the same time.
but only responding with the correct answer
will someone please tell me where my basis is way off?
every day http://en.wikipedia.org/wiki/Special:Random
Maybe he did, maybe he didn't.
Infuriate left and right
http://www.xkcd.com/773/
$300 says that there's a quantum computer at Y-12 National Security Complex.
There is an old paper, written by DJB, which gives a quick introduction to some (this and) other quantum computer resistant encryption methods: Introduction to post-quantum cryptography
Here is a link to the paper on the arxiv:
http://arxiv.org/abs/1008.2390
Reading through the abstract, I see that a significant feature of this cryptosystem is that it cannot be solved by "strong Fourier sampling", which makes the situation more interesting because it is only a slight exaggeration to say that quantum Fourier transforms are the only trick we know of that lets us get exponential speed-ups in quantum algorithms.
Snarkiness is inversely proportional to wisdom because it emphasizes feeling right rather than being right.
This doesn't rule out other methods of speeding up using quantum tricks. Also, keep in mind that this may all be for naught since no work of this form can rule out the existence of a fast classical algorithm for handling the problem. Thus, implicitly, all these sorts of results are interesting primarily if one assumes that these sorts of problems don't lie in P. The good news is that the hidden subgroup problem is very likely not in P.
How do you brute force (or solve) a one-time pad, where the pad was created from random atmospheric noise or any other truly random source?
[...]
The only downside (and it's really not much of a downside) of OTP technique is that you need the pads before you need the message. However, I actually can't think of a situation where that would seriously inconvenience modern users of the technique.
Oh, and how do you unbreakably update OTPs in the field? Easy: You encrypt them with the last/reserved OTP the other end has. Cyclic encryption of truly random numbers? Incomprehensible. It's just another 100% opaque data stream. Done deal.
I've fallen off your lawn, and I can't get up.
Wake me up when non-imaginary quantum computers can factor integers larger than 15. Every year we hear about breakthroughs in quantum computing, but nobody seems to be able to make one that actually does anything.
Anyway, good luck breaking RSA-4096 with your imaginary quantum computer. When your quantum computer can finally break RSA-4096 in the year 2510, we'll have moved on to RSA-16777216 thanks to our quantum computers, and you'll be just as fucked, since it'll take your quantum computer the same amount of time to break that as it takes modern computers to break RSA-4096.
I thought it had been proven that quantum computation was a pipe dream (you can't physically compute 2^N operations with less than 2^N atoms). Is the hypothesis still considered plausible ?
The Wise adapts himself to the world. The Fool adapts the world to himself. Therefore, all progress depends on the Fool.