Technology Review: Blogs: arXiv blog: 1978 Cryptosystem Resists Quantum Attack

Technology Review: Blogs: arXiv blog: 1978 Cryptosystem Resists Quantum 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."