Quantum computer?

[Artlav]

Haven't found much on the topic there, so asking away.

Let's say i have a practicable quantum computer or other device capable of rapid factorization of large enough integers.
What are the consequences to a developed bitcoin network?
Any way it could let me cheat in generation?
Any way it would let me cheat in transactions?

With a device of this kind i can get the private key from public key, right?
So after receiving a bitcoin from someone, can i subsequently successfully fake a transfer of all there was on his side?

[knightmb]

Haven't found much on the topic there, so asking away.

Let's say i have a practicable quantum computer or other device capable of rapid factorization of large enough integers.
What are the consequences to a developed bitcoin network?
Any way it could let me cheat in generation?
Any way it would let me cheat in transactions?

With a device of this kind i can get the private key from public key, right?
So after receiving a bitcoin from someone, can i subsequently successfully fake a transfer of all there was on his side?

I would say no to all questions because quantum computing is not like a magic converter. If you have a working quantum computer, you won't be able to feed in BitCoin hashes and spit out Private Keys. I think it would fall under the hashing collision topics here more than trying to factor large integers. While the media makes quantum computers seem like they will operate like a 1 Trillion MHz processor, they actually operate in a specialized way that is kind of hard to explain in terms of computer science.

[Quantumplation]

Classical computers work linearly, executing a specific set of instructions.  Quantum computing works by setting up a "situation", and then letting it evolve naturally in a quantum physical way, exploring multiple solutions at once.

Think of it like this:  A classical computer acts like a plinko machine.  You put a ball at the top in one of the possible positions, and it clunks down each step until it gets to the bottom.  A quantum computer puts a ball at the top in EVERY position, and lets it fall, until it finds the best one.

The trouble is setting up the situation in a very careful way, such that the interferences between different particles is used to your advantage in the calculation.

[Red]

Let's say i have a practicable quantum computer or other device capable of rapid factorization of large enough integers.
What are the consequences to a developed bitcoin network?
Any way it could let me cheat in generation?
Any way it would let me cheat in transactions?

If you had any system, quantum or not, that could solve the discrete logarithm problem, yes, you could generate the private key from any known public key. With that you could steal any coins you want.

However, you could also probably steal most of the Dollars, Euros, Roubles, etc.

[Artlav]

That's the kind of quantum computer i had in mind.

The regular currencies can adapt, by using symmetric cryptography at the expense of usability for example, but what would become of purely electronic thing like bitcoins are?

[HZPyR8eVk]

That's the kind of quantum computer i had in mind.

The regular currencies can adapt, by using symmetric cryptography at the expense of usability for example

They can't. Or rather, the secure Internet infrastructure is based on asymmetric cryptography (HTTPS). Quantum computer would break this infrastructure until most Internet users would have quantum computers which would use asymmetric cryptography algorithms adapted to the new technology.

[nimnul]

AFAIK quantum computers are hypothesized to solve the factoring problem, but not the discrete logarithm and SHA256 hash collision problems bitcoin security depends on.

[Basiley]

any scalable[like SHA family] hash/cipher don't need quantum computing horsepower efficency, just  amount of usual one.
quantum computing is interesting applications are something breaking "otherwise unbreakable" cryptosystems.

[qbg]

AFAIK quantum computers are hypothesized to solve the factoring problem, but not the discrete logarithm and SHA256 hash collision problems bitcoin security depends on.

Quantum computers do speed up brute force attacks, but that can be countered by doubling the size of the search space (in bits) if it poses a problem.

[jhansen858]

http://pqcrypto.org/    <- This

[payam]

This is not sci-fi anymore. Nasa and Google revealed their first Quantum computer that is 100,000,000 times faster than traditional ones. http://www.pcworld.com/article/3013214/hardware/nasa-google-reveal-quantum-computing-leap.html

[fbueller]

