This story is over 5 years old
Tech by VICE

How Five Times Three Equals a Hacking Revolution

The thing used to protect most of your digital secrets -- credit card numbers, email accounts, bank account information, whatever -- is a peculiar sort of lock and key, a variety of encryption called public key cryptography. In this secrecy scheme, the...

by Michael Byrne
Aug 21 2012, 2:30pm
The thing used to protect most of your digital secrets — credit card numbers, email accounts, bank account information, whatever — is a peculiar sort of lock and key, a variety of encryption called public key cryptography. In this secrecy scheme, the key being sent (what would allow your secrets to be viewed) is buried within a math problem too hard for even our best computers to figure out within a reasonable amount of time. Specifically, that problem is finding the prime factorization of a very large number. If you were to try and find that factorization for, say, a 601 digit number, the current upper-bound on numbers actually used in service of encryption, our current best algorithm used with a classical bit-based computer would take longer than the age of the universe to do the calculation. That’s not a particularly hackable system; it’s just a quirk of math that factorizations are relatively chaotic and, thus, hard to find. A quantum computer doing factorizations, however, is another story, and researchers at UC Santa Barbara have built the first solid-state quantum processor capable of just that.
The processor in question. Image: UCSB

A fully-functional quantum computer should be able to take on those 601 digits in minutes. “A quantum computer can solve this problem faster than a classical computer by about 15 orders of magnitude,” said Erik Lucero, the lead author of a new paper in Nature Physics describing the processor. “This has widespread effect. A quantum computer will be a game changer in a lot of ways, and certainly with respect to computer security.” Basically, a quantum computer up against classical encryption is like a truck-mounted battering ram against a rotting wood door.

Lucero’s computation was a bit smaller than 601 digits; instead, his computer found the constituent prime factors of 15, of which there are a whopping two, 2 and 5. That’s fine actually, given that the processor he used only had four qubits (like transistors) and five microwave resonators to work with, and that just controlling those elements is challenge enough. Understand that while nine is a small number, quantum computing involves computations happening in parallel — rather than computations happening one at a time, they’re happening all at once (sort of). Part of Lucero et al’s accomplishment here is that their computing architecture could potentially scale up to the full-on quantum computers of the future, e.g. when a processor has millions of quantum elements working on a problem instead of nine.

“Now that we know 15=3×5, we can start thinking about how to factor larger — dare I say —more practical numbers,” Lucero said.

The research team’s processor performed something called Shor’s algorithm. Which is a clever way of incorporating some structure/order into prime factorizations by using what’s known as the period (how often a sequence repeats) of a certain mathematical function. The algorithm would work for classical computing somewhat, but still not anywhere near enough to solve prime factorization problems in a reasonable amount of time. But Shor’s algorithm finds good use in quantum computing, getting past the mess that results from trying to parse large-scale factorizations with parallel processing. In any case, the combination of the two is all kinds of destructive for this most difficult math problem. Well, kind of — it’s actually only right about half the time, which, when you’re guessing encryption keys, perhaps isn’t too shabby.

In any case, death lurks for classical encryption. So is that the end of digital secrets? Hardly. Quantum encryption is gearing up for life beyond theory just as quantum computing is. “[Quantum encryption] is not only harder to break, but it allows you to know if someone has been eavesdropping, or listening in on your transmission,” Lucero noted. “Imagine someone wiretapping your phone, but now, every time that person tries to listen in on your conversation, the audio gets jumbled. With quantum cryptography, if someone tries to extract information, it changes the system, and both the transmitter and the receiver are aware of it.”

So I guess we’ll just be back where we started — with a more or less secure method of communicating/guarding secrets — only it’ll probably be a lot more expensive.

Connections: