Quantum Computing and Bitcoin

[8CommaClub]

If Quantum Computing is released into the wild and starts to attack bitcoin , what measures would we see to mitigate these attacks?

[1714148656]

1714148656

[1714148656]

1714148656

[1714148656]

1714148656

[bones261]

Hope some miners can also get a quantum computer to compete with mining and switch to an algorithm for the keys that would take the QC longer than it's expected Quantum decoherence time by a factor of billions upon billions.

[8CommaClub]

I

If Quantum Computing is released into the wild and starts to attack bitcoin , what measures would we see to mitigate these attacks?

Hope some miners can also get a quantum computer to compete with mining and switch to an algorithm for the keys that would take the QC longer than it's expected Quantum decoherence time by a factor of billions upon billions.

What if the government controls the Quantum computer , and there isn't anyone to fight back? Would that spell the end of Bitcoin? And if there is , would it be necessary to move to QC resistant cryptography?

[bones261]

I

If Quantum Computing is released into the wild and starts to attack bitcoin , what measures would we see to mitigate these attacks?

Hope some miners can also get a quantum computer to compete with mining and switch to an algorithm for the keys that would take the QC longer than it's expected Quantum decoherence time by a factor of billions upon billions.

What if the government controls the Quantum computer , and there isn't anyone to fight back? Would that spell the end of Bitcoin? And if there is , would it be necessary to move to QC resistant cryptography?

Back to the drawing board. If any entity gets control of 51% of the mining and there is no way to wrest back control, then Bitcoin is insecure and virtually worthless.

[8CommaClub]

I

If Quantum Computing is released into the wild and starts to attack bitcoin , what measures would we see to mitigate these attacks?

Hope some miners can also get a quantum computer to compete with mining and switch to an algorithm for the keys that would take the QC longer than it's expected Quantum decoherence time by a factor of billions upon billions.

What if the government controls the Quantum computer , and there isn't anyone to fight back? Would that spell the end of Bitcoin? And if there is , would it be necessary to move to QC resistant cryptography?

Back to the drawing board. If any entity gets control of 51% of the mining and there is no way to wrest back control, then Bitcoin is insecure and virtually worthless.

if this did happen and bitcoin did bring down the banks , so there is no "currency" system , i wonder what would come next.

[ABCbits]

ECDSA/secp256k1 is quantum-resistance as long as it's public key isn't known, which means users should be fine as long as they never re-use their Bitcoin address and Quantum computer isn't fast enough to find out it's private key before the transaction got confirmed/fully propagated to all nodes.

But there are proposal to use cryptographic signature which is quantum resistant, even though AFAIK there's huge trade-off such as far larger signature size and longer verification time.

[bones261]

ECDSA/secp256k1 is quantum-resistance as long as it's public key isn't known, which means users should be fine as long as they never re-use their Bitcoin address and Quantum computer isn't fast enough to find out it's private key before the transaction got confirmed/fully propagated to all nodes.

But there are proposal to use cryptographic signature which is quantum resistant, even though AFAIK there's huge trade-off such as far larger signature size and longer verification time.

I think if we are at the point in technology that a QC can be made that can break SHA256 in a relatively trivial manner, "ordinary computers" and network technology will be at the point that a larger signature size wouldn't be a problem either. Or are we still going to be fretting that someone's raspberry pi that they bought in 2009 should still be able to run a full node while only connecting with a 56K modem?

[tromp]

I think if we are at the point in technology that a QC can be made that can break SHA256 in a relatively trivial manner

Wrong; quantum computers need to run for 2^80 steps to find a private key mapping to a given 160 bit public key. That will remain infeasible for decades to come.

[mixoftix]

I think if we are at the point in technology that a QC can be made that can break SHA256 in a relatively trivial manner

Wrong; quantum computers need to run for 2^80 steps to find a private key mapping to a given 160 bit public key. That will remain infeasible for decades to come.

however the threat of QC is 51% attack, not directly breaking the key-pairs but while cryptographers think in probability space (2^80) of breaking something secure (in theory), there are Cryptanalysis methods out there to find shortcuts (in practice) and decrease the steps they need to pass:

https://en.wikipedia.org/wiki/Cryptanalysis

the most important point of failure that I see in asymmetric encryption is running a Random Function in key generation stage. providing real randomness is one of the hardest problems that I ever seen - because what you think is random at first sight, in fact carries a hidden pattern inside. so most of the time random number generation is where Cryptanalysis begin their job from.

[aliashraf]

I think if we are at the point in technology that a QC can be made that can break SHA256 in a relatively trivial manner

Wrong; quantum computers need to run for 2^80 steps to find a private key mapping to a given 160 bit public key. That will remain infeasible for decades to come.

