5 ms·
Both NSA and GCHQ have quite the history of co-opting smart mathematicians to create secret theoretical advances in cryptography and cryptanalysis, which could
by topynate 13y ago
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.
[1] https://en.wikipedia.org/wiki/Quantum_threshold_theorem https://en.wikipedia.org/wiki/Quantum_threshold_theorem.
Bounds lifted from http://arxiv.org/abs/0802.1464 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.
- Snail_Commando 13y agoIf 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?
- finnh 13y agoNot 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.
- topynate 13y agoI 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/ 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/ 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.
- pbsd 13y ago100-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.
- bdhe 13y agoWhy 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.
- pbsd 13y agoIn 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.
- bdhe 13y agoThanks 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.)
- bdhe 13y agoCan 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'.
- valarauca1 13y agoGover'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] [1] http://en.wikipedia.org/wiki/Grover%27s_algorithm http://en.wikipedia.org/wiki/Grover%27s_algorithm [2] http://en.wikipedia.org/wiki/Data_Encryption_Standard http://en.wikipedia.org/wiki/Data_Encryption_Standard [3] http://www.youtube.com/watch?v=dJh0mIJn6kE&feature=player_detailpage#t=188 http://www.youtube.com/watch?v=dJh0mIJn6kE&feature=player_de...