Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Bitcoin’s race to outrun the quantum computer

decrypt.co

Post reply on HN
Print view View original

41–50 of 90 posts

Re: Bitcoin’s race to outrun the quantum computer

#41

Post by krastanov »

Causality1 wrote: post #13
krastanov wrote: post #4

Just to be clear, this has barely anything to do with any crypto-currency organization. It is a really regrettable framing for an event that should be of great interest to anyone dealing with cryptography, not just the fairly restricted group of crypto-currentcy enthusiasts. If scalable quantum computers can be built (which seems probable, as we are progressing fast in the number of qubits we can keep together), then…

We seem to be getting better at using quantum computers for hard math. What I'm curious about is when we'll be able to use them for easy math. How many qubits do we need to run Doom Quantum?

Quantum computers are (conjectured to) outperform classical computers in a very restricted set of problems. These problems happen to be extremely important (e.g. protein folding and some forms of linear algebra), but for tasks that are already efficiently solved by classical computers you probably will never use a quantum computer (maybe in many decades this will change, when it becomes as "trivial" to construct quantum CPUs as it is to construct classical CPUs)

Re: Bitcoin’s race to outrun the quantum computer

#42

Post by [deleted] »

gruez wrote: post #37
DennisP wrote: post #12

Earlier quoted context omitted.

Yes, but the public key is exposed when you send from that address. If a quantum computer is quick enough, it could get your private key and issue its own transaction, racing you to get into a block.

Cracking a public key in 10 minutes is much harder than cracking a public key (at all). Considering we haven't cracked anything yet, I wouldn't be worried about that. Also, if you're transferring thousands of bitcoin and want to be safe, you could always privately send it to a miner rather than broadcasting it. In that case the tx would have 1 confirmation before the the public knows about it, requiring them to also…

[deleted]

Re: Bitcoin’s race to outrun the quantum computer

#43

Post by DennisP »

gruez wrote: post #37
DennisP wrote: post #12

Earlier quoted context omitted.

Yes, but the public key is exposed when you send from that address. If a quantum computer is quick enough, it could get your private key and issue its own transaction, racing you to get into a block.

Cracking a public key in 10 minutes is much harder than cracking a public key (at all). Considering we haven't cracked anything yet, I wouldn't be worried about that. Also, if you're transferring thousands of bitcoin and want to be safe, you could always privately send it to a miner rather than broadcasting it. In that case the tx would have 1 confirmation before the the public knows about it, requiring them to also…

A QC factors the current public key algorithms in constant time. More qubits just means you can factor bigger keys. How big that constant is will depend on how the QC works.

Sending privately to a miner would help, but you'd end up with a very centralized system since you would want to send to the biggest miner, to minimize the time until that miner produces a block. You can't have miners sharing the transaction, even privately among themselves, since if they did that then one of them could have a QC and you wouldn't have any way to know who stole your money.

Re: Bitcoin’s race to outrun the quantum computer

#44

Post by anm89 »

Mtinie wrote: post #22
anm89 wrote: post #20

"The amount of time the universe itself has left—around 0.65 billion billion years." Is this true?? I've never heard this claimed before.

I’ve never seen it framed that way, but they may be referencing the estimated timeframe for the “heat death” of the universe: https://en.m.wikipedia.org/wiki/Heat_death_of_the_universe

Yeah that was my assumption but I've never seen that specific time frame proposed and it just seems like the kind of thing I would have heard of if it was a know fact.

Re: Bitcoin’s race to outrun the quantum computer

#45

Post by mlyle »

krastanov wrote: post #39
tialaramex wrote: post #19

Earlier quoted context omitted.

> which seems probable, as we are progressing fast in the number of qubits we can keep together Are we? Every so often I check back to see how well they're doing with actually running Shor's algorithm. In 2012 they managed to find that 21 = 3 x 7. And today... 21 = 3 x 7. That doesn't sound like progressing fast. Quantum annealing is doing well for itself, but it isn't any sort of threat to encryption.

We definitely are getting closer. Look at any graph of "qubit lifetime" and you will see how we have orders of magnitude improvements. (a quick google search gives me page 9 of https://hpcuserforum.com/presentations/tuscon2018/QCOverview... ). We still need a couple more orders of magnitude before the qubits are useful, but the signs of exponential progress are unmistakable. I would not take any experiment performing…

So if we extrapolate out the current curve 2 more orders of magnitude, it looks good. Therefore we can conclude it's looking possible? ;)

Re: Bitcoin’s race to outrun the quantum computer

#46

Post by Avamander »

mlyle wrote: post #45
krastanov wrote: post #39

Earlier quoted context omitted.

We definitely are getting closer. Look at any graph of "qubit lifetime" and you will see how we have orders of magnitude improvements. (a quick google search gives me page 9 of https://hpcuserforum.com/presentations/tuscon2018/QCOverview... ). We still need a couple more orders of magnitude before the qubits are useful, but the signs of exponential progress are unmistakable. I would not take any experiment performing…

So if we extrapolate out the current curve 2 more orders of magnitude, it looks good. Therefore we can conclude it's looking possible? ;)

We can conclude that if we're optimists.

Re: Bitcoin’s race to outrun the quantum computer

#47

Post by nielsole »

sweeneyrod wrote: post #29
tialaramex wrote: post #19

Earlier quoted context omitted.

> which seems probable, as we are progressing fast in the number of qubits we can keep together Are we? Every so often I check back to see how well they're doing with actually running Shor's algorithm. In 2012 they managed to find that 21 = 3 x 7. And today... 21 = 3 x 7. That doesn't sound like progressing fast. Quantum annealing is doing well for itself, but it isn't any sort of threat to encryption.

Damn, looks like I should stop using 21 as my PK then.

Not sure what algorithm you use for encryption, but 21 doesn't look like a prime. Maybe run a Miller Rabin test on it? ;)

Re: Bitcoin’s race to outrun the quantum computer

#48

Post by rolltiide »

zazagura wrote: post #30
rolltiide wrote: post #24

Earlier quoted context omitted.

Its not much harder for bitcoin... The community will just do a blockchain snapshot of balances at an agreed upon block and start a new distributed ledger with quantum resistant encryption Snapshots have been done hundreds of times

Everybody will need new private keys. What do you do with old coins? Satoshi's one for example? Or lost coins that nobody has the key for? Do you set a threshold day, after which all unclaimed coins are just marked destroyed forever? If not, how do you know someone claiming some coins didn't use a quantum computer to get the key?

You wont know that, you will provide the tools and also new accounts will have assurance and regenerate confidence in the system

So we have moved from concluding that bitcoin use is an irreparably flawed concept to a method of maintaining viability of the concept

Re: Bitcoin’s race to outrun the quantum computer

#50

Post by neuralzen »

sweeneyrod wrote: post #29
tialaramex wrote: post #19

Earlier quoted context omitted.

> which seems probable, as we are progressing fast in the number of qubits we can keep together Are we? Every so often I check back to see how well they're doing with actually running Shor's algorithm. In 2012 they managed to find that 21 = 3 x 7. And today... 21 = 3 x 7. That doesn't sound like progressing fast. Quantum annealing is doing well for itself, but it isn't any sort of threat to encryption.

Damn, looks like I should stop using 21 as my PK then.

Just XOR 21 times, problem solved!
Post reply on HN