Talks

Elliptic curves play a prominent role in cryptography. For instance, the hardness of the elliptic curve discrete logarithm problem is a foundational assumption in public key cryptography. Drinfeld modules are positive characteristic function field analogues of elliptic curves. It is natural to ponder the existence/security of Drinfeld module analogues of elliptic curve cryptosystems. But the Drinfeld module discrete logarithm problem is easy even on a classical computer. Beyond discrete logarithms, elliptic curve isogeny based cryptosystems have have emerged as candidates for post-quantum cryptography, including supersingular isogeny Diffie-Hellman (SIDH) and commutative supersingular isogeny Diffie-Hellman (CSIDH) protocols. We formulate Drinfeld module analogues of these elliptic curve isogeny based cryptosystems and devise classical polynomial time algorithms to break these Drinfeld analogues catastrophically.  

The Hidden Subgroup Problem (HSP) aims at capturing all problems that are susceptible to be solvable in quantum polynomial time following the blueprints of Shor’s celebrated algorithm. Successful solutions to this problems over various commutative groups allow to efficiently perform number-theoretic tasks such as factoring or finding discrete logarithms. The latest successful generalization (Eisenträger et al. STOC 2014) considers the problem of finding a full-rank lattice as the hidden subgroup of the continuous vector space R^m , even for large dimensions m. It unlocked new cryptanalytic algorithms (Biasse-Song SODA 2016, Cramer et al. EUROCRYPT 2016 and 2017), in particular to find mildly short vectors in ideal lattices. The cryptanalytic relevance of such a problem raises the question of a more refined and quantitative complexity analysis. In the light of the increasing physical difficulty of maintaining a large entanglement of qubits, the degree of concern may be different whether the above algorithm requires only linearly many qubits or a much larger polynomial amount of qubits. This is the question we start addressing with this work. We propose a detailed analysis of (a variation of) the aforementioned HSP algorithm, and conclude on its complexity as a function of all the relevant parameters. Our modular analysis is tailored to support the optimization of future specialization to cases of cryptanalytic interests. We suggest a few ideas in this direction.

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.