Quantam: How Long Before Computers Crack Private Keys

[JollyGood]

If not via Quantam computers then maybe in a different way but will accessing private keys eventually happen?

Imagine checking your wallet one day just to discover the balance is zero, most probably because the private key has been cracked by a supercomputer of sorts.

What would be the best way for Bitcoin and alts to protect themselves against this threat when it is on the verge of being created?

[1715336324]

1715336324

[1715336324]

1715336324

[Cnut237]

Hi, I summarised the threat of Quantum Computers (and some potential solutions) in another thread. Hope this answers the question and/or provokes further discussion.
The weakest point with a QC attack is re-using addresses in a public-key (asymmetric) cryptographic system.
The question of 'how soon' someone will have a sufficiently powerful QC is difficult to answer, given all the hype and bluster that accompanies each announcement, and also the distinction between 'proper' QCs and approaches that are merely quantum annealing, such as D-Wave.

Hi all   I thought I’d try to summarise Bitcoin's vulnerabilities to Quantum Computers, as well as some potential defences, and get it all in one post. Apologies for the wall of text, but hopefully it is useful...


Mining can potentially be much quicker with QCs.
The current PoW difficulty system can be exploited by a Quantum Computer using Grover’s algorithm to drastically reduce the number of computational steps required to solve the problem. The theorised advantage that a quantum computer (or parallelised QCs) have over classical computers is a couple of orders of magnitude, so ~x100 easier to mine. This isn’t necessarily a game-changer, as this QC speed advantage is likely to be some years away, by which time classical computers will surely have increased speed to reduce the QC advantage significantly. It is worth remembering that QCs aren’t going up against run-of-the-mill standard equipment here, but rather against the very fast ASICs that have been set up specifically for mining.

Re-used BTC addresses are 100% vulnerable to QCs.
Address Re-Use. Simply, any address that is re-used is 100% vulnerable because a QC can use Shor’s algorithm to break public-key cryptography. This is a quantum algorithm designed specifically to solve for prime factors. As with Grover’s algorithm, the key is in dramatically reducing the number of computational steps required to solve the problem. The upshot is that for any known public key, a QC can use Shor’s approach to derive the private key. The vulnerability cannot be overstated here. Any re-used address is utterly insecure.

Processed (accepted) transactions are theoretically somewhat vulnerable to QCs.
Theoretically possible because the QC can derive private keys from used addresses. In practice however processed transactions are likely to be quite secure as QCs would need to out-hash the network to double spend.

Unprocessed (pending) transactions are extremely vulnerable to QCs.
As above, a QC can derive a private key from a public key. So for any unprocessed transaction, a QC attacker can obtain the private key and then create their own transaction whilst offering a much higher fee, so that the attacker’s transaction gets onto the blockchain first, ahead of the genuine transaction. So block interval and QC speed are both crucial here – it all depends on whether or not the a QC can hack the key more quickly than the block is processed.


Possible defences...

Defences using classical computers.

• Modify the PoW system such that QCs don’t have any advantage over classical computers. Defending PoW is not as important as defending signatures (as above), because PoW is less vulnerable. However various approaches that can protect PoW against QCs are under development, such as Cuckoo Cycle, Momentum and Equihash.
• Modify the signature system to prevent easy derivation of private keys. Again, various approaches are under development, which use some pretty esoteric maths. There are hash-based approaches such as XMSS and SPHINCS, but more promising (as far as I can tell) are the lattice-based approaches such as Dilithium, which I think is already used by Komodo.
  

Defences using quantum computers.
As I’ve said a few times, I’m more of a bumbling enthusiast than an expert, but exploiting quantum properties to defend against QC attack seems to me a very good idea. In theory properties such as entanglement and the uncertainty principle can offer an unbreakable defence. Again, people are busy researching this area. There are some quite astonishing ideas out there, such as this one.


I’ll leave it there. Apologies for all the external links, but hopefully this has summarised a few things.

[squatter]

If not via Quantam computers then maybe in a different way but will accessing private keys eventually happen?

Imagine checking your wallet one day just to discover the balance is zero, most probably because the private key has been cracked by a supercomputer of sorts.

Here's a relevant paper that speculates about when ECDSA will be broken: Quantum attacks on Bitcoin, and how to protect against them

