There is absolutely no way that the NSA or anyone else is going to build a quantum computer in the next twenty years.
The reason is that the overhead of error correction is, while feasible to meet long term, too large. The number of physical qubits that must exist in a system that can work with K logical qubits is O(K log(E)^c), where E is the logical error rate, which must be inversely proportional to the total runtime of the maximal feasible algorithm, and c is a constant that depends on the memory architecture (quantum error-correcting code, in general a subsystem of a degenerate ground state of an effective Hamiltonian on the qubits).
Shor's algorithm requires ~3N logical qubits and O(N^3) steps, where N is the length of the number to be factored. The minimum feasible size for a computer that could perform this calculation on a typical 2048-bit semiprime is several hundred thousand physical qubits.
By contrast, the largest quantum computer thus far constructed has less than ten qubits. Even if we double every 18 months (not at all likely), that's a good 22 years away with the most optimistic outlook for quantum stability.
Far more than 80 million dollars has already been invested into quantum computing research. I think it's money well spent, but it's not going to change the nature of the problem.
The NSA has already admitted that they are especially holding on to encrypted data for longer periods of time (and after the Utah data center, probably forever). In 20 years time they can start decrypting all that data with a quantum computer.
Think about it. Today's 20 year olds, could be tomorrow's 40-50 year old politicians. All sort of juicy data could be abused then to discredit, or worse, blackmail those politicians.
Right now the best weapon against it seem lattice-based encryption, so we should start working on it, so we can start using lattice-based cryptosystems within 5 years, which is a pretty small amount of time to verify this type of encryption and make it very usable, but I don't think we can afford more than that.
Homomorphic encryption using lattices is something companies like Google should already be researching and trying to implement, if they really care about user privacy (and they should, because I predict an increasingly hostile movement towards Google's data mining in the future, and they need to take steps to "fix" all the privacy invasions they are currently doing with their data mining).
http://tau.ac.il/~tromer/papers/cbtwirl.pdf
tl;dr - estimate is ~$10M
I'm not a cryptographer so I could be totally off base here.
I think this sort of budget indicates more of a research project.
> If it is feasible to build a quantum-theoretic machine to break RSA, it is vitally important that the NSA attempt to do so; such work is at the very core of their mission.
This is a key thing to remember - expect groups tasked with breaking crypto to be working on breaking crypto. In other news - Pope is Roman Catholic, water is wet. :-)
(This is Daniel J. Bernstein).
https://en.wikipedia.org/wiki/Elliptic_curve_cryptography
but, searching I found that it is apparently vulnerable to quantum computing attacks (wikipedia points me to: Nielsen, Michael A.; Chuang, Isaac L. Quantum Computation and Quantum Information. p. 202) and also found this:
http://www.mathcs.richmond.edu/~jad/summerwork/ellipticcurve...
https://en.wikipedia.org/wiki/Learning_with_errors
When last I checked there was still a lot of debate about choosing secure parameters for LWE-based cryptosystems, so it would be pretty risky to start using that right now.
If its just a matter of that amount of money, then the NSA has almost assuredly already broken it, no?
I'm fond of saying that the thing that takes out RSA-2048 is likely to take out RSA altogether, so, over the medium term, look to Elliptic Curve instead of RSA. New systems should be designed with ECC instead of classical IFP/DLP crypto.
Depending on how Moore's law progresses and our understanding of the Universe, you may never need to change (ignoring all other possible ways your key can be acquired).
Does the current state of quantum computing excite or keep security researchers awake at night?
This is rather like commercial fusion research; it has not yet been shown to even be possible to economically use fusion for power generation, yet it has not been proved impossible either. Contrast this to nuclear fission research, which at this point is more like engineering; modulo lawsuits and administrative compliance, we could probably take a pretty good guess at what it would take to, say, bring a commercial thorium reactor online.
Could you recommend some relatively accessible reading for the layman on how the security world would react to a sudden shift into the post-quantum world?
And, in your opinion, how concerned should average Joes and Janes, like me, be concerned about a sudden shift to a post-quantum world?
Edit: For example: Would my bank be safe? Would my health records be safe?
(On this hyperbolic fear legitimacy scale: Y2K <----> Cryptopocalypse)
Quantum computing is brilliant at certain types of computation, it's not a Singularity-level silver bullet. Simplified to the point of lie, it can transform certain classes of computation by taking shortcuts; the oft referenced Shor's algorithm, for example, can factor a prime in polynomial time, which is immensely faster. [0]
But that wouldn't necessarily be enough to break crypto, as anything that wasn't based on factoring a polynomial would need another algorithm. Also, while fast, the algorithm is not instant nor easy to run: a lot of qubits would be needed, and the current state-of-the-art can't support that level of computation against large numbers without a prohibitive amount of expense (qubits are not naturally stable at room temperature). For comparison, factoring a 1024 bit number would take 1024 qubits together, while only a few have ever operated together under ideal lab conditions (Wikipedia notes IBM's accomplishment factoring 15 with 7 qubits, and notes the number 21 was factored in 2012).
There is a huge amount of work in the pipe, and there's plenty of room to be shocked and amazed by new developments. But it will require innovations that would revolutionize whole industries. This is still very new tech, decades from maturity (though naturally not from commercial early-adoption).
At least, I think that's what tptacek meant. Sorta.
Actually, Shor's algorithm is for factoring composites, not factoring primes.
Don't feel bad about that little word mixup. You are in good company. Bill Gates did it in his book "The Road Ahead".
Are you talking about the hardware cost to brute-force a particular keypair, or the cost of somehow compromising the algorithm completely for everyone?
Aren't the most recently dated revealed Snowden docs almost 3 years old with the bulk being ~5 years old?
2. $80MM is way, way past the threshold believed to be required to break the most widely deployed public-key crypto, RSA-1024. Put differently: there are venture capitalists who could successfully fund an effort to break the most widely-deployed public key crypto.
3. If it is feasible to build a quantum-theoretic machine to break RSA, it is vitally important that the NSA attempt to do so; such work is at the very core of their mission.
I have no insight into what's actually happening behind this disclosure, but the price tag on it suggests to me that it's just a research project.
Since NSA is the kind of organization that historically spends $80MM on paper clips, the number suggests to me that quantum-theoretic attacks on IFP and DLP crypto aren't currently a serious thing. But that's a wild guess.