Re:Resources are being utterly and completely wasted on mini...
by bdhe on Tuesday May 31, 2011 @12:33PM
(#2603247)
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?
Re:Resources are being utterly and completely wasted on mini...
by DavidSJ on Tuesday May 31, 2011 @02:33PM
(#2603833)
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.
Re:Resources are being utterly and completely wasted on mini...
by caf on Tuesday May 31, 2011 @08:43PM
(#2605350)
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.
Re:Resources are being utterly and completely wasted on mini...
by DennisP on Tuesday May 31, 2011 @12:03PM
(#2603101)
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.
Re:Resources are being utterly and completely wasted on mini...
by daviddoran on Tuesday May 31, 2011 @03:06PM
(#2603979)
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.
Re:Resources are being utterly and completely wasted on mini...
by regularfry on Wednesday June 01, 2011 @08:26AM
(#2606950)
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?
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.