Quantum Resistance: Chris Peikert & the Power of Lattices

Wednesday, January 5, 2011


Cryptography as a human activity existed millennia before the invention of the computer. Evidence of codes and code-breaking dates back at least to the Greek classical period. Indeed, the “Caesar cipher” is named after Julius Caesar, who reportedly used it to communicate with his generals. Like all encryption methods, it involves a “problem” whose solution holds the key to the code. The harder the problem, the stronger the code.

“Without hard problems,” says Chris Peikert, “we couldn’t do much cryptography at all.”

An assistant professor in the School of Computer Science, Peikert—like all modern cryptologists—makes his living off the assumption that some problems are basically too tough to crack even with the world’s most powerful computers. However, in 2010, that assumption can sometimes look a bit shaky.

Peikert’s research focuses on “lattice-based” cryptography, a departure from the conventional “number-theoretic” approach. In an example of the latter, a cryptographic scheme chooses two almost unimaginably large (and random) prime numbers and multiplies them together. Cryptographers then take the resultant product and build an algorithm off it to encrypt a message. The original primes serve as the decryption key; anyone with the key can decrypt the message. Without it, the only solution lies in discovering the two prime factors of a number that is several hundred digits long (for a sense of scale, Peikert says, the number of atoms in the known universe is perhaps about 80 digits long).

Except these days, computer science is beginning to poke into the mysteries of the universe itself. Quantum computers and the algorithms that could run on them do not just promise faster computation; they promise a method of computation that is wholly different and radically more efficient than conventional processors. At least in theory, quantum computers could divine those primes, breaking the scheme completely—along with every other number-theoretic crypto scheme in wide use today.

What’s a cryptologist to do? Move from the incredibly hard problem … to the mind-bendingly hard.

Lattices have been studied in mathematics since the 19th century; ironically, in the 1970s they were sometimes used to attempt to break number-theoretic encryption. It’s only in the last two decades that they’ve been used to designcryptography schemes.

Lattice crypto works like this: Imagine a sequence of equally spaced points on a line, going off infinitely in both directions. These points constitute a one-dimensional lattice. Next, imagine a similar regular grid in two dimensions like on a sheet of graph paper, except the grid can be “slanted.” Now try to imagine a similar grid in hundreds of dimensions—this is where lattice crypto lives.

The difficulty in breaking lattice crypto comes from the "curse of dimensionality.” As one moves into larger and larger dimensions, it very quickly becomes astronomically hard to find two lattice points that are even moderately close to one another, and the encryption can only be broken by doing just that. A legitimate user creates the lattice knowing two or more nearby lattice points, which make up the decryption key. 

It is simple, elegant and, according to Peikert, so far unbreakable even by quantum algorithms.

Yet another advantage to lattice cryptography is it lends itself quite well to parallel computing—it’s “embarrassingly parallelizable,” as described by Peikert, whose research in large part examines how best to design lattice crypto for parallel systems.

“With this kind of cryptography,” he says, “you can very trivially implement and get the full benefits of a parallel machine. It is just lots of tiny additions that can all be done independently.”

Still, even with all its advantages, Peikert is the only lattice cryptography specialist at Georgia Tech and one of a handful in the world. Why has it not drawn more attention? Until recently, he says, lattices were very inefficient and thus interesting only on a theoretical level. Also cryptologists were only able to create basic encryption schemes (with comparatively basic security levels) out of lattices. Peikert’s research, however, is changing that. He’s shown that working with lattices can be quite practical (likely even fast, in the near future), and he’s designed schemes that are highly expressive and secure.

“For example,” he says, “we can now make a very flexible tool called 'identity-based' encryption, which means that users don't even need to generate their own keys. You could securely encrypt a message to, say, anyone at Georgia Tech, knowing just their name and a single GT-wide key.”

In sum, and largely due to Peikert’s work, lattice-based cryptography is on its way to providing a foundation for the kind of simple, efficient and secure encryption that even Julius Caesar could appreciate.