3 ms·

Bitcoin is not quantum-hard. When quantum computing reaches a certain threshold, bitcoin will lose its uniqueness and collapse. There are post-quantum algorith

by api 15y ago

Bitcoin is not quantum-hard. When quantum computing reaches a certain threshold, bitcoin will lose its uniqueness and collapse. There are post-quantum algorithms that are computable on ordinary computers, but they're still under research and they'd make Bitcoin's data set considerably larger.

DennisP 15y ago
Bruce Schneier has written that quantum computers only halve the effective number of bits for symmetric encryption algorithms, which seem more closely analogous to hashing than factoring. That would be a giant leap in mining capability, but perhaps not so much as to cause collapse. Switching to 512-bit hashes would bring us back to where we are now.
bdhe 15y ago
Bitcoin is not quantum-hard. When quantum computing reaches a certain threshold, bitcoin will lose its uniqueness and collapse. Could you elaborate which aspect of bitcoin has efficient quantum algorithms? The proof-of-work system requires you to invert hashes and quantum algorithms only give you a quadratic speed up (brute force takes time O(\sqrt{size of range}) rather than O(size of range)). Right now there is no quantum attack on SHA-256 (which is what Bitcoin uses). There are post-quantum algorithms that are computable on ordinary computers, ... This sounds interesting, but could you elaborate? What does it mean for a post-quantum algorithm to be computable on ordinary computers?
- DavidSJ 15y ago
  Could you elaborate which aspect of bitcoin has efficient quantum algorithms? BitCoin uses public key cryptography for its digital signatures. That in turn relies on the difficulty of factoring large numbers, for which there are efficient quantum algorithms.
  - caf 15y ago
    Bitcoin actually uses ECDSA for its digital signatures, which relies on the difficulty of calculating discrete logarithms rather than factoring. However I believe that there are efficient quantum algorithms for that, too.
daviddoran 15y ago
Correct, however the Bitcoin website has an answer for that: upgrade. The cryptographic methods are not fixed for all time, we can switch to other methods (which are quantum-resistant) when it becomes necessary.
- regularfry 15y ago
  Assuming they are available and deployable at that time. It's like arguing against climate change mitigation because a technological solution will present itself: you might be right, but why gamble?

by api 15y ago

DennisP 15y ago

Bruce Schneier has written that quantum computers only halve the effective number of bits for symmetric encryption algorithms, which seem more closely analogous to hashing than factoring. That would be a giant leap in mining capability, but perhaps not so much as to cause collapse. Switching to 512-bit hashes would bring us back to where we are now.

bdhe 15y ago

Bitcoin is not quantum-hard. When quantum computing reaches a certain threshold, bitcoin will lose its uniqueness and collapse. Could you elaborate which aspect of bitcoin has efficient quantum algorithms? The proof-of-work system requires you to invert hashes and quantum algorithms only give you a quadratic speed up (brute force takes time O(\sqrt{size of range}) rather than O(size of range)). Right now there is no quantum attack on SHA-256 (which is what Bitcoin uses). There are post-quantum algorithms that are computable on ordinary computers, ... This sounds interesting, but could you elaborate? What does it mean for a post-quantum algorithm to be computable on ordinary computers?

DavidSJ 15y ago
Could you elaborate which aspect of bitcoin has efficient quantum algorithms? BitCoin uses public key cryptography for its digital signatures. That in turn relies on the difficulty of factoring large numbers, for which there are efficient quantum algorithms.
- caf 15y ago
  Bitcoin actually uses ECDSA for its digital signatures, which relies on the difficulty of calculating discrete logarithms rather than factoring. However I believe that there are efficient quantum algorithms for that, too.

daviddoran 15y ago

Correct, however the Bitcoin website has an answer for that: upgrade. The cryptographic methods are not fixed for all time, we can switch to other methods (which are quantum-resistant) when it becomes necessary.

regularfry 15y ago
Assuming they are available and deployable at that time. It's like arguing against climate change mitigation because a technological solution will present itself: you might be right, but why gamble?