Bitcoin Forum

As we all know elliptic curve cryptography is vulnerable to a quantum computer. For a conventional computer difficulty of breaking 256-bit key equals 256/2=128 bits. For a quantum computer it's just sqrt(256)=16 bits.
Bitcoin address is a hashed public key of 256-bit EC. Hashes are resistant to quantum algos, so while someone keeps his public key unknown it's OK. But when he wants to transfer his money he must reveal the key.
Let's assume that an attacker with a quantum computer monitors all transactions. The attacker can pick any key while a transaction awaits to be included into a block. Now imagine that miners choose transactions with higher fees. The attacker can issue other transaction (when he picks the private key) that transfer coins to his address and set a higher fee. Or he could switch his mining rig on and try to find a block himself. With 0.1% of all hashpower he needs only 5 days to solve a block with 50% chance.

Seems Bitcoin is NOT safe. Or am I wrong?

Quantum computers are just a theoreticall concept

Sad if it's the only frontier...

Tell me more about that please !

http://en.wikipedia.org/wiki/D-Wave_Systems (http://en.wikipedia.org/wiki/D-Wave_Systems)

Edit : CIA involved

http://www.technologyreview.com/news/429429/the-cia-and-jeff-bezos-bet-on-quantum-computing/ (http://www.technologyreview.com/news/429429/the-cia-and-jeff-bezos-bet-on-quantum-computing/)

Neither is every public private keypair in the world, by your logic. So don't do online banking. Or shop online. Or do credit card transactions.
Bitcoin is not the only thing not safe from the concept.

That's interesting:

