The fact that quantum computers could in principle undermine the security of many deployed cryptographic schemes - including RSA and elliptic curve based digital signatures - is known. With the remarkable changes to NSA's Suite B in 2015, it is clear that quantum computing has - despite still being an emerging technology - already tangible effects on deployed cryptographic solutions. This Dagstuhl Seminar on Quantum Cryptanalysis targets the design and study of cryptographic proposals that could be suitable for standardization in the post-quantum setting as well as the study of quantum attacks against currently deployed information processing systems.

Core themes of the seminar are quantum algorithmic innovations to attack today's cryptographic solutions and post-quantum candidates for encryption, signature, and key establishment. We would like to emphasize quantitative aspects of quantum cryptanalysis and anticipate that this successor of Dagstuhl Seminars 11381, 13371, and 15371 can effectively inform standardization efforts in post-quantum cryptography. We will have participants across several disciplines from academia, government, and industry. This composition of the participant group ensures that scientific findings can be disseminated efficiently and increases the potential for genuine impact.

Seminar Goal and Scope

With the foundations of quantum cryptanalysis having been established, this iteration of the seminar wants to provide scientific results that pave the way for an informed transition to quantum-safe cryptographic standards. The seminar aims at leveraging the full potential of quantum attacks and knowledge about quantum computers to identify plausible post-quantum cryptographic solutions for basic cryptographic tasks. Naturally, we plan to address two main thrusts, which are not independent:

Algorithmic innovation. Here we intend to study problem instances and problem classes for which we believe to have (or hope to find) plausible evidence that they are hard for quantum computers - making them a plausible candidate to have post-quantum security rest on them. Ideally, one can establish a provable reduction of relevant security guarantees to a plausibly quantum hard problem. Complementing this, we are interested in quantum speed-ups of classical attack techniques (hybrid algorithms) and novel cryptographic attacks relying on quantum technology. We do care for moderate (not necessarily asymptotic) speed-ups that might be implementable with a small-scale quantum computer already, as this may affect the life-time of cryptographic standards.

Quantum resource estimation. Here we are interested in quantifying the resources of quantum attacks, e.g., what does it cost to forge a root certificate - can we detail a complete quantum circuit for this task? Constraints of quantum hardware (such as geometric constraints or gate fidelities) should be taken into account to obtain realistic statements - replacing or updating cryptographic solutions can be very costly, so requiring such a change deserves a sound justification. For instance, in hybrid algorithms, the reliability and error-correction needs of a classical control logic and quantum components are likely to differ substantially. We want to explore the applicability of existing software tools for advancing the cost analysis of quantum attacks - and to stimulate advances in quantum cryptanalysis.

Discussions are expected to focus mostly around popular post-quantum platforms such as error-correcting codes, lattice problems, systems of polynomial equations, and hash-based signing. Still, we want to leave room for exploring less prominent post-quantum candidates, which show potential. The use of isogenies of elliptic curves is a good example for such an approach.

Creative Commons BY 3.0 DE

Michele Mosca, Nicolas Sendrier, Rainer Steinwandt, and Krysta Svore

• Gorjan Alagic (University of Maryland - College Park, US) [dblp]
• Shi Bai (Florida Atlantic University - Boca Raton, US) [dblp]
• Gustavo Banegas (TU Eindhoven, NL) [dblp]
• Daniel J. Bernstein (University of Illinois - Chicago, US) [dblp]
• Jean-François Biasse (University of South Florida - Tampa, US) [dblp]
• Alexei Bocharov (Microsoft Corporation - Redmond, US) [dblp]
• Johannes A. Buchmann (TU Darmstadt, DE) [dblp]
• Yfke Dulek (CWI - Amsterdam, NL) [dblp]
• Serge Fehr (CWI - Amsterdam, NL) [dblp]
• Tommaso Gagliardoni (IBM Research Zurich, CH) [dblp]
• Vlad Gheorghiu (University of Waterloo, CA) [dblp]
• Maria Isabel González Vasco (King Juan Carlos University - Madrid, ES) [dblp]
• Sean Hallgren (Pennsylvania State University - University Park, US) [dblp]
• Peter Hoyer (University of Calgary, CA) [dblp]
• Andreas Hülsing (TU Eindhoven, NL) [dblp]
• David Jao (University of Waterloo, CA) [dblp]
• Stacey Jeffery (CWI - Amsterdam, NL) [dblp]
• Elena Kirshanova (ENS - Lyon, FR) [dblp]
• Stavros Kousidis (BSI - Bonn, DE) [dblp]
• Thijs Laarhoven (IBM Research Zurich, CH) [dblp]
• Bradley Lackey (University of Maryland - College Park, US) [dblp]
• Tanja Lange (TU Eindhoven, NL) [dblp]
• Yi-Kai Liu (NIST - Gaithersburg, US) [dblp]
• Alexander May (Ruhr-Universität Bochum, DE) [dblp]
• Michele Mosca (University of Waterloo, CA) [dblp]
• Michael Naehrig (Microsoft Research - Redmond, US) [dblp]
• Anderson Nascimento (University of Washington - Tacoma, US) [dblp]
• Maria Naya-Plasencia (INRIA - Paris, FR) [dblp]
• Phong Nguyen (University of Tokyo, JP) [dblp]
• Ray Perlner (NIST - Gaithersburg, US) [dblp]
• Martin Roetteler (Microsoft Corporation - Redmond, US) [dblp]
• Alexander Russell (University of Connecticut - Storrs, US) [dblp]
• John M. Schanck (University of Waterloo, CA) [dblp]
• Claus Peter Schnorr (Goethe-Universität - Frankfurt am Main, DE) [dblp]
• Nicolas Sendrier (INRIA - Paris, FR) [dblp]
• Daniel C. Smith-Tone (NIST - Gaithersburg, US) [dblp]
• Rainer Steinwandt (Florida Atlantic University - Boca Raton, US) [dblp]
• Adriana Suárez Corona (University of León, ES) [dblp]
• Tsuyoshi Takagi (University of Tokyo, JP) [dblp]
• Jean-Pierre Tillich (INRIA - Paris, FR) [dblp]
• Dominique Unruh (University of Tartu, EE) [dblp]
• Frank K. Wilhelm (Universität des Saarlandes - Saarbrücken, DE) [dblp]