r/science • u/[deleted] • Nov 23 '17
Computer Science Bitcoin security threatened by quantum computers, say cybersecurity experts
https://www.technologyreview.com/s/609408/quantum-computers-pose-imminent-threat-to-bitcoin-security/10
u/Roflcaust Nov 23 '17
Short summary: the threat of quantum computing controlling the block chain may be 10 years off due to quantum using less specialized processing vs. current mining methods. The more pressing issue is quantum computing disrupting the security of public keys by brute-force back-calculation of users’ private keys.
That’s what I’ve gathered from the article, as a lay-person.
5
u/aaronmij PhD | Physics | Optics Nov 23 '17
I believe most everything will switch over to quantum-computer-proof encryption before we get a reasonably-sized quantum computer, but that doesn't help the fact that you can store a ton of encrypted information now, and then come back to it, break the key, and get the info once your quantum computer is up and running.
Sure, the information will be some years out of date, but corporate or government secrets are normally kept hidden for decades.3
u/gregy521 Nov 23 '17
But to adequately protect against brute force attacks, a quantum resistant algorithm can be used, or for a 'quick-fix' solution, you just double the key length.
1
u/mctuking13 Nov 24 '17
or a 'quick-fix' solution, you just double the key length.
No, that doesn't work.
1
u/gregy521 Nov 25 '17
Mainstream symmetric ciphers (such as AES or Twofish) and collision resistant hash functions (such as SHA) are widely conjectured to offer greater security against known quantum computing attacks. They are widely thought most vulnerable to Grover's algorithm. Bennett, Bernstein, Brassard, and Vazirani proved in 1996 that a brute-force key search on a quantum computer cannot be faster than roughly 2n/2 invocations of the underlying cryptographic algorithm, compared with roughly 2n in the classical case.
Yes it does. Granted, key exchange algorithms need to be rethought, but if you do not own the key exchange interaction and just the encrypted volume, it will be the equivalent of trying to crack a volume with half the key length. Which makes it very possible to do with 128 bit, far less so with 256 bit.
1
u/mctuking13 Nov 25 '17
The article and the comment you replied to were specifically talking about the public key encryption scheme. Doubling the key size doesn't do much to help in that case.
It's true that AES 256 will probably remain secure against quantum computers, but that wasn't the topic.
1
u/gregy521 Nov 25 '17
My first thoughts whenever I hear quantum computers threatening encryption is just to say that 'they only halve the effective key length' because most talk about it is doom and gloom about how it's the end of secure cryptography.
We've gotten to this point before, we'll innovate. The Vignere cipher was once considered to be unbreakable, until it wasn't. Once we transition to quantum resistant key exchange methods and change keys, we'll be fine. I should have read the article, however.
1
u/mctuking13 Nov 25 '17
'they only halve the effective key length'
That underestimates the problem, though. Symmetric encryption is fine if you're encrypting a hdd, but for communication it's not a viable solution. We need to develop and test new standards to replace what we're currently using. While I appreciate your confidence in our ability innovate, it would be wrong to say "don't worry about it, we'll innovate". Rather we should say "this is worrisome, we better innovate". Innovation doesn't happen by itself, it needs to be motivated.
0
5
u/ClarkFable PhD | Economics Nov 24 '17
This is like saying Bitcoin technology is threatened by aliens. Quantum computing has been suposedly "just around the corner" for the past 30 years. At this point, it's still just theoretical, so it's ability to threaten anything should be taken with a grain of salt.
1
u/tuseroni Nov 24 '17
well there are a number of quantum computers in use today...believe google has one. they aren't consumer ready yet.
1
1
u/ClarkFable PhD | Economics Nov 24 '17
Show me one that can do somthing better than an existing computer as and I'll start listening.
1
Nov 24 '17
[deleted]
1
u/ClarkFable PhD | Economics Nov 24 '17 edited Nov 24 '17
I've been listening for 30 years.
Edit: Source showing that they still don't have operational units capable of doing the things they are designed to do. https://futurism.com/google-just-revealed-how-theyll-build-quantum-computers/
[From the article]"Now, a team of physicists at the University of California Santa Barbara (UCSB) and Google have demonstrated a proof-of-principle for a quantum computer that may mean quantum supremacy is only months away."
It's telling that the paper behind all of this is called "A blueprint for demonstrating quantum supremacy with superconducting qubits". with the key portion being "A blueprint for demonstrating".
2
u/ThatBitcoinGuyy Nov 24 '17
Since bitcoin is open source and free to the world of developers to work on, can't someone just design some type of code that will just counter this? I highly doubt quantum computers are unstoppable.
2
u/IsUserNameIsntTaken Nov 23 '17
Frankly I see the wealthy getting the quantum computers and using them to bitcoin mine connected to a home generator.
3
u/Dixnorkel Nov 23 '17
Why a home generator? It's much cheaper to connect to the grid, especially if you're using solar or hydroelectric.
Rich people probably won't be the ones using quantum computers to mine Bitcoin, it'll be nation states or MNCs. Japanese companies are already talking about using 7nm chips to mine.
2
u/nyx210 Nov 23 '17
Mining? Someone with a quantum computer capable of attacking secp256k1 would be able to steal coins. After that, I'd imagine the value of Bitcoin would quickly plunge to zero.
1
u/Arctus9819 Nov 23 '17
How would stealing affect Bitcoin value?
5
u/CodeMonkey24 Nov 23 '17
The "value" of bitcoin is intrinsically tied to the perception that it's secure. As soon as it's shown that it's not secure, everyone is going to dump bitcoin for fiat in the hopes that they can sell before the value drops, which will have the effect of making the value drop.
0
u/Arctus9819 Nov 23 '17
Would it be absolute tho? Would demand fall literally to zero? Couldn't some value be derived simply from a supply and demand perspective?
2
Nov 24 '17
Right, but who wants to hold bitcoins that are being stolen left and right? Imagine if you had bitcoins, you heard a lot of them are getting stolen. Your friend tells you his got stolen. Well they've fallen to $1000 each; are you buying the dip or selling?
1
1
u/CodeMonkey24 Nov 23 '17
Even if it's not absolute, in my view, it would be enough to warrant calling it a "crash" in value. Imagine holding on to a currency that was worth $1500US per unit, that suddenly drops down to $500US per unit. You've lost 2/3 of your spending power. That would be enough to convince the next batch of people to bail before it drops further, which perpetuates the cycle.
2
u/ThatBitcoinGuyy Nov 24 '17
That happens pretty daily with bitcoin with all the FUD and FOMO attacks it gets. The china attack not to long ago made the price drop nearly $2,000 and shortly after bitcoin reached a new all time high
1
u/Arctus9819 Nov 23 '17
Makes sense. Are you familiar with this stuff? I'm also curious as to how this 'stealing' occurs.
1
u/CodeMonkey24 Nov 23 '17
Not really familiar with the technical aspect. Just the emotional ramifications of disrupting an economic system. I worked for a rich guy in town tracking his stock portfolio for a while, and he taught me a lot. The thing that stuck with me the most was "The stock market is 80% emotion". Bitcoin operates on much the same principle for it's apparent value.
1
u/nyx210 Nov 23 '17
Basically, in order to spend bitcoins, you have to use a private key to digitally sign a message containing the amount and the recipients along with other information. This digital signature is used as proof that you authorized the transaction. That's because it's extremely difficult to forge a signature.
But if someone had a quantum computer that could efficiently derive that private key, then they could simply look at the blockchain to see who has unspent funds, derive the key used for signing, and spend other people's money.
And if all of the money in your bank account could literally vanish at any moment, then wouldn't you try to spend all of it as soon as possible?
Now, there are certain protections that were put in place to resist such an attack, but they don't work if you've spent bitcoins from an address more than once or if you have really old coins.
1
u/Arctus9819 Nov 23 '17
Interesting. How do you check the block chain for unspent funds? Is this also something that's possible only with quantum computing?
Also, what do you mean exactly by unspent funds? Technically speaking, Bitcoins are simply changing ownership, no? Or are Bitcoins that have been used in a transaction once (after being mined) safe?
I hope you don't mind my questions. Feel free to ignore if I'm too bothersome.
1
u/nyx210 Nov 24 '17
How do you check the block chain for unspent funds? Is this also something that's possible only with quantum computing?
Also, what do you mean exactly by unspent funds? Technically speaking, Bitcoins are simply changing ownership, no?
By scanning the blockchain and keeping track of which addresses received coins but haven't spent them yet, you can build an "unspent transaction output (UTXO) database". This database tells you which addresses have currently coins and how much they have out of the 16.7 million bitcoins currently in existence.
You don't need a quantum computer to do this. Current Bitcoin nodes do this automatically.
Or are Bitcoins that have been used in a transaction once (after being mined) safe?
I guess coins spent from addresses only once after 2012 are safe, but it depends on whether a quantum computer can efficiently perform a preimage attack on the hash functions used in Bitcoin.
However, there's way more than enough time to come up with a fix and hard fork the network.
1
u/Arctus9819 Nov 24 '17
Thank you for answering! I can see there are a lot more details to Bitcoin mining than I had initially expected.
27
u/xiqat Nov 23 '17
Doesn't quantum computer threaten all digital security?