3 ms·
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
by 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 agoThank you - I did feel I had missed a decade reading the article.
- shadowmint 13y agoI 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)
- pja 13y agoAs I understand things (and I'm not anything close to being an expert, just an interested outsider with enough of a physics education to be dangerous), you can add q-bits to cope with errors introduced by decoherence, but whether these codes work depends quite finely on the error rate. So if you can manage to keep the error rate low enough, then everything will be fine. If it turns out that the error rate depends (for physical reasons) on the the size of the system, then for some size of QC, adding error correcting q-bits will be counter-productive. Given that (in public) no-one has made a QC with more than a handful of coherent q-bits, no-one really knows where the limits are: it might well be that error-correction lets you build arbitrary sized coherent QCs, or there might be insurmountable physical limits that prevent that from happening. I look forward to people finding out! It's a fascinating new experimental field of physics.
- jwr 13y agoWhat about elliptic curves-based asymmetric cryptography?
- ryan-c 13y agoElliptic curve cryptography can also be broken with Shor's algorithm.