Quantam: How Long Before Computers Crack Private Keys

[JollyGood]

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.

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.

[johnyj]

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.

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

[Cnut237]

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

Shor I can. Sorry.

The maths is I think well established and universally accepted. I am by no means an expert, but section 2 of this paper guides you through it.

ECC security is reliant on the effective impossibility of solving the Discrete Logarithm Problem; it being implausibly difficult to reverse elliptic curve point multiplication using "normal" computers.

Shor's algorithm is famous for solving prime factorisation for any given integer. This can be applied to discrete logarithms (see: https://en.wikipedia.org/wiki/Shor%27s_algorithm#Discrete_logarithms), because the algorithm is equivalent to the hidden subgroup problem for finite Abelian groups. I'll not go into it further because as I say I'm no expert and the maths gets beyond me at this point.

Here's the relevant bit from the paper I mentioned above. I'll make a second post shortly answering your second question about how QCs work.

[Cnut237]

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

It's probably best to start by having a look at wave-particle duality, and from there the Schrodinger equation, and then quantum superposition.

The Schrodinger wave equation fully describes a quantum state. If for example we want to extract position data for the quantum 'particle', we are presented not with a fixed point-like position, but rather with a probability distribution, a sort of smearing, in effect. This does not mean that there is say 60% chance that the particle is at point A, 40% chance it is at point B... because we are talking about a wave function here. The 'particle' is in both places at once, it's not that it's in one but we just don't know which, it is effectively in both but with differing levels of concentration. It is only upon taking a measurement, interacting with the system, that the wave resolves to a point-like particle, and it slots 100% into one of A or B. I'm obviously simplifying in this A-or-B case, but this is superposition; those two classical outcomes are both present in the quantum state.

Classical computers use bits, each bit can be 0 or 1. Quantum computers use qubits, where each qubit is in a superposed state of both outcomes.
So the classical bit is either 0 or 1, whereas the qubit is both, simultaneously. We can then see that whilst classical processing power scales linearly with each new bit, the power in the equivalent quantum system scales exponentially, 2ⁿ.

You might object that the quantum system still resolves into the same number of classical outcomes. And that is true. However here we encounter another key basis of quantum computers: entanglement. Those quantum states can be tied together.

In a 3 bit system, with 8 outcomes {000,001,010,011,100,101,110,111}, the classical computer can only be in one end state. So can the quantum computer. The difference is that the classical computer took one path to get there. The quantum computer, if the qubits are entangled, can take all 8 at once. This is why QCs are so great at problems like prime factorisation, which brings us back to Shor again.

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

I would say that observation isn't necessarily physically observing, it's any interaction with the environment that can trigger wave function collapse. We also get into a discussion of whether the quantum wave function is a 'real' thing, or merely a mathematical model to describe the underlying reality. Quantum mechanics has some solid maths behind it; the big problem is making sense of what that maths means using our poor human brains, which aren't tremendously well suited to the task. I don't think anyone fully understands QM.

[johnyj]

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

Shor I can. Sorry.

The maths is I think well established and universally accepted. I am by no means an expert, but section 2 of this paper guides you through it.

ECC security is reliant on the effective impossibility of solving the Discrete Logarithm Problem; it being implausibly difficult to reverse elliptic curve point multiplication using "normal" computers.

Shor's algorithm is famous for solving prime factorisation for any given integer. This can be applied to discrete logarithms (see: https://en.wikipedia.org/wiki/Shor%27s_algorithm#Discrete_logarithms), because the algorithm is equivalent to the hidden subgroup problem for finite Abelian groups. I'll not go into it further because as I say I'm no expert and the maths gets beyond me at this point.

Thanks, that's a good explanation, at least it described a possible path toward that

[johnyj]

Quantum mechanics has some solid maths behind it; the big problem is making sense of what that maths means using our poor human brains, which aren't tremendously well suited to the task. I don't think anyone fully understands QM.

Great post!

