Quote from: haltingprobability on December 11, 2017, 04:07:56 AM

Quote from: tisata on December 10, 2017, 05:04:32 PM

I heard that Quantum Computer can destroy bitcoin.
Is it possible?

It's something that Bitcoin's designers need to keep in mind as a "tail risk".

Quantum computers reduce the effective security of our strongest cryptographic primitives (hashes, symmetric ciphers) by about half. That is, a 256-bit hash gives about 128 bits of effective security in a world where quantum computers are used for at-scale computation. 128 bits of security is pretty good security - searching 10³⁷ gives about a 10% chance of breaking a particular hash (finding the hash preimage). 10³⁷ is 10 quadrillion quadrillion quadrillion - that's more than a billion billion times the number of hashes performed by the combined hashpower of all Bitcoin miners in order to mine a block.

The hash address is only 160 bits but it still requires 256 bits of search to break, that is, address=RIPEMD160(SHA256(pubkey)) minus a few technical details. Once you get the pubkey, we typically assume that a quantum computer will easily recover the private key from the public key. However, quantum-resistant public key encryption is still possible. Because of its quadratic advantage (theoretical) over classical computers, we have to double the key space (note that this may more than double key size). IIRC, secp256k1 is 128-bits equivalent security which we have to cut in half in a quantum-computation world - effective security is 64-bits. While 64-bits is too small for securing a large asset (such as all bitcoins), note that each address is secured by 64-bits security. So the cost of breaking all addresses in the UTXO set is at least 64 * nUTXO where nUTXO is the number of unspent transaction outputs. In other words, even with a quantum computer, you still have to break each address separately, and there are a lot of addresses.

Finally, quantum computation will actually help Bitcoin more than it will hurt it. As QC's begin to approach sufficient complexity to be able to mount serious attack against Bitcoin's cryptographic primitives, they are going to force cryptographers to revise usage across many cryptographic applications - traditional banking, government communication and data-storage, military communications systems, and so on. Quantum cryptography offers the promise of new modes of communication that are not possible with classical communication channels. Perhaps you can secure your Bitcoin address with an entangled set of qubits such that only the holder of the originally entangled qubits can prove ownership of the address. So, Bitcoin should not be having FUD about QC.

Bitcoin also need to note an attacker maybe doesent need to brute the entire keyspace if shooting for one key ie rich wallet. What are the odds of hitting a key before the entire key space is bruteforced ?

Then theres cluster bruteforce - obviously nobody did that in a really madass large scale, at least not publicly yet. Are there even bencharks wha twould be possible? For example a botnet of really large server, 30x raids in a huge cluster. Since one of those boxes costs 50K plus, yeah one has to be serious - for that to happen the loot just has to be big enough and somebody will try.