Quantum computing and cryptography: Are Steemit and bitcoin safe?

in #steemit8 years ago (edited)

What is quantum computing?

In a classical computer bits are used that can either be 0 or 1. In a quantum computer these bits are replaced with Qubits (quantum bits). These Qubits can be 0 or 1, or both at the same time. This is caused by a phenomenon in the quantum realm called superposition. At scales the size of an atom and small molecules, the spin of particles is not determined until it is observed.

A pair of Qubits can be in any quantum superposition of 4 states, and three Qubits in any superposition of 8 states. In general, a quantum computer with n Qubits can be in a superposition of up to 2^n different states simultaneously (this compares to a normal computer that can only be in one of these 2^n states at any one time). Because of this, a quantum computer is able to perform computations at the same time, while classical computers perform computations one at a time. This effectively means that the computing power grows exponentially for each Qubit you add to the system. A quantum computer will be able to make really difficult calculations all the classical computers in the world together would not be able to do before the end of times, in a relatively short amount of time. This opens to world of computing to be able to perform amazingly complex calculations, such as weather or large scale quantum mechanics, with extremely high precision. Unfortunatly, it will also be great at cracking certain types of cryptography.


Bitcoin and quantum computing

A quantum computer would be able to decuce the private key from a public key. If a bitcoin adress has never been used before, the bitcoins inside would be safe because the public key would not be known. The problem is, how do you make a safe transaction? A bitcoin transaction must include a signature and a public key to ensure that it was the owner of the corresponding private key who made the transaction. When you make that transaction, all information a quantum computer needs to get the private key will be released to the public. This would enable the quantum computer to impersonate you and send other transactions from the same adress. For example if you make a transaction spending all 100 BTC in adress (A) with 30 BTC going to adress (B), to pay for goods, and 70 BTC returning to your own, new adress, (C). The first node you send the transaction to can change to return adress to their adress (D), get your private key, forge your signature and steal your BTC. The way to get around this would be to send your transaction directly to a trusted mining pool and have them include it directly in the blockchain. But then you would still be vulnerable to a Finney attack.


The solution

Lamport signatures. These one-time signatures are effectively unforgeable. It would take a quantum computer 2^80 steps to create a fake transaction in which they have to reveal the same private you have already revealed. Or it would have to take 2^(80*80) steps to try all the possibilities. Both numbers are too big, even for a quantum computer. The only change that would have to be made besides Lamport signatures, is that people should use an adress only once. because when you use it a second time, that number will drop to 2^40. In three uses it would fall back down to the amount of security we have today.


Conclusion / TL;DR

Eventhough quantum computing is coming closer and closer within the reach of humanity every day, it's still not quite there yet. Quantum computing will form a problem for bitcoin as it is today, but there are relatively small measures we can take to overcome that. It is time to start thinking about implementing these measures, because we can't know for sure how far we really are in achieving quantum computing.

Sort:  

Hi! I am a content-detection robot. This post is to help manual curators; I have NOT flagged you.
Here is similar content:
http://pastebin.com/pH0MGHkk

Yes that is my own pastebin of unfinished work, created today.

LOL cheetah fail. I'm tempted to downvote cheetah but that would be kind of harmful to its mostly useful function so I won't

It's quite alright, just hope it didn't hurt my post too much.

You better never downvote it. I did it once and got flagged by 5 other bots and warning from administrator lol

lol. Risky putting your original content up online before here.
I'd look into getting notepad++ or something similar for local backups!

It was to have a friend of mine proofread it, had no idea cheetah would flag that.

Take THAT, @cheetah! ;)

It usually works pretty well though.

Nexus (NIRO) is quantum resistant. We have 571-bit keys. Pure SHA3 using Skein and Keccak. Using Skein-1024 and Keccak-1600 for GPU PoW to produce a 1024 bit output hash used for the block hash providing the highest security.

Other cryptocurrencies will be quantum resistant too, with a few adjustments as explained aboved. So I dont really see the need for a special quantum resistant coin. But it's great to know that theres allready one out there.

Quantum-superpositioncoin?

Hahaha, i'dd tap that.

Good article man. Great information and I don't think you made it overly complicated. Keep it up.

thank you for that, good feedback.

This is way over my head... so I know it must be good. LOL

I'm sorry about that, should I put a disclaimer at the top?

Would the disclaimer say "This is way over Hanshotfirst's head"? If so, maybe not. Some people might not know I'm dumb yet.

I must admit this is one of the hardest topics i've forced myself to get familiar with.

Very interesting!
As fas as I know there are only two quantum computers in the world actually, offcially, and they are really expensive.

But the bitcoin problem would be also a problem with credit card - online transactions!

Bitcoin would be the finicial system with the least amount of problems.

True.It's long been thought in the Bitcoin Community that it would take something on the level of quantum computers to break bitcoin.

Well, I'm glad there is a solution to quantum computing. Hope this can be applied to passwords, too. I'm not comfortable having to submit my biometric data in order to access all my online accounts.

This could be applied to passwords.

This is a really nice post @bergy, quantum computing is extremely interesting, but as with anything dealing with the quantum world, very complex and a log of things in that realm don't make sense at first glance. When I took my first quantum mechanics class in undergrad it made my head spin a bit. You do a good job of boiling down quantum computing a bit, and your conclusions are strong. We should stay ahead of the curve cryptographically speaking, and keep BTC secure for the technologies of tomorrow.

Very interesting bergy quantum computing is more than i can wrap my head around.Be sure to check out my post here https://steemit.com/steemit/@me-tarzan/the-steemit-bull-report