The elliptic curve signature scheme used by Bitcoin is much more at risk and could be completely broken by a quantum computer as early as 2027, by the most optimistic estimates.

Wasabi Wallet creator nopara73 believes 2022–23 is closer to the mark:

For Bulletproofs, what matters is the Shor RSA2048 line, which is predicted to be broken in 2022–23. In fact, ECC is more vulnerable than RSA in a post-quantum world, so our discrete logarithm assumption may be broken even sooner.

[Cnut237]

For Bulletproofs, what matters is the Shor RSA2048 line, which is predicted to be broken in 2022–23. In fact, ECC is more vulnerable than RSA in a post-quantum world, so our discrete logarithm assumption may be broken even sooner.

Whilst it's true that ECC is more vulnerable than RSA, this is only a question of scale. With sufficient qubits, both can be broken, it's just that it takes more to break the equivalent RSA.

The problem here is that ECC and RSA are both asymmetric approaches. A symmetric approach such as AES256 offers far greater resistance.

The difference between the two is the QCs best method of attack. For asymmetric cryptography, Shor's algorithm is the answer. For symmetric, Shor's approach doesn't work, and Grover's algorithm is the approach to use. And whilst Grover does reduce the difficulty somewhat, it is nowhere near as effective for symmetric systems as Shor is for asymmetric systems. I presented the numbers in a different thread, and can share if anyone is interested.

[JollyGood]

Hi, I summarised the threat of Quantum Computers (and some potential solutions) in another thread. Hope this answers the question and/or provokes further discussion.
The weakest point with a QC attack is re-using addresses in a public-key (asymmetric) cryptographic system.
The question of 'how soon' someone will have a sufficiently powerful QC is difficult to answer, given all the hype and bluster that accompanies each announcement, and also the distinction between 'proper' QCs and approaches that are merely quantum annealing, such as D-Wave.

Thank you for the link and very detailed response. I will go through that thread in detail later when I have time.

Here's a relevant paper that speculates about when ECDSA will be broken: Quantum attacks on Bitcoin, and how to protect against them

The elliptic curve signature scheme used by Bitcoin is much more at risk and could be completely broken by a quantum computer as early as 2027, by the most optimistic estimates.

Wasabi Wallet creator nopara73 believes 2022–23 is closer to the mark:

For Bulletproofs, what matters is the Shor RSA2048 line, which is predicted to be broken in 2022–23. In fact, ECC is more vulnerable than RSA in a post-quantum world, so our discrete logarithm assumption may be broken even sooner.

The whole thing is fascinating in the link you provided about the question "Who will steal Satoshi’s bitcoins?" but the undeniable fact is that at some point something will come along (either out of the blue and shock us all or by virtue of a slow build up) to pose a serious threat to private keys.

[Cnut237]

the undeniable fact is that at some point something will come along (either out of the blue and shock us all or by virtue of a slow build up) to pose a serious threat to private keys.

Yes, perhaps. This is an important point to consider, and I do have a favoured approach which I'll get to in a moment.

Public key cryptography is insecure against a QC running Shor's alogrithm, whilst certain symmetric systems such as AES256 do seem quantum secure against the best QC attack (Grover)... and this holds no matter how many qubits you throw at it.

The key point in any cryptography is that it may be secure now, and it may be secure against such future technological or mathematical advances as we can envisage, but how can we ever say it's secure against such future technology as we can't even conceive right now? At first glance it seems we can never provide that absolute certainty. However I believe we can get close. This is where we have the distinction between post-quantum cryptography, which involves using classical computers to devise quantum-proof systems and algorithms, and quantum cryptography, which uses the laws of quantum mechanics to build a defence.

You will be aware of the Schrodinger's Cat thought experiment, where the cat is neither alive nor dead until it is observed, existing instead in a hybrid state, a superposition of both classical outcomes. Whilst this may be an absurd extension of the quantum realm into the macroscopic, it certainly holds true on a quantum level. The act of observation collapses the wave function and forces an outcome. This is an immutable physical law. And if we then combine this with quantum entanglement, this enables key sharing that in theory is immune to hacking or eavesdropping, because any attempt by a third party to intercept the key collapses and invalidates the whole thing. I'll go into it in more depth if the thread heads that way...

