Quantum Computer vs Bitcoin

[quantumcat]

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

No. Quantum theory is fake "science" and does not exist, nor do "quantum computers".

They don´t exist until they exist. BTW there are some projects out there that can kill bitcoin without the need for quantum computing.

Intriguing, what are those projects that can kill bitcoin?

[hatshepsut93]

After learning a bit more about Bitcoin I have a new question about theoretical attacks with quantum computer.

Public keys are generally hashed, so attackers can't use Shor's algorithm against an address that wasn't sending any transactions, but public key is included in transaction, so it gets exposed as soon a transaction is broadcast. If public key cryptography could be broken in seconds, would attackers be able to attempt to steal coins from any unconfirmed transaction by cracking private keys and broadcasting new transactions from the same address?

[ranochigo]

If public key cryptography could be broken in seconds, would attackers be able to attempt to steal coins from any unconfirmed transaction by cracking private keys and broadcasting new transactions from the same address?

There isn't any credible evidence that ECDSA could be broken using quantum computing in seconds. Even if it could and there is a negligible cost, nodes will not accept transactions with its inputs already spent by another transaction in the mempool.

[nullius]

After learning a bit more about Bitcoin I have a new question about theoretical attacks with quantum computer.

Public keys are generally hashed, so attackers can't use Shor's algorithm against an address that wasn't sending any transactions, but public key is included in transaction, so it gets exposed as soon a transaction is broadcast. If public key cryptography could be broken in seconds, would attackers be able to attempt to steal coins from any unconfirmed transaction by cracking private keys and broadcasting new transactions from the same address?

That’s a huge “if”.  Even if a practical quantum computer existed, what makes you expect it to break public key cryptography “in seconds”?  Please remember that even today, a security level of (say) 80 bits is considered far too weak; and yet, it is not something you should consider “broken in seconds”.  (Try to do 2^80 work, if you don’t believe me.)

But arguendo, assuming your “if”:  Well, then, yes, an attacker could race you to double-spend, or even mine his own block to double-spend your coins.  (I assume that an attacker equipped to break PK crypto “in seconds” could also have a big advantage over other miners.)  In that case, I would be very worried about Bitcoin security.  I would likewise be worried about the security of the entire Internet, the banking system, and everything else which would be totally shattered (worse than Bitcoin) in your scenario.  What would I do about my PGP keys?  My TLS?  My SSH?  Everything else?  Bitcoin would be one of the only things left with even a little bit of security.

I see that earlier, haltingprobability wrote me an excellent reply.  I should get back to that....

[arjun21]

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

[hatshepsut93]

That’s a huge “if”.  Even if a practical quantum computer existed, what makes you expect it to break public key cryptography “in seconds”?  Please remember that even today, a security level of (say) 80 bits is considered far too weak; and yet, it is not something you should consider “broken in seconds”.  (Try to do 2^80 work, if you don’t believe me.)

But arguendo, assuming your “if”:  Well, then, yes, an attacker could race you to double-spend, or even mine his own block to double-spend your coins.  (I assume that an attacker equipped to break PK crypto “in seconds” could also have a big advantage over other miners.)  In that case, I would be very worried about Bitcoin security.  I would likewise be worried about the security of the entire Internet, the banking system, and everything else which would be totally shattered (worse than Bitcoin) in your scenario.  What would I do about my PGP keys?  My TLS?  My SSH?  Everything else?  Bitcoin would be one of the only things left with even a little bit of security.

I see that earlier, haltingprobability wrote me an excellent reply.  I should get back to that....

I know that quantum computers are still mostly theoretical/at very early stages, so I wasn't asking if Bitcoin is in practical danger (I've read this whole thread), I'm just curious how it could work in theory.

There isn't any credible evidence that ECDSA could be broken using quantum computing in seconds. Even if it could and there is a negligible cost, nodes will not accept transactions with its inputs already spent by another transaction in the mempool.

Can attacker try to spawn some virtual nodes to slow down the propagation of original transactions and increase the chance of his own transactions reaching the miners faster?

[ranochigo]

There isn't any credible evidence that ECDSA could be broken using quantum computing in seconds. Even if it could and there is a negligible cost, nodes will not accept transactions with its inputs already spent by another transaction in the mempool.

Can attacker try to spawn some virtual nodes to slow down the propagation of original transactions and increase the chance of his own transactions reaching the miners faster?

I think it would be more worth it for the attacker to attempt a sybil attack.

