Topic: Quantam: How Long Before Computers Crack Private Keys - page 2. (Read 707 times)

Can you give an example of how to use Shor's algorithm to break ECC? I have a friend that is a professor in QC department in one of the famous Chinese universities, he is unable to answer this question

In fact I have never seen any one that can explain what is a QC and how it actually works, although there are so many material on internet, they all confuse people instead of help them

Schrödinger's cat for example, I think the experiment is designed to show that wave function collapse still happens without observation, since observing cat's status is not directly related to the observing of the particle, which is a prerequisit of wave function collapse in Copenhagen interpretation

Now that is an idea, it could easily be implemented with soft-forks.

Having said that, what is clear is that at some stage quantum resistant Bitcoin has to come in to force and become a reality. As mentioned in one of the links in this thread, it might take  5 years maybe 10 but eventually they will get access to private keys.

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.


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

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.


indeed!

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:

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.

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.

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

you've just highlighted the crux of the problem: https://bitcointalksearch.org/topic/theymos-bitcoins-belonging-to-satoshi-should-be-destroyed-1469099

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.


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.

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.

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.


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

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?

A good QC owner would use it as follows:


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.


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)

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.

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.

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}

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.

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

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.

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

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


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.

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.

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


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