New largest number factored on a quantum device is 56,153

[BusyBeaverHP]

http://phys.org/news/2014-11-largest-factored-quantum-device.html

"Researchers have set a new record for the quantum factorization of the largest number to date, 56,153, smashing the previous record of 143 that was set in 2012. They have shown that the exact same room-temperature nuclear magnetic resonance (NMR) experiment used to factor 143 can actually factor an entire class of numbers, although this was not known until now. Because this computation, which is based on a minimization algorithm involving 4 qubits, does not require prior knowledge of the answer, it outperforms all implementations of Shor's algorithm to date, which do require prior knowledge of the answer. Expanding on this method, the researchers also theoretically show how the same minimization algorithm can be used to factor even larger numbers, such as 291,311, with only 6 qubits."

If QC accelerates in the upcoming years, then perhaps even 10^77 may not be enough to guarantee our network security.

Not a quantum computing expert here... just wanted to hear from those in the field... what do you think?

[1714639769]

1714639769

[1714639769]

1714639769

[DannyHamilton]

what do you think?

I think that bitcoin doesn't use large prime products for security, so it really doesn't matter.

[Flashman]

I am thinking that noise from quantum vacuum will make it statistically impossible to get much beyond about 10^10 or so.

[jonald_fyookball]

well not in the field but from what I've heard, the theory is that a general purpose quantum computer could someday use shor's algorithm to break ECC.  we've always said the biggest number factored by a quantum computer is 143 so this is definitely news, but seems we are still a long ways away from quantum computers posing a real threat.

Also, if you are paranoid, you shouldn't reuse addresses because fresh addresses would be immune from quantum attacks due to the RIPEMD-160 hash.

if and when it does become a real issue, bitcoin security protocol can be upgraded.

[BitCoinDream]

well not in the field but from what I've heard, the theory is that a general purpose quantum computer could someday use shor's algorithm to break ECC.  we've always said the biggest number factored by a quantum computer is 143 so this is definitely news, but seems we are still a long ways away from quantum computers posing a real threat.

Also, if you are paranoid, you shouldn't reuse addresses because fresh addresses would be immune from quantum attacks due to the RIPEMD-160 hash.

Care to explain the bold part ? How new address use is more secured because of RIPEMD-160 hash ?

[DannyHamilton]

well not in the field but from what I've heard, the theory is that a general purpose quantum computer could someday use shor's algorithm to break ECC.  we've always said the biggest number factored by a quantum computer is 143 so this is definitely news, but seems we are still a long ways away from quantum computers posing a real threat.

Also, if you are paranoid, you shouldn't reuse addresses because fresh addresses would be immune from quantum attacks due to the RIPEMD-160 hash.

Care to explain the bold part ? How new address use is more secured because of RIPEMD-160 hash ?

When you generate a bitcoin address, and receive bitcoins at that address, the public key is unknown to anybody.  Since the public key is unknown, it would be insufficient to "use shor's algorithm to break ECC".  You would first need to find a way to reverse the RIPEMD-160 hash which would give you the SHA256 hash.  Then you would need to find a way to reverse the SHA256 hash which woud give you the public key.  Only then would you be able to use a quantum computer to calculate the private key.

When you send the bitcoins that you received at that address (when you spend any of the unspent outputs that have ever been received at that address), then the public key is included in the transaction and is permanently stored in the blockchain.  At that time, it is no longer necessary for an attacker to reverse the RIPEMD-160 or SHA256 hashes.

If you use a new address for EVERY transaction (as suggested by Satoshi in the whitepaper), then each address will only ever receive 1 output.  When you spend that 1 output, the public key will become visible, but there will no longer be any unspent outputs associated with that address for anybody to steal.  All your other bitcoins will be associated with other addresses that haven't had their public key exposed yet.

[jonald_fyookball]

well not in the field but from what I've heard, the theory is that a general purpose quantum computer could someday use shor's algorithm to break ECC.  we've always said the biggest number factored by a quantum computer is 143 so this is definitely news, but seems we are still a long ways away from quantum computers posing a real threat.

