1978 Cryptosystem Resists Quantum Attack 185
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."
Hidden subgroup problem is under active research (Score:5, Informative)
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.
Re:ElGamal?? (Score:5, Informative)
No - both prime factorization and discrete logarithms can be done in polynomial time with a quantum computer. [arxiv.org]
Re:Can be broken? (Score:3, Informative)
Re:Good but not great (Score:5, Informative)
Feel secure again. Only a variant was broken. [iacr.org]
The article agrees with you (Score:5, Informative)
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.
It's "Caltech", not "CalTech" or "Cal Tech" (Score:3, Informative)
Seriously, Slashdot gets it wrong EVERY TIME. Next time, would it kill the editor to go to http://www.caltech.edu/ [caltech.edu] and, you know, read any of the words on the page?
Re:New assymetric algorithms needed? (Score:3, Informative)
Three reasons:
1: Public keys are not just used for real time exchanges. Public keys are sometimes used for data archiving where the private keys are held in an offline area. Same with keys that sign programs to detect tampering.
2: Quantum links are really, really slow. Instead of a one time pad, realistically you want to generate a key through the secure channel via a Diffie-Hellman handshake that is used for some time then chucked (like for a transaction or for a chunk of data.) Then send the bulk data through a standard link.
3: Quantum key exchanges have had some issues that could allow an attacker to get knowledge of the key.
4: One would have to drop parallel pipes everywhere that supported quantum channels. It is hard to get ISPs to drop one chunk of fiber, much less the fiber needed to interconnect for the secure quantum channels and the partial photons.
5: There is the issue of trust. You can set up a quantum exchange with another machine and come up with a key that you know hasn't been touched... but is that really your bank, or is it some site in Elbonia that is patched in? Quantum key selection won't help you here in knowing that you are talking to the right host.
Regardless, even if we had secure point to point connections via quantum key generation and bulk tunnels, public key cryptography is still an important part of life, even if it to sign documents and ensure they won't be tampered with.
Re:Good but not great (Score:2, Informative)
Feel secure again. Only a variant was broken. [iacr.org]
The date of your document July 2008 precedes the successful decryption in October 2008.
Introduction to post-quantum cryptography (Score:2, Informative)
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 [pqcrypto.org]
Re:conspiracy theory (Score:3, Informative)
Only 50,000 sq. ft.? Times have changed, computers are getting smaller as they get bigger. Back in the day, that was a mid-size corporate server farm. Of course now, that's a lot more computing power.
As for power, most secure computing facilities have their own power generation capability - if nothing else then just a motor-generator to assure clean power all the time. An old Army base's power system is not likely to be up to the standards of today for this purpose.
There's a facility in the wilds east of Bend OR that was built in the 1980s as a backup government facility in case of nuclear war - this is where the Western governors and such were going to hang out till the radiation in the big cities got down to a reasonable level. It has about 40,000 sq. ft. of raised floor, plus a couple of acres worth of space for people, with food and everything you need for 150 people for a year, four hidden satellite dish platforms, four diesel generators each the size of a large room, and a fuel supply the size of an Olympic swimming pool.