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."
ElGamal?? (Score:4, Interesting)
conspiracy theory (Score:4, Interesting)
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?
New assymetric algorithms needed? (Score:5, Interesting)
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.
Early connection? (Score:5, Interesting)
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.
Re:If you want to test it (Score:5, Interesting)
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
Secure encryption (Score:2, Interesting)
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.
Re:Timeless saying applies here... (Score:4, Interesting)
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).
Re:Timeless saying applies here... (Score:3, Interesting)
It's worth noting that social engineering is quite often the cheapest method. I was at a conference back in 1999, where a Navy guy pointed out that in 'red team' testing, they'd found that the typical Systems Administrator would roll over for an average of $7000. No, I don't know how the details of how they conducted the test.
One could argue (or hope) that _most_ SysAdmins these days are more cognizant of the risks, so probably not as casual as they used to be.
Let's just back up a moment. (Score:3, Interesting)
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.
Re:I'm sorry, I'm an idiot- (Score:3, Interesting)
No, it doesn't brute force every possible combination. You can perform an operation on a superposition of all possible k-bit strings, but you can't actually get all of the 2^k outcomes of that operation. If you measure the result, you'll get one of the 2^k outcomes at random.
Basically you start from that superposition of k-bit strings, then you apply some operations to that state so that all of the the correct answers are in phase with each other and constructively interfere. Effectively, you can only apply this kind of speed-up if you can exploit the numerical properties of the problem to ensure that this happens.