Thirty-Year-Old Encryption Formula Can Resist Quantum-Computing Attacks That Defeat Common Codes

08-19-2010 • Clay Dillow via PopSci

The core advantage of quantum computing -- the ability to compute for many possible outcomes at the same time and therefore crunch data much more quickly than classical computers -- also creates a problem for data security. Once the first high-powered quantum computers are functioning, they'll be able to quickly saw through many of our most common data encryption algorithms. But as it turns out, an obscure encryption code created in 1978 is resistant to all known methods of quantum attack.

Hang Dinh at the University of Connecticut and a few colleagues figured out that CalTech mathematician Robert McEliece's code is structured in such a way that a quantum computer couldn't just pull it apart, at least not by any known process. Rooted in a mathematical puzzle called the hidden subgroup problem, standard quantum fourier analysis simply can't crack the code.

What does all that mean? For a more extensive mathematical explanation, click through to Tech Review's more thorough and astute review of quantum encryption. But in summary, encryption is often conducted using asymmetric codes, meaning there's a public key that anyone can use to encrypt data and a private key for decrypting it. The basis of these encryption schemes is math that flows easily in one direction but not so easily in the other.

Such asymmetric code can be tricky for a classical computer to figure out but quantum computers are well suited to such work. To take a simple example, say a message was encrypted using basic multiplication -- one number is multiplied by a number to get a third number. It's not so easy to look at the third number and quickly determine the two numbers that spawned it.