Topic: quantum computing & BTC (Read 508 times)

Yes. Bruteforcing being the only known way to find the original input (in this case: the public key).



I wouldn't say "totally impossible", but right now we have absolutely no reason to believe that a quantum computer would be better at this task than a classical computer.

Note that the theory of quantum computing far precedes it's practical implementation so it's fairly well understood. Accordingly it's rather unlikely that a surprise solution breaking those specific cryptographic hashes will come out of nowhere.

By (b) you meant "finding the public key from BTC address", right?

And you said that it was totally impossible to perform even with quantum computer, right?

What do you mean by "why"?


Technically because we're talking about two completely different types of cryptography.

One is asymetric cryptography:
https://en.wikipedia.org/wiki/Public-key_cryptography

The other are cryptographic hashes:
https://en.wikipedia.org/wiki/Cryptographic_hash_function

Note that a weakness to quantum computing is neither inherent to asymetric cryptography nor to cryptographic hashes. Not all private / public key schemes are necessarily at risk and not all cryptographic hash functions are necessarily quantum resistant. There's a lot of cryptographic algorithms for either type of cryptography, based on different kinds of math problems; some for which quantum computing will provide little to no speed-up.


In terms of what satoshi intended -- who knows? The quantum algorithms in question have been developed in the 90s so it might well be that satoshi anticipated a possible quantum threat in the future.



*without knowing the public key, yes. At least according to our current understanding of mathematics.

@HeRetiK

So why private keys aren't linked to the public keys the same way public keys are linked to BTC addresses?

This will make impossible quantum computer to crack private key with knowing public key.

Oh quantum computing is already here. Matter of fact, you can have some fun with quantum computing today:

https://quantumexperience.ng.bluemix.net/qx/experience

It's just that it still has a long way to go before any of the currently known algorithms can be applied to cryptography in practice. To give some perspective, breaking ECDSA as used by Bitcoin is expected to require thousands of qubits [1][2]. Currently we're at the tens of qubits [3] (ignoring D-Wave quantum computers which follow a fairly different approach that isn't applicable to the sort of math problem that ECDSA poses [4]).

[1] https://security.stackexchange.com/questions/87345/how-many-qubits-are-needed-to-factor-2048-bit-rsa-keys-on-a-quantum-computer
[2] https://en.wikipedia.org/wiki/Elliptic-curve_cryptography#Quantum_computing_attacks
[3] https://www.quora.com/How-many-qubits-does-the-current-state-of-the-art-quantum-computer-have
[4] https://crypto.stackexchange.com/questions/40893/can-or-can-not-d-waves-quantum-computers-use-shors-and-grovers-algorithm-to-f



Deriving (a) the private key from a public key is a completely different operation from (b) bruteforcing the public key from its nested cryptographic hashes. While (a) may become feasible with quantum computing eventually, (b) appears to be infeasible even for quantum computers.



Capable of trying maybe, but not capable of succeeding.

If you'd try to brute force the Bitcoin address space -- and brute forcing is all you could do, given that there's currently neither a way to derive a private key from a public key nor a way to derive a public key from a BTC address -- you'll be engulfed by the sun turning into a red giant before finding even your first active private key (Timeframe for the sun turning into a red giant: 5 - 6 billion years [5]. Yearly chance of finding an active private key using the large bitcoin collider: approx 0.000000000000000000000000055% [6]). And that's just for finding a random private key, not a specific one.

Obviously that's based on the computational power we currently have available. However quantum computing is unlikely to have much of an impact on improving the odds of brute forcing a BTC address in practice, which is why the threat posed by quantum computing is one of mathematical prowess (ie. deriving the private key from a public key using what is essentially a computational shortcut) rather than one of brute force (ie. scanning Bitcoin's key space).

[5] https://en.wikipedia.org/wiki/Red_giant#The_Sun_as_a_red_giant
[6] https://bitcointalksearch.org/topic/m.48145266

in theory yes, you have to have the public key in order to brute force that private key from the public key.

but with that being said, the current computing power is also capable of doing so. technically you can brute force anything, even with a pen and paper you have a chance above 0% of getting the private key. but it's a merely a question of how hard and how much does it cost.

but in general if someone has the power to crack the private key from a public key, they would probably make more profit mining.

so honestly i do not see any threat coming from quantum computing . btw here is a nice read on the limits of qc >
 
http://www.cs.virginia.edu/~robins/The_Limits_of_Quantum_Computers.pdf

@HeRetiK

OK I learned that public key is not BTC address.

My BTC are stored on a BTC address which has never spent any BTC so I can sleep good at night even if quantum computing arrives.

However, can you derive public key from BTC address with Quantum Computing? I think the answer is no according to what HeRetiK said.

Very good point and probably one of the first things to remind people who talk about the quantum computing threat. Yes, it's a threat, but not one that is present. By the time there is a such a computer capable of cracking a Bitcoin private key, it's a very solid assumption to say that Bitcoin by then would have adopted superior algorithms. It's the nature of tech and cryptography to stay ahead of the curve, and there's every reason to believe Bitcoin will stay far, far ahead of that.

And if that doesn't happen, then the very simple solution of single-use addresses for spending nullifies that threat.

The BTC address is not the public key. It's the RIPEMD-160 hash of a SHA-256 hash of the public key, including some bits of error correction and encoded as Base58 [1]. The public key is not published until the first outgoing transaction is made from a BTC address [2], since only then the public key becomes necessary to validate the transaction.

Modern P2SH and Bech32 addresses and transactions work slightly differently, but in either case the public key is not published until an outgoing transaction is made. SHA-256 appears to be not especially vulnerable to quantum computing [3] (ie. quantum computing does not offer any advantage over classical computing for the subset of mathematical operations required for SHA-256); I think the same holds true for RIPEMD-160 but I'm not sure.

