Antarctica Starts Here.

For many years in the hidden spaces of the Net, rumors have spread that cryptographic systems as we know them are worthless. Some claim that every cryptographic system out there has already been compromised because the National Security Agency only permits those systems that it has been able to tamper with in subtle ways to be published. Cryptographers they can't compromise, so the stories go, silently disappear and are never to be heard from again. More recently, advances in quantum computing have caused brand new stories to appear on forums and in IRC channels, with the requisite flame wars hot enough to reduce the planet Mercury to slag. The new rumors say that multi-qubit quantum computers exist and can be reliably used to extract plaintext from encrypted material (nobody ever says what kind of encrypted material, it's left to the reader to assume whatever kind they're most concerned about), and that we should all give up on using darknets and encrypted e-mail and turn ourselves in before the Men in Black come and make us all disappear. When asked why this isn't being done to anyone who heavily uses the Tor or I2P darknets (or against cypherpunks who have come in from the cold), arguments to the effect of "If They proved that They had this technology by compromising the network, (Others would start World War III to destroy it/post-quantum cryptography would be deployed by everyone, making all of Their work useless/cryptosystems would be changed to use keys longer than current quantum computers could handle/it is happening, They are keeping it from getting out)" tend to be made. Handy, that.

Then something odd popped up in the news, like it does these days.

But before I talk about what twigged one of my recognizers I should answer an important question: What the hell is a quantum computer?

First, the obligatory disclaimer: I am not a cryptographer or a quantum physicist. I don't work for the NSA, and if I did I certainly wouldn't be allowed to talk about anything like this. I'm not Bruce Schneier, Ron Rivest, Nick Herbert, or anyone on this list. Where possible I'll refer you to source material written by people a lot smarter than I am; to give a full explanation would require retyping all of those books so you'd be better served by going out and reading them yourself, starting with Applied Cryptography.

To explain what a quantum computer is and how one would work, I first need to talk a little about the field of quantum mechanics. Axiom number one: if somebody claims to understand quantum mechanics, they really don't understand quantum mechanics. Nobody really 'gets' quantum phenomena, even the people who study it every day because it's weird, counter-intuitive, and flies in the face of pretty much the rest of physics as we know it. Quantum mechanics is unusual because it is a set of theories which together seem to explain some bizarre experimental evidence (repeatable by anyone who would like to try for themselves) that is internally consistent and can be used to predict the results of new experiments. However, because of the scale quantum phenomena usually take place at nobody is really certain of what the mechanism is underlying them. Do waves really turn into particles and then back into waves when nobody looks at them? What makes two particles pretend to be one particle? Are there even two particles in the first place after entanglement happens? Nobody really knows. For a good overview of quantum mechanics which doesn't require advanced degrees in mathematics or physics I highly recommend the book Quantum Reality: Beyond the New Physics by Dr. Nick Herbert. It is concisely written, witty, and makes a very complex topic accessible to everyone.

It is important to note that quantum mechanics ordinarily deals with things a lot smaller than we can see with visible light, magnify with lenses we know how to manufacture (or possibly can manufacture), or find easily. Past a particular size we really don't know what's going on with any certainty. All we can do is bounce known particles (like protons (hydrogen ions) and electrons) off of other particles we think might be a particular space, measure their diffraction or absorption, and calculate probabilities. Probabilities are key here: until a measurement is made,all we have to work with are statements to the effect of "there is a 40% chance of foo, a 15% chance of bar, and a 45% probability of baz." One of the more illogical-seeming things is that the experimental data which eventually resulted in the creation of what we now call quantum mechanics strongly suggests that, until a measurement is made, the states foo, bar, and baz all exist simultaneously. All of those states collapse into a single state whenever someone (or something) takes a look at them. To put it another way, you don't know what you've got until you poke it with a stick. This phenomenon, called quantum superposition, is the functional principle at the heart of quantum computing.

