Dagstuhl Seminar 13371
Quantum Cryptanalysis
( Sep 08 – Sep 13, 2013 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/13371
Organizers
- Serge Fehr (CWI - Amsterdam, NL)
- Michele Mosca (University of Waterloo, CA)
- Martin Roetteler (Microsoft Corporation - Redmond, US)
- Rainer Steinwandt (Florida Atlantic University - Boca Raton, US)
Contact
- Susanne Bach-Bernhard (for administrative matters)
Schedule
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.
Motivation and Background
This (second) quantum cryptanalysis seminar aimed at improving our understanding of quantum attacks against modern cryptographic schemes, a task that is closely related to the question of plausible quantum computational hardness assumptions. By bringing together researchers who work in the field of quantum computing with those who work in the field of classical cryptography, the seminar aimed at identifying practical approaches to achieve cryptographic security in the presence of quantum computers. A lesson learned from an earlier edition of this seminar (Dagstuhl Seminar 11381) was that statements about the security of cryptographic schemes in the presence of a quantum attacker require the study and characterization of quantum security parameters. Those parameters measure the amount of resources that have to be spent in order to "break" a system. In this spirit, the following three topics turned out to be particularly relevant for the seminar:
- Quantum attacks on currently deployed schemes: Derive quantitative estimates for the resources (like no. of qubits and quantum gates) that are needed to carry out quantum attacks with cryptographically relevant parameter choices.
- New quantum algorithms to attack potential new hardness assumptions: For instance, can quantum algorithms be used to improve on classical solutions for computational problems in lattices or for the decoding of error-correcting codes?
- Quantum computational assumptions: Which problems are currently considered as intractable, even for a quantum computer, and possibly might have the potential to be of cryptographic interest? Examples are certain hidden shift and hidden subgroup problems.
One indicator for the importance of these topics for the seminar was that most talks addressed (at least) one of them. The invited group of researchers as well as the organizing team was chosen to offer a balance of expertise from the different relevant disciplines, but also to have a substantial common ground for making progress towards the seminar goal.
Seminar Organization
The seminar involved 37 participants from around the globe, ranging from young researchers to colleagues with many years of interdisciplinary research experience. For young researchers the interdisciplinary set-up of the seminar offered an excellent opportunity to make new connections beyond the familiar research communities. Based on the experience from the predecessor (Dagstuhl Seminar 11381), we decided for a schedule which has enough flexibility to add presentations that grow out of discussions during the week, and indeed these additional slots could be brought to good use. We made an effort to keep the number of presentations limited to have ample time for open discussions between presentations. Having two research communities present at the meeting, it also seemed realistic to assume that not all participants are familiar with the latest developments in the complementing discipline. Placing survey presentations on critical topics early in the schedule was well received by the participants.
To ensure an adequate connection with the technological state-of-the-art of implementing quantum computers, one of the survey presentations was specifically devoted to this subject, and the seminar included discussions on implementation aspects of quantum computing. Keeping with the Dagstuhl tradition and the tradition of the predecessor, for Wednesday afternoon we did not schedule any presentations, allowing seminar participants to enjoy a hike in the woods, a visit to Trier, or to use the time for longer technical discussions.
Achievements and Next Steps
As in the first edition of this seminar, there were many fruitful discussions across discipline boundaries. At the time of writing this report, two seminar participants had already published a preprint with a generalization of a previously known quantum attack to a more general class of algebraic structures. We expect further publications to come forward in the coming months. While we are still far from a thorough understanding of the cryptanalytic potential of quantum computing, synergetic collaborations of seminar participants have helped greatly to advance the state-of-the-art in quantum cryptanalysis.
The seminar also successfully facilitated the exchange among colleagues from academia, government, and industry. We believe that in regard to a standardization of post-quantum cryptographic solutions, this type of exchange across community boundaries is valuable and deserves to be intensified further in future meetings.
Creative Commons BY 3.0 Unported license
Serge Fehr, Michele Mosca, Martin Roetteler, and Rainer Steinwandt
- Aleksandrs Belovs (University of Latvia, LV) [dblp]
- Daniel J. Bernstein (University of Illinois - Chicago, US) [dblp]
- Johannes A. Buchmann (TU Darmstadt, DE) [dblp]
- Andrew Childs (University of Waterloo, CA) [dblp]
- Frédéric Dupont-Dupuis (Aarhus University, DK) [dblp]
- Serge Fehr (CWI - Amsterdam, NL) [dblp]
- Katalin Friedl (Budapest University of Technology & Economics, HU) [dblp]
- Markus Grassl (National University of Singapore, SG) [dblp]
- Nadia Heninger (University of Pennsylvania - Philadelphia, US) [dblp]
- Peter Hoyer (University of Calgary, CA) [dblp]
- Gabor Ivanyos (Hungarian Academy of Sciences - Budapest, HU) [dblp]
- Stacey Jeffery (University of Waterloo, CA) [dblp]
- Stephen P. Jordan (NIST - Gaithersburg, US) [dblp]
- Thijs Laarhoven (TU Eindhoven, NL) [dblp]
- Bradley Lackey (National Security Agency - Fort Meade, US) [dblp]
- Tanja Lange (TU Eindhoven, NL) [dblp]
- Yi-Kai Liu (NIST - Gaithersburg, US) [dblp]
- Alexander May (Ruhr-Universität Bochum, DE) [dblp]
- Kirill Morozov (Kyushu University - Fukuoka, JP) [dblp]
- Michele Mosca (University of Waterloo, CA) [dblp]
- Maris Ozols (IBM TJ Watson Research Center - Yorktown Heights, US) [dblp]
- Youming Qiao (National University of Singapore, SG) [dblp]
- Martin Roetteler (Microsoft Corporation - Redmond, US) [dblp]
- Louis Salvail (University of Montréal, CA) [dblp]
- Miklos Santha (University of Paris VII, FR) [dblp]
- Christian Schaffner (University of Amsterdam, NL) [dblp]
- John M. Schanck (University of Waterloo, CA) [dblp]
- Nicolas Sendrier (INRIA - Le Chesnay, FR) [dblp]
- Daniel C. Smith-Tone (NIST - Gaithersburg, US) [dblp]
- Rolando Somma (Los Alamos National Lab., US) [dblp]
- Fang Song (Pennsylvania State University - University Park, US) [dblp]
- Rainer Steinwandt (Florida Atlantic University - Boca Raton, US) [dblp]
- Krysta Svore (Microsoft Corporation - Redmond, US) [dblp]
- Wim van Dam (University of California - Santa Barbara, US) [dblp]
- Joop van de Pol (University of Bristol, GB) [dblp]
- Maarten van den Nest (MPI für Quantenoptik, DE) [dblp]
- Frank K. Wilhelm (Universität des Saarlandes, DE) [dblp]
Related Seminars
- Dagstuhl Seminar 11381: Quantum Cryptanalysis (2011-09-18 - 2011-09-23) (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 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
- Cryptographic Protocol Design