however the threat of QC is 51% attack, not directly breaking the key-pairs but while cryptographers think in probability space (2^80) of breaking something secure (in theory), there are Cryptanalysis methods out there to find shortcuts (in practice) and decrease the steps they need to pass:

https://en.wikipedia.org/wiki/Cryptanalysis

the most important point of failure that I see in asymmetric encryption is running a Random Function in key generation stage. providing real randomness is one of the hardest problems that I ever seen - because what you think is random at first sight, in fact carries a hidden pattern inside. so most of the time random number generation is where Cryptanalysis begin their job from.

Wrong. There is no shortcut for sha2 and if it would be ever possible to find such a shortcut the whole bitcoin blockchain security will become void and you don't need to wait for QC to bring it down.

[mixoftix]

Wrong. There is no shortcut for sha2 and if it would be ever possible to find such a shortcut the whole bitcoin blockchain security will become void and you don't need to wait for QC to bring it down.

misunderstood. the SHA256 is not broken in output. what I wrote above is about the weakness in providing input for the SHA256 - because of weakness in random number generation. this is much more about vulnerabilities that exist in implementation stages of a secure platform - not the Math behind it. so we need to know how QC could influences in the structure of providing (and predict) input for SHA256 (or any other hash algorithm).

UPDATE:
we all know several online/offline bitcoin address generators that only run random function in javascript / server-side script. better solutions make the user to move her mouse to reach better amount of randomness. as I know we have no control over quality of randomness in bitcoin protocol. hope the paper bellow help:

http://www.mixoftix.net/knowledge_base/security/Key_Generation_with_Verifiable_Randomness.pdf

[aliashraf]

Wrong. There is no shortcut for sha2 and if it would be ever possible to find such a shortcut the whole bitcoin blockchain security will become void and you don't need to wait for QC to bring it down.

misunderstood. the SHA256 is not broken in output. what I wrote above is about the weakness in providing input for the SHA256 - because of weakness in random number generation. this is much more about vulnerabilities that exist in implementation stages of a secure platform - not the Math behind it. so we need to know how QC could influences in the structure of providing (and predict) input for SHA256 (or any other hash algorithm).

Now it makes a bit more sense but not enough. Again, it has nothing to do with QC:

If hypothetically, one could find such a vulnerability in the RNG used in a wallet, to be able to "narrow" the search space in brute forcing RIPEMD-160 hash he needs to:
1- 'Guessing' a 'more likely' private key (using the vulnerability in the Random Number Generator),
2- Performing one simple multiplication to compute a public key for it,
3- Generating  ripemd-160 hash of the public key,
4- Praying for a match.

None of the above is QC related.

[bones261]

I think if we are at the point in technology that a QC can be made that can break SHA256 in a relatively trivial manner

Wrong; quantum computers need to run for 2^80 steps to find a private key mapping to a given 160 bit public key. That will remain infeasible for decades to come.

You are taking my post out of context... the word "if" should clue you in. I know that this is nowhere close to feasible now. Perhaps I should have replaced it with the word when to make it more clear?

[mixoftix]

1- 'Guessing' a 'more likely' private key (using the vulnerability in the Random Number Generator),

please keep us posted about any improvement by QC in RNG attacks, Ali. I just googled and found nothing worthy. but found something amazing in these old stuffs:

https://en.wikipedia.org/wiki/Random_number_generator_attack#cite_note-20
https://www.theregister.co.uk/2013/08/12/android_bug_batters_bitcoin_wallets/
https://bitcoin.org/en/alert/2013-08-11-android

------------------

now, there is a question. while machine learning could be used in attack to RNG and macine learning could also improve by QC, there should be a chance in doing something real with QC on RNG - just a gesture..

update:
https://en.wikipedia.org/wiki/Quantum_machine_learning

[8CommaClub]

1- 'Guessing' a 'more likely' private key (using the vulnerability in the Random Number Generator),

please keep us posted about any improvement by QC in RNG attacks, Ali. I just googled and found nothing worthy. but found something amazing in these old stuffs:

https://en.wikipedia.org/wiki/Random_number_generator_attack#cite_note-20
https://www.theregister.co.uk/2013/08/12/android_bug_batters_bitcoin_wallets/
https://bitcoin.org/en/alert/2013-08-11-android

------------------

now, there is a question. while machine learning could be used in attack to RNG and macine learning could also improve by QC, there should be a chance in doing something real with QC on RNG - just a gesture..

