Ask Slashdot: Post-Quantum Asymmetric Key Exchange?

First time accepted submitter LeDopore writes "Quantum computers might be coming. I'd estimate that there's a 10% chance RSA will be useless within 20 years. Whatever the odds, some of the data we send over ssh and ssl today should remain private for a century, and we simply can't guarantee secrecy anymore using the algorithms with which we have become complacent. Are there any alternatives to RSA and ECC that are trustworthy and properly implemented? Why is everyone still happy with SSH and RSA with the specter of a quantum menace lurking just around the corner?"

Comments

Re:Fine. You find an asymmetric primitive

[Anonymous Coward]

ECC is AFAIK theoretically vulnerable (i.e. while there aren't KNOWN quantum gate implementations of ECC, there are no good reasons to think it is unfeasible).

McEliece and the Lattice-based stuff are promising, they just hadn't be as inspected as RSA yet...

Re:Vulnerable in 20 years

[steevven1]

I think the author's point is that data sent today could be sniffed, stored, and cracked in 20 years. Some of that data may still be sensitive in 20 years, so we need to switch now.

ECC is not voulerable

[Anonymous Coward]

There is no known attack on ECC using quantum computers.

If you assume it might be broken because there is no proove that it's secure, you might assume the same fron any other method - there is no known method to proove that some algorithm is _not_ attackable by quantum computers.

(Of course, knowing the "new" slashdot, AC comments are never moderated +1, so noone will read this).

(And, hey, my captcha is 'druggist'...)

Re:ECC is not voulerable

[CuBr]

There is no known attack on ECC using quantum computers.

This should not have been modded up, because it is blatantly false. The security of ECC relies on the presumed hardness of the discrete logarithm problem (in elliptic curves over finite fields). But Shor's algorithm can solve the discrete logarithm problem in ANY finite group (assuming you have an efficient way of operating on the group elements).

what's old is new again

[Nightshade]

This 1978 crypto is supposed to be safe against quantum computers: http://www.technologyreview.com/blog/arxiv/25629/ (if that's the specific angle you're worried about). The downside is the key management because the keys have to be really really long (i.e. 20,000+ characters vs having a memorable passowrd or passphrase that you'd be able to use today).

No expert but...

[TheCarp]

In previous discussions it has been pointed out that not all encryption algorithms are susceptible to quantum computers. If I remember right (I am sure someone has a reference that I don't) it only effects RSA and others that rely on the hardness of factoring discrete logarithms.

Anyway...only reference I can find, from wikipedia (http://en.wikipedia.org/wiki/Quantum_computers#Potential ):

However, other existing cryptographic algorithms do not appear to be broken by these algorithms.[11][12] Some public-key algorithms are based on problems other than the integer factorization and discrete logarithm problems to which Shor's algorithm applies, like the McEliece cryptosystem based on a problem in coding theory.[11][13] Lattice based cryptosystems are also not known to be broken by quantum computers, and finding a polynomial time algorithm for solving the dihedral hidden subgroup problem, which would break many lattice based cryptosystems, is a well-studied open problem.[14] It has been proven that applying Grover's algorithm to break a symmetric (secret key) algorithm by brute force requires roughly 2n/2 invocations of the underlying cryptographic algorithm, compared with roughly 2n in the classical case,[15] meaning that symmetric key lengths are effectively halved: AES-256 would have the same security against an attack using Grover's algorithm that AES-128 has against classical brute-force search (see Key size). Quantum cryptography could potentially fulfill some of the functions of public key cryptography.

20 years is extremely unlikely

[JoshuaZ]

I wouldn't be surprised if in 20 years we can use a quantum computer to factor a number greater than 100. But that only requires a handful of functioning qbits. It is unlikely that the technology will be that advanced. There are however non-factoring based cryptosystems that are not as of yet known to be vulnerable to quantum computing. Unfortunately, we're a long way from proving that. The claim that there exists an encryption system which is not breakable by a quantum computer is a claim which is much harder than P != NP (you are in fact making a claim that us substantially stronger than NP not being a subset of BQP which many people aren't even sure they believe). In fact, even the existence of encryption secure against classical computers requires believing claims which imply P != NP. Moreover, if one starts implementing other encryption systems that aren't as widely studied as things like RSA one opens up the danger that those encryption systems have their own flaws as well.Also, at a practical level, there's very likely not going to be someone who is going to be recording all your RSS sessions on the offchance that they can decrypt them thirty years down the line. But if you really care then use one variant of elliptic curve cryptography. http://en.wikipedia.org/wiki/Elliptic_curve_cryptography. ECC systems are well-studied and have implementations. The people who study these sorts of things seem to think that ECC is one of the systems that is more likely to not be unable breakable by quantum systems.

What world do you live in?

[slaad]

I'd estimate that there's a 10% chance RSA will be useless within 20 years. Whatever the odds, some of the data we send over ssh and ssl today should remain private for a century, and we simply can't guarantee secrecy anymore using the algorithms with which we have become complacent.

Maybe I'm just paranoid, but I pretty much assume that every algorithm that we have now could well be effectively useless in 20 years. And I would never presume to think any of them even has a chance of lasting 100 years, or even close to that.

Computers will get faster. Weakness will be found in algorithms. Any other number of things that no can predict might happen. It would be silly to assume things encrypted today, left untouched, would be safe in 20 years and completely naive to have even a sliver of hope they'd be safe in 100, quantum computers or not.

Re:Fine. You find an asymmetric primitive

[ewanm89]

Different sort of quantum computer, it can't do general computing or schors algorithm, it's more like a quantum calculator, relegated to very specific statistical calculations rather than generic 3 bit computing.