When Bitcoin switches to post quantum algo - which one will it take?

[mynonce]

Post-quantum encryption contender is taken out by a common PC

"Last month, the US Department of Commerce's National Institute of Standards and Technology, or NIST, selected four post-quantum computing encryption algorithms to replace algorithms like RSA, Diffie-Hellman, and elliptic curve Diffie-Hellman, which are unable to withstand attacks from a quantum computer.

In the same move, NIST advanced four additional algorithms as potential replacements pending further testing in hopes one or more of them may also be suitable encryption alternatives in a post-quantum world. The new attack breaks SIKE, which is one of the latter four additional algorithms. The attack has no impact on the four PQC algorithms selected by NIST as approved standards, all of which rely on completely different mathematical techniques than SIKE."

source: https://arstechnica.com/information-technology/2022/08/sike-once-a-post-quantum-encryption-contender-is-koed-in-nist-smackdown/


NIST homepage - Post-Quantum Cryptography
The above algorithm is the 4th on NIST's Post-Quantum Cryptography PQC Round 4 Submissions page
https://csrc.nist.gov/projects/post-quantum-cryptography/round-4-submissions


When Bitcoin switches to post quantum algo - which one will it take?

[NeuroticFish]

When Bitcoin switches to post quantum algo - which one will it take?

The first question is whether Bitcoin needs a change for this yet. And I think that the answer is still no.

And if so, sorry, but your question makes no sense (and I'm being nice). From what I've read some of those submissions may be a bad joke. So we will need to see which of those is/are good enough and pass the test of time. May be some options, may be none(!), however, we simply don't know that now. So, again, your question doesn't make sense because it cannot get a proper answer.

[jackg]

The current thoughts with bitcoin is that quantum technology will only be able to affect bitcoin stored in keys that have already been signed or used for a transaction (I wonder if there's a figure for this)? It also affects funds stored where public keys have been exposed but I think this is an unlikely thing to happen.

In it's current design, bitcoin is fairly quantum safe because it uses ripemd and sha2 hashes for public key security (they're used to make addresses). If quantum technology becomes strong enough to be deemed a threat to bitcoins current algorithm, a hard fork could then be enforced to switch algorithm to one that was quantum proof.

I think the best algorithm to pick by that point is one that's most used and one that's considered most secure - if one isn't found by that point I'd assume hashing algorithms could provide for it in some fancy way.

[NotATether]

Nobody knows which quantum algorithm will untimately be selected by the developers because there literally has been no discussion about this yet.

In it's current design, bitcoin is fairly quantum safe because it uses ripemd and sha2 hashes for public key security (they're used to make addresses). If quantum technology becomes strong enough to be deemed a threat to bitcoins current algorithm, a hard fork could then be enforced to switch algorithm to one that was quantum proof.

Perhaps there can be a soft-fork in the style of Segwit, where there is a txid Merkle tree and a witness txid merkle tree in the blocks. So, a third merkle tree that uses a quantum-resistant hash function could be placed inside the otherwise empty blocks, and then a new consensus rule is added for nodes to reject blocks that do not have a valid quantum txid merkle tree, which nodes will enforce eventually after they upgrade to new Bitcoin Core versions.

[hZti]

Since there is not even a quantum computer out there I think this discussion did not really take place so far. What would be nice however is to know, if bitcoin would even be attackable with a quantum computer. Because if it is and there is no solution before quantum computers are build (and that could basically be tomorrow) bitcoin would fail big time.

[hatshepsut93]

Bitcoin always used mainstream tried and tested cryptographic standards that are used by everyone else, so I assume it would be the case with quantum-resistant cryptography too. If there will be multiple options, the devs would choose the one that suits Bitcoin's needs best - smaller signature size, faster verification speed, etc.

[o_e_l_e_o]

