Hacker News Reader

To my understanding, even with Shor's algorithm, RSA is quantum-resistant when applying sufficiently large numbers such that the quantum computer used to locate the prime must be "sufficiently larger", i.e. a cat and mouse game of sorts until some major breakthrough comes along. I agree with simply moving to Ed25519 and X25519/ML-KEM etc.

View on HN

well, it depends on the size of the quantum computer. of course you can make large enough RSA keys (depends whats your security margin/assumptions) but the problem is that the size/computational increase is exponential whereas the solving speed scales polynomially.

https://eprint.iacr.org/2017/351

The size/computational complexity of usage also only grows as a polynomial with RSA. But even with this in mind, a quantum computer that can crack in polynomial time is still problematic. While you can increase the key size, the operator of the quantum computer could enlarge his computer, a true cat-and-mouse game. Unlike the current situation where usage complexity grows as a polynomial, while cracking grows exponentially. This difference is the reason why we can pick key sizes where signing/decryption takes a millisecond while cracking it takes (presumably) billions of years.

Reply on news.ycombinator.com