Quantum computing as a threat to Bitcoin

Another threat to Bitcoin. Quantum computing:

Quantum computers and the Bitcoin blockchain

An analysis of the impact quantum computers might have on the Bitcoin blockchain

Regarding the threat from a quantum computer, the public key is directly obtainable from the address. Since all transactions in Bitcoin are public, anyone can obtain the public key from any p2pk address. A quantum computer running Shor’s algorithm could then be used to derive the private key from this address. This would allow an adversary who has a quantum computer to spend the coins that the address had.

Google Aims for Commercial-Grade Quantum Computer by 2029.

A friend who was lured out of early retirement after multiple successful startups claims he has held a million (IIRC) qubit chip in his hand. He told me about this in January of 2020 when he was seeking funding to take it commercial. The last time I talked to him about this COVID had halted his funding quest.

Whether it is Google, IBM, Microsoft, other big names, or any number of startups who want a piece of the pie quantum computing is going shake up a lot of things. Bitcoin, at least as we know it, will probably be an early casualty but it will be far from the only one.


14 thoughts on “Quantum computing as a threat to Bitcoin

  1. “…quantum computing is going shake up a lot of things.Bitcoin, at least as we know it, will probably be an early casualty but it will be far from the only one.”

    Write that down and pin it to the corkboard in your office.
    It will turn out to be one of the greatest understatements you will have ever made.

    Not that quantum computing will not produce many absolutely amazing positive results, it will, but the view of them will be obscured by all the smoking craters QC causes.

  2. Would not quantum computing be capable of breaking any security system? If so, we have a lot more problems than bitcoin. So what we have is an arms race with all the players ranging from amoral to downright evil. Winner gets to take over everything. We have seen this before in the case of nuclear weapons. The US hesitated to use its monopoly to take over the world for long enough for MAD to develop. I have no confidence that this group of players will exercise similar restraint. Not having much success thinking of defensive measures. As for technical solutions, it took decades for SDI to show up and it never was operational. Perhaps a radical turnaway from virtual things toward physical things would do it.

    • You’ll probably see a rise in airgapping and physical security, yes.

      As I’ve remarked before, I don’t care what kind of computer you have or how good your hacker is; if they can’t get connection to the device, they can’t access the data.

      What will be interesting is if you could apply quantum computing to the problem and build unbreakable ciphers.

      • That’s two very large caveats. If it’s electronic, it can be remotely accessed. I remember a conversation with a very smart researcher at a very large software company. Long story short, he related a case (IIRC) where a laptop computer in a closed Faraday-cage room with no external modem or wire or WiFi connection, no power cord, no extra keyboard or screen or mouse was hacked into…. Several of us at the table were reasonably knowledgable about computer hardware and software, and pretty much everyone was at a loss of how to access it, let alone hack it. But considering this is the guy that rewrote the OS on a pallet-load of Kin phones to make a RF connected thousand-core virtual computer, in a week or two, in his spare time, and ported Linux to the XBox360 for fun….

        • I would like to see the technical details behind that assertion.

          It’s true that sometimes there are surprising covert channels. One of the most impressive ones, which seems like fiction until you see the reproduction and realize it was done by serious cryptographers, involved recovering an RSA private key used to authenticate web traffic by listening to the sounds made by the smartphone doing the crypto (with an ultrasonic microphone). It turns out there is a straightforward fix for that, but this is one of the things you would not expect to implement until the attack is demonstrated.

          Another amazing one was recovering (enough of) the plaintext speech on a Skype connection from analysis of the packet lengths. (See the paper “Hookt on Foniks”.)

  3. Quantum computing is the new digital snake oil. It does nothing that can’t be done faster, better and cheaper with a true random number generator. It can be done better and cheaper (but not necessarily faster) with hydraulics.

    • Um, no. Read the literature, your comment about random number generators is entirely off base.

      That said, there certainly is a very large hype component. On the comment earlier of a million qubit chip, I find that implausible given that the largest documented quantum computers have on the order of 100 qubits. The WSJ article recently about Google’s efforts mentioned a goal to get to a million by 2029. That’s quite a stretch, four orders of magnitude in just 9 years. The other issue is that the need for error correction consumes many of those qubits. I have seen estimates of a factor of 100, so if that it correct, a million raw qubits would get you 10k useable ones. That makes it just barely able to break a 4k bit RSA public key, and not good enough for a 6k bit one.

      On “Would not quantum computing be capable of breaking any security system” — no. There’s a lot of research going on involving “post-quantum crypto systems”. Quantum computing isn’t magic, it’s merely a different (and much harder to understand) way of doing computation, with different properties and in particular different scaling. But it’s not omnipotent.

      For example, the one time pad is unconditionally secure against all attack, whether performed by conventional or quantum computers. Demonstrating this is a simple exercise for the student.

      • Yeah, I have been thinking about one-time pads lately. Other than the PITA factor, how do you know that the production of the pads hasn’t been compromised? If I were No Such Agency, I would make such compromise a priority. If they come into widespread use, criminal organizations could play too. I suppose you could manufacture them yourself but that would take software which is another point of compromise. Or you could do it manually but you would probably compromise randomness then.

        As for post-quantum security, that is what I meant with the arms race analogy. First one side, then another gets an advantage but in the meantime a lot of damage is done.

        • Production of one time pads? There are lots of ways to produce them, basically involving noise sources of one kind or another. How would the NSA compromise radium? Yes, of course you manufacture them yourself, that has to be the case by definition. It’s no more logical to buy a “one time pad” than it is to buy a password.

          Post-quantum security is well underway, and has been for a number of years, long before there was any practical need for it. It may not get deployed yet (it’s substantially less efficient than older algorithms) but it certainly can be, well before there is a practically credible threat of QC use against existing crypto. So I don’t think “lot of damage” applies here.

  4. “… If it’s electronic, it can be remotely accessed.”

    Sometimes, and in ways most of us never thought about.

    Can’t remember where, but several years back it was demonstrated, in a SCIF-type environment nonetheless, that computers in the same environment which were not physically or electronically connected in any way could communicate, and one could hack the other.

    It was done with sound – the speaker of one PC emitted coded sounds the microphone on the other PC picked up, and via an internal code bug (a la a Windows 10 zero day hack, anyone?) the OS could be accessed and modified.

    I thought “pure horsehockey” until one of our ace lab nerds did it with 2 Windows XP boxes. He figured it would take him a week to learn how to get full control of the OS, but after that it would be just another canned hacker program.

    Admittedly, the environment he used was a “quiet room,” so it may not be possible in a typical noisy office environment, but never underestimate what a frustrated but dedicated and driven diabolical mind can come up with.

    • It was many years ago now, but back when we connected to the ‘net with an acoustic modem the ‘net traffic could be sniffed optically via the blinking LEDs on the modem.

  5. Meanwhile, on the original article: a crypto expert friend who I asked about it replied that the claim has some connection to reality, but not a big one. The block chain is made of hashes that are not affected by QC. And delivery of bitcoin to a recipient does not disclose that person’s key, only the hash of the key. The full key (via a digital signature) only appears when you spend the bitcoin. Note you can use a different key each time if you so choose. If you do, you’re not vulnerable to any of this unless the attacker can delay your transaction long enough to run Shor’s algorithm, recover your key, and submit a forged transaction in place of yours.

  6. Pingback: Quote of the day—Francisco | The View From North Central Idaho

  7. Quantum computing will endanger ALL information that is encrypted by current methods. Once quantum computing becomes widely available expect Quantum Encryption to be developed. Just like any other “arms race” both sides of the issue advance….just at different times and speeds.

Comments are closed.