[figmentofmyass]

What would be the best way for Bitcoin and alts to protect themselves against this threat when it is on the verge of being created?

post-quantum cryptography like lamport signatures already exists, and it could be implemented into bitcoin today. that's the easy part.

the difficult part is dealing with the 5+ million vulnerable coins (p2pk outputs, outputs sitting in reused addresses, shared xpubs, etc). implementing a post-quantum signature scheme alone doesn't address the fact that 1/3 of the supply is vulnerable to theft. people need to voluntarily move their coins to quantum-safe addresses for the fork to be effective. that could take a few years, based on the adoption rate of segwit.

[Cnut237]

the difficult part is dealing with the 5+ million vulnerable coins (p2pk outputs, outputs sitting in reused addresses, shared xpubs, etc). implementing a post-quantum signature scheme alone doesn't address the fact that 1/3 of the supply is vulnerable to theft. people need to voluntarily move their coins to quantum-safe addresses for the fork to be effective. that could take a few years, based on the adoption rate of segwit.

Indeed. The question of what to do with the coins that are not moved to quantum-proof addresses is a huge problem.

From my amateurish perspective, it seems to me that if the problem couldn't be solved in time, and it came to a choice between either
(a) burning anything that hasn't been moved, or
(b) leaving them there to be scooped up by a QC

... then I think option (a) is far preferable.

You can't just soft-fork to a situation where some bitcoins are quantum resistant and some aren't; (b) could lead to another gox or worse.

A hard-fork option (a) would still be hugely contentious but if it comes down to a question of bitcoin's survival, it's the better option. Either way you're never going to get a consensus, and there would likely be a serious* chain-split.

_{*serious, not like BCH.}

[PrimeNumber7]

If the technology ever exists with the ability to crack private keys ever exists, it will probably not be used to steal any crypto, and probably not on a large scale. QC will not be able to calculate your private keys if you have never published a signed transaction with the specific private key securing your coin. This distinction may be moot if technology exists to calculate a private key within under 10 minutes.

This technology would be very valuable to whoever creates it, and its value would decrease if it were to be known to exist. If someone can use this technology in private, they can secretly decrypt certain communications and continue doing so, keeping this advantage. If the technology is public, companies and people will move to new and better encryption that QC cannot break. If someone were to use QC to steal coin, it would be obvious that someone has developed the technology and people will move to better encryption.

This is partly why I am concerned anytime I read about internet traffic getting routed through China temporarily in “error” as the Chinese government can capture the encrypted traffic and potentially decrypt it once they develop the technology to do so.

[Cnut237]

This is partly why I am concerned anytime I read about internet traffic getting routed through China temporarily in “error” as the Chinese government can capture the encrypted traffic and potentially decrypt it once they develop the technology to do so.

Bit of an aside, but China are probably the world leaders in quantum cryptography (using quantum mechanics to build quantum-safe solutions that are fundamentally unhackable due to the laws of physics). Have a look at their work with Micius, part of their QUESS (Quantum Experiments at Space Scale) project. They have already demonstrated quantum key distribution (QKD) wirelessly via satellite, generating a pair of entangled photons using an interferometer. Their aim is to have a global quantum network in place by 2030...

... and if they are that far ahead of the game here, I certainly wouldn't bet against them being first to develop a proper QC capable of real-world decryption.


