Quantum computers and Bitcoin

[Carlton Banks]

Forgive me if I'm wrong, but in a world where quantum computing becomes actually prevalent, as opposed to just plainly possible in a laboratory setting, there is nothing to stop Bitcoin from leveraging QC for it's encryption. This would kind of ruins the argument of ever more sophisticated QC cracking current cryptography; the new cryptographic possibilities that QC could achieve will eventually be available to the Bitcoin dev team, as well as the general public.

I'm not so sure about that. In Bitcoin you need a public key cryptosystem. In elliptic curve cryptography, the trick is that the direct problem (computing the public key or the signature) is easy if you know the private key. However, if you have the public key there is no known efficient method to deduce the private key (with a classical computer).

If everyone had quantum computers, both problems would become easy. You cannot simply scale the numbers as you would with hashing. You need asymmetry.

There are a few alternatives under study:
http://en.wikipedia.org/wiki/Post-quantum_cryptography

The important point is that, as opposed to symmetric systems, where you can just scale everything, you need some asymmetric problem. With quantum computers there are less available problems like that.

Yes, I see what you mean. I read up on the maths behind cryptographic key pairs quite some time ago, and the (infinitely parallel?) nature of QC would blow that paradigm away. I guess that's what I'm driving at then: there must be some way of using quantum computers to create openly exchanged secrets that are inpenetrable to QC cracking methods. If not, then I guess all bets are truly off with just about every form of encryption that exists, even if there was some new discovery in cryptographic maths.

Well, even that isn't entirely true with how Bitcoin uses public key encryption.  Simply publishing a single bitcoin address doesn't actually publish the private key, it publishes a structured hash of the public key.  The actual public key isn't published until the first time funds are spent from that address.  If SHA-256 is subject to being brute forced into collisions by a quantum computer, a different hashing algo may not be, and that could be used instead.  If you use a new address for each transaction, which is how bitcoin does it by default and really is a best practice, it would be very difficult for a quantum breaker to steal your coins.

I apologize if I wasn't being clear with my post, I am aware that private keys cannot be computed from public keys (and the, er, *ahem* obvious security hole that would represent, lol). I imagine it would be possible to use the high level of parallel processing that a QC could be scaled up to to simply brute force private keys directly using the blockchain database. This would presumably take a QC with a high qubit count, but it's clearly the most common sense approach to hacking Bitcoin with quantum computing. It'd have to have a half decent rate of key discovery though, as the chances of finding a private key with alot of money in it's addresses could be pretty slim (this is an impression, I don't know any hard stats offhand, but I suspect the vast majority of keys have <10 BTC contained)

I don't think you understand his point.  Yes QC could (in theory) be used to determine the private key FROM the public key.  However with Bitcoin the address isn't the public key it is a structured hash of the public key.   The public key isn't known until the first time Bitcoins are spent from a given address.

How strange, this is turning into a cascade of misunderstanding! I think what happened was: he interpreted what I initially said (and it was pretty loosely defined to be fair) in a way that he felt to make his point, whereupon I told him the detail of what I was actually suggesting. Sorry if I've confused you too, it really wasn't my intention!

[MoonShadow]

Forgive me if I'm wrong, but in a world where quantum computing becomes actually prevalent, as opposed to just plainly possible in a laboratory setting, there is nothing to stop Bitcoin from leveraging QC for it's encryption. This would kind of ruins the argument of ever more sophisticated QC cracking current cryptography; the new cryptographic possibilities that QC could achieve will eventually be available to the Bitcoin dev team, as well as the general public.

I'm not so sure about that. In Bitcoin you need a public key cryptosystem. In elliptic curve cryptography, the trick is that the direct problem (computing the public key or the signature) is easy if you know the private key. However, if you have the public key there is no known efficient method to deduce the private key (with a classical computer).

If everyone had quantum computers, both problems would become easy. You cannot simply scale the numbers as you would with hashing. You need asymmetry.

There are a few alternatives under study:
http://en.wikipedia.org/wiki/Post-quantum_cryptography

The important point is that, as opposed to symmetric systems, where you can just scale everything, you need some asymmetric problem. With quantum computers there are less available problems like that.

Yes, I see what you mean. I read up on the maths behind cryptographic key pairs quite some time ago, and the (infinitely parallel?) nature of QC would blow that paradigm away. I guess that's what I'm driving at then: there must be some way of using quantum computers to create openly exchanged secrets that are inpenetrable to QC cracking methods. If not, then I guess all bets are truly off with just about every form of encryption that exists, even if there was some new discovery in cryptographic maths.

Well, even that isn't entirely true with how Bitcoin uses public key encryption.  Simply publishing a single bitcoin address doesn't actually publish the private key, it publishes a structured hash of the public key.  The actual public key isn't published until the first time funds are spent from that address.  If SHA-256 is subject to being brute forced into collisions by a quantum computer, a different hashing algo may not be, and that could be used instead.  If you use a new address for each transaction, which is how bitcoin does it by default and really is a best practice, it would be very difficult for a quantum breaker to steal your coins.

I apologize if I wasn't being clear with my post, I am aware that private keys cannot be computed from public keys (and the, er, *ahem* obvious security hole that would represent, lol). I imagine it would be possible to use the high level of parallel processing that a QC could be scaled up to to simply brute force private keys directly using the blockchain database. This would presumably take a QC with a high qubit count, but it's clearly the most common sense approach to hacking Bitcoin with quantum computing. It'd have to have a half decent rate of key discovery though, as the chances of finding a private key with alot of money in it's addresses could be pretty slim (this is an impression, I don't know any hard stats offhand, but I suspect the vast majority of keys have <10 BTC contained)

If you are talking about using a QC to simply brute force key 'collisions' in order to take the coins from random accounts, then  QC is almost certainly not going to be the best way to do this.  Moore's Law, assuming it holds up, would create a greater threat to the current algo first; IMHO.

[Carlton Banks]

I apologize if I wasn't being clear with my post, I am aware that private keys cannot be computed from public keys (and the, er, *ahem* obvious security hole that would represent, lol). I imagine it would be possible to use the high level of parallel processing that a QC could be scaled up to to simply brute force private keys directly using the blockchain database. This would presumably take a QC with a high qubit count, but it's clearly the most common sense approach to hacking Bitcoin with quantum computing. It'd have to have a half decent rate of key discovery though, as the chances of finding a private key with alot of money in it's addresses could be pretty slim (this is an impression, I don't know any hard stats offhand, but I suspect the vast majority of keys have <10 BTC contained)

If you are talking about using a QC to simply brute force key 'collisions' in order to take the coins from random accounts, then  QC is almost certainly not going to be the best way to do this.  Moore's Law, assuming it holds up, would create a greater threat to the current algo first; IMHO.

Well, that sounds like pretty good news for Bitcoin then, it's going to take a change in the manufacturing process/transistor substrate before Moores law can carry on down past 10nm. So, in practical terms, Quantum Computing may never be able to brute force valid private keys, and an efficient transistor based solution needs at least a decades worth of more node process shrnikage as well as an economically viable new manufacturing technique. Go Bitcoin!

[QuantumKiwi]

Quantum technology is far different than digital technology, so i highly doubt anyone will take the time to bring down quantum technology to a digital level, it just wouldn't be worth the ROI.

Quantum technology is still another 50 years away from being inter-mingled with digital tech.