Talks

In this talk, we will first give an introduction on multivariate public key cryptography with the emphasis on the fundamental cryptanalysis tools. We will then discuss a new quantum attack algorithm developed by Gao etc against the multivariate schemes using the HHL quantum algorithm. The complexity of this algorithm depends on the so-called condition numbers.  The work of Gao etc  claims that there is a possibility such an algorithm is polynomial asymptotically. If it is indeed true, then we will have a quantum algorithm to solve a NP-complete problem in polynomial time. We will present a proof we developed recently that in general this new algorithm is actually exponential in terms of its complexity in solving a set of quadratic equations over a finite field. This second part  of the talk is a joint work with Vlad Gheorghiu from University of Waterloo.

We will focus on the open questions surrounding applying Kuperberg's quantum algorithm to solve the Dihedral Hidden Subgroup Problem to CSIDH. We will recap results on understanding the asymptotic complexity of an oracle call, and of the number of queries needed, and then look at some work on concrete complexities for specific instances. We will focus on joint work with Bernstein, Lange, Panny, and myself on computing the exact complexity of one oracle call, and give a list of open questions to be studied in order to get an approximation for secure parameters (according to the definitions given by NIST).

(joint work with Lars Schlieper and Jonathan Schwinger) In the first part of the talk we show that quantum period finding algorithms like Simon and Shor (variants) are surprisingly robust under compression. This implies that in some cryptanalytic relevant cases we can significantly decrease the required number of qubits at the cost of only few more measurements. In the second part we consider the error robustness of Simon period finding on noisy quantum devices, by running experiments on IBMQ-16. We show that our IBMQ-16 data can be tranformed into a problem that is equivalent to LPN. Nevertheless, we achieve quantum speedups for noisy quantum devices even for large error rates.