5 ms·

So, basically, as soon a someone builds one of those optimised for factoring primes, all our encryption methods are finished, as is the Bitcoin economy, right?

• igul222 13y ago
  Not exactly. D-Wave quantum computers (like the one in the article) use "adiabatic quantum computing", which is more limited than normal quantum computing (it can't run every quantum algorithm). We're still a little ways off from breaking RSA.
  • mtrimpe 13y ago
    Indeed; you can't build a quantum CPU with D-Wave's system. It's conceptually more similar to a GPU which can solve a specific subset of (non-embarrassingly-parallel) problems in polynomial rather than exponential time, with the published number of qubits essentially being the amount of working memory available. In practice these machines would probably be found optimizing certain steps in machine learning algorithms.
    • mtrimpe 13y ago
      edit: Just to be clear, it does seem that adiabatic quantum computing can do factorization in quadratic time [1] http://arxiv.org/abs/0808.1935 http://arxiv.org/abs/0808.1935
  • Devilboy 13y ago
    D-Wave does have a factoring algorithm. See the comments from D-Wave here: http://dwave.wordpress.com/2011/05/11/learning-to-program-the-d-wave-one/ http://dwave.wordpress.com/2011/05/11/learning-to-program-th... "We do have a factoring algorithm that I’m going to do a series of blog posts on"
• NickM 13y ago
  Well, actually not all our encryption methods: there are asymmetric encryption algorithms that provide strong encryption even in the face of quantum computers. Unfortunately, the whole world is using RSA which is vulnerable. I don't know that much about quantum computing, but I believe it may be possible that D-Wave has managed to figure out how to build a useful quantum computer that is nevertheless not general-purpose enough to execute Shor's algorithm for factoring primes.
  • mtgx 13y ago
    When the FBI stops asking for backdoors in Internet services, we'll know they probably don't need them anymore. Then take into account that NSA is already probably 5-10 years ahead of them for any sort of surveillance technology.
    • rohansingh 13y ago
      A little paperwork to get a backdoor is probably cheaper, faster and easier than using a quantum computer, even if one is available.
• pjmlp 13y ago
  Yes, because they are all based on the assumption how much time it takes to break them with brute force attacks using the current architectures.
• Devilboy 13y ago
  Bitcoin addresses are hashes, not the public keys themselves. Thus they are safe against a quantum factoring algorithm. If you spend money from a bitcoin address though, the public key does get written to the block chain but to combat this you merely have to send your change to a new address and you'll be safe again.
• pja 13y ago
  Pretty much: Quantum Computers (QCs) can factor numbers (Shor's algorithm) and calculate discrete logarithms in polynomial time. I don't know whether there's an algorithm for hash-calculation that will let someone dominate the BitCoin hashing chain with a QC though. On the other hand, no one actually knows whether it's possible to build a quantum computer with enough q-bits that will stay coherent for long enough to carry out the calculation: as you add q-bits, noise becomes more and more of a problem. You can add error correction, but that makes keeping all the q-bits coherent harder because now you've got even more of them! At the moment, no-one knows (unless the NSA has built one and isn't telling!) which effect is going to win out as the number of q-bits increases. (You can't use a smaller QC to simulate a slower version of a larger one, unlike in the non-quantum computing world: if you need to factor a 1024 bit number and you only have a 1000 bit QC you can't do it, as I understand things.) Note that Quantum Computers don't help as much with symmetric encryption, unless someone comes up with a much better algorithm. They let you effectively halve the key-space, which is a fairly big deal, but you can get back to the same level of difficulty by doubling up the size of your keyspace: a 256-bit AES key provides roughly the protection of a 128-bit key in a quantum computing world. This is different to public-key encryption, where you can double the key size, but if your opponent has a quantum computer with enough q-bits, they can still break your new key in reasonable time.
  • lifeisstillgood 13y ago
    Thank you - I did feel I had missed a decade reading the article.
  • shadowmint 13y ago
    I actually thought that error correction codes were largely considered to solve the problem of decoherence, at least theoretically. (aka. http://www.google.com.au/url?sa=t&rct=j&q=&esrc=s&source=web&cd=4&ved=0CEUQFjAD&url=http%3A%2F%2Fwww.theory.caltech.edu%2Fpeople%2Fpreskill%2Fph229%2Fshor_error.ps&ei=SMqQUaKNK8XmiAfs-4HQDA&usg=AFQjCNEVRTSN2PNKgUKy1Sr-2mFDLEHPpQ&sig2=wng6eCmyuiGIpnp6e15GrQ&bvm=bv.46340616,d.aGc&cad=rja http://www.google.com.au/url?sa=t&rct=j&q=&esrc=... or perhaps more easily explained @ http://en.wikipedia.org/wiki/Quantum_error_correction http://en.wikipedia.org/wiki/Quantum_error_correction)
• rorrr2 13y ago
  https://en.wikipedia.org/wiki/Post-quantum_cryptography https://en.wikipedia.org/wiki/Post-quantum_cryptography
• Jach 13y ago
  Bitcoin is relatively safe; there's Glover's Algorithm [1] which would effectively turn computing sha-256 hashes into computing sha-128 hashes (so I read somewhere) which is a problem, but not an impossible one. The majority of the miners plus core devs can agree to upgrade the protocol to use a different hash algorithm, like scrypt (which Litecoin uses) or something specifically made that's not vulnerable to quantum algorithms. (I don't know if scrypt is.) This upgrade wouldn't need to happen overnight, either. I bet the first quantum computer that can compute sha-256 hashes at all will do so slower than the latest classical ASICs of the time. [1] http://en.wikipedia.org/wiki/Grover%27s_algorithm http://en.wikipedia.org/wiki/Grover%27s_algorithm
• xorbyte 13y ago
  FWIW, someone on Crypto.SE reached out and received comments from DWave stating that it's not a problem in the foreseeable future. http://crypto.stackexchange.com/a/439 http://crypto.stackexchange.com/a/439