Talks
Spring 2020

Quantum cryptanalysis with Q#

Saturday, February 22nd, 2020 2:45 pm3:00 pm

Add to Calendar

Speaker: 

Martin Roetteler, Microsoft

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 https://arxiv.org/abs/2001.09580 and work on implementing Grover oracles for quantum key search on AES and LowMC https://arxiv.org/abs/1910.01700.

 

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.