I used to accept all those things from modern physics programs in university in 1990s. However, after more than 20 years seeing the very slow progress in this area, I start to doubt if those claims are really making a lot of sense, just like segwit: a complex theory that does not deliver on what it promises.

For example wave-particle duality, why particles travel like a wave? I start to lean on the original thought that there must be some medium (Ether), without a medium, things tends to go stright or static, there is no reason they would travle like a wave in vacuum. Wave means there is a force drag the particle back to their balance position once they travel too far away from it. And quantum potential might answer that question but bring other questions

And that spooky action proved by Bell equation, sounds like a magic, but in reality it is a very small difference than classical physics predicted, the difference is so small that you must run the test thousands of times to make sure you see the difference. And that's also why the difference is even less observable once the number of qbuits get large

But still, the fundamental difference between Einstein's glove explanation (Reality were decided before they were observed) and Copenhagen interpretation's spooky action (Your observation change the reality by a small degree) is not answered in a satisfactional way, what is your thought on this?

I just saw this short BBC video during a travel and I think it is quite interesting, but it became unclear when it comes to the test that proves bell equation
https://www.youtube.com/watch?v=6k6BuYK_PwQ&t=3s

So, without these fundamental problems cleared, it is difficult to believe any claims on what a QC can do, unless it really did it

[Cnut237]

And that spooky action proved by Bell equation, sounds like a magic, but in reality it is a very small difference than classical physics predicted, the difference is so small that you must run the test thousands of times to make sure you see the difference. And that's also why the difference is even less observable once the number of qbuits get large

But still, the fundamental difference between Einstein's glove explanation (Reality were decided before they were observed) and Copenhagen interpretation's spooky action (Your observation change the reality by a small degree) is not answered in a satisfactional way, what is your thought on this?