It is possible for the attacker to spawn nodes under his control to capture and slow down the propagation but it isn't easy by any standards. The reference client only connects to a node per IP block and it would require a tremendous amount of IPs for the chance to be significant. If any other node is connected to the victim, the propagation would be too fast. The amount of time it takes to crack a key is still way too slow.

[hodlcoinfan]

an answer close to the truth might be "we don't know yet" but its fun to speculate!

[gargavaar]

So the general consensus is somewhere along the lines of "if quantum computing cracks Bitcoin, there will be bigger and more serious problems to worry about"?

[haltingprobability]

Security agencies and the US DoD have tech that is at least 30 years in advance of the stuff you buy on Amazon. Quantum was likely put into production for breaking RSA 2048 in the 1990's, which is why they stopped making such a big fuss. The fact that publicly available crypto is allowed to be freely shared should tell you it's all broken.

I suspect stuff like this is going.

I think we are doomed if this is indeed true. Am sorry for guys who trust earthly government as we know it. You are creating monsters in the name of government.
Powerful entity keeping secrets is DANGEROUS.

One day you will all understand. May be too late by then.

Translation:

FUD and the FUD have FUD that is at least FUD years in advance of the stuff you buy on Amazon. FUD was likely put into production for breaking RSA FUD in the 19FUD's, which is why they stopped making such a big FUD. The fact that publicly available FUD is allowed to be freely FUD'd should tell you it's all FUDDDD!!!11

I suspect FUD like this is going FUD.

I think we are FUD if this is indeed true. Am sorry for guys who FUD earthly government as we know it. You are creating FUD in the name of FUD.
Powerful FUD keeping FUD is FUD.

One day you will all understand. May be too late by then.

FUD!!!!!

 

[Shamie1002]

I don't think that any quantum computers could destroy bitcoins. It's almost a decade and all that they can do is copy and enhance a specific feature to create new coin. If bitcoin can be destroyed, maybe it was done already and alts are never called as alts anymore.
My opinion it quite through objective and observation.

With some of what I have read and my understanding. Quantum computers are becoming huge ten years from now that would give higher risks to bitcoin. The elliptic curve signature scheme used by bitcoins can be broken or cracked by that time.
But as also said, bitcoin has another security feature called public key scheme wherein protocols itslef can be revised to safer usage though there is no such steo for it as we have seen.

There are no guarantees and future might bring us intense situations that is why we need resolutions as early as possible. I hope that we won't wait for that time to happen before taking an action. Just like today by slow transactions and high fees.

[haltingprobability]

So the general consensus is somewhere along the lines of "if quantum computing cracks Bitcoin, there will be bigger and more serious problems to worry about"?

Pretty close. Here are the facts:

1) Quantum computing (QC) is really hard. It's not just easy-in-theory-but-hard-in-practice, it's theoretically and practically hard. This is why there has been, to date, no definite demonstration of quantum speedup and this is why the quantum-skeptics in the thread are saying, "Quantum is a conspiracy, it's science made up by the government."

2) QC, when we do get it working, will not provide exponential speedup.

3) For certain kinds of problems, QC can provide quadratic speedup, which is a massive speedup. For symmetric ciphers, this probably just means you double your key size - where 128 bits of security used to be sufficient, now you need 256. No big deal. The real problem is with public-key encryption. But lay-people often forget that the quantum speedup blade cuts both ways. We can build encryption systems which take advantage of quantum speedup and make quantum cryptanalysis of PKE quadratically more difficult, mooting the theoretical advantage that cryptanalysts get from quantum speedup. In fact, this is why Bitcoin uses the public-key hash instead of the public-key itself and recommends against address-reuse; in the event of working, at-scale QC, your coins are still secured behind 128-bit-equivalent security as long as you don't reuse addresses or publish the public-keys for your addresses.

4) The most valuable uses of QC will not be for breaking encryption unless you're the military, in which case, you more or less don't care about civilian encrypted traffic. Even in the worst-case-conspiracy-scenario where the government has had quantum computers for decades, or whatever, it is highly unlikely that this immensely valuable equipment would be used to steal your $3,786 worth of Bitcoin. A civilian breakthrough in QC will result in a flurry of cryptographic updates to bring popular public-key encryption systems up-to-date. But even if a working QC with, say, 128 qubits were announced tomorrow, the initial applications of this QC would go to sciences like aerodynamic modeling (auto + aircraft fuel efficiency), traffic modeling (metropolitan commute + traffic efficiency), financial modeling (stock price predictions), medical research (drug development + protein-folding + cell modeling), and so on. Breaking HTTPS would be very far down on the list of priorities of anyone with enough disposable cash on hand to actually purchase and operate QC hardware. And we know that QC will be expensive because of point (1).

