Sean Hallgren (Penn State) - Quantum Algorithms and Post-Quantum Cryptography

Quantum Algorithms and Post-Quantum Cryptography

Understanding the strengths and limitations of quantum computers is a fundamental problem.  Finding quantum algorithms that have exponential speedups over the best known classical algorithm is particularly interesting.  So far examples of this type have been mostly number theoretic in nature.  As public-key cryptography is based on computationally hard problems in number theory, developing post-quantum cryptography depends on understanding which problems have efficient quantum algorithms. For example, our efficient quantum algorithm for computing the unit group was one of the ingredients for breaking some systems that are based on finding short generators in ideal lattices. In this talk I will discuss my work in quantum algorithms and its connections to post-quantum cryptography.

Host: Fred Chong