Spring 2020

Quantum cryptanalysis with Q#

Saturday, Feb. 22, 2020 2:45 pm3:00 pm

Add to Calendar


Martin Roetteler, Microsoft


Calvin Lab Auditorium

We use Microsoft's Quantum Development Kit and its main programming language Q# for resource estimation of large scale quantum algorithms. We discuss applications in quantum cryptanalysis, including work on improved quantum circuits for elliptic curve discrete logarithms and work on implementing Grover oracles for quantum key search on AES and LowMC


Regarding the former, we obtain an affine Weierstrass point addition circuit that has lower depth and uses fewer T-gates than previous circuits. Regarding the latter, we present a Q# implementations of the full Grover oracle for AES-128, -192, -256 and for the three LowMC instantiations used in Picnic, including unit tests and code to reproduce our quantum resource estimates.


Joint work with Thomas Haener, Samuel Jaques, Michael Naehrig, Mathias Soeken, and Fernando Virdia.