Cristopher Moore, University of New Mexico
Abstract
Since Shor's algorithm breaks RSA cryptography, it makes sense to look for post-quantum cryptosystems: cryptosystems that can be carried out with classical computers today, but which will remain secure even if and when quantum computers are built.
In this talk I will give an introduction to the McEliece and Niederreiter public-key cryptosystems, which are based on error-correcting codes, and argue that they are possible candidates for post-quantum cryptography. Specifically, I will show that they are immune to quantum algorithms based on the natural reduction to the Hidden Subgroup Problem, where we construct a coset state and perform strong Fourier sampling on it. This does not rule out other quantum (or classical) attacks on these systems, but it suggests that additional algorithmic ideas would be needed to break them.
Part of a MITACS seminar series
This is joint work with Hang Dinh (Indiana, South Bend) and Alex Russell (Connecticut).