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."

Re:Timeless saying applies here...

[Jack9]

> If it can be engineered, it can be reverse-engineered.

How does that apply to this article, in any way?

Re:Timeless saying applies here...

[kalirion]

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.

Re:Timeless saying applies here...

[da cog]

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.

Re:conspiracy theory

[woolpert]

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?

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.

Re:Timeless saying applies here...

[Frequency Domain]

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.

Re:conspiracy theory

[Anubis IV]

Of course, your point doesn't consider the fact that the information sharing only goes one way. If THEY come up with something new, it's not always put back out into the field where it can be worked on by others and built upon. If THEY then find something new, THEY can be the first and only ones building upon it, and THEY do not have to sacrifice the ability to build on everything else that is coming out in the field as well. If that something new is a breakthrough concept, then THEY may be able to build a lead of years or decades. Of course, as you pointed out, researchers tend to be much more aware of what is going on these days than in the past, due to the speed and ease of communication, which reduces both the likelihood of THEM getting a breakthrough first and also reduces the time that THEY will likely be the only ones exclusively holding that knowledge. Despite that, I seem to recall hearing stories of various encryption ideas the NSA developed in the '70s and '80s which weren't developed in the open until the late '90s and early 2000s (sorry, no citation).

Re:New assymetric algorithms needed?

[FrangoAssado]

What you're describing is a NP-complete problem -- assuming P != BQP != NP. But I'm guessing that you already know that :)

Still, it's still very hard to build a cryptosystem that exploits the hardness of solving NP-complete problems. The main problem is, NP-completeness only guarantees that some instance of the problem is hard, it says nothing about a specific instance. So, for instance, if you have a specific 3-SAT formula, there's no guarantee someone can't come up with a solution for it in polynomial time.

That being said, there are some candidates for a cryptosystem based on NP-completeness. Check for example the McEliece cryptosystem [wikipedia.org].

Re:Timeless saying applies here...

[Anonymous Coward]

This exchange is illustrated here:

http://imgs.xkcd.com/comics/security.png