20 sats \ 2 replies \ @TwoLargePizzas 14 Nov \ on: Why does hashing public keys not provide "any" quantum resistance? bitcoin
Sure, maybe. But there's still some fundamental assumptions built into this.
First of all, quantum computers are not magic. They can theoretically do things faster than classical computers but they're still bound by physical time constraints.
Using Grover's Algorithm for searching unsorted databases has quadratic speedup compared to classical computers. When applied to breaking SHA-256, Grover's algorithm would theoretically take around 2^128 / 4 ≈ 2^127 steps on a quantum computer.
The exact time it takes for a single step depends on the specific implementation and hardware of the quantum computer. For today's early-stage machines, each operation might take microseconds to milliseconds.
With those speeds, breaking SHA-256 would still take a very long time:
- At 1 microsecond per operation: ~300 years
- At 1 millisecond (0.001 second) per operation: ~90,000 years
These are rough estimates and don't account for the significant overhead of error correction, control systems, and other aspects needed to make a large-scale quantum computer work reliably.
So yes, while quantum computers can do it significantly faster than classical computers we're still talking about huge numbers.
Yaa but I think breaking hash functions (SHA-256) is fundamentally different from breaking ECC or RSA.
I still have a question that I don't have an answer to: if ECC and RSA could be broken with the advent of quantum computers, what makes hash functions remain secure?
reply
deleted by author
reply