My position (again I must stress I'm an amateur here) is in line with the experimental evidence. Quantum mechanics does violate Bell inequalities. This means that if there is any 'hidden variable', then it's non-local. But the whole point of these hidden variable theories is to conserve locality, so in this context a non-local hidden variable is irrelevant.

Underlying everything for me is a concern that we have to interpret QM via our human brains, and that this problem is perhaps insurmountable. How can you describe the universe if you, and everything you can interact with, is and always has been a part of that universe? I can't see that a complete and perfect understanding is possible from human perspective. For a start we interpret everything in terms of the framework of our consciousness, space and time. As for wave-particle duality, I certainly don't believe that for example an electron is sometimes a particle and sometimes a wave, that's absurd. I do believe that sometimes it exhibits wave-like properties and sometimes particle-like, but fundamentally I think an electron is something else entirely. Waves and particles are things that the human brain can conceive of, they are part of our model of reality. Electrons though? A thing that has mass but (apparently) absolutely no size? We can model it mathematically, we can convert that maths into a human understanding of reality, but I firmly believe that any underlying truth is and will remain perpetually elusive.

I have a friend that is a professor in QC department in one of the famous Chinese universities

I really want your friend to set up an account on this forum and join the discussion!

[PrimeNumber7]

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.

You are describing something on the other end of the equation, that is something that would serve as a countermeasure to QC cracking encryption.

I don't know if the Chinese scientists came up with this technology/ability on their own, but I do know the Chinese have a long history of stealing technology from the West. If a western company working for a Western government originally created this technology, it may not be publicly known.

I also believe that QC and QC proof encryption are two separate and distinct technologies. I don't believe having the ability to do one does not necessarily make it easier to obtain the technology to have the ability to do the other.

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.

This technology is very valuable. Its value will decline if it is known the technology exists. My prediction is the technology would be more valuable, and probably more costly to create than a few thousand coin. Someone with QC technology that can crack encryption quickly will not only target cryptocurrencies, they will likely be used by governments to steal rival governments' secrets.

The value in being able to trivially steal a rival government's secrets can probably not be measured in dollars, but rather in millions of lives (of its own citizens/military) possibly saved in the event war breaks out.

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.

Using QC technology to destroy faith in cryptocoins might allow a country to collect more tax revenue, or maintain better control over its citizens, but this is nothing compared to a country's ability to learn what other countries are doing and know. This technology would also prove useful in warfare:

Last year the US downed an Iranian drone near one of it's warships with technology that disabled the drone. I don't know the specifics of what the US ship did, nor the underlying technology. Imagine a country could prevent another country's war planes from taking off (or from continuing to fly), or could send a signal to change the course of another country's missiles that have been launched.

[Cnut237]

Bit of an aside, but China are probably the world leaders in quantum cryptography [...snip...]

You are describing something on the other end of the equation, that is something that would serve as a countermeasure to QC cracking encryption.

I don't know if the Chinese scientists came up with this technology/ability on their own, but I do know the Chinese have a long history of stealing technology from the West. If a western company working for a Western government originally created this technology, it may not be publicly known.

I also believe that QC and QC proof encryption are two separate and distinct technologies. I don't believe having the ability to do one does not necessarily make it easier to obtain the technology to have the ability to do the other.

You are absolutely correct that QC and QC-proof encryption are entirely separate areas. QC-proof encryption is post-quantum cryptography, which aims to devise and employ cryptographic techniques that are secure because they negate any quantum advantage. Approaches like AES256, where the best quantum attack (Grover algorithm) gives QCs only a very minor advantage. P-QC is classical; in this defence there is no dependency on quantum hardware.

You are also correct that in that post I was describing a different countermeasure, quantum cryptography, which involves employing quantum processes to achieve security. It does irritate me that post-quantum cryptography and quantum cryptography have such similar names, when they are fundamentally different things.

I do think that post-quantum cryptography is what we need in the near future to defend against QC attack. However longer-term I'm not so sure. I believe that post-quantum cryptography can never be as secure as a system that relies on the basic 'unhackability' of an entangled quantum system, such as that being developed by China's QUESS and Micius.

As for whether China stole the technology, I'm not so sure. It's difficult to deny that they are ahead of the rest of the world in quantum cryptography, so whatever base they started from they have advanced by themselves. All new tech, all new science, is built on the successes of predecessors.

Last year the US downed an Iranian drone near one of it's warships with technology that disabled the drone. I don't know the specifics of what the US ship did, nor the underlying technology. Imagine a country could prevent another country's war planes from taking off (or from continuing to fly), or could send a signal to change the course of another country's missiles that have been launched.

That's obviously impressive and potentially concerning. We do need to remember though that the advantages of quantum computers are limited to very specific areas, such as prime factorisation. In other areas they are no better than normal classical computers. Certainly the ability of QCs to break asymmetric cryptography could wreak havoc, but P-QC does offer solid defences, so - and I may be being naive - I think that the abilities of QCs are sometimes overstated, and critical systems can be protected, it's just a case of getting that protection implemented in time.

[johnyj]

I really want your friend to set up an account on this forum and join the discussion!

He is not able to join our discussion. I grew up in university, I knew many of those professors, their lifetime is dedicated to publishing articles on science and nature and giving lectures, they don't see the bigger picture, they don't have the motivation to dig into something, like making a quantum miner

Similarly, I highly doubt those experiments since no one can prove they are right or wrong, it just as abstract as Quantatative Easing, more politics instead of real truth seeking. And when you see a lot of complex formula, you know that something is used to let other people shut up if they are not good at high level mathematics (which most of the people are), and even they do, they can not really relate those formulas to physical world in a very strict way

For example, have you seen the card dealer analogy in that BBC documentary? I think it is not very convincing. Based on Einsteins glove theory, the content of the two cards are decided before the dealing, and they are always different(entanglement); and based on copenhagen interpretation, the content of the card only appears when you turn them over

The obvious difference in these two theories lies in: In hidden variable theory, the content of two cards are calculatable and predictable, but we don't know how to calculate. While in copenhagen interpretation, the content of two cards is unknown all the time until you turn them over, no way to know in advance

So, based on this difference, you would easily design a test that turn cards at different time, if they are always the same, then hidden variable theory wins, if they are random, copenhagen interpretation wins.

Unfortunately, once the cards are turned, there is no way to do the test again. So you can not really make an experiment that exploit this obvious difference

However what Bell did is another experiment involving the correlation of different polarization of the lights at different angle. It is very difficult to see the direct relation of his experiment and the above mentioned fundamental differences in hidden variable theory and copenhagen interpretation. Again here politics takes over, complex formulas and experiments seems to be able to shut most of the people's mouth

BTW, I have seen similar kind of goal shifting when I was in university. When the professor could not answer my question in a satisfactional way, they usually say that your way of thinking is too classical, you have not adopted a new mindset of modern physics. But this kind of personal attack does not really help me to get any further. I think the right way is to either admit that there is no sensable explanation on the matter, or explain the thing in a step-by-step, human understandable way. It is worse when you in fact is human but you pretend to be god

[AIQC]

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.

Yes, you're right, not 100%. But our AI says it is > 99.99999999999999999999%.

[PrimeNumber7]

Last year the US downed an Iranian drone near one of it's warships with technology that disabled the drone. I don't know the specifics of what the US ship did, nor the underlying technology. Imagine a country could prevent another country's war planes from taking off (or from continuing to fly), or could send a signal to change the course of another country's missiles that have been launched.

That's obviously impressive and potentially concerning. We do need to remember though that the advantages of quantum computers are limited to very specific areas, such as prime factorisation. In other areas they are no better than normal classical computers. Certainly the ability of QCs to break asymmetric cryptography could wreak havoc, but P-QC does offer solid defences, so - and I may be being naive - I think that the abilities of QCs are sometimes overstated, and critical systems can be protected, it's just a case of getting that protection implemented in time.

A drone needs to communicate with someone on the ground to receive instructions on how to operate. If this communications channel is not encrypted, anyone could send instructions to the drone to tell it what to do.

A QC could possibly crack whatever encryption is being used to communicate with the drone, then another computer could use the now found decryption key to communicate with the drone, and give it instructions to shut off its motor, or whatever.

So any military using QC in the battlefield would need to use QC, plus additional technology. I believe the additional technology is already widely available.

[Cnut237]

A drone needs to communicate with someone on the ground to receive instructions on how to operate. If this communications channel is not encrypted, anyone could send instructions to the drone to tell it what to do.

Agreed. Encryption is necessary.

A QC could possibly crack whatever encryption is being used to communicate with the drone, then another computer could use the now found decryption key to communicate with the drone, and give it instructions to shut off its motor, or whatever.

Disagree. QCs can break public key cryptography, but symmetric cryptography is not vulnerable. If good post-quantum cryptographic encryption is in place, there is no threat - or at least no threat beyond what there already is without the QC.

So any military using QC in the battlefield would need to use QC, plus additional technology. I believe the additional technology is already widely available.

Disagree that you need a QC to defend against quantum attack. You can do so using classical methods, with no need for a quantum computer - use symmetric key post-quantum cryptography such as AES256. An example:

• For standard asymmetric cryptography, a QC running Shor's algorithm absolutely obliterates the difficulty. It takes 2¹²⁸ classical operations to break ECDSA and derive a bitcoin private key from the public key, but only 128³ for a QC running Shor.
• For symmetric cryptography, Grover's algorithm is the best attack. But this only square-roots the difficulty, so for something that takes 2¹²⁸ classical operations, a QC running Grover still takes a huge 2⁶⁴.

[Cnut237]

what Bell did is another experiment involving the correlation of different polarization of the lights at different angle. It is very difficult to see the direct relation of his experiment and the above mentioned fundamental differences in hidden variable theory and copenhagen interpretation. Again here politics takes over, complex formulas and experiments seems to be able to shut most of the people's mouth

It's not just theory; there is now hard evidence, too. Here is photographic proof, the first ever image of quantum entanglement (and violation of the Bell inequality), from the University of Glasgow last July.
_{paper: https://advances.sciencemag.org/content/5/7/eaaw2563}



the experiment:

[johnyj]

what Bell did is another experiment involving the correlation of different polarization of the lights at different angle. It is very difficult to see the direct relation of his experiment and the above mentioned fundamental differences in hidden variable theory and copenhagen interpretation. Again here politics takes over, complex formulas and experiments seems to be able to shut most of the people's mouth

It's not just theory; there is now hard evidence, too. Here is photographic proof, the first ever image of quantum entanglement (and violation of the Bell inequality), from the University of Glasgow last July.
_{paper: https://advances.sciencemag.org/content/5/7/eaaw2563}



the experiment:

The experiment just proves what the experimenter claims, nothing more. This is what I call technology politics, very common in modern physics. Need a better way to convince other people

That's exactly what I see in the laboratory that my friend professor was doing all day, lots of lens and filter and electronic devices, but he still can not make a quantum miner

I have promissed to him that he will make billion dollars by inventing a quantum miner, he only need to work out the theories, I do the physical production, but he obviously have no idea how to even form the concept

[JollyGood]

When to adapt is a valid question because as you mentioned moving too late would mean Bitcoin holders are in trouble and moving early or without consensus will have its own problems. Eventually all forms of technology will adapt and an example is quantum computing. If Bitcoin adapts to become quantum resistant then no doubt other form of computing will emerge and then Bitcoin will adapt, the cycle will continue.

Maybe a couple of decades from now, in the end it might be a case of Bitcoin not having a way to protect itself and it simply becomes overpowered by the threats that emerge - who knows.

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.

[The_Bitcoin_Game]

If Bitcoin adapts to become quantum resistant then no doubt other form of computing will emerge and then Bitcoin will adapt, the cycle will continue.
Maybe a couple of decades from now, in the end it might be a case of Bitcoin not having a way to protect itself and it simply becomes overpowered by the threats that emerge - who knows.

That's the 'Bitcoin Game' and that cycle will never end. All "lost" coins in the old system will be activated in the new system. The first change to quantum resistant system will activate all lost P2PK coins. The next update will be a change from hashing system and will activate all lost coins, and so on.

[Docnaster]

In my opinion, the time expected for computers to crack down private keys is dependent on the computing power and since that is limited due to our current technology . not much could be said after that. What's clear, however, is that once one builds up or manages to access as much computer power as required to compute all the different pattern permutations the security will be entirely breached.

Though, this is requires an enormous amount of energy, and also resources we currently don't have, and are in the process of just about understanding what they are.
So it will take at least 10-20 years before private keys become useless.

[WHIZZ718]

Guys, are we looking at the wrong threat here ?
Given a quantum magic crack, however that works, and a choice between stealing a million bitcoins, or stealing a trillion dollars, which do you think most criminal masterminds would go for ?
The infrastructure for laundering that much money through all sorts of holding companies, overseas mailboxes, financial advisors, and comparable intermediaries is all well established, and when it is time to take the money and run, you can always sell CDO's of junk bonds whatever those get called next time.  So, from "what would the criminal mastermind do with the fabled quantum crack ?", it is surmised that conventional money would probably get raided before bitcoin did.
Therefore the quantum crack would be discovered doing something terrible to somebody else's money, not my bitcoins.

[JollyGood]

The game (as it were for better words) will continue for a long time. Whenever a danger is on the horizon updates and upgrades will be made. Just imagine if Bitcoin mining was resistant to these miners, the overall supply would so low right now and there still would be significant scope for growth. Mass mining Bitcoin using farms was something that maybe should have been blocked a long time ago but probably even now developers never see it as a threat of a different sort which allows conglomerates to mine and profit from Bitcoin on an industrial scale.

That's the 'Bitcoin Game' and that cycle will never end. All "lost" coins in the old system will be activated in the new system. The first change to quantum resistant system will activate all lost P2PK coins. The next update will be a change from hashing system and will activate all lost coins, and so on.