[haltingprobability]

I know that quantum computers are still mostly theoretical/at very early stages, so I wasn't asking if Bitcoin is in practical danger (I've read this whole thread), I'm just curious how it could work in theory.

Quantum computing could, in theory, make a 51% attack into a 25% attack, if you can find a way to use a QC to provide a quadratic speedup in mining. If this happens, the network difficulty will be adjusted accordingly and miners will be forced to transition to quantum mining equipment.

The main attack vector, however, is through public keys (address reuse). If you reuse a Bitcoin address, the public key for that address is published to the world and anyone can try to reconstruct your private key from your public key. With current computers, secp256k1 gives about 128-bits equivalent security, if I'm not mistaken. So, with a quantum computer, this becomes a 64-bits search space, which is small by modern standards (even though 2⁶⁴ is more than a billion billion, an enormous number). Every reused address is susceptible to key-search in about 2⁶⁴ time with a QC.

[nullius]

haltingprobability, thank you for your informative overview of the sitation.

A few nits:

In fact, this is why Bitcoin uses the public-key hash instead of the public-key itself and recommends against address-reuse; in the event of working, at-scale QC, your coins are still secured behind 128-bit-equivalent security as long as you don't reuse addresses or publish the public-keys for your addresses.

0. Actually, that would be 160-bit equivalent security, yes?

1. As a general point, I will worry about disclosing Bitcoin public keys at the same time I start to worry about disclosing my long-term PGP public key.  (For those in the peanut gallery:  The latter would be entirely useless without public disclosure.)

There are excellent reasons to avoid address reuse; but this is not one of them.  I say this as a paranoid security nut:  The security of publicly disclosed public keys is just fine.  That is why they are called public keys.  The only exception I would here make is if you have coins which you intend to potentially leave in cold storage for decades.  Then, yes, you will want the extra security margin of the key being unpublished.  That’s not only a concern about quantum computers:  Unexpected cryptanalytic techniques could develop over the course of many years.  For cryptography which really needs to stand the test of time, reducing your security requirements to a hash is simply good security hygiene.  (For the same reason, I want to switch from the trust anchoring of my “nullius” nym from Ed25519 to Lamport signatures; I simply need to find or build a readily available, reasonably usable, long-term stable implementation.)

[haltingprobability]

haltingprobability, thank you for your informative overview of the sitation.

A few nits:

In fact, this is why Bitcoin uses the public-key hash instead of the public-key itself and recommends against address-reuse; in the event of working, at-scale QC, your coins are still secured behind 128-bit-equivalent security as long as you don't reuse addresses or publish the public-keys for your addresses.

0. Actually, that would be 160-bit equivalent security, yes?

No, because the Bitcoin address is RIPEMD160(SHA256(pubkey)), with some additional protocol things tacked onto it. If you can find some reduction of SHA256 to RIPEMD160 such that you can recover any SHA256 preimage more or less for free from the RIPEMD160 preimage, then it would be 160-bit equivalent security. The 128-bit number comes from dividing 256 by two on the assumption that the best way to brute-force a Bitcoin address with a QC is to break the RIPEMD160 (I'm counting this as zero-cost) and then break the SHA256 (I'm counting this as 256-bit / 2 security = 128-bits security).

1. As a general point, I will worry about disclosing Bitcoin public keys at the same time I start to worry about disclosing my long-term PGP public key.  (For those in the peanut gallery:  The latter would be entirely useless without public disclosure.)

Mostly agreed. AFAIK, no one has ever shown any evidence that a PGP public key has ever been brute-forced to its private key. I would imagine that the NSA may have built equipment capable of doing that, among other things, if for no other reason than for research purposes, to probe the limits of what's possible (because, the Russians, of course).

There are excellent reasons to avoid address reuse; but this is not one of them.  I say this as a paranoid security nut:  The security of publicly disclosed public keys is just fine.  That is why they are called public keys.  The only exception I would here make is if you have coins which you intend to potentially leave in cold storage for decades.  Then, yes, you will want the extra security margin of the key being unpublished.

Bingo.

[nullius]

Translation:

FUD and the FUD have FUD that is at least FUD years in advance of the stuff you buy on Amazon. FUD was likely put into production for breaking RSA FUD in the 19FUD's, which is why they stopped making such a big FUD. The fact that publicly available FUD is allowed to be freely FUD'd should tell you it's all FUDDDD!!!11

You forgot the fearsome new technology of Quantum FUD®.  With Quantum FUD® technology, the quantum computer will use quantum tunnelling teleportation to sneak into your house, eat all the cookies you left out for Santa, spray-paint graffiti all over your walls, ravish your spouse, and then sit down at your computer and send all your bitcoins to 1BitcoinEaterAddressDontSendf59kuE.  But you will never even know it, because it will also use relativistic speed-of-light acceleration to compress you thinner than dollar bill, slow down your clocks, and produce a paradox where you become your own grandfather (“hello, Mom!”).

With Quantum FUD® technology, the quantum computer will rewrite the blockchain; and also, it will rewrite the history of the entire universe multiverse.

The quantum computer with Quantum FUD® technology is insidious and subtle.  It is dangerous and terrifying to behold.  It is also a rather interesting shade of mauve.

Now that I know the truth about Quantum FUD®, I am scared.  I will now stay away from Bitcoin.  Also, I will avoid computers, sunlight, and breathing.  Thank you for informing me about this horrific existential threat to the Bitcoin.

Yeah, most of the Bitcoin FUD is ridiculous but the quantum FUD is particularly hard to stomach.

Quantum FUD®.  What a most excellent buzzword.

[nullius]

In fact, this is why Bitcoin uses the public-key hash instead of the public-key itself and recommends against address-reuse; in the event of working, at-scale QC, your coins are still secured behind 128-bit-equivalent security as long as you don't reuse addresses or publish the public-keys for your addresses.

0. Actually, that would be 160-bit equivalent security, yes?

No, because the Bitcoin address is RIPEMD160(SHA256(pubkey)), with some additional protocol things tacked onto it. If you can find some reduction of SHA256 to RIPEMD160 such that you can recover any SHA256 preimage more or less for free from the RIPEMD160 preimage, then it would be 160-bit equivalent security. The 128-bit number comes from dividing 256 by two on the assumption that the best way to brute-force a Bitcoin address with a QC is to break the RIPEMD160 (I'm counting this as zero-cost) and then break the SHA256 (I'm counting this as 256-bit / 2 security = 128-bits security).

I think I see what you mean.  I got wrong what I said in my “nit”; but I now have another.  Please correct me if I messed up something else here; I think that breaking a keyhash found on blockchain would require the following steps, in this order:

0. It’s impossible to recover 256 bits of pseudorandom anything from 160 pigeonholes; so I will infer that to be, find any P0 of the many 256-bit preimages for a given RIPEMD160 hash.  With a quantum computer, consider that to be the equivalent of an 80-bit problem.  Not what I would call zero.

1. Then, find a string P1 which is a valid secp256k1 public key, and is a SHA256 preimage for the SHA256 image P0.  I will wave my hands around various factors which make the search easier by expanding the search set (compressed or uncompressed public keys double the possibilities—but only if the output is not for a Segwit address) or harder (need a valid secp256k1 pubkey, not an arbitrary bitstring).  For the reason you stated, count this as the equivalent of a 128-bit problem.

2. Wield the almighty Quantum Computer to break the public key—thus revealing a private key which can spend for a public key which SHA256 hashes to a bitstring which hashes to the RIPEMD160 hash specified in the Bitcoin output.  Breaking the public key would still not be free.  I don’t know how to quantify that in “bits of security”.

So—I see the equivalent of 208+x bits of quantum computer work.  Did I get it right here?

Mostly agreed. AFAIK, no one has ever shown any evidence that a PGP public key has ever been brute-forced to its private key. I would imagine that the NSA may have built equipment capable of doing that, among other things, if for no other reason than for research purposes, to probe the limits of what's possible (because, the Russians, of course).

Even if they could, why bother to ever apply the fruits of that hypothetical research?  Endpoint security is so awful, and rubber hoses/$5 wrenches/long prison sentences are readily available.

That’s another point which should be well remembered by the people worried about hypothetical future post-quantum attacks on Bitcoin:  Malware, kidnappings, and similar attacks are the biggest vulnerability for the average user today.  Do you even know how to properly secure a computer against even the stupidest commodity s’kiddie coin stealer?  Do you brag about th size of your coin stash on Internet forums, under the doubly false presumption that both Internet posts and bitcoins be “anonymous”?  Don’t worry so much about threats which do not currently exist and may perhaps never exist, when shoot your own foot off every day.