what about QC on Fibonacci Sequence? (http://www.ijesi.org/papers/Vol(6)9/Version-3/B0609030714.pdf) Scroll down to encryption / decryption?

[crptomoon1001]

I think if we are at the point in technology that a QC can be made that can break SHA256 in a relatively trivial manner

Wrong; quantum computers need to run for 2^80 steps to find a private key mapping to a given 160 bit public key. That will remain infeasible for decades to come.

You are taking my post out of context... the word "if" should clue you in. I know that this is nowhere close to feasible now. Perhaps I should have replaced it with the word when to make it more clear?

Great question. Made me to think a bit on a possible solution. Below is just my high-level thought without getting into too much of feasibility check.

Quantum computer possesses two major threats to bitcoin Network.

Challenge 1. Quantum computer can rig up blockchain by centralizing its hashing power and

Challenge 2. It can crack to cryptography key and the encryption.

Both are valid security concerns. Something to worry about for sure. But let's understand this basic that it is not just a security threat to bitcoin, but also a security threat to all software's that use encryption see for example it is the threat to all the WhatsApp messages that you send to your friends, it is a threat for you to secure your login credentials for bitcointalk, it is a thread for you as a customer of a bank to prevent your money in the bank account and so on and so forth.

Having established that it is not just a Bitcoin Network security concerned also a security concern for every software that uses encryption technique, let's evaluate two possible solutions to the problem. Once again let me clarify that double two solutions are just my high-level thoughts.

Solution 1.  DAG based blockchain network will grow in future and Proof of Work based blockchain network systems will possibly be eliminated. This might take care of challenge number 1 above

Solution 2. One time password (OTP) or additional security layer to get access to the account will rise and might take care of challenge number 2 above. Two-factor Authentication may become more advanced by the time. Face recognition or voice recognition maybe used along with biometrics in order to get an access to an account in next few years maybe. But this challenge is not hard to overcome. In this manner The Challenge number can be solved.

[mixoftix]

what about QC on Fibonacci Sequence? (http://www.ijesi.org/papers/Vol(6)9/Version-3/B0609030714.pdf) Scroll down to encryption / decryption?

thanks for the paper, my friend.
these sort of encryption algorithms belong to a major family of algorithms that we call them One-Time-Pad:

https://en.wikipedia.org/wiki/One-time_pad

the operator XOR (or MOD when you try to work with ASCII values of characters) is necessary -  not a simple ADD operation. including fibo sequence here doesn't provide a better level of security..

[aliashraf]

1- 'Guessing' a 'more likely' private key (using the vulnerability in the Random Number Generator),

please keep us posted about any improvement by QC in RNG attacks, Ali. I just googled and found nothing worthy. but found something amazing in these old stuffs:

https://en.wikipedia.org/wiki/Random_number_generator_attack#cite_note-20
https://www.theregister.co.uk/2013/08/12/android_bug_batters_bitcoin_wallets/
https://bitcoin.org/en/alert/2013-08-11-android

------------------

now, there is a question. while machine learning could be used in attack to RNG and macine learning could also improve by QC, there should be a chance in doing something real with QC on RNG - just a gesture..

update:
https://en.wikipedia.org/wiki/Quantum_machine_learning

It is a new proposal: Attacking RNG by machine learning boosted by QC. Your previous suggestion was taking advantage of a vulnerable RNG to narrowing down the search space and using QC for boosting the process. I am afraid the new attack is unlikely to work, as well.

We have Cryptographically Secure Pseudo Random Number Generators (CSPRNG), that are provably safe against AI techniques including neural networks and machine learning. For instance suppose we are getting closer to machine learning being disruptively boosted by a hypothetical QC machine reasonably cheap and powerful. Wallets would be able to apply a Von Neumann extractor to their systems in case they have not already considered it.

Bottom line: QC is just another technology and technology can't fight mathematics. It is always possible to force cryptographers to use more sophisticated techniques because of significant technological achievements that provide more processing powers, but it is not possible to beat cryptography in the race.

[CryptoSpark]

NIST is working on a timeline of around 5 to 10 years before publishing recommendations of the best quantum resistant algorithms to apply.
There's a lot of great work already going on and already a range of algorithms to choose from, the question which are the most efficient and reliable and ultimately which get NIST backing and make it into standards.

With regards to timelines, I often hear two opinions, neither of which I have any reason to accept over the other.

The first is that practical quantum computing is still a decade away and so there's time to get this right through NIST. That could very well be true.
The second is that quantum computing is more advanced that is publicly understood and is in part why a certain agency is accelerating the replacement of their Suite B cryptography suite with a new quantum resistant suite.

Whatever the truth, we need to follow standards bodies like NIST and work methodically to get things right.

[seoincorporation]

If Quantum Computing is released into the wild and starts to attack bitcoin , what measures would we see to mitigate these attacks?

We should migrate all the sha256 functions to sha-3, that would be the measures to take, but remember, is aquantum computer can break bitcoin, then that's the smaller issue because in that point all the security agencies would be vuln, sha256 is protecting the military  secrets and all the gov important stuf, so, with that power who will fuck bitcoin while he can fuck the world.