Quantum computers will pose a threat to ECSDA. Whilst 256-bit ECC is comparable in strength to 4096-bit RSA, to a quantum computer, all it's concerned with is the length of the numbers. A 256-bit integer is far easier to solve for compared to 3072-bit.. A single signature would be enough to compromise a private key, with a strong enough quantum computer. They pose less of an issue to hash functions, so funds received on a bitcoin address are safer (until the first transaction redeeming them reveals it's public key and signature)

While quantum computers of this size aren't practical right now, they soon will be. I read a journal article documenting a quantum computer for factorizing integers using chemical computers. Nuclear magnetic resonance was used to induce quantum states in a molecule containing 5 fluorine atoms (used to store qubits of information). It's a pretty extreme approach (they won't break ECDSA using this setup), but it was also largely successful. (https://cryptome.org/shor-nature.pdf)

We're mainly waiting on something that helps us realize quantum computing to a practical extent, but upgrading bitcoin to use a new signature algorithm can be accomplished by either a soft or hard-fork if preferred. With all systems, they will be upgraded whenever the risk becomes real.

wrt upgrading, we can only make it opt-in, so softfork is probably best. Anyone who has funds protected by ECDSA would move their coins one, to a new scriptPubKey protected by: OP_PQCHECKSIG (post-quantum checksig, whatever we decide to adopt). We would generate a new address type, starting some other prefix besides 1...., or 3....., and then life would carry on!

[Straux]

Have you head of the Google Dwave computer? It's supposedly 100 million times faster than the average PC.

A quantum computer should be able to calculate some algorithms much faster than others, but things like hashing would stay about the same speed. If there is a need, miners could push out a new type of encryption to prevent quantum computers from dominating the hashrate.

[fbueller]

Bitcoin doesn't use encryption. Quantum doesn't doom all kinds of algorithms, our main concern (pending new research) is Shors algorithm.

[xmax]

I am assuming that what you are referring to would be considered hacking.  From what i understand, there is no way to hack the block-chain that records all of the BTC transactions that make it what it is.  So in order to successfully steal like that, you would need to be able to change all the code to match in place, which is next to impossible with more code being added each second.

[calkob]

Classical computers work linearly, executing a specific set of instructions.  Quantum computing works by setting up a "situation", and then letting it evolve naturally in a quantum physical way, exploring multiple solutions at once.

Think of it like this:  A classical computer acts like a plinko machine.  You put a ball at the top in one of the possible positions, and it clunks down each step until it gets to the bottom.  A quantum computer puts a ball at the top in EVERY position, and lets it fall, until it finds the best one.

The trouble is setting up the situation in a very careful way, such that the interferences between different particles is used to your advantage in the calculation.

Great example for the diff between classical computers and quantum computers.  i think if anyone ever gets a working quantum computer going that could possiblly be capable of this it would probably be a reputable organization who we would hope could be trusted to not screw things up, at least until we get some Quantum Nodes up and running......   even some Quantum mining rigs..... lol  thats gona be one hell of a difficulty that day. 

[extrabyte]

Quantum computers can be very dangerous for many things like banks which can be affected the first, because these computers have large power and can decrypt any encrypted key or crypto algorithm.

[iotatoken]

IOTA avoids this by design: http://188.138.57.93/tangle.pdf

[Sir_lagsalot]

Quantum computers can do certain things many, many times faster, but things like hashing wil stay bout the same. Don't worry, unless quantum computers become ridiculously cheap, we all have nothing to worry about. Even then, the community will push out a new type of cryptography that's quantum proof. You have nothing to worry about.

Quantum computers are close to being invented, but not that colose.

[iotatoken]

Quantum computers can do certain things many, many times faster, but things like hashing wil stay bout the same. Don't worry, unless quantum computers become ridiculously cheap, we all have nothing to worry about. Even then, the community will push out a new type of cryptography that's quantum proof. You have nothing to worry about.

Quantum computers are close to being invented, but not that colose.

This is naive as hell. All you'd need is a single quantum computer to cripple all cryptocurrencies overnight. IOTA (www.iotatoken) is currently the only crypto to take this seriously