[1] Bitcoin uses Elliptic Curve cryptography (http://en.wikipedia.org/wiki/Bitcoin)
[2] Gavin is the lead Bitcoin developer (https://bitcoinfoundation.org/about/board)
[3] Gavin visits CIA (https://bitcointalk.org/?topic=6652.0)
[4] CIA involved into quantum computing (http://www.technologyreview.com/news/429429/the-cia-and-jeff-bezos-bet-on-quantum-computing/)
[5] Elliptic Curve cryptography is breakable with quantum computing (http://pqcrypto.org/)

Shouldn't we change Bitcoin signing algorithm? If Gavin is against these changes it will be very suspicious...

Why does CIA need to destroy the banking system?

What do you suggest changing it to which won't be breakable with quantum computing (assuming anyone cared to throw quantum computing resources at breaking it in the first place)?

ALL VALID POINTS

we need a suggestion here as to quantum resistant

if there is one think we have learnt about the slightly advanced monkeys on orb 3 they keep at it until they can do it, and will f*ck anything just because they can or want to have control over the other monkeys...if they had a blow up the universe button they could not help themselves

This is a hard choice for me. Signature sizes of quantum-proof schemes are too long for 250k block limit. I expect the community has much smarter people who can solve the issue.

Why doesn't the CIA need to?

very wrong as the power of mathematics used increases the level of the cracking cpu rises exponetially meaning that soon the step required from the cpu will be unfathomable

i call this type of cpu that requires the next cpu to be almost infinite in computing power, a number powered cpu

Obviously u are talking about some other Bitcoin implementation. What about the current one?

unless you have studied mathematics for years on end id expect this concept to be a little difficult to graph

write yourself an oct  counter then examine this true oct counter

#include<stdio.h>
#define P printf
#define F for

int main(void){

int dec,oct=0,x;

F(dec=1;dec<=1000000;dec++){

oct++;

F(x=10; (oct/(x/10))>0; x*=10){

if((oct%x)==(8*(x/10))){

oct+=(2*(x/10));      }        }

P("%5d%5d\n",dec,oct);
}
return 0;
}

Quantum computers would be so awesome (according to David Deutsch, a 300 qbit QC could simulate a whole universe), that the failure of bitcoin would be a tiny price to pay.

In a way, you can even see bitcoin as yet an other incentive for scientists and engineers to build a quantum computer.

The spooky stuff - action at a distance and entanglement - might well simply be a very very basic failure to account for the topology of space, a kind of mis-use of units.

There seems to be a big tendency to claim a boolean is a boolean so that in essence the actual units get forgotten about, leading to massive surprise ("that is spooky!!!) when they (the units: the topology of the space) manifest themselves at the other end.

Hard to describe in easy familiar terms I guess, but maybe somewhat analogous to measuring volumetric booleans at one end, forgetting they are volumes (and thus actually speak volumes compared to scalar booleans), then being stupefied when measuring them at the other end rediscovers the fact they are, in fact, volumetric afterall.

Harmony Christian has been trying to explain this stuff for years, but physics forum inhabitants don't fancy it at all at all...

...If he is right, it seems one should be able to simulate quantum computers on classical computers by using octonians.

-MarkM-

Why do you assume the CIA will control a quantum computer initially, assuming it is invented and practically usable?

banks and credit cards are also backed up if you're robbed.

OK, I'll play your game.

Why does CIA need to destroy the Bitcoin network?

The point is that if Bitcoin's algorithm can be broken then there will be more profitable targets than Bitcoin.

We can't rely on a piece of technology not being created to keep out coins safe. Imagine if bitcoin hadn't grown at this rate, $500 of ASIC could have done a 51%

By the way, I love how your address has QR in it, and vice versa :D

I just read this thread up to this point.  It is almost all nonsense.  The capabilities of quantum computers have been describe well in other forum topics.

Bottom line:  Quantum computers can't do anything, except this: 15 = 3 * 5;

So it does computations...backwards :P

What a bad quantum computer would that be.
Everyone knows the optimal way to get 15 is 15*1, not 3*5 ;)

Shouldn't we be ready for the worst case scenario when the CIA controls a QC initially?



Shouldn't we be ready for the worst case scenario when the CIA needs to destroy the Bitcoin network?



Shouldn't we be ready for the worst best case scenario when Bitcoin is the most profitable target?



Shouldn't we be ready for the worst case scenario when a QC, that is able to break Bitcoin, appears in a few years?


--------------------------------------------

Well guys. I see that most of you just hope that Bitcoin won't be broken and there is no REAL protection against an attack, described in the original post.

--------------------------------------------

I do not really consider the purported capabilities of so called quantum computers really well "proven", actually, in the light of Harmony Christian's work.

Because if he is correct that the so called "spooky" stuff is simply the failure of a generation or few of physicists to account the topology of the units correctly in Bell's (and similar) inequalities, resulting in surprise when the 7-sphere topology bit them for forgetting about it / dismissing it as irrelevant, there might not actually be anything spooky going on at all, and the failure to factor anything larger than 15 might simply be because 15 is trivial enough it doesn't really actually require anything "spooky" to factor it.

-MarkM-

If Christian is right, then classical computing should be able to reproduce all the results so called "quantum computing" can achieve, although how much slower it would be to do it that way I don't know.

Furthermore, he even has an experiment one can do with macroscopic balls that, if he is right, should reproduce the "spooky" results on the macroscopic scale, thus demonstrating they are simply the topology of space, applicable at all scales, not some special weirdness down where things get small enough to introduce measurement uncertainties and such.

Unfortunately, as far as I have heard so far, no one has actually built the little plastic balls prescribed and run the actual experiment yet. Partly it seems everyone is so sure the universe is fundamentally spooky that no one can be arsed to actually check whether, in fact, it actually is.

Basically it is classical geometry of the n-sphere and/or classical topology of the n-sphere kind of stuff, best represented using Clifford algebras, but even those who purport to be familiar with Clifford algebras don't really seem to be particularly handy with them.

He presents it in other notations too but his detractors tend to keep shooting him down inventing weird glitches almost as oopsie as the one Bell started his theorem / inequalities paper with that Christian is attempting to elucidate.

-MarkM-

The best explanation for 8 yo ever!

Wouldnt stronger cryptography fix that?

It will. But we should start doing ANYTHING except praying to Satoshi.

ITT https://i.imgur.com/vKpJQlb.gif

If a malicious individual gets a hold of a single computer capable of that kind of speed, I think Bitcoin will be the least of our worries.

On a side note, I just found a bunch of interesting material that might answer all the OP's questions though I cannot say for sure since I have not read the material myself yet.
https://bitcointalk.org/index.php?topic=133425.0
http://www.cs.virginia.edu/~robins/The_Limits_of_Quantum_Computers.pdf
https://www.google.ca/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&cad=rja&ved=0CDoQFjAB&url=http%3A%2F%2Fwww.springer.com%2Fcda%2Fcontent%2Fdocument%2Fcda_downloaddocument%2F9783540887010-c1.pdf%3FSGWID%3D0-0-45-645102-p173864247&ei=3IdGUc-lI4muyQG554CIBA&usg=AFQjCNElz3JULn_Aa1H6NolkLNb9tbuX_g&sig2=0uHjvbW2jIBxRwMP7VIySg&bvm=bv.43828540,d.aWc

EDIT: I believe my third link has all answers.

So in summary: ESDSA would be broken and SHA256 would be fine.

If Qubits really can solve such problems and Christian is right maybe we can solve them on GPUs using Octonians.

-MarkM-

it would have be a quantum asic to have the desired effects, not enough zeros on the processor speed will be added imo

It still seems possible to me that quantum computing cannot really solve stuff the way it likes to claim.

This is because the claims are based on hypothetical spookiness. If really there is no spookiness, just plain old classical geometry of the 7-or-less sphere, once you have gone around the sphere a couple of times (a "double cover") maybe that is all you get, since going around more times still leaves you at a point of that same kind of sphere, and if the cover is only a double cover you only get two "different kinds" of "being there", you're either there with a twist or there without a twist, kind of thing, any larger number of twists unravels into one twist or none.

15 = 3 x 5 only involves the second prime, if you allow 1 to count as the zeroeth prime and 2 as the first prime. I'd like to see at least one more prime get solved otherwise maybe we can only solve for an untwisted case, say, 2 and a twisted case, say 3, and all the rest ahead might just unravel into one of those two cases, blowing all the wonderful quantum algorithms that all think quantum is some spooky thing not just simple geometry / topology of n-spheres.

-MarkM-

Setting aside the fallacious leap that quantum computing would be a magic bullet, I would really be interested to hear some peoples' reasoning for WHY the government (CIA) would want to kill bitcoin in the first place? Seems so many people think its a foregone conclusion that if BTC gets big, the Fed will look to kill it. Is that really true?

If the US State Department is directly funding subversive and disruptive technologies such as Tor for the benefit of pro-dem activists in China and the Middle East, it stands to reason that the State Dept would also find Bitcoin beneficial, as it allows them an avenue to fund disruptive activism without the finger falling back on the POTUS.

I don't think you can reconcile an attack against the one truism of BTC, the best use of superior computational power will always be to 'print your own money.'

Even if quantum does work, it isn't useful for hashing.

So all those SA goons with quantum computers in their mother's basement aren't going to be able to use them for hashing, thus to make money the mining way, they'll have to find other ways to put their toys to use. Such as by breaking all kinds of crypto all over the world, much of which might be even more profitable than hacking bitcoin txouts.

-MarkM-

"Give me control of a nation's money and I care not who makes it's laws." (c) Rockefeller



They are funding Tor to be able to use it by themselves. They disguise activity of their agents who use Tor making appearance they are ordinary hackers.

The feds made Tor... so sure why not?

Bitcoin has some protections against a quantum computer, although not enough.

The thing about addresses is that they aren't cleartext public keys - they're hashes thereof, which for quantum computers are only slightly less infeasible to brute-force.

So the good news is that until you spend from a particular address, your coins at that address are safe; if you avoid reusing addresses, and if you always empty them out when you spend them, and if you submit your transactions directly to the big pools, the risk of someone stealing your coins with a quantum computer is low (because even if they cracked your private key, stealing the coins would effectively require them to double-spend against you).

Really, a quantum-resistant signature scheme would be ideal, but they all have a digest+public key size in the kilobytes (which would require significant, possibly infeasible, block size increases). Hopefully, as the state of the art advances, a more succinct post-quantum signature algorithm will be found that can be easily rolled into Bitcoin.

Quantum Computing is a risk to Bitcoin in 20+ years. For now we are fine as even the newest quantum computer arent even close to catching the Bitcoin Network.

It's not about network , it's about break a private key !

If this attack were ever to become a potential threat it would be simple to avoid being a victim without altering the protocol but just with client behavious change. So with your theory, after you do a transaction from an address a quantum computer could break the private key from the transaction and use the remainder of bitcoins in that address.

The answer is not to leave any coins on that address... so when you want to make a payment you give it two outputs, one to the person you want to pay, and the other output is your next generated address which has no transactions to crack.

No. I meant the key could be picked while a transaction is unconfirmed, so an attacker could double-spend the coins. Two outputs won't help.

15 = (3 * 5) 48% of time

http://www.youtube.com/watch?v=Yl3o236gdp8

Real quantum computing will break most existing widespread forms of cryptographic security. If someone is able to jump the gun and realize a full quantum computer (not just quantum annealing like D-Wave) before it's expected, they will wreak havoc on the Internet. It's far more likely that technology innovators will simply replace security layers with quantum-proof ones before then however. Bitcoin's security layer can easily be swapped out with another -- as Litecoin shows.

Some things need clarification:

A 256-bit EC key has an effective security level of 128 bits against brute force attacks. EC keys can be broken in minutes regardless of the number of bits, theoretically as long as the QC has enough qubits. Shor's (http://en.wikipedia.org/wiki/Shor's_algorithm).

A hashing algorithm such as SHA-256 would be reduced to the sqrt of 256-bits which is 128 bits, not 16. Grover's (http://en.wikipedia.org/wiki/Grover's_algorithm). So any hashing algorithm or public key system that does not rely on factoring is as secure with double the bits.

Banks do not store your money via public/private keypairs that are accessible to everyone. Arguing that banks will be insecure is downright stupid. Yes their websites will be insecure, but the money will be fine. Bitcoin is far, far more vulnerable than the traditional banking system to quantum computing.

Bitcoin is a living, breathing code-base. Most of the attacks that are discussed could be dealt with quickly - if they occur. Yes some merchants could get hurt by it in the short term.

The real question is if the feds really wanted to shut down Bitcoin there are much easier methods to do so that don't require the use of quantum computation.

Even if, in some period of years, it becomes possible to crack Bitcoin (I assume the day will arrive sometime), that is probably not the first thing TPTB would do with it.  In fact, it is more likely they'd sit on the capability and not use it, because it is a capability that is much more useful to have if nobody knows you have it.

I'd assume by the time it becomes possible for the kind of bad guys I'm more worried about to do this, work will be done to transition to some more resistant technology.  I will leave it to those more knowledgeable than I to find these.

Because linear key space expansion exponentially increases brute force difficulty.  /Thread

It's a shame that factorization to prime numbers is not a brute force attack.

Dont worry q-computer can solve algorithms quickly but not crack SHA256 that quickly

The problem is with Elliptic Curve Crypto, not hashing algo.