Numbers are internally represented in computers by strings of bits, or binary digits. As their name implies, bits can be in only one of two states: one or zero, on or off, high or low. So-called quantum bits, or qubits are implemented using particles whose quantum states have been entangled (when they're simulated in software running in a conventional computer or particles suspended in lab apparatus somewhere). What this means is that entanglement of quantum particles gives qubits their ability to represent multiple values simultaneously until a trigger event of some kind occurs that forces them to take on a single, definite value.

Now, let's scale things up a bit. In conventional computers multiple bits (usually eight at a time) are strung together to make bytes, which can represent numbers larger than zero and one by counting in binary. Bytes can then be strung together to represent even larger values, and so on. The date of the article aside, it seems that the same principle applies to qubits. I'm not a physicist but reading through the linked paper on Arxiv I see none of the usual signs of someone pranking their colleagues so, for the moment I'll cite it as a reference. Assuming for the moment that this is correct, it would seem that a qubyte consists of all of the possible values it can hold in the system until it's observed. It would then stand to reason that all of the usual operations of an arithmatic logic unit could then be implemented. To put it another way, it would then be possible to construct a processor core that manipulates quantum values.

Before any actual hardware had been constructed a number of algorithms were developed which are supposed to be able to execute on quantum computing hardware. The most famous of them is Shor's Algorithm for factoring numbers, which I will explain a bit later. First, a little about cryptography, or the art and science of turning plaintext into what appears to be junk so nobody but the intended recipient can read it and vice versa. To put it plainly, bad crypto is easy, lousy crypto is tricky, and good crypto is hard. Not many of us will ever see what might be truely excellent crypto because organizations like the NSA classify their work TOP SECRET/CRYPTO and summon up the hounds of hell to handle security breaches. Insofar as the crypto you or I will ever get to see, most of the cryptosystems in use today are based around the fact that factoring large numbers (on the order of hundreds of digits in length) into two less big prime numbers is hard. By 'hard' I mean that it would take several thousand times the life of the universe to perform the calculations. Every time you add a digit to the length of the number you're factoring, you double the amount of time required to factor it. There are prime decomposition algorithms that can do this but they're considered nontrivial, which is to say that you might get lucky one day far in the future. This is why many attacks against cryptosystems involve nonlinear thinking and dirty tricks like attacking vulnerabilities in the implementation, having knowledge of some of the bits in the key, knowing that some bits that come out of the random number generator really aren't random (which makes the number of keys you need to guess smaller), or some part of the system itself leaking information. This is all assuming that you don't know any magickally esoteric number theory tricks that only three people on the planet know about because the research is so highly classified.

This is why cryptology is considered a black art.

That said, remember what I said about using strings of bits to represent numbers, and systems of quantum bits representing all possible values for that system? Theoretically, a big enough system of qubits could be used to represent key values that would be factored into their constituent primes. RSA keys are usually around 1024 bits in size, while AES keys in practice tend to top out at 256 bits (but the AES algorithm was designed to use up to 512 bit keys). So, if the rumors on the darknets are to be believed all you have to do is get hold of a block of encrypted data, figure out where in the block the session key is (if there is one, and best practices say there should be), load it into a quantum computer with enough qubits, and turn it loose to figure out the keys sooner than the heat death of the universe. All your data are belong to whoever owns a sufficiently advanced quantum computer, be it an encrypted hard drive, encrypted file, or recording of SSL-protected traffic.

Now for the thing that got my attention.

Some time ago a company called D-Wave announced that they were manufacturing quantum computers. Their first production model, dubbed the D-Wave One and costing somewhere in the neighborhood of $10mus, is supposedly a 128-qubit superconducting quantum computer (implemented as a four by four array of eight-qubit clusters) that uses quantum annealing to search the space of solutions to a parallelizable problem for the best answer. It would appear from the descriptions of quantum annealing that the problem solving process is probably closer to thermodynamics than anything resembling computation as we commonly use it. Quantum annealing is not the same thing as performing quantum computations by collapsing the wave function of entangled particles, so two things stand to reason. First, the D-Wave One isn't really a quantum computer, so it follows that secondly, the D-Wave One isn't a threat to encryption as we know it.

If you read the extant documentation on the D-Wave One (there isn't much; I suspect that to get anything substantial that isn't an academic paper you'd have to be part of a company that at least looks like it might be in a position to buy a D-Wave One to get documentation out of their sales team) it says that it was designed specifically for the purpose of optimizing solution sets represented as Markov random fields and that's about it. It's also been demonstrated by using it to search an unstructured database for known entries, computing optimal seating arrangements given certain constraints, classifying images (which is, to be fair, not an easy problem), and solving a sudoku puzzle. None of these are even on the same continent as factoring numbers a few hundred digits in length, and the company itself never makes the claim that the D-Wave One is capable of solving NP-complete problems (like numerical factoring) in anything like a reasonable period of time.

By the way, don't let anyone try to convince you that solving sudoku puzzles is the same as executing a factoring algorithm. I've linked to enough source material to show that isn't the case. There's thinking out of the box, and then there's saying anything to make people think you're right.

Then a couple of articles hit the Net that said that Lockheed-Martin, one of the tier-one defense contractors in the United States, had purchased a D-Wave One for their facility in Bethesda, Maryland. Supposedly they're going to use it to help solve problems involving the integration of an environmental sensor grid and CA (control/analysis) software. There is also word going around that it'll be used to help streamline business processes in a couple of big-budget projects, and there is some speculation that they want to get in on the ground floor of developing this platform. It was probably an article like this that helped fuel the speculation that Lockheed-Martin was going to be cracking crypto for the government (it must be a sign of the times that nobody suggested the defense contractor was going to be cracking crypto for their own nefarious purposes). Also, it would appear that enough controversy has boiled over in a number of fields about the real capabilities of the D-Wave One that an FAQ was written with links to external sources of verifiable facts, as well as a healthy dose of something smelling suspiciously like common sense.

Even though the Wikipedia article about Markov random fields I linked to above has a subsection bearing the title Clique Factorization, I don't think this has anything to do with prime factorization of large values (and if it does, please say so in the comments and provide proof for the education and paranoia of us all!) Also - and I can't stress this enough - if they were going to be pwning the twenty-first century as we know it do you really think that either D-Wave or Lockheed-Martin would announce it?

A little cryptologic history for you: in 1932 Polish cryptologists broke the German Enigma cypher; in 1939 they let France and England in on their work, whereupon the techniques were enhanced by the team at Bletchley Park. Some of the research done at Bletchley Park is still highly classified today. Some time before the United States got involved in the World War Two the US Army's Signal Intelligence Service broke the highest security Japanese diplomatic cryptosystem (codenamed PURPLE) and the cryptosystem used to secure communications by the Japanese Navy (codenamed JN-25), meaning that the Allies were able to decrypt the communications of some of the members of the Axis. However, there is a subtle problem with being able to monitor your enemies' encrypted communications: if you act too often on the information you decrypt your enemies will decide sooner or later that their codes are broken and change them. You'll be back at square one because you gave away your SIGINT capabilities, and you may not be successful in breaking the cryptosystems again. So, if an organization was in possession of a computer that could decrypt even unclassified information they wouldn't tell anyone about it let the shitstorm they stirred up cause everyone to start using cryptosystems resistent to quantum cryptanalysis. At the very least for public key cryptosystems like RSA, to buy yourself some time you could make the keys longer (remember, with every digit you add to the number being factored, you double the amount of time required to factor it).

So, to sum everything up, I don't think we're in any trouble yet. The D-Wave One isn't a general purpose quantum computer or even a dedicated purpose quantum cryptocracker. It's a unique development in the field, to be sure - hell, it appears that they're able to manipulate qubytes now - but it probably does not function in ways that would threaten modern cryptosystems. No peer-reviewed papers anywhere seem to suggest that you could run any of the quantum cryptanalytic algorithms we know of on it, and in fact a few papers have been published claiming that the D-Wave One isn't really a quantum computer (not that this will reassure some people - when in doubt, Appeal To Secrecy). It doesn't look like it has enough qubits on board to factor large semi-primes at the moment (because the quantum factoring algorithms require extra qubits to use as scratch space as well as more quantum logic gates than we can stabilize right now). Regardless of what some people like to claim I don't think that usable quantum computing technology (general purpose or otherwise) has existed in any meaningful form prior to the D-Wave One because the technology just didn't exist to generate and manipulate entangled qubits. By definition they're fiddly and prone to decoherence from thermal noise as well as casual observation collapsing their states prematurely (again, those who Appeal To Secrecy will disagree vehemently). Fixing a system in which not blinking at the wrong time can cause the whole thing to come apart isn't exactly an easy problem to solve because the person solving the problem becomes an integral part of the problem.

By the way, did I forget to mention that Shor's Algorithm only attacks the RSA public key cryptosystem? There are other PK cryptosystems out there which Shor's Algorithm can't be used against.

So I think it's safe to sit back, relax, and not worry overmuch that whoever's recording all of your encrypted BitTorrent traffic is going to find out anytime soon that you've been downloading episodes of My Little Pony. Your encrypted e-mail is going to stay encrypted, and nobody will be able to figure out which theads of the North Central Positronics customer support forums you're anonymously trolling using the Tor darknet. If you really are being a misfeature in the posterior of Somebody Important you actually stand a better chance of someone running a black bag job against you to copy your hard drive or sneak keyloggers into your machines.

Thanks to Kernel Panic for sanity checking me, and for making sure that I stayed on the right track.