Topic: Quantum Computer vs Bitcoin - page 4. (Read 2486 times)

I couldn't agree more! no such thing!

The word "computer" has been changed by the transistor, integrated circuits, personal computers and the Internet. 50 years ago, the word "computer" had a lot more mystique and referred to a much broader class of systems. Today, the word "computer" refers to a very definite kind of system, the kind you're using to view this post. Prior to the rise of the digital computer, there were many types of computers, including mechanical computers and analog electronic computers. Analog computers are very efficient for specialized problem solving.

Quantum computers are best thought of as a very noisy analog computer. On a digital computer, we ask a question just once, and it either calculates the answer or hangs. On an analog computer, we pose a problem within the computer's domain and then we set it solving. Usually, the analog computation proceeds "directly" to the solution, that is, with a minimum of wait time. But the results of the analog computation are subject to limits of precision imposed by physical measurement - to get more digits of accuracy, you require finer measurement and more lossless action within the mechanism or circuit. For a quantum computer, we have the same measurement problem as with analog computers, plus the solutions it gives do not have the property that digital computers have - either correct or it hangs. Rather, the quantum computer will return a "distribution" of answers over repeated computations that hopefully clusters tightly around an average value, which we take to be the solution.

Imagine you're a physicist running simulations on some difficult problem of physics. Your options:

- Build a digital simulation (requires a lot of programming). Once finished, set the simulator running and walk away. When you come back, either the simulator will have solved your problem (exactly) or it will have hung.

- Build an analog simulator. You have to build a new simulator for each problem domain you want to solve. It also requires high-precision parts and cannot perform simulations to the level of precision of a digital computer. But, once built, it's much faster than a digital computer.

- Build a quantum computer. This also requires a lot of programming but you don't have to build a new quantum simulator for each problem domain since quantum computers are "general-purpose". It requires high-precision parts and other exotic measures to prevent "decoherence" (a problem that other computers do not have). It can, in principle, perform simulations to the level of precision of a digital computer but each "run" of a quantum computer is random, meaning, you don't get "the answer" on any particular run of the computer, you must run the problem repeatedly and take the average on the output. This makes quantum computers quite different from either analog computers or digital computers.

I just read about Quantum Computer on google. But honestly, I didn't get a clear picture. Can anybody help me out here with some simple words? I read the replies on this thread as well. But everybody is using "fake science" or similar words. What is the reality here?

I just think that the relationship are directly proportional.  To be more specific, if Quantum Computers evolve to common use, the security encryption will also evolve to match.  The quantum computing technology is not one faceted, meaning it's not only for breaking encryptions, it can be used to create more sophisticated levels encryption.

That's why abutingting's argument is a non sequitir. QC is not a direct threat to Bitcoin for a variety of reasons - the cost of quantum computing is a part of the reason that FUD about QC is ridiculous, but not because anyone is being "priced out" of quantum computing.

Well, but goverments, Google, Microsoft, all of them can use quantum computers.

These could be added to Script as new opcodes and you can use P2WSH to implement a smart-contract that uses them.


You can use a script to hash-lock a transaction multiple times over. This would not really add any security, however, it would just be a silly way to subsidize miners with needless transaction fees.

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

@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.

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.


Don't get me started...

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?


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.

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.

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).


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).


Bingo.

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

A few nits:


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.)

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.

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).

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.

Translation:


 

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"?

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