Also, if you are paranoid, you shouldn't reuse addresses because fresh addresses would be immune from quantum attacks due to the RIPEMD-160 hash.

Care to explain the bold part ? How new address use is more secured because of RIPEMD-160 hash ?

When you generate a bitcoin address, and receive bitcoins at that address, the public key is unknown to anybody.  Since the public key is unknown, it would be insufficient to "use shor's algorithm to break ECC".  You would first need to find a way to reverse the RIPEMD-160 hash which would give you the SHA256 hash.  Then you would need to find a way to reverse the SHA256 hash which woud give you the public key.  Only then would you be able to use a quantum computer to calculate the private key.

When you send the bitcoins that you received at that address (when you spend any of the unspent outputs that have ever been received at that address), then the public key is included in the transaction and is permanently stored in the blockchain.  At that time, it is no longer necessary for an attacker to reverse the RIPEMD-160 or SHA256 hashes.

If you use a new address for EVERY transaction (as suggested by Satoshi in the whitepaper), then each address will only ever receive 1 output.  When you spend that 1 output, the public key will become visible, but there will no longer be any unspent outputs associated with that address for anybody to steal.  All your other bitcoins will be associated with other addresses that haven't had their public key exposed yet.

Yes that is what I meant about RIPEMD-160.

We may have discussed this before Danny, and I don't remember the conclusion, but I was under the impression that it is not necessary to "reverse the SHA256 hash"... Because this hash is only used as a function within ECDSA.  (see step 1 of http://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm).   For example, a bad k value will be insecure here, and can be exploited without reversing any hashes.  Not sure if you can speak to that.

[DannyHamilton]

I was under the impression that it is not necessary to "reverse the SHA256 hash"... Because this hash is only used as a function within ECDSA.  (see step 1 of http://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm).

You are mistaken.

The "address" that bitcoins are "sent to" (or more specifically, the hash value that is compared in the transaction output script) is an RIPEMD-160 hash of a SHA256 hash of the public key.  If you could reverse the RIPEMD-160 hash, you still wouldn't have the public key, you'd just have the SHA256 hash of the public key.

Take a look at step two on this page:
https://en.bitcoin.it/wiki/Technical_background_of_Bitcoin_addresses

[jonald_fyookball]

nice.  thx.

I guess I was thinking once we do have the public key...
What hash function is Bitcoin ECDSA using there?  Is it SHA-256 again?

[thejaytiesto]

Quantum computers are overrated, or the fear of it breaking Bitcoin security that is. In 1000 years, sure, maybe Bitcoin is totally useless by then and anyone can crack the current security with a quantum laptop, but during our lifetimes I think this is the last of our worries.

[jonald_fyookball]

Quantum computers are overrated, or the fear of it breaking Bitcoin security that is. In 1000 years, sure, maybe Bitcoin is totally useless by then and anyone can crack the current security with a quantum laptop, but during our lifetimes I think this is the last of our worries.

Well, that's whats noteworthy of the article -- the current power of quantum computers did just increase by 2 orders of magnitude, at least by
one measurement.

Whether that trend will continue remains to be seen.

[hhanh00]

The title of the article is quite misleading IMO. The experiment is not new. It was made in 2012. Very roughly, the idea is that when two numbers are multiplied, their digits are combined. We know the product, so this gives a set of equations. If the target has a particular bit pattern, the equations reduce and can be solved as the minimisation of a function. The minimization is ran on a quantum NMR computer.

The original team factored 143, the new discovery is that there are higher numbers that exhibit a similar pattern and thus can be solved with the same apparatus. It is not a general purpose algorithm for factorization.

And It's not Shor's algorithm. The largest number is still 15 for it.
ECC doesn't use prime number factorisation. It is subject to a modified version of Shor's algorithm but would still require ~1000 q bits.

References
http://arxiv.org/pdf/quant-ph/0301141v2.pdf
http://arxiv.org/pdf/1411.6758.pdf