Quantum Algorithms for Number Theory and their Relevance to Cryptography

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. See more on this video at https://www.microsoft.com/en-us/research/video/quantum-algorithms-number-theory-relevance-cryptography/