Quantum Cryptanalysis

Summary

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.