[haltingprobability]

No, because the Bitcoin address is RIPEMD160(SHA256(pubkey)), with some additional protocol things tacked onto it. If you can find some reduction of SHA256 to RIPEMD160 such that you can recover any SHA256 preimage more or less for free from the RIPEMD160 preimage, then it would be 160-bit equivalent security. The 128-bit number comes from dividing 256 by two on the assumption that the best way to brute-force a Bitcoin address with a QC is to break the RIPEMD160 (I'm counting this as zero-cost) and then break the SHA256 (I'm counting this as 256-bit / 2 security = 128-bits security).

I think I see what you mean.  I got wrong what I said in my “nit”; but I now have another.  Please correct me if I messed up something else here; I think that breaking a keyhash found on blockchain would require the following steps, in this order:

0. It’s impossible to recover 256 bits of pseudorandom anything from 160 pigeonholes; so I will infer that to be, find any P0 of the many 256-bit preimages for a given RIPEMD160 hash.  With a quantum computer, consider that to be the equivalent of an 80-bit problem.  Not what I would call zero.

Approximately 2⁹⁶ SHA256 outputs map to each RIPEMD160 output (by the pigeon-hole principle). But the attack complexity of recovering the SHA256 preimage (the pubkey) is still 2²⁵⁶ bits of security. In other words, the RIPEMD160 step does not reduce the security of the system against recovering the pubkey. However, it does reduce the complexity of substituting another pubkey in its place (second preimage security) since you "only" have to search an average of 2¹⁵⁹ pubkeys to find one whose SHA256 hash collides with the RIPEMD160 hash:

RIPEMD160(SHA256(my_key)) = RIPEMD160(SHA256(attackers_key)) <-- brute-forcing this "only" requires 2¹⁵⁹ attempts on average

Now, you can reduce the complexity further by only attempting public keys with valid private keys (2¹²⁸ or so):

RIPEMD160(SHA256(priv_to_pub(my_priv_key))) = RIPEMD160(SHA256(priv_to_pub(attackers_priv_key))) <-- brute-forcing this "only" requires 2¹²⁷ attempts on average, however, priv_to_pub() is a very computationally expensive operation.

2. Wield the almighty Quantum Computer to break the public key—thus revealing a private key which can spend for a public key which SHA256 hashes to a bitstring which hashes to the RIPEMD160 hash specified in the Bitcoin output.  Breaking the public key would still not be free.  I don’t know how to quantify that in “bits of security”.

So—I see the equivalent of 208+x bits of quantum computer work.  Did I get it right here?

I think it's still about 128 bits search space because there are about 2¹²⁸ valid secp256k1 private keys. However, since there are 2¹⁶⁰ possible addresses, we are not guaranteed to find a collision - it is possible that a given secp256k1 private key has no other colliding Bitcoin address. But since it is a (pseudo)-random mapping, there are surely collisions (birthday paradox). If a given private key and its associated address have no collisions, the search time (not average) is 2¹⁶⁰ (you must exhaust all addresses to be sure); if 1 collision the average search time to find it is 2¹⁵⁹; if 2 collisions, the average search time is greater than 2¹⁵⁸; if 4 it is 2¹⁵⁸, and so on. I'm sure this could be written out as a sum using sigma notation if a person was determined to do so.

Endpoint security is so awful

Don't get me started...

[hatshepsut93]

@nullius, @haltingprobability

Thank you guys for your posts, I find it much easier to learn about cryptography and comp science from examples and discussions rather than just raw theory, and this is exactly the kind of replies I wanted to see when I posted my question.

Now, I got more questions.

1. Would it be possible and would it make sense to add more digital signature algorithms and more hash functions with various key/hash sizes?

For example, shorter keys, signatures and hashes would result in addresses that have smaller transaction sizes, so people could optionally use them to save up on fees. Longer keys, signatures and hashes would provide some additional security for paranoid people, at costs of higher fees.

2. RIPEMD-160 is not the only hash function in Bitcoin's Script, there's also SHA256. Does this mean that even now we can create our own P2SH outputs with more bits of security than the standard addresses that useRIPEMD-160?

P.S. To clear any possible misunderstanding - I'm not scared of QC, my questions are purely theoretical and discussions like this are helping me to get a better understanding of Bitcoin in general.

[abutingting]

Quantum computers is definitely not a threat to Bitcoin. These computers cost millions of DOLLARS and undoubtedly be able to spread.