Quantum Computer vs Bitcoin

[hatshepsut93]

I've read on the Bitcoin wiki that Bitcoin private key is usually a 256 bit number, but it can also be between 128 to 512 bits. Does this mean that someone with a quantum computer can theoretically generate all 128 bit long private keys in 2^64 time using Grover's algorithm? Also, is there any way to check if an address corresponds to a key of certain length? So, if such attack is possible, how likely it is to be executed on practice (how likely early quantum computers will be able to break 64 bits of security) and what can be done to prevent it?

[1715032642]

1715032642

[1715032642]

1715032642

[1715032642]

1715032642

[nullius]

I've read on the Bitcoin wiki that Bitcoin private key is usually a 256 bit number, but it can also be between 128 to 512 bits.

Are you speaking of this page?  It is wrong (permalink to incorrect section in incorrect version).  I will apply for wiki editing privileges to correct it.  A Bitcoin private key is always exactly 256 bits, no more and no less.  I infer that the editor who wrote the incorect text was confusing private keys with HD seed values, or something of that nature.  On a brief glance, this page and this page seem correct.

Others on this thread have already explained the basic technical details of what a quantum computer could do.  The takeaway is that Bitcoin’s public-key crypto would be broken—however, public keys which have not yet been exposed would be safe.  There is no way to recover the public key from its hash, not even with a quantum computer.  For other hash properties, in a PQ world, a 256-bit hash should be considered to have today’s equivalent of a 128-bit security level; that’s adequate.

The more important point is that a practical, real-world quantum computer would shatter the banking system, as well as the security of the whole Internet.  Bitcoin would actually fare relatively well, due to its use of hashes in transaction outputs.  This is not really a Bitcoin issue.  Some people (not you) who ask about quantum computers in this context tend to imply that it’s a Bitcoin risk, whereas you should be (relatively) much more worried about your bank accounts.

[hatshepsut93]

Are you speaking of this page?  It is wrong (permalink to incorrect section in incorrect version).  I will apply for wiki editing rights to correct it.  A Bitcoin private key is always exactly 256 bits, no more and no less.  I infer that the editor who wrote the incorect text was confusing private keys with HD seed values, or something of that nature.  On a brief glance, this page and this page seem correct.

Yes, that's exactly what I was asking about, thanks!

Indeed, this part:

Code:

In Bitcoin, a private key is usually a 256-bit number (some newer wallets may use between 128 and 512 bits)

got me confused a bit, since I'm not very familiar with ECDSA.

