08.09.13 - 13.09.13, Seminar 13371

Quantum Cryptanalysis

The following text appeared on our web pages prior to the seminar, and was included as part of the invitation.

Motivation

This seminar is a sequel to Dagstuhl Seminar Nº 11381 with the same title which was held at Schloss Dagstuhl in September 2011. The goal is to develop a better understanding of the potential of quantum algorithms for solving algorithmic questions with cryptographic significance. Joining forces of classical cryptography and of quantum computing, we want to find plausible computational assumptions that help in developing robust ‘post-quantum cryptography’. Motivating examples are a cryptographic scheme by Regev and a candidate one-way function suggested by Moore, Russell and Vazirani: the former is a classical public key scheme based on the hardness of the unique shortest vector problem for lattices. It can be argued to be resilient against quantum attacks by relating security guarantees to a hidden subgroup problem in dihedral groups for which despite much effort by experts on quantum algorithms, no polynomial quantum algorithm has been found. Moore et al.’s proposal rests on an argument from lower bounds on the size of a quantum memory that would be required for the standard quantum approach to graph isomorphism by reducing again to a hidden subgroup problem.

As in the previous seminar, the group of participants will involve both colleagues working in classical cryptography and colleagues working in quantum computing. Discussions crossing community boundaries are a central goal, and the following topics are of particular interest:

  • Quantum attacks on currently deployed schemes: We are interested in quantitative estimates for the resources (such as the number of qubits and quantum gates) that are needed to carry out quantum attacks against established cryptographic schemes.
  • Quantum algorithms to attack potential new hardness assumptions: Especially the quantum perspective on lattice problems, decoding problems for error correcting codes, computational questions in number theory, and multivariate cryptography are of interest.
  • Quantum computational assumptions: We are interested in problems that are currently considered as intractable, even for a quantum computer, and might have cryptographic potential. This includes technological assumptions, like bounded quantum-storage.

The general organization of the seminar will be similar as for the predecessor; we plan to schedule the talks so that there is ample time for discussions and personal interaction.