[Infowarrior] - 30 y/o Cryptosystem Can Resist Quantum-Computing Attacks

[Richard Forno]

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

http://gizmodo.com/5615939/thirty+year+old-encryption-formula-can-resist-quantum+computing-attacks-that-defeat-all-common-codes

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.

In math, the process of doing this is called factorizing, and mathematicians factorize through a quality called periodicity — the idea that a mathematical entity with the right periodicity will divide an object correctly while others will not. In 1994, a mathematician created an algorithm that does this very well, and that shortcut to finding  periodicity has a quantum analogue known as quantum fourier sampling. Using fourier sampling, quantum computers can quickly factorise codes, rendering most of our most common encryption schemes useless.

But McEliece's little-used code doesn't rely on factorization, meaning quantum fourier analysis can't break it down. That means it's essentially impervious to all known forms of quantum attack. That's not to say that new modes of quantum hacking won't be developed to decrypt McEliece's system, but it's interesting that while standing at the threshold of a new era of computing power researchers are finding solutions that can keep our data safe more than three decades in the past. [Technology Review]