Lattice Cryptography
Thursday, September 14th, 2006I was under the impression that the uncracked public-key cryptosystems were all based on number theory, which made them vulnerable to variants of Shor’s algorithm. Yesterday I learned via Dave Bacon that there are cryptosystems based on the hardness of finding the shortest vector on a lattice. Here is a survey paper on the subject by Oded Regev. There is also the McEliece cryptosystem, which is based on coding theory.