Dagstuhl Seminar 17401
Quantum Cryptanalysis
( Oct 01 – Oct 06, 2017 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/17401
Organizers
- Michele Mosca (University of Waterloo, CA)
- Nicolas Sendrier (INRIA - Paris, FR)
- Rainer Steinwandt (Florida Atlantic University - Boca Raton, US)
- Krysta Svore (Microsoft Corporation - Redmond, US)
Contact
- Andreas Dolzmann (for scientific matters)
- Susanne Bach-Bernhard (for administrative matters)
Schedule
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
Motivation and scope
Like its predecessors, this fourth installment of a Dagstuhl seminar on Quantum Cryptanalysis was devoted to studying cryptographic solutions that might be suitable for standardization in the post-quantum setting and to studying quantum attacks against currently deployed cryptographic solutions. Two main thrusts were of particular interest:
Algorithmic innovation. Quantum resources can be used in various way for attacking cryptographic solutions, and the seminar included multiple presentations on exploiting quantum resources for cryptanalytic purposes. Both attacks on symmetric and asymmetric primitives were considered, and there were lively discussions on the feasibility of mounting particular types of attacks. Complementing the presentations on quantum attacks, the program included presentations on advanced classical algorithms, raising the question of identifying possibilities to speed up such classical attack venues through quantum "subroutines."
Quantum resource estimation. It goes without saying that asymptotic improvements are of great interest when trying to tackle computational problems underpinning the security of cryptographic constructions. However, when looking at an actually deployed scheme, quantifying the exact resources (such as the number of qubits) needed by an attacker is relevant to judge the practical impact of a proposed attack strategy. The seminar included presentations on the estimation of resources for attacking some prominent cryptographic schemes.
As expected from a seminar with this title, many talks were indeed devoted to cryptanalysis, but the program also included presentations on establishing provable security guarantees in a post-quantum scenario. With the field becoming more mature, we did not schedule much time for survey talks. However, we did include a presentation on the emph{status of the development of quantum computers} in the program, thereby helping to get a better idea of potential obstacles when trying to implement quantum cryptanalytic attacks.
Organization
This was the fourth Dagstuhl seminar devoted entirely to quantum cryptanalysis, and as in the prior editions the set of participants included both experts in quantum algorithms and experts in classical cryptography. Some of the participants had already participated in earlier editions of this seminar series, but a number of colleagues attended such a seminar - or any Dagstuhl event - for the first time. In total, we had 42 participants from academia, government, and industry. This time we also included an open problem session in the program, which will hopefully help to stimulate further work in this vibrant research area. In the schedule we tried to leave sufficient time for discussions and for collaborative work in smaller groups. In line with the Dagstuhl tradition, no presentations were scheduled for Wednesday afternoon, and the seminar participants could devote the afternoon to a hike, an excursion, or to their research.
Results and next steps
Over the course of the years, communication and collaboration between the classical cryptographic and the quantum algorithmic research communities has intensified, and many colleagues cross traditional discipline boundaries. As evidenced in the seminar, available quantum cryptanalytic results can go well beyond asymptotic statements and include rather fine-grained resource counts. The seminar covered the analysis of both symmetric and asymmetric primitives, and ongoing efforts toward standardizing quantum-safe cryptographic solutions are likely to stimulate more progress, in particular on the quantum cryptanalysis of asymmetric cryptographic primitives.
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]
Related Seminars
- Dagstuhl Seminar 11381: Quantum Cryptanalysis (2011-09-18 - 2011-09-23) (Details)
- Dagstuhl Seminar 13371: Quantum Cryptanalysis (2013-09-08 - 2013-09-13) (Details)
- Dagstuhl Seminar 15371: Quantum Cryptanalysis (2015-09-06 - 2015-09-11) (Details)
- Dagstuhl Seminar 19421: Quantum Cryptanalysis (2019-10-13 - 2019-10-18) (Details)
- Dagstuhl Seminar 21421: Quantum Cryptanalysis (2021-10-17 - 2021-10-22) (Details)
- Dagstuhl Seminar 23421: Quantum Cryptanalysis (2023-10-15 - 2023-10-20) (Details)
- Dagstuhl Seminar 25431: Quantum Cryptanalysis (2025-10-19 - 2025-10-24) (Details)
Classification
- data structures / algorithms / complexity
- security / cryptology
Keywords
- Quantum computing
- post-quantum cryptography
- computational algebra
- quantum circuit complexity
- quantum hardware and resource estimation
