Talks

(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.  

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.

Hash functions are ubiquitous in cryptography. One example application are digital signature schemes. On the one hand, there are schemes whose security is solely based on hash functions, like e.g., SPHINCS+. On the other hand, there are several NIST post-quantum candidate digital signature schemes that make use of the Fiat-Shamir transformation, that uses a hash function to make a public-coin interactive proof system non-interactive. Another example is chosen-ciphertext security for key encapsulation mechanisms. Here, many schemes use the Fujisaki Okamoto transformation to lift weaker security to chosen-ciphertext security.   After introducing hash functions, giving an overview over the different points of attack they allow for, I will introduce the two mentioned generic transformations. I will discuss the problems of the (quantum) random oracle model, in which the transformations have security proofs. Subsequently, I will contrast the status of the two transformations with respect to attack opportunities. I will show how the Fiat Shamir transformation allows for an attack matching the bound given by a recently published security proof, but how the situation is unclear for the Fujisaki Okamoto transformation.

This talk aims at providing an overview of recent quantum algorithmic techniqes and improvements, in particular speed-ups for solving linear systems of equations, random walk based search algorithms, and Monte-Carlo methods. We will also highlight some application that are relevant from a quantum cryptanalysis perspective.