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."
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.
Would ElGamal also be immune since it's based on Discrete Logarithms?
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?
If it can be engineered, it can be reverse-engineered.
That only works for "security through obscurity" type of problems. A good encryption should not be "solvable" - it must be brute forced. The question is how expensive the brute force method is in processing power and time.
It doesn't apply to this article. The way that one typically breaks a cryptosystem is not by reverse engineering (which is not even meaningful here, given that the algorithm is already completely open), but by finding a clever new way to solve the mathematics underlying the system using less information than the designers of the system had thought was needed.
Snarkiness is inversely proportional to wisdom because it emphasizes feeling right rather than being right.
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.
Feel secure again. Only a variant was broken.
How can I believe you when you tell me what I don't want to hear?
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
Actually, with really hard-core crypto systems there are three traditional ways to break them: 1) rubber hose; 2) dumpster diving; or 3) box of chocolates/bouquet of roses.
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.
Pidantic much? {sic}
That falls under the generalization of (3).
(1) Threat/intimidation/violence
(2) Exploit a careless mistake
(3) Bribery/persuasion
I suppose (1) and (3) even could blur together into "influence" (negative and positive).
...the future crusty old bastards are already drinking the Kool-Aid.
WTF... OK... I can deal with slashdot being overrun by morns who know little but act big, but now we have to put up with text-ese ?
His UID is lower than yours so shouldn't it be "I can deal with that slashdot was overrun by morns who knew little when I signed up. (eol)"
Maybe he did, maybe he didn't.
Infuriate left and right