_{https://www.sciencemag.org/news/2017/06/china-s-quantum-satellite-achieves-spooky-action-record-distance}

[philipma1957]

If the technology ever exists with the ability to crack private keys ever exists, it will probably not be used to steal any crypto, and probably not on a large scale. QC will not be able to calculate your private keys if you have never published a signed transaction with the specific private key securing your coin. This distinction may be moot if technology exists to calculate a private key within under 10 minutes.

This technology would be very valuable to whoever creates it, and its value would decrease if it were to be known to exist. If someone can use this technology in private, they can secretly decrypt certain communications and continue doing so, keeping this advantage. If the technology is public, companies and people will move to new and better encryption that QC cannot break. If someone were to use QC to steal coin, it would be obvious that someone has developed the technology and people will move to better encryption.

This is partly why I am concerned anytime I read about internet traffic getting routed through China temporarily in “error” as the Chinese government can capture the encrypted traffic and potentially decrypt it once they develop the technology to do so.

Yeah first person to be able to crack keys 🔑 in a reasonable time will not want to do so in a blatant way.

Just a piece here or there. Better yet maybe take out an exchange wallet since they have claimed being hacked more then once.  Just think grab 10000 coins from an exchange. The exchange will claim hack we all will think bullshit. 💯 million score. No one the wiser.

[JollyGood]

The more I read about this subject the more fascinating it gets. Thank you for the link, although the Op-Ed seems to be dated in 2013 the essence of the current problem is contained within it.

For those have used the same address for multiple payments might be feeling more uncomfortable at this moment in time but in general I guess the underlining fear for crypto users might be that one day they might check their balance only to find their wallet has been emptied and at some stage discover Quantum computing was the tool used for the theft.

What would be the best way for Bitcoin and alts to protect themselves against this threat when it is on the verge of being created?

post-quantum cryptography like lamport signatures already exists, and it could be implemented into bitcoin today. that's the easy part.

the difficult part is dealing with the 5+ million vulnerable coins (p2pk outputs, outputs sitting in reused addresses, shared xpubs, etc). implementing a post-quantum signature scheme alone doesn't address the fact that 1/3 of the supply is vulnerable to theft. people need to voluntarily move their coins to quantum-safe addresses for the fork to be effective. that could take a few years, based on the adoption rate of segwit.

[newBTCdecade]

A good QC owner would use it as follows:

We don't think that QC development will happen step by step. Our expectation is that someone will find a QC technology, that allows "far beyond expectations" numbers of qubits, that will allow this QC to get all private keys immediately.
We think that such a QC will surprise the Bitcoin community and only thereafter we will upgrade to a quantum resistant Bitcoin network. We hope that the user of such a QC to get the private keys, knows exactly how Bitcoin works and allows the owners to transfer their coins to the new QC resistant addresses. It would be a win-win game: the QC user would get the "lost" coins, the Bitcoin owners could transfer their coins to QC resistant addresses, the Bitcoin ecosystem wouldn't be affected, we would have a stronger Bitcoin network. How would a QC user act: starting with the oldest "lost" coins and moving them, so that the Bitcoin community can realize that someone is moving the "lost" coins (e.g. a special posting board here on bitcointalk) but gives the owners the possibility to transfer their coins to other addresses. In the meantime we will have a very quick "quantum resistance upgrade". And it will continue like DannyHamilton described it:

The coins that are still remaining in the weak transaction outputs once Quantum Technology becomes a realistic threat will be those coins that are effectively "lost".  The QC owners will become the new owners of those coins, and Bitcoin will carry on as it always has.

but stronger

The aim is to generate a win-win situation for the QC owner and the Bitcoin community. Satoshi knew that one day QC will move the "lost" coins otherwise he could transfer them to QC resistant unused P2PKH addresses. And his early mined "lost" coins have the most volume, but they are distributed on thousands of addresses that nobody can get them at once (number of transactions and block size). We will know that someone owns a QC if these "lost" coins start to being moved and can change to QC resistant addresses.

Just think grab 10000 coins from an exchange. The exchange will claim hack we all will think bullshit. 💯 million score.

That would end the Bitcoin project.


Btw.: Satoshi has enough other Bitcoins than the known "lost" coins. He mined on several machines but we only know his "lost" coins.  (our opinion)

[Cnut237]

A good QC owner would use it as follows:

We don't think that QC development will happen step by step. Our expectation is that someone will find a QC technology, that allows "far beyond expectations" numbers of qubits, that will allow this QC to get all private keys immediately.
We think that such a QC will surprise the Bitcoin community and only thereafter we will upgrade to a quantum resistant Bitcoin network. We hope that the user of such a QC to get the private keys, knows exactly how Bitcoin works and allows the owners to transfer their coins to the new QC resistant addresses. It would be a win-win game: the QC user would get the "lost" coins, the Bitcoin owners could transfer their coins to QC resistant addresses, the Bitcoin ecosystem wouldn't be affected, we would have a stronger Bitcoin network. How would a QC user act: starting with the oldest "lost" coins and moving them, so that the Bitcoin community can realize that someone is moving the "lost" coins (e.g. a special posting board here on bitcointalk) but gives the owners the possibility to transfer their coins to other addresses. In the meantime we will have a very quick "quantum resistance upgrade". And it will continue like DannyHamilton described it:

The coins that are still remaining in the weak transaction outputs once Quantum Technology becomes a realistic threat will be those coins that are effectively "lost".  The QC owners will become the new owners of those coins, and Bitcoin will carry on as it always has.

but stronger

My bold.

Point 1 - There is a common misconception about quantum processing power. With a classical computer, this scales linearly. With a QC, it scales exponentially with the number of qubits, 2ⁿ. So as you increase processing power:
Classical: 1, 2, 3, 4, 5, 6 etc
Quantum: 1, 2, 4, 8, 16, 32
I definitely think that once we have a reliable low qubit QC, then the steps to a powerful QC that can break public-key cryptography may be achieved more rapidly than commonly anticipated. It's a mistake to think in terms of how 'normal' power in computers scales up. Not saying you're doing that at all, it's just a point of which we should all be aware.

Point 2 - It's one option, but I thinking burning the coins that aren't moved to q-safe addresses is preferable. Ideologically it's questionable, sure, but 5m or 6m bitcoins suddenly available to possibly a single bad actor could quite reasonably be considered an existential threat. And it would be outright theft, not a 'reward' for developing a QC. Unless the real owners consent, which of course they don't. Hard fork and a burn seems the sensible option. The question here is: what should happen when the purity of the original vision intersects the problem of basic survival? A safety tweak, or death?

[squatter]

This technology would be very valuable to whoever creates it, and its value would decrease if it were to be known to exist.

We can't think only in terms of profit-based incentives. Some adversaries -- like nation states or a consortium thereof -- could permanently destroy faith in Bitcoin by releasing this sort of quantum computer in the wild. That may be incentive enough.

Yeah first person to be able to crack keys 🔑 in a reasonable time will not want to do so in a blatant way.

Just a piece here or there.

You're thinking like a thief, not an adversary who wants to destroy Bitcoin. We should plan for both scenarios.

[JollyGood]

I have to agree with you. In such a scenario if it were to happen it goes without say that burning would be preferable and the appropriate thing to do rather than allow them to be funnelled by quantum computers.

If it did come down to it I honestly cannot see anybody complaining about a hard fork if it was a simple choice between the end of Bitcoin or it carrying on (but those who did not move their coins before any fork just might have a differing view).

Every so often a possible threat to either Bitcoin or to private keys will emerge, Bitcoin and altcoins need to adapt to any perceived threat before they can cause any harm therefore need to be prepared for any and every eventuality.

Indeed. The question of what to do with the coins that are not moved to quantum-proof addresses is a huge problem.

From my amateurish perspective, it seems to me that if the problem couldn't be solved in time, and it came to a choice between either
(a) burning anything that hasn't been moved, or
(b) leaving them there to be scooped up by a QC

... then I think option (a) is far preferable.

You can't just soft-fork to a situation where some bitcoins are quantum resistant and some aren't; (b) could lead to another gox or worse.

A hard-fork option (a) would still be hugely contentious but if it comes down to a question of bitcoin's survival, it's the better option. Either way you're never going to get a consensus, and there would likely be a serious* chain-split.

_{*serious, not like BCH.}

[figmentofmyass]

the difficult part is dealing with the 5+ million vulnerable coins (p2pk outputs, outputs sitting in reused addresses, shared xpubs, etc). implementing a post-quantum signature scheme alone doesn't address the fact that 1/3 of the supply is vulnerable to theft. people need to voluntarily move their coins to quantum-safe addresses for the fork to be effective. that could take a few years, based on the adoption rate of segwit.

Indeed. The question of what to do with the coins that are not moved to quantum-proof addresses is a huge problem.

From my amateurish perspective, it seems to me that if the problem couldn't be solved in time, and it came to a choice between either
(a) burning anything that hasn't been moved, or
(b) leaving them there to be scooped up by a QC

... then I think option (a) is far preferable.

You can't just soft-fork to a situation where some bitcoins are quantum resistant and some aren't

i agree, (a) is hands down the most reasonable option.

you've just highlighted the crux of the problem: https://bitcointalk.org/index.php?topic=1469099.0

it's crazy, but most bitcoiners would prefer not to burn QC-vulnerable outputs. they would prefer to let QC wreak havoc on bitcoin's monetary integrity. the consensus is that burning outputs is "stealing" and that we simply shouldn't worry about the QC boogeyman.

if that's what the community plans to do, then everyone should stop repeating that "lost coins are a donation to holders". that's a lie---they aren't a donation because they can be stolen and dumped on the market once ECDSA is compromised.

If it did come down to it I honestly cannot see anybody complaining about a hard fork if it was a simple choice between the end of Bitcoin or it carrying on (but those who did not move their coins before any fork just might have a differing view).

it could even be done with soft forks---one soft fork to implement a post-quantum signature scheme, and another to destroy all ECDSA-secured outputs after date x.

[Cnut237]

Bitcoin and altcoins need to adapt to any perceived threat before they can cause any harm therefore need to be prepared for any and every eventuality.

Yes, definitely. The question is when should bitcoin adapt, and that is a balancing act.

Move too late, and people won't have sufficient time to move their coins to quantum-safe addresses.

Move too early, and there will be chaos as a) there isn't a consensus on exactly what is the best quantum-safe cryptography to move to, and b) as QCs are still widely considered a future rather than current threat, the inevitable disagreements about whether or not to burn coins that don't move could erupt into civil war, or if not that then people would at least separate into opposing camps and begin to become entrenched in their opinions.

