We noticed you're browsing in private or incognito mode.

To continue reading this article, please exit incognito mode or log in.

Not an Insider? Subscribe now for unlimited access to online articles.

Emerging Technology from the arXiv

A View from Emerging Technology from the arXiv

1978 Cryptosystem Resists Quantum Attack

The search for encryption algorithms that will be safe against attacks by quantum computers has thrown up a surprise, say mathematicians

  • August 18, 2010

Nobody has built a quantum computer much more powerful than a pocket calculator but that hasn’t stopped people worrying about the implications of the post-quantum computing world. Most worried are the people who rely on cryptographic codes to protect sensitive information. When the first decent-sized quantum computer is switched on, previously secure codes such as the commonly used RSA algorithm will become instantly breakable.

Which is why cryptographers are scurrying about looking for codes that will be secure in the post-quantum world. Today, Hang Dinh at the University of Connecticut and a couple of pals show that cryptographers have been staring at one all along. They say that a little-used code developed by the CalTech mathematician Robert McEliece in 1978 can resist all known attacks by quantum computers.

First, let’s a make a distinction between symmetric and asymmetric codes. Symmetric codes use identical keys for encrypting and decrypting a message. Quantum computers can dramatically speed up an attack against these kinds of codes. However, symmetric codes have some protection. Doubling the size of the key counteracts this speed up. So it is possible for code makers to stay ahead of the breakers, at least in theory. (Although in practice, the safe money would be on the predator in this cat and mouse game. )

Asymmetric codes use different keys for encrypting and decrypting messages. In so-called public key encryption systems such as the popular RSA algorithm, a public key is available to anyone who can use it to encrypt a message. But only those with a private key can decrypt the messages and this, of course, is kept secret.

The security of these systems relies on so-called trap door functions: mathematical steps that are easy to make in one direction but hard to do in the other. The most famous example is multiplication. It is easy to multiply two numbers together to get a third but hard to start with the third number and work out which two generated it, a process called factorisation.

But in 1994, the mathematician Peter Shor dreamt up a quantum algorithm that could factorise much faster than any classical counterpart. Such an algorithm running on a decent quantum computer could break all known public key encryption systems like a 4-year old running amok in Legoland.

Here’s a sense of how it works. The problem of factorisation is to find a number that divides exactly into another. Mathematicians do this using the idea of periodicity: a mathematical object with exactly the right periodicity should divide the number exactly, any others will not.

One way to study periodicity in the classical world is to use fourier analysis, which can break down a signal into its component waves. The quantum analogue to this is the quantum fourier sampling and Shor’s triumph was to find a way to use this idea to find the periodicity of the mathematical object that reveals the factors.

Thanks to Shor, any code that relies on this kind of asymmetry (ie almost all popular public key encryption systems) can be cracked using a quantum fourier attack.

The McEliese cryptosystem is different. It too is asymmetric but its security is based not on factorisation but on a version of a conundrum that mathematicians call the hidden supgroup problem. What Dinh and buddies have shown is that this problem cannot be solved using quantum fourier analysis. In other words it is immune to attack by Shor’s algorithm. In fact, it is immune to any attack based on quantum fourier sampling.

That’s a big deal. It means that anything encoded in this way will be safe when the next generation of quantum computers start chomping away at the more conventional public key cryptosystems. One such system is Entropy, a peer-to-peer communications network designed to resist censorship based on the McEliese cryptosystem.

But Entropy is little used and there are good reasons why others have resisted the McEliese encryption system. The main problem is that both the public and private keys are somewhat unwieldy: a standard public key is a large matrix described by no fewer than 2^19 bits.

That may seem less of a problem now. It’s possible that the McEleise system will suddenly become the focus of much more attention more than 30 years after its invention.

However, it’s worth pointing out that while the new work guanratees safety against all known quantum attacks, it does nothing of the sort for future quantum attacks. It’s perfectly possible that somebody will develop a quantum algorithm that will tear it apart as easily as Shor’s can with the RSA algorithm. “Our results do not rule out other quantum (or classical) attacks,” says Dinh and co.

So s more likely scenario for future research is that crytpographers will renew their efforts in one of the several other directions that are looking fruitful, such as lattice-based algorithms and multivariate cryptography.

Either way, expect to hear a lot more about post quantum cryptography–provided the powers that be allow.

Ref: arxiv.org/abs/1008.2390 : The McEliece Cryptosystem Resists Quantum Fourier Sampling Attacks

Tech Obsessive?
Become an Insider to get the story behind the story — and before anyone else.

Subscribe today

Uh oh–you've read all of your free articles for this month.

Insider Premium
$179.95/yr US PRICE

Want more award-winning journalism? Subscribe to Insider Premium.
  • Insider Premium {! insider.prices.premium !}*

    {! insider.display.menuOptionsLabel !}

    Our award winning magazine, unlimited access to our story archive, special discounts to MIT Technology Review Events, and exclusive content.

    See details+

    What's Included

    Bimonthly magazine delivery and unlimited 24/7 access to MIT Technology Review’s website

    The Download: our daily newsletter of what's important in technology and innovation

    Access to the magazine PDF archive—thousands of articles going back to 1899 at your fingertips

    Special discounts to select partner offerings

    Discount to MIT Technology Review events

    Ad-free web experience

    First Look: exclusive early access to important stories, before they’re available to anyone else

    Insider Conversations: listen in on in-depth calls between our editors and today’s thought leaders

You've read all of your free articles this month. This is your last free article this month. You've read of free articles this month. or  for unlimited online access.