The current thoughts with bitcoin is that quantum technology will only be able to affect bitcoin stored in keys that have already been signed or used for a transaction (I wonder if there's a figure for this)?

There are currently around 4 million coins between P2PK addresses and reused addresses with known public keys which would be vulnerable to quantum computers, according to this article: https://www2.deloitte.com/nl/nl/pages/innovatie/artikelen/quantum-computers-and-the-bitcoin-blockchain.html. As a viable quantum computer become closer to being a reality, though, then a number of these coins would be moved to new unused addresses, so the number of coins which could be stolen will be much less than this.

Choosing a quantum resistant algorithm now would be a huge mistake. Bitcoin has to consider more than just security - it has to consider size and speed as well. Given how young the field is, then any algorithm we settle on now will be outdated and potentially insecure by the time it is necessary, and would need to be replaced again, perhaps by something which doesn't even exist yet.

There was some discussion on the mailing list about this a few months ago: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-April/020209.html

[dothebeats]

I think all the talks about algo change especially to a quantum one is still very early right now. Making the switch in a haste would just compromise a lot of things for bitcoin, mainly its infrastructure and the machines that help make the bitcoin network secure. If we were to change that in a jiffy, the migration to it will become cripplingly slow, because not a lot has the capability to buy quantum computers capable of getting the right computations which bitcoin will be based on.

[o_e_l_e_o]

mainly its infrastructure and the machines that help make the bitcoin network secure.

A quantum computer will have no effect on mining, at least not in the short to medium term.

The risk of quantum computers over traditional computers when it comes to bitcoin is that they are significantly faster at reversing the ECDLP, which allows them to calculate a private key from knowledge of the corresponding public key. They do not provide a significant speed up against traditional computers when it comes to mining, and certainly not when it comes to considering mining as performed by ASICs, which are already orders of magnitude faster than CPUs or GPUs. Quantum computing would not affect the infrastructure of the network or mining until decades after they were mainstream and were able to challenge ASICs. And even then, all that would happen is that the difficulty would adjust to compensate for this increased hashrate.

[franky1]

quantum wont break every bitcoin address at the same time.
it could however be used to try to get a privkey from a address(easier if they have spent before, even easier if it is p2pk instead of p2pkh). where by the effort/time/cost to do so would only be worth it if the address had significant balance worthy to attempt it

here is the thing though... satoshi's tx to hal, is on an address that done 6 spends and is p2pk.. yet after 12 years no one has bruteforced it. so the current binary logic fear of address re-use/p2pk risk is very low and proven to be low due to lack of that address being emptied after 12 years..

now talking about QC:
because each address has a individual key. any malicious user with a quantum system would prefer to target a large significant amount under 1 key.

this is more likely to be where they would go for a fiat banking system with a master key to enter entire systems to hack. rather then trying to get someones value from one key.. repeatedly

the risk/reward psychology would not make bitcoin network a direct threat of QC.
if anything. exchanges using a single key(not multisig) might be a higher risk

for instance.. looking at the bitcoin richlist. you can skip the multisig.. and probably deem
3   1LQoWist8KkaUXSPKZHNvEyfrEkPHzSsCd - as probably something a malicious QC owner might target first as a address to try and bruteforce with QC

now here is the thing...
quantum is great at vector stuff (like elliptic curve, where binary is slow at) however with all the bitcoin features done as binary, sha,ripemd160. the process has to stick to a binary approach to get a result acceptable to the binary bitcoin system.. . so QC cant just throw in any 3d pathway of a result that QC finds. it has to be a pathway that results in something a binary system can accept.

so QC cannot just utilise all of its features to multiply its efforts exponentially. with multiple possible results(outsside binary rules)
sha and some parts of the priv-pub key process slow down QC ability by magnitudes. where it only becomes a few multiples of speed compared to CPU/GPU even with eliptic aspects. but especially with sha aspects

so dont expect that they can just find a key in milliseconds even if things stay as they are.
and the cost of running multiple QC to multiply efforts then become too costly for small value amounts.

so dont fear large risk of full network break or stealing everyones funds in seconds.
but also dont be ignorant to the small chances of large hoards on legacy/segwit keys being 100% shielded if their balance becomes something of a worthy target

[edgycorner]

Quantum computing is still in its research phase. It's quite early to choose any one algorithm. We got another 10 years easily. By the time quantum computers become powerful enough to break existing cryptographic algorithms, new quantum-resistant algorithms will have been developed and standardized.

I would guess we would need a quantum resistant hash function and quantum resistant elliptic curve. So it probably won't choose any one algo.  Instead, it would likely adopt a hybrid approach that uses multiple post-quantum algorithms in order to be more secure.

And should we trust anything vetted by the NIST? https://en.wikipedia.org/wiki/Dual_EC_DRBG
lol

[AmoreJaz]

Quantum computing is still in its research phase. It's quite early to choose any one algorithm. We got another 10 years easily. By the time quantum computers become powerful enough to break existing cryptographic algorithms, new quantum-resistant algorithms will have been developed and standardized.

I would guess we would need a quantum resistant hash function and quantum resistant elliptic curve. So it probably won't choose any one algo.  Instead, it would likely adopt a hybrid approach that uses multiple post-quantum algorithms in order to be more secure.

And should we trust anything vetted by the NIST? https://en.wikipedia.org/wiki/Dual_EC_DRBG
lol

this situation in bitcoin will be a long way to go. though there are some coins that are claiming to be quantum-resistant, we don't know the authenticity of their claim yet. and when it comes to bitcoin, the question is indeed not yet relevant. we may talk about this again once quantum computers are already out in the market. but for now, it seems too early to predict which one will bitcoin use because we don't know yet the future of quantum computers and how it will affect with bitcoin tech.