Accordingly a BTC address only becomes potentially vulnerable to quantum computing once the first outgoing transaction has been made, since in either case the public key is not known prior to that transaction.


[1] https://en.bitcoin.it/wiki/Technical_background_of_version_1_Bitcoin_addresses
[2] https://en.bitcoin.it/wiki/Transaction
[3] https://crypto.stackexchange.com/questions/59375/are-hash-functions-strong-against-quantum-cryptography-and-or-independent-enough

Actually, a company called d-wave is selling 2000 qubit computers. However, the applications that it is good for would not be suitable for cracking algorithms. Also, the majority of the qubits have to be used for error correction due to quantum decoherence. There are other challenges with quantum computing as well. Also, the ECDSA can be changed, however; old coins sitting in "legacy" address may still be redeemable. If Satoshi never moves his coins, the ~ 1 million coins recovered could pose a problem. However, I doubt that quantum computing will become a reasonable threat in the near future. Maybe a few decades from now. This should give the BTC dev team plenty of time to come up with a solution.

Common misconceptions are that quantum computers will be the end of Bitcoin. That's untrue and the only thing quantum computers break is the ECDSA algorithm that Bitcoin currently uses. Please note that I said "currently" indicating that we could possibly change to a quantum resistant algorithm in the future which already exist and several products are already using such a algorithm. Ok so why haven't we changed yet? There's is no need to as quantum computers are far off from becoming a threat. I think the best quantum computer out there right now is 5 qbits and thousands qbits are needed to pose a threat to the algorthim. I'm planning on writing a thread which will go into a little more depth about this soon. Quantum computers are very effective at certain things such as exploiting rules in quantum mechanics that traditional computers cannot access. They are very good at soling specific mathimatical problems e.g factoring integers. However this doesn't mean that they are efficient in all areas.

Yes. It's true that you can deprive a private key from a public address using a quantum computer. But we are very far off achieving this with quantum mechanics. Currently as mentioned before the most powerful quantum computer is around 5 qubits right now. However it would require several thousand for it to become a threat to EDSCA. By then I like to think that we would have either moved to a quantum resistant algorithm by then.

@HeRetiK

Once you get private key, You get the BTC on the public address.

If quantum computing takes 6 months to derive my private key from my public key and I leave my BTC on this public key (BTC address) during this time duration of more than 6 months. My BTC get stolen.

So will we need to constantly make transaction in order to move BTC from a public key to another?

Quantum has a long way to go before you need to start to worry about this playing out IRL.

They are still trying to work out the qubit's and the size of the machines fill rooms so no need to panic yet.

This will depend on how effective a quantum computer will be at deriving the private key from its respective public key.

The first viable quantum attacks on Bitcoin's public / private key cryptography will probably still take days, weeks or even months to derive the private key from a public key. At this point address reusage will become a serious security risk; however one time usage of an address should still be fine for the most part.

The attack you describe (ie. in-flight, during an outgoing transaction) would become a risk once quantum computing reaches an effectiveness that allows deriving the private key within a block interval (ie. within minutes or even seconds, rather than days). At this point each Bitcoin transaction as we know it would be at risk of being diverted in an unprecedented form of double-spend attack (ie. one that requires no hashing power and allows you to double-spend someone elses coins, rather than only your own). Needless to say this would render Bitcoin useless.

However we're still very far from the first scenario, let alone the second. For all we know reaching even the first scenario could still take 10, 20 years, if we even see it come to fruition at all. Either way Bitcoin will likely have sufficient time to switch to a quantum resistant private / public key encryption and / or transaction scheme before any such attacks become close to viable.

1) Basically the amount of adresses that can be generated are infinite (Well, not exactly infinite, 2^160(i think it was??)). Any wallet such as Bitcoin core/Electrum can simply generate a new private key -> public key -> adress.
https://en.bitcoin.it/wiki/Technical_background_of_version_1_Bitcoin_addresses


Yes. If you make an output to adress X with 1 BTC and to adress Z with 0.5 BTC, from adress Y holding 1.5 BTC,they will indeed be different UTXO’s.

2) I’m not an expert on this. The only thing i do know is that, once you broadcast a transaction,the public keys of the adresses belonging to the UTXO’s that are being spend become known. How and when in this process quantum computing will make use of this to bruteforce your privatekey, i have no clue.

1) So how is it possible for some wallet online or hard wallet to give a new address for every transaction?
Does this mean that the BTC sent to those address are separated?

there is something as a general key for a wallet called " ECDSA public key"

2) But if you use even one time your public key, this is as risky as you use it several time. Because you display it. I think that cracking with quantum computing is done during transaction. don't you think?

1) You can't? You'll need to use a wallet that'll generate a new adress every time you want to receive coins. I don't think that's possible with any paper wallet as the entire idea of a paper wallet is having 1 adress...?

2) The theory is, (correct me if i'm wrong) that it'll need your public key to do so, (cracking the privkey) which is always made public after you signed/broadcasted a transaction from said adress.
Afterall, your adress is simply a one-way hash..

3) https://en.bitcoin.it/wiki/Quantum_computing_and_Bitcoin
There's some other threads about this, too. https://bitcointalksearch.org/topic/is-quantum-computing-threat-to-bitcoin-4266048

Hello,

I found out that maybe one day, it will be able to find private key from a public key using quantum computing (around 2030)

1) it is said that using several time the same BTC address is risky. I am using a paper wallet with a unique address. How can I use another address with the BTC arriving on the same paper wallet?

2) I have heard that quantum computing will be able to acted for craking a public address ONLY during the transaction process? is it true or not?

3) except making the public address more heavy, what are the options for BTC to be saved from quantum computing?

Thanks for your help.