Quote from: haltingprobability on January 02, 2018, 01:21:21 AM

Quote from: ArithmomanicVampire on January 01, 2018, 09:48:40 PM

Quote from: haltingprobability on January 01, 2018, 05:06:38 AM

Quote from: ranochigo on January 01, 2018, 03:18:12 AM

The current problem with ECDSA is that it is susceptible to attacks by quantum computer due to Shor's algorithm. This means that quantum computers can potentially crack ECDSA in a reasonable amount of time.

Shor's algorithm only provides quadratic speedup. That means that the approx. 256 bits of security of secp256k1 becomes approx 128 bits of security in a world of readily-available, at-scale quantum computing. I wouldn't call 2¹²⁸ brute-forceable "in a reasonable amount of time."

I think you're mixing up Shor's with Grover's.

https://en.wikipedia.org/wiki/Elliptic-curve_cryptography#Quantum_computing_attacks

Yes, thank you. Both provide quadratic speedup so I forget which is which. QC is not my field, I just see a lot of obvious misinfo and FUD on this forum and feel the urge to try to set the record straight as best I can.

Unfortunately, Shor's is stronger than just quadratic speedup: in the case of secp256k1 it transforms the roughly 2²⁵⁶ into roughly 256³. This writeup: https://arxiv.org/abs/quant-ph/0012084 while a bit technical, details what's going on under the hood, and how breaking RSA (integer factorization) and ECDSA (discrete logarithm) are just special cases of a more general principle.

Of course, the quantum computer to implement this will not be built for at least another decade, so we can relax for the time being