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.
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.
No - both prime factorization and discrete logarithms can be done in polynomial time with a quantum computer.
Feel secure again. Only a variant was broken.
How can I believe you when you tell me what I don't want to hear?
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
Simplistically:
If THEY bought out 50% of the researchers in the field, without arousing suspicion amongst those who turned down the offer, THEY would only have a 50% chance of having one first.
More realistically,
If THEY bought out a significant percentage of the researchers in the field, without arousing suspicion amongst those who turned down the offer, THEY would likely only be a few months / years (at best) ahead.
And since the outlook on the QC front is rather bleak (in terms of a functional QC with any real power) the odds are strongly in favor of THEY not having squat.
Especially in today's world it isn't like top researchers are fragmented and isolated. In the past it was possible for a governmental organization to use its greater vision to collect isolated researchers and be the first to introduce them to each other, magnifying their individual efforts. Today everybody who is anybody in these fields is at least aware of the others, if not following closely.
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.
Even then, they would probably spend a long time creating other circumstances in which to pick you up that would give plausible deniability as to how they caught on.
One can google one's own references as I'm sort of lazy today, but a good example: the British had thoroughly broken Enigma during WWII, and at one point in the war knew where -every- German U-boat was. This created a dilemma for them: should they act on this information, and if so, how to do it without tipping their hand? If they just went and rounded up every single one, it would be pretty obvious that the code had been broken.
What they did, according to the stories, is send out disinformation that a) they had ramped up production of a bunch of new long-range sea-spotting planes (they didn't, they only had the resources for a few); and b) these planes would fly near where they already -knew- the U-boat was, and 'spot it' (making sure it was obvious they'd been seen by the U-boat itself before flying back). The British were also careful not to find too many U-boats -- only the ones that they needed out of the way for critical operations. The Germans were convinced they just had really bad luck and were the victim of a very expensive and thorough patrol system by the British.
If the guys in dark suits can crack PGP, Blowfish, etc. easily, they won't obviously act on it until they first get dirt on you via other means. :p
But how will I know they're not just knocking at my door out of a desire to make my acquaintance?
Easy. If they use your door knocker, they want to make your acquaintance. If they bring their own, they're coming for more than tea and crumpets.