Topic: Quantam: How Long Before Computers Crack Private Keys (Read 696 times)

The problems here are a) achieving sufficient consensus on a QC-proof update to avoid a damaging chain-split and, more importantly b) deciding what to do with any coins that remain vulnerable to QCs after the upgrade.
If a QC-proof upgrade of bitcoin is implemented, the coins are not safe until they are moved to QC-proof addresses. Some coins have not been moved in years, and early coins are particularly vulnerable. There is the highly contentious issue of how to resolve this impasse for coins that are not moved in time, or that can no longer be accessed classically. Should they be burned to prevent theft by a QC? Or should they be left alone to be stolen? What constitutes theft anyway? It's been discussed at length and quite some time ago.


There's a later discussion here:

I think as technology makes bigger strides the time-frame to access Bitcoin by cracking private keys becomes smaller. It is probably sooner than we think but there is every chance an update will be made to counter any threat before it arises. There is no reason crypto will not be able to stay one step ahead of any perceived threat.

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.

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.

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.

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.

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.

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

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:

Agreed. Encryption is necessary.

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.


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

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.

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

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

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.


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.

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.

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.

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.

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 really want your friend to set up an account on this forum and join the discussion!

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

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

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.

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.

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.