Dagstuhl Seminar 23421
Quantum Cryptanalysis
( Oct 15 – Oct 20, 2023 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/23421
Organizers
- Gorjan Alagic (University of Maryland - College Park, US)
- Stacey Jeffery (CWI - Amsterdam, NL)
- Maria Naya-Plasencia (INRIA - Paris, FR)
- Rainer Steinwandt (University of Alabama in Huntsville, US)
Contact
- Michael Gerke (for scientific matters)
- Christina Schwarz (for administrative matters)
Impacts
- Quantum Sieving for Code-Based Cryptanalysis and Its Limitations for ISD - Engelberts, Lynn; Etinski, Simona; Loyer, Johanna - Cryptology ePrint Archive, 2024. - 28 pp..
- Improved Quantum Linear Attacks andApplication to CAST : article - Bashiri, Kaveh; Bonnetain, Xavier; Hosoyamada, Akinori; Lang, Nathalie; Schrottenloher, Andre - Cryptology ePrint Archive, 2024. - 41 pp..
Schedule
Motivation and technical scope
Due to the coronavirus pandemic, the previous Dagstuhl Seminar in the Quantum Cryptanalysis series (in 2021) took place in a hybrid format. With this latest installment in 2023, we returned to the standard fully in-person format at Schloss Dagstuhl and incorporated more group work. Since the 2021 meeting, the scientific community progressed significantly in developing and standardizing post-quantum cryptography for general use. In particular, the U.S. National Institute of Standards and Technology (NIST) announced that it will standardize several public-key cryptographic schemes. The study of candidates in this process has been a focus of past installments of the Quantum Cryptanalysis seminar series and this year's Dagstuhl Seminar. The 2023 seminar was also interested in the analysis of two more scheme categories. The first category consists of additional public-key schemes that either have different performance profiles, or different security properties (e.g., are based on the hardness of other mathematical problems) than the NIST-selected schemes. The second category consists of symmetric-key schemes; while post-quantum standardization has not as yet focused on symmetric-key cryptography, there are many open questions about their security in the presence of quantum adversaries.
As one would expect from the title of the seminar, studying the best-known algorithmic attacks on cryptographic schemes was a focus of the conversations. Understanding the best-known attacks enables cryptographers to select the strongest schemes and set their parameters in a manner that appropriately balances security with performance. Technical talks included work on quantum-computational algorithms for attacking three categories of public-key schemes: lattice-based, code-based, and isogeny-based. We also had two presentations on new ideas for attacking symmetric-key cryptography using quantum computers. In addition, the technical program included an update from NIST on the progress of their various standardization processes related to the seminar scope.
As in the past, the seminar brought together researchers in several relevant fields, including quantum-computational algorithms, classical public-key and symmetric-key cryptography, and the mathematics of lattices and codes. This enabled the participants to get an overview of the latest advances in all of these fields.
Organization
To leverage some of the unique opportunities Schloss Dagstuhl offers, as in the past, we left ample time for discussions and collaboration; the typical day called for between two and three presentations total. The remaining time was more structured than in past instances of the seminar. Before the seminar began, the organizers contacted the participants to solicit topics and started to organize working groups. The first day of the seminar was then mainly focused on establishing the working groups and the technical topics they would focus on. The working groups met throughout the week to discuss their technical subjects and regularly reported their progress to the entire seminar. The participant-selected working group topics were:
- quantum algorithms for the lattice isomorphism problem (a new problem with potential for post-quantum applications),
- Regev's quantum factoring algorithm (a new algorithm that may affect how soon current cryptography will become obsolete),
- cryptanalysis of LR5 (a fundamental building block in symmetric-key cryptography), and
- code-based cryptosystems (these are next on the slate of possible standardized schemes).
Following the Dagstuhl tradition and in line with prior seminars in the Quantum Cryptanalysis series, there was no technical program during Wednesday afternoon. This enabled participants to explore the surroundings or spend more time on collaborative research.
With 34 participants, Schloss Dagstuhl hosted a diverse group of leading experts from across the globe. A significant number of the participants were graduate students. These young researchers were able to interact with leading experts in working on the latest science and gain valuable insights to help them developing their career.
Results and next steps
The working groups were a welcome addition this year, with several participants praising this style of seminar structure. The working groups were able to make technical progress during the week and several groups continued collaborating after the seminar.
The various technical presentations showed that significant progress is being made in the field more generally. This indicates that the intersection of quantum computing and classical cryptography is a vibrant and active field. The Dagstuhl Seminar series on Quantum Cryptanalysis plays an important role in this area of science. We expect this will continue, as the community carries on with the process of standardizing and deploying post-quantum cryptography in the real world. This process is already generating challenging scientific questions that the seminar could help address. For instance, the only general-purpose schemes currently slated for standardization are based on lattice problems; how can the community select high-performing replacement schemes that can serve as a backup in case lattices fail?
Creative Commons BY 4.0
Gorjan Alagic, Stacey Jeffery, Maria Naya-Plasencia, and Rainer Steinwandt
Located at the crossroad between quantum computing and cryptography, quantum cryptanalysis is the study of quantum attacks against cryptographic solutions. The focus of this Dagstuhl Seminar includes algorithmic insights, as well as software tools that support the quantum cryptanalyst in optimizing resources. We are especially interested in the quantum-resistance of symmetric and asymmetric cryptographic solutions that are deployed or considered for standardization.
This is the 7th in a series of Dagstuhl Seminars on quantum cryptanalysis (following Nº 11381, Nº 13371, Nº 15371, Nº 17401, Nº 19421, and Nº 21421). To pave the road for the next round of post-quantum standardization, which has already been announced, this seminar is expected to have a stronger emphasis on (in particular lattice-based) constructions for post-quantum digital signatures. The symmetric cryptanalysis component of the program addresses the fact that, based on more recent results, lightweight ciphers may be more vulnerable to quantum attacks than originally anticipated. Taking a step back from the parameter-level analysis of very specific standardization candidates, we expect more discussions and presentations on asymptotic insights, complemented by experimental results.
There are two core themes of this Dagstuhl Seminar:
- quantum-algorithmic innovations to attack various cryptographic building blocks, with an emphasis on digital signatures and block ciphers, and
- computational problems that enable the construction of post-quantum cryptographic schemes.
In view of the fast-paced research in quantum cryptanalysis and to make effective use of the opportunities that Schloss Dagstuhl offers, we plan to determine the exact technical focus 2-3 months before the seminar based on feedback from the seminar participants. We plan for a small number of working groups that can spend a substantial part of the week on a specific problem domain within quantum cryptanalysis. The seminar schedule will also ensure regular exchange among the different working groups over the course of the week.
Currently anticipated focus areas include computational problems in lattices and symmetric quantum cryptanalysis beyond quadratic speed-ups, but participants may opt for alternate topics. A key goal is to maintain a strong seminar character, and not be confined to traditional presentations of completed results. As in prior editions, this seminar brings together researchers from academia, government, and industry, including experts from quantum computing and experts in classical cryptography, as well as members of the new generation of native quantum cryptanalysts who are fluent in both disciplines.
Gorjan Alagic, Stacey Jeffery, Maria Naya-Plasencia, and Rainer Steinwandt
- Gorjan Alagic (University of Maryland - College Park, US) [dblp]
- Kaveh Bashiri (BSI - Bonn, DE)
- Jean-François Biasse (University of South Florida - Tampa, US) [dblp]
- Xavier Bonnetain (LORIA & INRIA Nancy, FR) [dblp]
- Yanlin Chen (CWI - Amsterdam, NL) [dblp]
- Arjan Cornelissen (IRIF - Paris, FR) [dblp]
- Martin Ekerå (KTH Royal Institute of Technology - Stockholm, SE) [dblp]
- Lynn Engelberts (CWI - Amsterdam, NL & QuSoft - Amsterdam, NL)
- Simona Etinski (CWI - Amsterdam, NL) [dblp]
- Paul Frixons (INRIA Nancy - Grand Est, FR) [dblp]
- Vlad Gheorghiu (University of Waterloo, CA & softwareQ Inc. - Waterloo, CA) [dblp]
- Sean Hallgren (Pennsylvania State University - University Park, US) [dblp]
- Jacek Horecki (BEIT - Kraków, PL)
- Akinori Hosoyamada (NTT - Tokyo, JP) [dblp]
- Péter Kutas (University of Birmingham, GB) [dblp]
- Johanna Loyer (INRIA - Paris, FR) [dblp]
- Frédéric Magniez (CNRS - Paris, FR) [dblp]
- Christian Majenz (Technical University of Denmark - Lyngby, DK) [dblp]
- Alexander May (Ruhr-Universität Bochum, DE) [dblp]
- Garazi Muguruza (QuSoft & University of Amsterdam, NL)
- Maria Naya-Plasencia (INRIA - Paris, FR) [dblp]
- Lorenz Panny (TU München - Garching, DE) [dblp]
- Galina Pass (QuSoft - Amsterdam, NL) [dblp]
- Yu Sasaki (NTT - Tokyo, JP) [dblp]
- André Schrottenloher (INRIA - Rennes, FR) [dblp]
- Yixin Shen (King's College London, GB) [dblp]
- Manasi Shingane (University of Maryland - College Park, US)
- Daniel C. Smith-Tone (NIST - Gaithersburg, US) [dblp]
- Jana Sotáková (University of Amsterdam, NL) [dblp]
- Rainer Steinwandt (University of Alabama in Huntsville, US) [dblp]
- Jean-Pierre Tillich (INRIA - Paris, FR) [dblp]
- Maya-Iggy van Hoof (Ruhr-Universität Bochum, DE) [dblp]
- Michael Walter (Ruhr-Universität Bochum, DE) [dblp]
- Sara Zafar Jafarzadeh (University of Waterloo, CA & Synopsys Inc. - Ottawa, CA)
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 19421: Quantum Cryptanalysis (2019-10-13 - 2019-10-18) (Details)
- Dagstuhl Seminar 21421: Quantum Cryptanalysis (2021-10-17 - 2021-10-22) (Details)
- Dagstuhl Seminar 25431: Quantum Cryptanalysis (2025-10-19 - 2025-10-24) (Details)
Classification
- Cryptography and Security
- Data Structures and Algorithms
- Emerging Technologies
Keywords
- Cryptanalysis
- post-quantum cryptography
- quantum algorithms
- quantum resource estimation
- computational algebra
