Hacker News new | ask | show | jobs
by placeybordeaux 3300 days ago
I was under the impression that ecdsa was potentially broken by quantum computers, but SHA-256 was not. Is that not the case?
1 comments

Yes, in theory. See https://en.wikipedia.org/wiki/Elliptic_curve_cryptography#Qu...

ECDSA is vulnerable to a modified version of Shor's quantum integer factorization algorithm. However, nobody on Earth is known to be close to producing such a computer. Adiabatic quantum computers like the ones produced by D-Wave are not known to be capable of running Shor's algorithm. See https://en.wikipedia.org/wiki/Adiabatic_quantum_computation

SHA-256 and hashing algorithms have no known quantum attack against them, but one could theoretically gain a sqrt(n) advantage in brute-force search using Grover's quantum search algorithm. https://en.wikipedia.org/wiki/Grover%27s_algorithm

Huh I knew that Grover's algorithm would yield speed ups in db searches, but apparently I didn't read the wikipedia article closely enough. It allows for inversion of any function in sqrt time!