The Math, Clearly Explained Hang Dinh et al. via arXiv:1008.2390v1

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]

10 Comments

This is the equivalent of finding out that an ancient mummy has the cure for AIDS or cancer. Weird.

Ha ask and you shall receive. I just posted on another article asking the difference between probability processing and quantum computing and this article answered that. Sqweet.

Solace

from Ojai, California

Or that Romans had a better recipe for cement than we do now? (Turns out they did.)

Yeah well back to the basics

This is more like finding a book made 30 years ago is still interesting today.

Just because a problem from 30 years ago hasn't been cracked doesn't mean it's that much better, but just different. If this started being used in regular encription I'm sure someone would figure out how to crack it in a month or so.

There are languages that are thousands of years old that people have a hard time deciphering, but that doesn't make them better, only different than we're used to.

Actually this is not surprising at all for me. People seldom realize that mathematicians have been "solving" "problems" long before they were found useful, for a long time. I remember when I heard about the how they patented the ZIP algorithm that was in fact a mathematically formula developed 40 years before that (they didn't have to worry the mathematician was long dead).

And as to the idea that these are just different, and once known they could be cracked in a month. The basic math used in current encryption has been known for many decades if not centuries, and they certainly haven't been able to break them in a month. Sure eventually they might break them, but that doesn't mean that it will be simple.

as tcolguin said, mathematicians have been solving problems we didnt even know were problems yet. i recall some professors doing excessively complicated math work to see who would get the biggest slice of pizza, and it ended up being useful for some obscure purpose. google fails me for recovering this article bssed on what i remember :(

I actually find this incredibly amusing.

Here's why :

"Security researchers using hardware hacking techniques have unearthed generic flaws in supposedly ultra-secure quantum cryptography systems.

The security of quantum cryptography hinges on using the fundamental properties of quantum physics for quantum key exchange. Any attempts to monitor this exchange would inevitably be detected as increased noise on the line and an abandoned data exchange. That principle remains solid and the attack, like others before it, relies on exploiting implementation flaws."

There's even a documentation as pictures and reports, here:

www.iet.ntnu.no/groups/optics/qcr/hacking-commercial-quantum-cryptography-2010/

(not quite sure I followed the link rule - says starting with www but anyway apologies in advance ..)

Personally, I would call any claim of fool-proof security (which it may not be directly, but it does imply it in some form and the point remains the same) not only foolish, but it's in essence using the old security through obscurity thinking (which is foolish actually).

And of course, just realized one more thing :

It could be a specific algorithm (as I see now). However, again, the same point is there. Two commercial quantum physic encryption algos were cracked, which is to say they can all be, in time. Sure, it's interesting, but I don't think there will ever be an algorithm that is 100% secure. Unfortunately (fortunately to some) there's so many different ways, even indirectly (brute forcing) - you still get what you want. Though I guess with semantics, you can say the algorithm is not cracked. But the main point (I would think) is that the algorithm is there to protect something, and no matter how it's done, if it's found or discovered, it's not protecting that thing.

humbug is onto something, true quantum computing would be able to "hear" when it was being cracked . What is being called quantum computing is very very basic. probably the equivalent of the first division of a fetus. any real quantum computer could bypass any existing system, virtually instantaneously. Likely true quantum encryption is unbreakable except to those meant to decrypt it. in theory any attempt to "listen" would entangle the system, making it very easy to track. quantum computers might put security software makers out of business.


138 years of Popular Science at your fingertips.

Innovation Challenges



Popular Science+ For iPad

Each issue has been completely reimagined for your iPad. See our amazing new vision for magazines that goes far beyond the printed page



Download Our App

Stay up to date on the latest news of the future of science and technology from your iPhone or Android phone with full articles, images and offline viewing



Follow Us On Twitter

Featuring every article from the magazine and website, plus links from around the Web. Also see our PopSci DIY feed


February 2012: The Future of Fun

Science is reinventing play, from extreme sports to gamification to ridiculous roller coasters to the playgrounds of tomorrow, and this issue is chock full of fun. Also, on a less fun note: Did global warming destroy my hometown?


circ-top-header.gif
circ-cover.gif