Search Talks

Minkowski's first fundamental theorem in its counting form tells us that in a Euclidean lattice of determinant 1, the number of lattice points contained in any origin centered ball is essentially lower bounded by its volume. One may wonder if this statement can be reversed: namely, if all sublattices of the lattice have determinant at least 1 (i.e. are sparse), can one derive a good upper bound on the number of points in any origin centered ball? Regev and Stephens-Davidowitz (STOC `17) answered this question in the affirmative, establishing a so-called reverse Minkowski theorem. Building on this work, our first main result is an algorithmic counterpart to the reverse Minkowski theorem, where we give a Discrete Gaussian Sampling based exponential time algorithm for finding O(log n)-approximately densest sublattices. The initial motivation for this theory, as developed by Regev and the author (FOCS `16), was to tackle the dual problem of tightly characterizing the covering radius of a lattice (i.e. farthest distance to the lattice) in terms of only determinants of projected sublattices. In particular, we showed that assuming the reverse Minkowski theorem, the covering radius of a lattice can be determined up to polylogarithmic factors using only such determinantal information, resolving a conjecture of Kannan and Lovasz (Annals of Math `88). For our second result, under the assumption that the integer lattice approximately maximizes the covering radius among all so-called stable lattices, we improve this approximate characterization to be constant factor tight, removing any dependence on dimension. In particular, this conjecture implies that the problem of approximating the covering radius up to O(1)-factors is in coNP.

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.

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.

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.

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