It's a difficult situation, but I am an amateur with only a superficial understanding of the various possibilities, and fortunately the people who have to make the decisions here are far smarter and more knowledgeable than I am. I may have little faith in politicians, but I have considerably more faith in bitcoin devs.



edit:

you've just highlighted the crux of the problem: https://bitcointalk.org/index.php?topic=1469099.0

Thanks for the link, this is exactly what I meant in my last sentence - I am worrying about this now; Theymos was worrying about it at least 4 years ago, and probably since the very beginning.

it's crazy, but most bitcoiners would prefer not to burn QC-vulnerable outputs. they would prefer to let QC wreak havoc on bitcoin's monetary integrity. the consensus is that burning outputs is "stealing" and that we simply shouldn't worry about the QC boogeyman.

Yes, this is a big concern. It's a form of zealotry, it's a demand for ideological purity, and that never ends well. It's just not conducive to rational thought.
Kind of strange that burning is stealing, but using a QC to hack someone else's private keys and take their coins isn't.

[figmentofmyass]

Bitcoin and altcoins need to adapt to any perceived threat before they can cause any harm therefore need to be prepared for any and every eventuality.

Yes, definitely. The question is when should bitcoin adapt, and that is a balancing act.

Move too late, and people won't have sufficient time to move their coins to quantum-safe addresses.

