Dagstuhl Seminar 19421
Quantum Cryptanalysis
( Oct 13 – Oct 18, 2019 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/19421
Organizers
- Michele Mosca (University of Waterloo, CA)
- Maria Naya-Plasencia (INRIA - Paris, FR)
- Rainer Steinwandt (Florida Atlantic University - Boca Raton, US)
- Krysta Svore (Microsoft Corporation - Redmond, US)
Contact
- Andreas Dolzmann (for scientific matters)
- Annette Beyer (for administrative matters)
Impacts
- Improved Quantum Circuits for Elliptic Curve Discrete Logarithms : article in LNCS 12100 - Häner, Thomas; Jaques, Samuel; Naehrig, Michael; Rötteler, Martin; Soeken, Mathias - Berlin : Springer, 2020. - pp. 425-444 - (Lecture notes in computer science ; 12100 : article).
- Low-gate Quantum Golden Collision Finding : article in SAC 2020 - Jaques, Samuel; Schrottenloher, Andre - sac2020.ca, 2020. - 30 pp..
Schedule
At this point in time, it is clear that quantum computers can in principle undermine the security of many of the deployed cryptographic schemes—including RSA and elliptic curve based digital signatures, to give prominent examples. These attacks become relevant as soon as an attacker has access to a scalable quantum computer. As a result, standardization efforts for asymmetric cryptography are underway to find post-quantum replacements that can form the foundation for security protocols once quantum attacks are a reality.
In the 2019 installment of the Quantum Cryptanalysis Dagstuhl Seminar series we want to focus on practical cryptanalytic aspects, needed for standards and implementers of post-quantum cryptography. We are less interested in novel designs for post-quantum cryptography, but very much welcome demonstrations and discussions of implementations of more mature candidates for post-quantum cryptography. The seminar focus is on
I. Identifying new cryptanalytic improvements by means of quantum algorithms and optimizing the best available cryptanalytic attacks in meaningful quantum attack models. We want to fully leverage state-of-the-art quantum computing.
II. Establishing reasonable precise quantum resource counts for cryptanalytic attacks, especially for problem instances and parameter choices that are actually deployed or considered for standardization for future deployment.
The overarching goal of this Dagstuhl Seminar is the identification of robust guidelines, backed by precise cryptanalytic analyses, for parameter choices in state-of-the-art proposals for post-quantum cryptography. This comes naturally with the analysis of quantum attacks against today’s RSA and elliptic-curve based cryptography, as this is needed to have reliable estimates for when a transition is needed. We explicitly include the quantum cryptanalysis of relevant symmetric primitives (like SHA-3 or AES) in the seminar scope.
As in the past, the seminar brings together researchers who work in the field of quantum computing with experts in classical cryptography, taking into account the latest advances in both fields, and we aim at a group composition with about 50% of the participants having strong roots in each of the two underlying fields.
Creative Commons BY 3.0 DE
Michele Mosca, Maria Naya-Plasencia, Rainer Steinwandt, and Krysta Svore
Motivation and Scope
This fifth installment of a Dagstuhl seminar on Quantum Cryptanalysis was heavily informed by NIST's ongoing standardization effort in post-quantum cryptography. Several NIST employees attended the seminar and lead a discussion session on the topic. As one would hope hoped for, many talks had an algorithmic focus. Two areas were of particular interest for this seminar:
- Quantum cryptanalytic progress. Identifying new cryptanalytic improvements that make use of quantum algorithms and expanding the applicability of the best known cryptanalytic attacks by means of quantum technology. Different quantum attack models can be considered here, and attack models that are close to being realizable with today's technology are particularly relevant. We want to fully leverage quantum computing, including expected mid-term advancements.
- Quantum resource estimation. Establishing reasonably precise quantum resource counts for cryptanalytic attacks against symmetric and asymmetric schemes, especially for problem instances and parameter choices that are actually deployed or considered for standardization for future deployment. In addition to logical resources, understanding the overhead caused by handling imperfections of quantum hardware is of interest.
In addition to original quantum cryptanalytic research, the program included presentations with a strong survey component, explaining key concepts of particular areas within post-quantum cryptography. Deviating from prior editions, this time we did not include a presentation to document the status of the development of quantum hardware. Such a talk could have been a welcome addition, but the seminar program was already packed with a substantial number of relevant cryptanalytic results, and it was important to leave sufficient time for discussions.
Organization
Following the organization of the prior quantum cryptanalysis seminars in Dagstuhl, for this fifth edition, again experts from academia, government, and industry came together. We re-invited a number of leading experts in the field from the prior quantum cryptanalysis seminar edition, and at the same time invited several new participants. This included in particular young scientists, who entered this exciting research area more recently. In total, we had with 46 participants a slightly larger number of participants than in the preceding meeting. In line with the Dagstuhl tradition and with prior quantum cryptanalysis seminars, for Wednesday afternoon we left the schedule open. Seminar participants could devote the afternoon to an excursion, to discussions, or to work on their research.
Results and next step
At this point, communication and collaboration between the classical cryptographic and the quantum algorithmic research communities has become very fruitful, and it seems fair to say that this seminar is also of significant value in supporting ongoing standardization efforts in post-quantum cryptography. In addition to quantum cryptanalytic results on asymmetric cryptography, more results on symmetric cryptography are emerging. There is still substantial research potential -- and research need -- in quantifying security margins in the presence of quantum computing, and the field keeps moving fast. Improved software tools become available to analyze quantum resources and describe quantum algorithms, bringing research in quantum cryptanalysis closer together with areas in traditional computer science.
Michele Mosca, Maria Naya-Plasencia, and Rainer Steinwandt
- Gorjan Alagic (University of Maryland - College Park, US) [dblp]
- Daniel C. Apon (NIST - Gaithersburg, US) [dblp]
- Daniel J. Bernstein (University of Illinois - Chicago, US) [dblp]
- Jean-François Biasse (University of South Florida - Tampa, US) [dblp]
- Christian Bischof (TU Darmstadt, DE) [dblp]
- Xavier Bonnetain (INRIA - Paris, FR) [dblp]
- Harry Buhrman (CWI - Amsterdam, NL) [dblp]
- Jintai Ding (University of Cincinnati, US) [dblp]
- Martin Ekerå (KTH Royal Institute of Technology - Stockholm, SE) [dblp]
- Philippe Gaborit (University of Limoges, FR) [dblp]
- András Gilyén (Caltech - Pasadena, US) [dblp]
- Maria Isabel González Vasco (King Juan Carlos University - Madrid, ES) [dblp]
- Sean Hallgren (Pennsylvania State University - University Park, US) [dblp]
- Akinori Hosoyamada (NTT - Tokyo, JP) [dblp]
- David Jao (University of Waterloo, CA) [dblp]
- Samuel E. Jaques (University of Oxford, GB) [dblp]
- Stacey Jeffery (CWI - Amsterdam, NL) [dblp]
- Antoine Joux (Sorbonne University - Paris, FR) [dblp]
- Elena Kirshanova (Immanuel Kant Baltic Federal University, RU) [dblp]
- Thijs Laarhoven (TU Eindhoven, NL) [dblp]
- Bradley Lackey (Microsoft Corporation - Redmond, US) [dblp]
- Tanja Lange (TU Eindhoven, NL) [dblp]
- Alexander May (Ruhr-Universität Bochum, DE) [dblp]
- Shaun Miller (Florida Atlantic University - Boca Raton, US) [dblp]
- Dustin Moody (NIST - Gaithersburg, US) [dblp]
- Michele Mosca (University of Waterloo, CA) [dblp]
- Priyanka Mukhopadhyay (University of Waterloo, CA) [dblp]
- Maria Naya-Plasencia (INRIA - Paris, FR) [dblp]
- Phong Nguyen (ENS - Paris, FR) [dblp]
- Ray Perlner (NIST - Gaithersburg, US) [dblp]
- Edoardo Persichetti (Florida Atlantic University - Boca Raton, US) [dblp]
- Rachel Player (Royal Holloway University of London, GB) [dblp]
- Thomas Pöppelmann (Infineon Technologies AG - Neubiberg, DE) [dblp]
- Yu Sasaki (NTT - Tokyo, JP) [dblp]
- John M. Schanck (University of Waterloo, CA) [dblp]
- André Schrottenloher (INRIA - Paris, FR) [dblp]
- Nicolas Sendrier (INRIA - Paris, FR) [dblp]
- Yixin Shen (Paris Diderot University, 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]
- Jean-Pierre Tillich (INRIA - Paris, FR) [dblp]
- Maya-Iggy van Hoof (TU Eindhoven, NL) [dblp]
- Fernando Virdia (Royal Holloway University of London, GB) [dblp]
- Thomas Wunderer (BSI - Bonn, DE) [dblp]
- Bo-Yin Yang (Academia Sinica - Taipei, TW) [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 17401: Quantum Cryptanalysis (2017-10-01 - 2017-10-06) (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
- quantum hardware and resource estimation
