Quantum Algorithms for Number Theory and their Relevance to Cryptography

  • Jean-Francois Biasse | University of South Florida

I will report on recent results about quantum algorithms for solving computational problems in number theory. I will show how they impact the security of certain post-quantum cryptosystems. Shor’s quantum algorithm for factoring large integers and solving the discrete logarithm problem has been the motivation for an entire new area of research in cryptology: namely “post-quantum” cryptography. It consists of designing new cryptographic primitives which will resist attacks from quantum computers. In a recent work in collaboration with Fang Song, I presented a quantum polynomial time algorithm for solving the so-called “Principal Ideal Problem” (among other things) in arbitrary fields. We will see how this impacts the security of some ring-based proposals for quantum resistant cryptography. In collaboration with David Jao and Anirudh Sankar, I also described a quantum algorithm which finds an isogeny between two given supersingular curves over a finite field, a hard problem on which some post-quantum cryptosystem rely. Finally, if there is enough time, I’ll mention some recent work on factorization.

Series: Microsoft Research Talks