Hacker News Reader

Comment by tnash | Hacker News Reader

At what point do we no longer trust public key cryptography (RSA)? Where's the break point?

If I remember correctly, it takes a quantum computer with roughly 2N qubits to break N-bit RSA. So we should be ok until thousand-qubit systems are being developed.

Increasing key lengths is a short-term workaround, but the real solution is post-quantum public key encryption, which is currently an area of active research.

Do you know what the implications are for symmetric ciphers or [elliptic curve] Diffie-Hellman key exchange? I.e. will forward secrecy still hold up against such future quantum computing?

The implication for symmetric ciphers is that key lengths will need to be doubled. 128-bit ciphers like standard AES have 64-bit security against a quantum attack. I expect to see 256-bit keys adopted widely in the not-too-distant future.

I don't know off the top of my head what the implication for key exchange would be, but I know that anything that depends on the discrete logarithm problem for security is vulnerable to a quantum attack. I believe that includes all forms of Diffie-Hellman.

With a quantum computer and Grover's algorithm, 128-bit AES is breakable in 2^64 steps. But the quantum computer still needs to have a 128-bit quantum memory.

I’m not sure if you mean to be disagreeing here or simply adding color, but what you’re saying is the same as the parent comment. Grover’s algorithm allows symmetric key recovery for n bits in 2^(n/2) steps; as the parent commenter said, symmetric algorithm key sizes need to be doubled. A break in 2^64 steps is the same as 64-bit security, so changing the key size to 256-bit will offer 128 bits of security.

Just wanted to clarify that in this case, 64-bit quantum computer is not enough to break said 64-bit security, still need 128 bits of memory.

SIDH (https://en.wikipedia.org/wiki/Supersingular_isogeny_key_exch...) is one of the few popular post-quantum variants of DH key exchange, and it supports forward secrecy as well.

One nice property of ECC pubkeys is that they easily fit into UDP packets, URIs and other very compact data structures. Currently all post-quantum schemes have fairly bulky pubkeys.

SIDH keys are 330 bytes long when compression is used, so they too will fit nicely into network packets.

> It is estimated that 2048-bit RSA keys could be broken on a quantum computer comprising 4,000 qubits and 100 million gates. Experts speculate that quantum computers of this size may be available within the next 20-30 years.

https://www.entrust.com/wp-content/uploads/2013/05/WP_Quantu...

The paper is from 2009, so ~2030 to break 2048-bit RSA seems about right. If they can double the number of qubits every two years, then we should have:

100-qubit by 2020.

200-qubit by 2022

400 qubit by 2024

800 qubit by 2026

1600 qubit by 2028

3200 qubit by 2030

6400 qubit by 2032.

It's also possible the rate of progress will be slightly higher than 2x every 2 years, so doing it a few years sooner than that is not out of the question.

Also, you have to consider that once you get a quantum computer that can break 2048-RSA, you'll be able to break all the encrypted communications you've stored in the past few years, too. So you can't "switch-on" the quantum-resistant crypto in 2031 and think you're all good. You have to do it as soon as possible, especially after practical quantum computers that are capable of scaling in a scheduled way start appearing (which seems to have happened).

Plus, even if Google is super-quick to adopt quantum-resistant crypto, doesn't mean the rest of the internet will be, too. It could take a few more years for that to happen, too.

From the Wikipedia timeline[1], it seems to be growing linearly.

1 - https://en.wikipedia.org/wiki/Timeline_of_quantum_computing

To quote my thesis advisor's terrible joke: "Everything's linear to first order"

Not too long ago I summarized every datapoint in that page. It is almost perfectly linear (there's 1 qubit lower somewhere, 1 qubit higher elsewhere), the noise is way lower than anything I was expecting to see.

>Also, you have to consider that once you get a quantum computer that can break 2048-RSA, you'll be able to break all the encrypted communications you've stored in the past few years, too

isn't that what PFS is supposed to prevent?

PFS can slow it down a bit, but not much. Assuming before PFS everyone changed their keys every 3 years, and with PFS they change them every 2 weeks, then it should be about 80x harder (slower to break the encryption). 80x harder may seem like a lot but it's not that much in the context of quantum computers.

Also, PFS uses 256-bit ECC, which only requires a 512-qubit quantum computer to break it. So it's possible that a 4,000 qubit quantum computer, or even a smaller one, could break ECC with PFS even faster than it can break 2048-bit RSA.

> Also, PFS uses 256-bit ECC, which only requires a 512-qubit quantum computer to break it.

Grover's algorithm is a quadratic, not exponential speedup. It may require 512 qubits, but it still requires 2^128 time.

ECC is vulnerable to Shor's algorithm, which gives exponential speedup. A rough calculation implies that 256-bit ECC would take on the order of 25k quantum operations to break.

You have to divide the qubit count by 100 to account for error correction.

It's interesting to imagine what connected planet with no reliable encryption would be like.

Although I guess we can always fall back on one-time pads.

Quantum computers don't break all encryption. There's no risk of that, fortunately.

Please expand on that. What encryption is vulnerable and what isn't?

I don't know a lot about it, only just enough to know what search term to look for, and Wikipedia had an article that probably fits the bill: https://en.m.wikipedia.org/wiki/Post-quantum_cryptography

Non-mobile link:

https://en.wikipedia.org/wiki/Post-quantum_cryptography

Symmetric encryption will need to double key lengths, such as using 256-bit AES keys instead of 128-bit.

All currently popular forms of asymmetric / public key encryption (including RSA and ECC) are vulnerable to quantum attack.

Reply on news.ycombinator.com