Recently Google, NASA, and the Universities Space Research Association joined the short list of organizations with access to quantum computing. Is the tough-to-crack math of today's encryption imperiled by the computers of tomorrow?
In the movie Sneakers, a scientist creates a device that can break even the strongest encryption. One of the protagonists delivers Hollywood's best five-second explanation of cryptography, stating: "Cryptography systems are based on mathematical problems so complex they cannot be solved without a key." This prompts his co-conspirator to realize that the scientist must have figured out a way to solve those problems without a key. Ominously, Robert Redford's character observes that the device isn't a code breaker, it's the code breaker. No more secrets. Naturally the device was fiction, but the statement about the foundations of cryptography was and remains true.
That was in 1992. Fast-forward a couple decades, and encryption is no less dependent on computational infeasibility (ignoring quantum key exchange, which is an entirely different thing), but the keys have gotten bigger. For every single bit added to the key size, the time to crack it might as much as double, making sufficiently large keys effectively impossible to break. In the present day, cracking a 512-bit RSA key costs less than buying a code signing certificate and can be accomplished in a few daysa point on the trajectory driving security best practices to recommend ever larger key sizes, such as 1,024 bits, 2,048 bits, and beyond. But what if there came a day when no RSA key sizes were big enough to offer an acceptable level of security?
Recently it was announced that Google and the Universities Space Research Association are collaborating to buy and operate a quantum computer from D-Wave Systems, to be hosted at NASA's Ames Research Center. A quantum computer isn't just a powerful computer, it's a fundamentally different kind of computer that taps into astounding properties of reality manifesting on a microscopic level. Generally speaking, a quantum computer arranges tiny physical systems called quantum bits, or qubits, to be "entangled" with one another. Entanglement, unlike cryptography, has no casual five-second explanation. Hopefully it's both comprehensible and accurate to say that the universe considers all of an entangled system's possible evolutions simultaneously before the system collapses randomly into one of its most likely states, and in this way, entangled systems can be used to (probabilistically) solve some intimidatingly complex mathematical problems that even a classical supercomputer couldn't put a dent in. Problems, perhaps, like cryptographic ones.
In 1994, then-Bell Labs scientist Peter Shor formulated an algorithm for factoring integers that could run in polynomial time on a quantum computer, compared to sub-exponential time for the best known algorithm on a classical computer. "Polynomial time" means that the amount of time needed to solve the problem grows in a way that keeps pace with the size of the problem, at least when compared with higher time complexities, where the required run time quickly becomes absurd. As an example, an exponential-time algorithm might require eight times more computation for each three bits added to the size of the input number, while the amount of computation needed to complete a polynomial-time algorithm might increase by eight times only when the bit count is doubled. If a given problem could be equivalently solved using either a polynomial-time algorithm or an exponential-time algorithm, the polynomial-time algorithm could be used to solve the problem for far larger numbers than could the exponential-time algorithm.
Substitute "key" for "number" above, and you're talking about an algorithm that could make infeasible code-breaking feasible. Using Shor's algorithm, a sufficiently powerful quantum computer could factor any public RSA key, enabling the computer's operator to reconstruct the matching private key, and by extension, decrypt and sign exactly like the key's legitimate owner. Did Google, NASA, and the USRA just gain access to such a computer?
D-Wave Systems, Inc.'s 128-qubit quantum processor.
News coverage is clear that a computer was indeed purchasedwith a $10 million price tag to suggest that the buyers believe in what D-Wave has builtand recent research establishes that D-Wave's quantum computer is actually demonstrating quantum behavior, but can it break RSA? Scientific skepticism of the company's computers seems to be becoming more nuanced, but there are still prominent critics such as Scott Aaronson of MIT who argues that the exhibited quantum behavior won't actually allow the machine to outperform a classical computer. It's also been mentioned that the computer would require multiple qubits for each bit in an integer to be factored, which means that the D-Wave computer couldn't possibly factor a 2,048-bit number even after it's been upgraded to sport 2,048 qubits. And the whole discussion may be moot if, as Joe Fitzsimons of the National University of Singapore previously pointed out, the particulars of the D-Wave computer mean its capabilities fall short of a universal quantum computer and thereby preclude it altogether from running Shor's algorithm.
But note the specificity of these criticisms. The obstacles in quantum computing, and particularly in implementing Shor's algorithm, are in practice rather than principle, and even if D-Wave's present-day quantum computer isn't the solution, a plethora of particle-scale manipulations has been developed and is continually being added to. Inexorably, increasingly sophisticated nanotechnology will cross the ever-lowering threshold of commercial exploitability, and quantum computing will become an unqualified reality, first for the wealthiest organizations, then for the people who hack into those organizations, and eventually, maybe for everyone. Then what?
It's impossible to overstate that the very notion of security depends on integer factorization remaining difficult. Eventually, quantum computing will make factorization easy for the people we don't want to have our secrets, and then much of what's based on present-day public key cryptography will be left in shambles. If the speed with which we've migrated away from MD5 is any indication, we should already be seriously thinking about post-quantum cryptography, in anticipation of the day when a press release announcing the purchase of a powerful-enough quantum computer hits the wires. Unless, of course, we're willing to live in a world with no more secrets.