Move too early, and there will be chaos as a) there isn't a consensus on exactly what is the best quantum-safe cryptography to move to, and b) as QCs are still widely considered a future rather than current threat, the inevitable disagreements about whether or not to burn coins that don't move could erupt into civil war, or if not that then people would at least separate into opposing camps and begin to become entrenched in their opinions.

the dilemma is further compounded by the fact that all known quantum-safe signature algorithms are very unwieldy in size. lamport transactions would likely be hundreds of times larger than their ECDSA counterparts. https://crypto.stackexchange.com/a/51947

this would be horrible for scalability, absent significant technological/infrastructural progress re bandwidth, latency, storage. it would also force us to revisit the question of increasing block size---already a contentious issue.

it's a clusterfuck with no easy solutions, which is probably why no one is talking about it.

Kind of strange that burning is stealing, but using a QC to hack someone else's private keys and take their coins isn't.

indeed!

[malevolent]

Yes, this is a big concern. It's a form of zealotry, it's a demand for ideological purity, and that never ends well. It's just not conducive to rational thought.
Kind of strange that burning is stealing, but using a QC to hack someone else's private keys and take their coins isn't.

Who said QC attacks on ECC signatures to seize someone else's coins also wasn't stealing? Both are stealing, one in the pursuit of money, another one to prevent the loss of value of one's own stash of bitcoins.

Btw.: Satoshi has enough other Bitcoins than the known "lost" coins. He mined on several machines but we only know his "lost" coins.  (our opinion)

No one's 100% certain these P2PK coins are all owned by Satoshi.