42

You have a good discussion in: https://bitcointalk.org/index.php?topic=133425.0 Basically, ECDSA is compromised, hashing isn't. With a quantum computer, you could easily deduce the private key corresponding to a public key. If you only have an address, which is a hashed public key, the private key is safe. Anyway, to spend a transaction, you need to send ...


29

Although hashing a public key by itself does provide quantum resistance, this is really only when it is considered by itself in a vacuum. Unfortunately, public key hashes do not exist in a vacuum and there are many other things in Bitcoin that need to be considered. Firstly, if public keys were hashed, the funds are only protected before they are spent. As ...


19

Worst case scenario: Bitcoin ECDSA algorithm would be broken. Because quantum computers can easily decrypt the private key using the public key, anyone with a quantum computer can extract Bitcoins using the corresponding public key. Bitcoin hashing would become exponentially difficult. There's already a predicted escalation in mining difficulty due to the ...


12

No, ECDSA and EC-Schnorr, as well as related schemes like EdDSA, all belong to the class of elliptic curve cryptography. Their security is based on the assumption that the EC discrete logarithm is unfeasibly hard to compute. This assumption is not true if a sufficiently strong general purpose quantum computer would exist. Quantum resistant signature ...


8

asymmetric ciphers Ones based on specific primitives, like RSA and ECDSA specifically. Symmetric algorithms are supposed to be safe. With approximately half the number of bits of security due to Grover's algorithm. Which components of the bitcoin blockchain would be exposed to quantum attacks? The security of SHA256 would be halved, ECDSA would be ...


6

There are two different things here: D-Wave machines ARE ASICs. They only solve certain particular problems. It is not really clear they take advantage of quantum effects or that they perform better than a classical ASIC working on the same problem would. In any case, they would be quantum ASICs, not general purpose quantum computers. Mining can be ...


6

No. CoinJoin does not rely on any cryptography to hide transaction flows. It merely combines multiple transactions into one, and randomizes the order of inputs and outputs. Of course, as you point out, quantum computing would allow stealing ECDSA outputs...


5

We're deep in speculative territory here but, theoretically, if the elliptic curve algorithm were broken the entire Bitcoin system would immediately collapse. Let's consider the case where you've successfully guarded your own funds somehow. How many public keys would still be out there vulnerable to such an attack? Even though your "base" survived the ...


5

The block halving takes place every 210,000 blocks. The difficulty retargeting mechanism makes it so that 210,000 blocks take approximately 4 years, but this is not exact. If the hashrate is rapidly growing, it will take a little less than that. For example, if the total network hashrate doubles every year, it will take about 1 month less. If it doubles ...


4

SHA256 is used primarily for "proof of work" The concept originated as a way to prevent email spam, oddly enough. https://en.wikipedia.org/wiki/Hashcash Hashcash is a proof-of-work system used to limit email spam and denial-of-service attacks, and more recently has become known for its use in bitcoin (and other cryptocurrencies) as part of the ...


4

This particular response is approximately tripe. Building on Pieter Wullie's comment. find an appropriate post-quantum DSA and it might push the the time to make Bitcoin quantum-secure from 5-10 to 10-20 years, as much more research is needed. We really know what to do to make Bitcoin Quantum safe, there's been methods for doing hash based ...


3

Let me start by addressing the misconceptions in the posts you're quoting. DSA (and Schnorr) are inherently based on the discrete logarithm problem, which is vulnerable to (sufficiently powerful) quantum computers. As a result, there is no such thing as a "post-quantum DSA". DSA also doesn't have Schnorr's linearity property - if "linear DSA" means anything ...


3

Quantum computing isn't simply faster. It is entirely different. Some computations are massively faster on a quantum computer, and other are not faster at all. What has been demonstrated is meaningless: the "program" that was executed was in fact a randomly generated one, designed to be specifically hard on traditional computers, but easy on that specific ...


3

Yes, it uses a Winternitz OTS scheme. It is believed that Lamport signatures would still be secure against a quantum adversary. No merkle signature scheme used with IOTA for transactions, as the result of a number of design and security decisions, for instance, signature size. It was a conscious decision to not use a stateless merkle scheme like sphincs. So ...


3

If quantum computers become viable and the approach of factorization of numbers which has been theoretically presented works, this means that Bitcoin will have to use a different way of signing transactions as through the use of quantum computers, it becomes easy (only polynomial time required) to calculate a private key from a public key. Simply increasing ...


3

The simple explanation is that the attacks that quantum computing enables require information (the public key) that isn't available until after the first transaction is seen. Until the first transaction spending an output, all that is known is the hashed version of the recipient key (aka the address) which isn't enough to mount the attack. If fully ...


2

With the current mining difficulty classical computers need to do 2*10^21 SHA256D invocations in average to find a block nonce. A quantum computer would need to do 4.5*10^10 invocations, which is billions times "faster". This means that the answer is: It would be able to doublespend as many times as the quantum adversary wants.


2

I want to point out a quick possibly important point. As other answers have mentioned current implementations of Bitcoin could be compromised by a quantum computer. However, Quantum Computers do not solve all known classically hard problems and so any cryptography that is based on problems that are also difficult for a Quantum Computer to solve should work ...


2

The best thing I can imagine is running Grover's algorithm, which speeds up what would be an exhaustive search for a single solution among N input values to take only about the square root of N actual evaluations. Only very special problems, like factoring numbers, have better known quantum algorithms. If you imagine connecting a hypothetical quantum ...


2

The short answer is yes, provided the difficulty factor feedback loop (adjusted after 2016 (14*24*6) block awards which nominally maps to every two weeks for whatever next generation hardware gets used) remains stable, which it should from basic control theory 101. The reason has everything to do with mathematics and the convergence of the geometric series ...


1

First of all, it's important to note that Google's Sycamore has not (yet) processed any quantum algorithm, but instead has just proved that the quantum processor is capable of maintain quantum effects on all 53 qubits during operations. This is important because there's still controversy on if all quantum computers built to date exhibit real quantum ...


1

It is often said that if a bitcoin user uses addresses only once, then quantum computer cannot compromise their security since the public key is revealed only when the money are actually spent. There's no quantum computing algorithm that can easily find the pre-image of a hash. Therefore, single-use P2SH/P2PKH/P2WSH/P2WPKH addresses are safe. Its not so ...


1

This is basically an invalid question. It doesn't matter how you sign data. As long as you're using elliptic curve and (EC)DLP (Elliptic Curve Discrete Logarithm Problem), then a quantum computer should be (by definition, with Shor's algorithm) be able to break it. This is because signature verification requires a publicly available public key. If you have a ...


1

Signing of transactions in bitcoin is based on addition in elliptic curves, relatively easy to perform, like modular exponentiation (like in RSA), but hard to invert with a classical computer. In both cases, essentially the same quantum algorithm (Shor's algorithm) can be used to invert this operation on a quantum computer in polynomial time with high enough ...


1

In principle the Mastercoin protocol should be exactly as safe as bitcoin (which it uses as a back end) against the powers of quantum computation. However, there is one important difference. bitcoin addresses that were used at least once are not safe against quantum computers (look for example in this article by Vitalik Buterin). Since all Mastercoins were ...


1

Using Qubits doesn't automatically make everything faster. There are certain quantum algorithms that can only be run on quantum computers that take advantage of qubits. These algorithm's might be able to solve certain problems "faster" but not necessarily in linear terms -- that is, you wouldn't be able to say it did something ten, or one hundred, or one ...


Only top voted, non community-wiki answers of a minimum length are eligible