NSA seeks to build quantum computer that could crack most types of encryption
washingtonpost.com
washingtonpost.com
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.
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".
Does the current state of quantum computing excite or keep security researchers awake at night?
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)
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.
(This is Daniel J. Bernstein).
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.
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...
> 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. :-)
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.
Are you talking about the hardware cost to brute-force a particular keypair, or the cost of somehow compromising the algorithm completely for everyone?
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).
Aren't the most recently dated revealed Snowden docs almost 3 years old with the bulk being ~5 years old?
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).
What we should not do is use those discoveries to illegally spy, but rather to improve our security. Unfortunately, the NSA has lost credibility in contributing to encryption standards, so how that would happen is unclear.
Breaking encryption with new technology is entirely different than subverting encryption technologies intentionally or using their asymmetrical powers to tap into communication systems. Any attacks that can be discovered will hopefully first be discovered by relatively good actors (US intelligence) rather than relatively bad ones (Chinese intelligence.)
While the NSA wants communications to be vulnerable to them, they certainly don't want communications to be vulnerable to others.
The fact that an algorithm exists for a non-existent computer system does not meet that bar. Conventional computers can also break encryption given enough speed and power - it's just not yet feasible as with quantum computers.
If the NSA did have a quantum computer they might fund a project like this as it would be suspicious not to.
EDIT: The more I think about this, the less it says about the NSA capabilities. They may attempt multiple paths to QC. The classification document that WashPo released (http://apps.washingtonpost.com/g/page/world/classifying-nsa-...) outlines Level A (public) and Level B (classified) research. All this shows is that the NSA is dedicating at least ~0.8% of their budget to QC.
* Fully general. By this I mean capable of solving BQP problems in polynomial time. This excludes D-Wave machines, for example.
* Sufficiently large. 100 qubits would probably enable qualitative advances in cryptanalysis.
* Low enough error rate. This is a slightly redundant requirement, as too high an error rate would provably prevent the computer from being asymptotically faster than classical - which is what we care about.
The last requirement is due to the quantum threshold theorem[1]. Briefly, there is an error rate below which quantum computing is possible and above which it is not. The precise value is not known but it is probably over 1% and, at least for some kinds of circuits, under about 40%. That means that at the theoretical level, the task is to create a model of computation that has as high a threshold limit as possible, and then to design an error correcting scheme that comes close to that limit. This is something that a secret agency could plausibly do in-house.
However, there is then the question of implementing the model of computation in a physical system, with a sufficiently low error rate. NSA, GCHQ etc. are not known to have this sort of experimental expertise - they would probably have to contract it out (and indeed this is the major piece of new information in the article). The history on fundamental advances over civilian technology shows that this normally depends on co-opting basically the entire research community working in the field - as in radar, nuclear weapons, stealth etc. This is not at all the case for experimental quantum computing, which is not in practice treated as a 'sensitive' field.
Thus it is my opinion that the NSA may well already have some theoretical tricks up its sleeve that it can use in the future for a decent edge, but is unlikely to get the opportunity to use them before quantum computing becomes considerably more feasible in the unclassified world.
[1] https://en.wikipedia.org/wiki/Quantum_threshold_theorem. Bounds lifted from http://arxiv.org/abs/0802.1464. Qualifications: I studied the mathematics of quantum computing as a Masters student, although I can't claim to still be current on the state of the art.
It gets a bit laborious walking through the entire "complexity zoo", but does a good job of laying out the general space in which quantum computers may (and may not, as far as we can tell) be useful.
If you have some mathematical maturity, I heartily recommend Quantum Computing since Democritus, by Scott Aaronson. The book's web page is at http://www.scottaaronson.com/democritus/, where you will also find freely available the lecture notes on which the book is based. Scott Aaronson's blog (http://www.scottaaronson.com/) is also a very valuable source of insider knowledge on QC, much of it targeted at a broader audience. I recommend his "Ask Me Anything!" posts for a good breadth of topics and technicality.
Schrödinger's Killer App by Jonathan P. Dowling is a pleasant alternative to Fabric of Reality if the latter is too out-there for your tastes. No equations, but it definitely has some conceptual meat on it.
But when it comes to public-key crypto, you need more. Shor's algorithm (applicable to integer factorization, but also to discrete logarithms and some other schemes) originally needed 2n qubits to factor an n-bit number. Later improvements put this somewhere over n qubits for an n-bit number. So RSA-1024 would need at least a 1024-qubit machine. Elliptic curves need a small multiple (6, last I checked) of the bitsize of the prime modulus, so the same 1024-qubit machine might be able to break a 160-bit elliptic curve.
Does using Shor to attack EC discrete log require us to work in the group of integers mod p? If it can work with the generic group then you might not need to go beyond 160-qubits. (But all of the above reasoning is based off the wiki article, so I might be mistaken.)
If that doesn't make sense Bruce Schneier explains it also. [3]
[1] http://en.wikipedia.org/wiki/Grover%27s_algorithm
[2] http://en.wikipedia.org/wiki/Data_Encryption_Standard
[3] http://www.youtube.com/watch?v=dJh0mIJn6kE&feature=player_de...
Because there is no limit to tax dollars the government would be willing to spend to spy on it's own citizens. Congresspeople are already happy to line up to throw money at the spy machinery which is the new arm of the industrial war complex.
This underscores the need to revive Occupy.
We have to be more targeted about the changes we want. "We're pissed off about lots of stuff and you better fix it all or else!" isn't going to work.
At this point though, it's almost like the house is completely engulfed in flames. Which section do we put out first?
- The corrupt banking and money system? Our capitalist system is an immense ponzi scheme. Economists act like you can have infinite growth. Forever. They're delusional. At some point, you run out of people's back to crawl on top of and your system collapses.
- On top of that, we have a one-party system: the capitalist-imperialist party. It is impossible to get a non-capitalist-imperialist elected in the United States! We need a voting system overhaul, but good luck getting that when everyone is bickering about abortion and gay marriage. The system has successfully turned us against ourselves on issues that do not affect the overall outcome of the nation, leaving the people in charge to do whatever they feel like.
- We have a government agency with a bottomless pit of money spying on everybody, effectively cutting off our freedom of speech (who is going to speak out against the government when a giant eyeball hovering over them at all times?) At this point, there's no ring to cast into the volcano either. Even if the NSA's activities are ruled unconstitutional, who's going to stop them?
- Our country's leaders are spending millions to create more terrorists by bombing countries in the middle east with drones. You take out some kid's house and family with a drone, what do you expect is going to happen? They'll thank you for keeping the streets safe? No, they grow up to be a "terrorist."
I hate to be one of those "the sky is falling" nerds, but if it takes as much work and pressure as it has to get the people around you to barely even raise an eyebrow at what's going on, you know you're not headed for something good.
I also find it incredibly naive of others who make statements, here on HN and elsewhere, that the US is NOT a real tyranny as compared to others like Russia/CHina/Whatever.
Sure it is - its just much much more successful at population control.
For comparison, but by no means state-of-the-art, there's Deep Crack, which I thought was a neat did searching for a cost: http://en.wikipedia.org/wiki/EFF_DES_cracker
http://www.washingtonpost.com/world/national-security/nsa-se...
Nothing to see here but false outrage and surprise, move along.
The fact they're continuing their work, is blatant contempt and disregard for not just the citizens of the U.S. but for the rest of the world, too. American tax payer money goes to fund this, it's absolutely criminal. They're expecting you to pay for them to spy on you, for you 'safety'. We need counter measures or to target them directly. They need taking down.
It's absolutely insane, 'okay, you caught us! But we don't care!' is the message this act emits.
How to reduce the value of the Internet as much as possible for everybody.
Nice, really nice.
Seriously, I don't think it's illegitimate to pursue new technologies that would render the old ones obsolete.
The real quantum defence appears to be something rather different. Quantum cryptography (https://en.wikipedia.org/wiki/Quantum_cryptography) uses polarised photons to create very strong guarantees that your communication is secure. We can say that if you do the engineering correctly, the laws of physics would have to be violated to intercept your messages.
http://rdist.root.org/2008/10/24/quantum-cryptography-is-use...