But I think my question can be repeated for wallet seeds: how long would 128 bit seeds be secure against QC, and how do you think Bitcoin community will react if/when someone will start claiming coins from those wallets that were considered to be lost (I'm assuming that most holders will move their funds to new wallets before quantum brute force will become feasible). Of course it's a far smaller threat than the complete failure of public key cryptography, but still I'm curious.

[Noctis Connor]

I heard that Quantum Computer can destroy bitcoin.
Is it possible?

No. Quantum theory is fake "science" and does not exist, nor do "quantum computers".

You're mad bro, this thing exist. you need to read it here http://www.wired.co.uk/article/d-wave-2000q-quantum-computer Quantom does really exist but it cost a lot of fortune in it.

[hasmukh_rawal]

I heard that Quantum Computer can destroy bitcoin.
Is it possible?

No. Quantum theory is fake "science" and does not exist, nor do "quantum computers".

You must be tripping heavy to live in that imaginary world. The quantum theory as well as the quantum computer both are real and working.
D-Wave was the first company to officially build a quantum computer. You can read it out on Wikipedia here https://en.wikipedia.org/wiki/D-Wave_Systems . Also Google and NASA are joining hands to build a quantum computer which would be much powerful and can solve a problem 100 million times faster than a standard computer.
Take a read about it here : http://www.popularmechanics.com/technology/gadgets/a18475/google-nasa-d-wave-quantum-computer/

[nullius]

But I think my question can be repeated for wallet seeds: how long would 128 bit seeds be secure against QC, and how do you think Bitcoin community will react if/when someone will start claiming coins from those wallets that were considered to be lost (I'm assuming that most holders will move their funds to new wallets before quantum brute force will become feasible). Of course it's a far smaller threat than the complete failure of public key cryptography, but still I'm curious.

The seeds are run through a KDF (key derivation function) which uses iterated hashing.  I am not qualified to say definitively whether a quantum computer could efficiently attack those; and I should know better than to even hazard a guess, without really thinking about it for a very long time.  But my gut says this would probably not be a profitable attack.  Now, watch someone else show me up here...

No. Quantum theory is fake "science" and does not exist, nor do "quantum computers".

quantum mysticism. haha

You're mad bro, this thing exist. you need to read it here http://www.wired.co.uk/article/d-wave-2000q-quantum-computer Quantom does really exist but it cost a lot of fortune in it.

You must be tripping heavy to live in that imaginary world. The quantum theory as well as the quantum computer both are real and working.
D-Wave was the first company to officially build a quantum computer. You can read it out on Wikipedia here https://en.wikipedia.org/wiki/D-Wave_Systems . Also Google and NASA are joining hands to build a quantum computer which would be much powerful and can solve a problem 100 million times faster than a standard computer.
Take a read about it here : http://www.popularmechanics.com/technology/gadgets/a18475/google-nasa-d-wave-quantum-computer/

There is a pernicious little subcultural strain of arrogant doofuses who enjoy spouting “skepticism” of quantum mechanics.  Put that aside; of course, they’re morons—and all the moreso, when they make Internet posts using computers which could not be built without the practical application of quantum mechanics.  Rather like Flat Earthers who use GPS.

There is a huge difference between that, and skepticism of quantum computers.  A quantum computer is not a sure thing!

I should preface this by saying, I’m not endorsing the opinions of Scott Aaronson.  I’m only citing him as someone who is not a moron, and wrote a book on quantum computing (which I have not read).  I seem to recall some wager on his blog over the (im)possibility of quantum computing, but I can’t find it right now; anyway, D-Wave has a long history (2013) of drawing his ire (2017), to say the least.

See how he discusses skepticism of quantum computers:

What I did is to write out every skeptical argument against the possibility of quantum computing that I could think of. We'll just go through them, and make commentary along the way. Let me just start by saying that my point of view has always been rather simple: it's entirely conceivable that quantum computing is impossible for some fundamental reason. If so, then that's by far the most exciting thing that could happen for us. That would be much more interesting than if quantum computing were possible, because it changes our understanding of physics. To have a quantum computer capable of factoring 10000-digit integers is the relatively boring outcome -- the outcome that we'd expect based on the theories we already have.

Though he’s not a good speaker, an interesting lay-level talk is “What Quantum Computing Isn’t” (August 2017).  At 09:39, he notes, “The trouble is, if you want it to be useful, well, at some point you’ve got to observe your computer, you know, to read an answer out.  And if you just measure, you know, the superposition of all answers, not having done anything else, the laws of quantum mechanics say that what you’re going to see will be a random answer.  Okay?  Well, if you just wanted a random answer, then you could have picked one yourself, with a lot less trouble.  (Audience laughs.)”  Funnily enough, at 12:55, “QUANTUM BITCOIN” appears on the screen on a slide discussing Silicon Valley Startup “QUANTUM” buzzwords.  He does say of quantum computing that “it’s not science fiction” (13:15), when discussing Google’s 22-qubit chip; near the end (14:17), he says, “Already within a few years, we may achieve what I think of as the number-one application of quantum computing, which is just to disprove the people who say that it’s impossible.  (Audience laughs.)  Could it be impossible for some deep reason that nobody has figured out yet?  Well, of course.  But in some sense, that’s the more exciting possibility.  Because that’s the possibility that means we have to rewrite all the physics textbooks.”

Aside, just to cut through some more of the quantum hype:

djb derides the alleged physical security of quantum cryptography (PDF) (“Is the security of quantum cryptography guaranteed by the laws of physics?”  djb’s answer seems to be “hahaha!”).  (To be clear, quantum cryptography is a different matter than quantum computing.)  He has also attacked the motives of quantum computing and quantum cryptography researchers (“How quantum cryptographers are stealing a quarter of a billion Euros from the European Commission. #qkd #quantumcrypto #quantummanifesto”).  Hmmm.

As for myself, I account myself moderately skeptical of quantum computing; I’ll believe it when I see it, but meanwhile I think it’s a good idea to move to PQ crypto.  I would be more surprised if quantum cryptography can deliver on its promises.  I don’t like the hype around any of it, especially when it’s sometimes used to FUD Bitcoin.

[haltingprobability]

I account myself moderately skeptical of quantum computing

I recommend the following to anybody seriously interested in understanding QC:

- https://arxiv.org/abs/1312.4455 --> "The Universe as quantum computer" by Seth Lloyd, professor of mechanical engineering and physics at the Massachusetts Institute of Technology.
- https://www.youtube.com/watch?v=dEaecUuEqfc --> "The Quantum Conspiracy: What Popularizers of QM Don't Want You to Know" by Ron Garret

Lloyd argues that quantum physics tells us that the universe is indistinguishable from a quantum computation. This is a powerful meta-argument for the perennially fashionable idea that we're inside a computer - but Lloyd argues convincingly that it's a quantum computer.

Garret explains that a lot of the popular conceptions about quantum mechanics are not only incorrect, they are locked onto pernicious misconceptions that are simply false. He throws light on the phenomena of entanglement, quantum randomness, among others. In short, Garret's approach is to look at QM through the lens of QIT (Quantum Information Theory). Combined with Lloyd's thesis that we are inside a quantum computer, this gives a "post-Simulation Hypothesis" interpretation of QM. The behavior of quantum particles is only "weird", "strange" or "bizarre" because we're using the wrong metaphors (tiny billiard balls). Nobody expects the bits in a classical computer to behave like classical particles because, obviously, bits are not particles. But, if Lloyd is right, quantum particles are ontologically informational, just like classical bits.

Consider the question: Where are the bits that encode the letter between the single-quotes? ---> 'q'

This question has no correct answer. There is no "where". Copies of the letter exist in several locations, ephemerally scattered throughout the memory of your computer, the memory of the computer that served this webpage to you, and so on. Under Lloyd's thesis, this fact is related to the fact that we can end up getting nonsense when we ask a question like, "Where is the quantum particle that ____?" Garret convicts QM popularizes of contributing to mysticism in the public about the solid facts of quantum physics.

I don’t like the hype around any of it, especially when it’s sometimes used to FUD Bitcoin.

Yeah, most of the Bitcoin FUD is ridiculous but the quantum FUD is particularly hard to stomach.

[nullius]

I recommend the following to anybody seriously interested in understanding QC:

- https://arxiv.org/abs/1312.4455 --> "The Universe as quantum computer" by Seth Lloyd, professor of mechanical engineering and physics at the Massachusetts Institute of Technology.
- https://www.youtube.com/watch?v=dEaecUuEqfc --> "The Quantum Conspiracy: What Popularizers of QM Don't Want You to Know" by Ron Garret

Thanks for that.  It’s refreshing to read a post by somebody who knows more than I do about a subject.  Though I look forward to the video, I haven’t yet put an hour of dedicated focus to it; I appreciated your brief summary.  Garret’s thesis as you describe it is fascinating, as is Lloyd’s paper.

This seems to intersect; I presume that Garret was taking aim with his “post-Simulation Hypothesis”:  “Because you asked: the Simulation Hypothesis has not been falsified; remains unfalsifiable”.

Garret explains that a lot of the popular conceptions about quantum mechanics are not only incorrect, they are locked onto pernicious misconceptions that are simply false. [...] The behavior of quantum particles is only "weird", "strange" or "bizarre" because we're using the wrong metaphors (tiny billiard balls).

What evils have been wrought by the wrong metaphors!  (Pseudo)scientifically, and otherwise.  It is the twin sin of asking the wrong questions.

Garret convicts QM popularizes of contributing to mysticism in the public about the solid facts of quantum physics.

Whilst on the subject of pseudoscientific mysticisms woven under the rubric of “educating the public”, quantum talk seems somehow incomplete without mentioning its spacetime counterpart.  One section of one webpage (plus its companion) will suffice to burn away mountains of garbage from “science popularizers” about special relativity.  It’s not even necessary to work through the equations:  Simply look at the pretty pictures of a ruler on a rotating grid.  The light bulb goes on.  Rulers never change their lengths.  Clocks never tick at different rates.  There are no paradoxes.  Those are only illusions caused by three-dimensional thinking, lack of vector maths, and too many “science popularizers”.  Of course, you probably know this...

Granted, the popular explanations sell better.  They provide an instant psychological substitute for the theological paradoxes and impossibilities of popularly fading religions.  It’s not the first time in history that similar has occurred.

As for myself:  I don’t understand special relativity.  I don’t understand quantum mechanics.  I know just barely enough to know that I would need to dedicate years of intensive study to properly claim such understanding.  I’m disgusted by the culture of “popularizers”, and the mass pretense that anybody but a few elite scholars can understand such things; these eviscerate the meaning of the word “understand”.  Attainment of actual understanding in any scientific discipline or engineering endeavour requires both innate ability and hard work.  The same applies as for any art worthy of the word.

But hey, who am I to speak?  I heard that quantum mechanics proves we have entered the astrological Age of Aquarius.  Also, it explains psychic powers.  Thanks, popularizers!

Yeah, most of the Bitcoin FUD is ridiculous but the quantum FUD is particularly hard to stomach.

Quantum FUD®.  What a most excellent buzzword.

[haltingprobability]

One section of one webpage (plus its companion) will suffice to burn away mountains of garbage from “science popularizers” about special relativity. 

What a great resource - bookmarked. There are oodles of false conceptions about SR. If I had to identify one common theme to all of these errors (and the popular errors about QM), it is forgetting that science is about observation and experiment - the maths are just a tool for organizing observed phenomena and guiding further research in an efficient way that hopefully gives us some insight into the nature of physical causality. So, when the popularizers start saying things like, "Physicists have proved the existence of unobserved dark matter and dark energy" (to take one bit of popular science mumbo-jumbo, for example), they are just taking mathematical models and reifying their components as though those components have been actually observed! Instead, mathematical models of physics often use hypothetical components that are merely inferred from experimental data - such as dark matter/energy. At the end of the day, all these formulas describe what happens (or could happen) in a laboratory, in an observatory, and so on. Without that connection to empirical measurement, physics is just really crappy, hard-to-use math.

[bijansha]

I heard that Quantum Computer can destroy bitcoin.
Is it possible?

The difficulty level of bitcoin mining gets adjusted once every two weeks. the faster the processors, the higher the difficulty level. So no, they won't destroy cryptocurrencies (bitcoin might be destroyed by other things such as competition, however)

[KaliLinux]

I heard that Quantum Computer can destroy bitcoin.
Is it possible?

We just named it and created its features that it has quantum things to do. We are applying them in our real world.
Its not a true science like destroying and it is not possible to break bitcoin. May be quantum computer have advanced technology in it which will not destroy anything.
I don't know why are you thinking about destruction which we can feel only in dreams

[Oceat]

I heard that Quantum Computer can destroy bitcoin.
Is it possible?

We just named it and created its features that it has quantum things to do. We are applying them in our real world.
Its not a true science like destroying and it is not possible to break bitcoin. May be quantum computer have advanced technology in it which will not destroy anything.
I don't know why are you thinking about destruction which we can feel only in dreams

Quantum Computer could be a big help but it does not and can not destroy Bitcoin and it cost a lot money to buy a single Quantum Computer for yourself. It may be a big help if someone would have a Quantum Computer like NASA because it is too powerful to process any large memories of files into it. Anyway, how is this going to destroy Bitcoin, it doesn't makes sense at all.

[bakerlisa510]

I heard that Quantum Computer can destroy bitcoin.
Is it possible?

Yes, you are correct it can because it uses quantum-mechanical phenomena, such as superposition and entanglement, and after research I got to know that they are using AI for superposition in which it can choose both on and off (1 and 0) while computing and correct the errors and configure the private keys through public on its own!
I can see that most of people are talking about SHA-256 algorithm

SHA-256 algorithm generates an almost-unique, fixed size 256-bit hash

There might be a solution for this also I have heard about this Blockchain Security system http://blockshield.io/ which can block even AI.

[Vannie12]

No. I think it's false.
Bitcoin may not be perfect but surely it's vulnerability is not wholly. I have read that Satoshi knew the risks that bitcoin could face with such developed powerful computers that is why he built a protocol to avoid and withstand attacks. And I think bitcoin is safe against quantum computer but since there are more technological developments coming in the future, we will not know if something could come up to attack bitcoin.

[TonyMark]

such developed powerful computers that is why he built a protocol to avoid and withstand attacks. And I think bitcoin is safe against quantum computer but since there are more technological developments coming in the future, we will not know if something could come up to attack bitcoin.

and explain what that protocol is? is this the reason why people's BTC is getting stolen? Cause of this so called "Protocol"

There might be a solution for this also I have heard about this Blockchain Security system http://blockshield.io/ which can block even AI.

I checked the site I liked what they have done, Most of us are aware of the term 'Ransomware'; lately, it became a very popular term. It is a method by which cybercriminals make money. May be this one can help a little in this rather like movement against Cybercrime.

[Ucy]

Security agencies and the US DoD have tech that is at least 30 years in advance of the stuff you buy on Amazon. Quantum was likely put into production for breaking RSA 2048 in the 1990's, which is why they stopped making such a big fuss. The fact that publicly available crypto is allowed to be freely shared should tell you it's all broken.

I suspect stuff like this is going.

I think we are doomed if this is indeed true. Am sorry for guys who trust earthly government as we know it. You are creating monsters in the name of government.
Powerful entity keeping secrets is DANGEROUS.

One day you will all understand. May be too late by then.

[Rooster101]

It is said that quantum computer's massive calculating power can be able to break bitcoin security within a decade and there are report that the first quantum computer are currently under development. Some also suggest that the bitcoin protocol should be revised to make the system safer. Whether it is true or not, bitcoin must always be prepared to cope with the future's challenges to beef up its security.

[hopeAo]

I heard that Quantum Computer can destroy bitcoin.
Is it possible?

It can only pose an imminent threat to bitcoin security it can’t destroy bitcoin and moreover, bitcoin has overcome so many threats in the past.
Although, Quantum Computer will surpass the processing power of today’s classical computers, and if it does then it could break RSA (Rivest–Shamir–Adleman) encryption, a tool used to secure data transmission on the Internet. In a similar vein could also break the digital signatures used in Bitcoin and other cryptocurrencies. And the upshot of that is not good.
I believe that bitcoin will overcome this threat.

[gargavaar]

There are no quantum algorithms out there that really makes breaking hashes used by bitcoins easier.
Yet. The RSA crypto was belived to be unbreakable for some time until it was shown that a quantum computer strong enough would shred it.

Quantum computing is still quite young and the science is complicated on account of there's not really that much of quantum computers to run tests on.
When the quantum computers start to make their way out to the universities and governments, rest assured we'll see some crazy stuff, one of which might be cracks in the bitcoin integrity.
That being said, by that time, quantum encryption will be widespread and implemented in most major crypto currencies.

As it stands, the biggest threat quantum computers pose to bitcoin is the risk of rumors.
Even a false rumor can start a bank run. A widespread rumor about a bitcoin security breach could turn nasty really fast.

[quantumcat]

It is said that quantum computer's massive calculating power can be able to break bitcoin security within a decade and there are report that the first quantum computer are currently under development. Some also suggest that the bitcoin protocol should be revised to make the system safer. Whether it is true or not, bitcoin must always be prepared to cope with the future's challenges to beef up its security.

Precisely, the first quantum computers are under development and quantum computing has been a hot topic the last few months. There are some interesting developments in the area, for ex. recently Microsoft programming language called #Q -  https://www.forbes.com/sites/fredcampbell/2017/12/18/microsofts-quantum-computing-vaporware/

Edit: There are so many interesting news lately, that a fast google on 'quantum computers' shows a lot of good articles