1. $80MM isn't even in the ballpark of what it would cost to build a quantum-theoretic machine that could break IFP (RSA) or DLP (DH, DSA) crypto.
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.
Hi! I do research in quantum error correction and topological quantum memory.
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 problem is that if quantum computers are viable in 20-30 years, then we need to start using quantum-resistant algorithms today.
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).
Is it really $10M per key? DJB points out that if you're willing to spend a lot of money building parallel hardware, you can get some surprising performance benefits allowing you to crack large numbers of keys at once.
That paper does not apply to integer factorization, and number field sieve computations in general. DJB himself, in another paper [1, §5], argues that is more cost effective to factor one number at a time.
Per that paper, it would be $10M per 'device', with one device managing one key per year. Of course you might as well build more hardware while you are at it.
I'm not sure about that; the paper talks about parallel machines that can search out many keys at once. Its focus is on known plaintext attacks against AES, but it seems like the techniques described could apply to IFP for RSA.
I'm not a cryptographer so I could be totally off base here.
I only had time to skim it, so you might be right. Either way, I think it is only safe to operate with the assumption that 1024bit keys are well within the grasp of projects with modest funding.
Yeah basically. But if this is what the NSA were actually doing, I suspect they'd be throwing way more than $80M at it for a handful of devices, and instead be throwing half a billion at it for half a datacenter full of them. Why build a dozen or two crackers when you have the money for hundreds?
I think this sort of budget indicates more of a research project.
That paper is about 10 years old, or at least the research is. The most current source cited is from 2003. I like to think we've made significant progress in a decade, but in reality inflation would probably be enough by itself to throw those numbers completely out the window.
Quantum computing is undergoing active research and productization (there's a company in Vancouver, BC - D-Wave - working on making a quantum computer product). Historically, quantum computers are considered to be have crypto-breaking applications.
> 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. :-)
D-Wave is what makes the $80MM number look so small: nothing D-Wave has done has come close to threatening cryptography of any sort, and D-Wave has taken almost $80MM themselves.
D-wave's system is fundamentally not amenable to cryptography. As they describe it it's a quantum annealing system; good for finding optimal parameters to some loss function, but not for instance Shor's algorithm.
It would generally seem they've silenced all but a few of their most vehement critics with the latest round of publications (which seem to suggest they are doing better than some of the best CSAT solvers on uninteresting problems). There is some suggestion the next round of hardware will have enough q-bits to do something "really interesting", but I'm still quite skeptical that the device, even if a truly functioning quantum adiabatic machine, shows any sort of true entanglement in a way that would satisfy the non-adiabatic QM aficinados.
What would you use as an RSA replacement? Beyond that, is there a technique that's still relatively simple like RSA (humor me) but impervious to publicly-known quantum attack vectors like Shor's algo?
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:
Elliptic curve cryptography is logically equivalent to prime-factorization cryptography in a sense: both are special cases of the hidden subgroup problem. DLP is also a version of the hidden subgroup problem. Any variant of HSP can be broken by a quantum computer using a variant of Shor's algorithm.
How broken is the question - NSA cracks 2048 keys we just double the key size and are safe for 3-4 more years, or making it so trivial it doesn't matter how big the key size is.
In one of the crypto talks at the 30C3 the speaker mentioned that quantum computers are actually a greater danger to ECC, because of the smaller key sizes. ( I think this sounds plausible, but I am not an expert.)
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.
That's a better question for 'pbsd, but 4096 bit keys are infeasible to attack (outside of quantum computing) using any technique currently known to science.
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.
Is it unreasonable to call a thread that decidedly ignores quantum attacks worthless? I mean, absolutely speaking, given that quantum attacks really are or will be out there, is it not bad advice to suggest systems be built with quantum-vulnerable algos?
Assuming nothing changes, 4096-bit RSA has around 160 bits of security, roughly equivalent to 320-bit elliptic curves.
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).
What do you think would be the correct order of magnitude of cost to build "a quantum-theoretic machine that could break IFP (RSA) or DLP (DH, DSA) crypto"?
Judging from the current state of quantum computing? For the USG to allocate funds with the expectation of a reasonable chance of success? Billions of dollars.
Nobody really knows. It has not been proved that useful QC is possible. (All existing QC is practically useless, and it is not clear that it is even possible to scale it up. This is not snark; if it ever will be useful, we must of course walk before we run.) It is possible that there is no amount of money that will make it useful. It has also not been proved to be impossible, and interesting and tantalizing breakthroughs have been made over time such that it's hard to look at them and firmly promise it's impossible, either. (I fall on the skeptical side myself, but it's what I call "true" skepticism; produce it and I won't try to argue out it out existence, I'll just update my beliefs and move on. And celebrate whoever produces it for doing what I believed to be impossible.)
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.
Well anyone with photovoltaics can demonstrate working economical fusion power at a certain large scale. At least there is an existence proof at the extreme there, which QC does not have.
It's a long-term concern. One way to gauge it is that many researchers working seriously on post-quantum cryptography are far more seriously engaged in pre-quantum work like secure elliptic curve.
Ok thanks, last question and I'll leave you alone.
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)
I wish people could make requests for supporting information like the grandparent post did without getting this kind of snarky reply. Sometimes questions are just questions, not attacks.
In this case, it would be easiest to simply read the sentence as though there's no snark, as I'd bet it's the correct answer.
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.
True, but sometimes questions also don't show a whole lot of effort on the part of the asker, and so the answerer is not inclined to put in much of their own. If I'm going to ask a question and want a thorough answer, I try to at least provide a little background on what I already know.
> Put differently: there are venture capitalists who could successfully fund an effort to break the most widely-deployed public key crypto.
Are you talking about the hardware cost to brute-force a particular keypair, or the cost of somehow compromising the algorithm completely for everyone?
This is the sort of code-breaking the NSA should be doing. If breaking encryption algorithms is possible with quantum computers, we should figure out how to do it before any other nation-state or hacker does. This discovery would hopefully push forward encryption standards toward less breakable encryption.
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.)
If the NSA broke RSA, they'd know that it was only a short matter of time before other intelligence agencies did the same, so it would be pretty stupid of them to not hint to industry that they should upgrade their algorithms.
While the NSA wants communications to be vulnerable to them, they certainly don't want communications to be vulnerable to others.
You don't need a quantum computer to break encryption in order to know that it's breakable. This has already been proven (Shor's Algorthm). You also don't need quantum computers to construct stronger cryptography, immune to quantum cryptanalysis. This has also already been done as well (post-quantum cryptography).
You are likely to need quantum computers to demonstrate that they can feasibly break encryption in order to get people to switch to post-quantum cryptography.
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.
This is the first leak that lower bounds the NSA's capabilities. It suggests that the NSA does not have a quantum computer.
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.
Both NSA and GCHQ have quite the history of co-opting smart mathematicians to create secret theoretical advances in cryptography and cryptanalysis, which could well be relevant given a quantum computer with the following three properties:
* 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.
100-qubit machines would help in breaking some small-key symmetric algorithms (e.g., 80-bit key block/stream ciphers, etc), but it would have negligible effect on public-key crypto.
Why do you say that? Is it because 100-qubits roughly corresponds to attacking 100-bit keys? I am not sure if that intuition is correct. AFAIK, quantum computing is supposed to help with mathematical cryptanalysis like breaking Discrete Log and Factoring. I do not think it will have any effect on attacking symmetric primitives such as AES and SHA.
In symmetric primitives, Grover is the useful quantum algorithm. It reduces unordered (read: brute-force) searches from 2^n to 2^(n/2) operations, and requires n qubits. This is a big deal one the 64-128 bit range: it makes very costly or impossible searches possible. This is one of the reasons it is sensible to want 256-bit symmetric ciphers today.
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.
Thanks for the info. I forgot about the Grover speedup. I think it would still be amazing to get 2^64 operations on a 128-qubit quantum computer to break current 128-bit schemes. It seems like quite a tall order.
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.)
You work modulo p, yes, but the group is the set of points of the curve. The qubit bottleneck seems to be the Extended Euclidean Algorithm to perform modular divisions, which requires the greatest amount of space. Check [1, §6.2] for details.
Can you provide a reference about the fact that 100 qubits would enable qualitative advances in cryptanalysis? I'm also not sure what you mean by `qualitative'.
Gover's Algorithm[1] halves the time to search an unsorted list. Which basically means the time to pick a random number 200 bits long, is now equal to the time to pick a random number 100 bits long. Keys as large as 60 bits are currently vulnerable to attack[2], so logically post grover's algorithm we could attack 120 bit symmetric encryption.
If that doesn't make sense Bruce Schneier explains it also. [3]
If you had to pick, say, three books (or the online equivalent) on quantum computing that are relatively accessible to an educated layman, which ones would you recommend?
I can tell you the book that got me excited about quantum computing: The Fabric of Reality, by David Deutsch. It ranges over a much, much wider field than just QC, but if you want to understand how one of the best theoreticians thinks then there is no better book. Comprehensible by a smart 13 year old (as I was when I read it).
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.
Not the OP, but the one full book I've read on the topic is Scott Aaronson's "Quantum Computing Since Democritus".
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.
When the limit to breaking encryption becomes only cost and not technical hurdles, we have a huge problem.
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.
It's not even tax dollars. The Federal Reserve is at the root of many of our problems -- congressional spending, the industrial war complex & NSA spying -- none of it would be possible if we weren't able to create money out of thin air.
Thus illustrating exactly who is running the world and why when Occupy started up they actually drafted plans to have LEOs assassinate the "leaders" of Occupy.
Not to be a jerk, but Occupy was ineffective. Let it RIP. It spent so much time being leaderless they couldn't decide what the hell they wanted.
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.
Great post. I totally agree, and it is for these reasons I loathe anyone who defends the actions of the USG/NSA.
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.
Exactly. Our propaganda isn't posters of people marching in support of our glorious nation. It's much more subtle. Instead you just make people think they're free when really, they are only free to march along the dotted line. Free to buy what they want. Free to watch 500 channels. The government doesn't even need to enforce it because it's engrained in our culture. Try bringing up how failingly stupid US capitalism is or how broken the voting system is and people spend every breath they have bitching you out for being unamerican. I feel like we got really close to people waking up a little bit around when the 2008 crash happened, but since then it's been business as usual for the most part, unfortunately.
This is likely already the case. I haven't found the reference, but I've heard the number 10 million USD as the cost to brute force a message (I think that covers co-opting an awful lot of supercomputing time for a while).
Good. That's their job. I'm not worried about the NSA using quantum computing, as fiscal realities dictate that it would have to be narrowly targeted at a small subset of the encrypted information out there. I'm fine with them recovering plaintext from pgp-encrypted emails sent between suspected al-Qaeda members. I'm not fine with them break encryption en masse and compromising the integrity of the Internet.
I thought the whole point of using quantum computing to break crypto, is that you can break encryption (e.g. RSA private keys) en masse for the same or less cost than traditional computing requires to break them one-at-a-time.
"Physicists and computer scientists have long speculated about whether the NSA’s efforts are more advanced than those of the best civilian labs. Although the full extent of the agency’s research remains unknown, ___the documents provided by Snowden suggest that the NSA is no closer to success than others in the scientific community.___"
Nothing to see here but false outrage and surprise, move along.
Wait what? The NSA is still going? Surely it should be shut down after its discovery, and the mass outrage it caused worldwide.
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.
I honestly don't understand why the NSA bothers with this. All they have to do is claim that someone is a threat and they are then able to seize said person, secret them away, and make them an unperson in some government facility that we've yet to learn about.
I didn't know when it was going to happend but i knew it would. That 80m investment is nothing, imagine if they will use it to crack sha256 from bitcoins ? A 9-10 billion "business" opened for them.
Plus, privacy = lost
Apologies for being extremely clueless, I don't even understand advanced math, not to mention encryption, not to mention "quantum stuff" - that's why I ask here: is it theoretically possible (or could it be in the future) to use quantum computers for encryption, too? If so, would that reduce options for breaking it to "brute force on the quantum level"? Does this question even make sense?
I don't know of any research into this area, but it's conceivable that you could have an encryption algorithm that is polynomial time (given the key!) on a quantum computer but exponential time classically, and that has some better security guarantees given certain common assumptions. However, quantum algorithms of any sort are difficult enough to invent that we'll likely end up using classical algorithms that 'look' hard to break with quantum computers, i.e. ones where prime factoring doesn't help.
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.
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.