TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Please select your role
to obtain appropriate quick-links.
As a LIPIcs/OASIcs author, you will be invited by e-mail to register at the Dagstuhl Submission Server. The server will guide you through the publication workflow. Preliminary information can be found here:
Quick Links

Dagstuhl Seminar 15371

Quantum Cryptanalysis

( Sep 06 – Sep 11, 2015 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/15371
Organizers
Contact
Publications
Press/News
Impacts
Schedule
Motivation
Show Motivation

While it has been known for some time that quantum computers could in principle undermine the security of many schemes—including RSA and elliptic curve based digital signatures—significantly less is known on actual estimates about the required resources that would be needed to carry out such quantum attacks. This leaves the providers and consumers of cryptographic methods in a fundamental dilemma, namely to estimate the impact of future quantum computers on the landscape of currently deployed cryptography and on the landscape of potential quantum-safe alternatives.

  • Is it reasonable to assume that quantum computers pose a threat for currently deployed cryptography? What are concrete implications for the security level of currently deployed cryptographic schemes? In particular, does the threat of a quantum computer at the horizon require the change of key sizes now or in the near future?
  • What is the time horizon until when a physical quantum computer capable of say breaking a discrete logarithm problem on a 163-bit binary elliptic curve will be available?
  • To what extent are the proposed post-quantum cryptosystems truly resistant to quantum attacks? And what are appropriate key sizes and security parameters?

Questions like these are pertinent to this third installation of a quantum cryptanalysis seminar at Schloss Dagstuhl. We seek to leverage the full potential of quantum attacks on today’s cryptographic schemes and at the same time to identify plausible quantum computational assumptions for their replacements. We are particularly interested in

  • Algorithmic Innovation: computational assumptions, recent trends and innovations in cryptography and quantum algorithms, new ideas to attack classical cryptography.
  • Resource Estimation: quantify the quantum hardware resources required to carry out attacks against classical schemes. We intend to hold a “hardware day” devoted to circuit-level discussions and quantum hardware/implementation survey talks.
  • The seminar aims to be interdisciplinary with participation of colleagues from classical cryptography and quantum computing. The general organization will follow its predecessors in that we plan to have ample time for discussions and personal interactions.
Press Room
Show Press Room

Press Reviews

Summary
Show Summary

It is known that quantum algorithms exist that jeopardize the security of most of our widely-deployed cryptosystems, including RSA and Elliptic Curve Cryptography. It is also known that advances in quantum hardware implementations are making it increasingly likely that large-scale quantum computers will be built in the near future that can implement these algorithms and devastate most of the world's cryptographic infrastructure. What is not known is an estimate of the resources that will be required to carry out these attacks -- or even whether other quantum attacks exist that have not yet been accounted for in our security estimates. In this seminar, we examined both computational resource estimates for meaningful quantum cryptanalytic attacks against classical (i.e.: conventional) cryptography, as well as the security of proposed quantum-safe cryptosystems against emerging quantum cryptanalytic attacks.

This seminar had a number of research highlights spanning the areas of implementations of quantum hardware and software, quantum algorithms, and post-quantum cryptography.

Implementations of quantum information processing were outlined to help contextualize the current state of quantum computation. Recent advances in the synthesis of efficient quantum circuits were presented, as well as an update on implementations - particularly in the domain of superconducting integrated circuits. Seminar participants were warned that traditional approaches to the modeling of quantum processors may be reaching an end, while the LIQUi|> software architecture for control of quantum hardware and simulation of quantum algorithms was unveiled. Challenges involving practical costs for error correction in systems with specific types of quantum memory (particularly quantum bucket brigade RAM architectures) were articulated.

In the domain of algorithmic advances, seminar participants demonstrated quantum improvements on the gapped group testing problem, as well as improvements on lattice sieving using nearest neighbour search algorithms. A discussion of how quantum computers can sometimes provide quadratic speedup for the differential cryptanalysis of symmetric-key cryptosystems was also presented. A quantum version of the unique-SVP algorithm was discussed, but it was found to have slightly worse performance than its' classical counterpart. For the purposes of improving our understanding quantum algorithms before large-scale quantum computers become available, a technique involving trapdoor simulation of quantum algorithms was proposed.

Seminar participants also gave a number of recent results in the domain of quantum-safe cryptography. These included a provably-secure form of Authenticated Key Exchange based on the Ring-Learning with Errors problem, a proposal for a quantum-safe method to prevent key leakage during key agreement failure stemming from invalid public keys, and updates on hash-based digital signatures. The EU PQCRYPTO project also presented some preliminary recommendations for post-quantum cryptography.

In the domain of code-based cryptography, it was demonstrated that assuming hardness of Niederreiter problem, CFS signatures are strongly existentially unforgeable in the random oracle model. A number of results related to lattice reduction were also presented, including an improvement on the BKZ lattice reduction algorithm, some lattice enumeration work involving factoring integers by CVP algorithms for the prime number lattice, and a reduction of gapped uSVP to the Hidden Subgroup Problem in dihedral groups. A LIQUi|> implementation of a quantum algorithm to extract hidden shift was also presented, as well as demonstration of instances of HSPs over dihedral group which can be efficiently solved on a quantum computer. Seminar participants also proposed alternative ways of thinking about the dihedral coset problem, including some hardness reductions. A very new result on finding a generator of a principal ideal was also debuted at this seminar and provoked lively and ongoing discussion among participants.

Other talks were presented on diverse and compelling topics including quantum-mechanical means for program obfuscation, and a means for quantum indistinguishability of some types of ciphertext messages. A presentation was also made about how standardization bodies and industry deal with information security and risk, and many discussions - both formal and informal - among participants began to deal with the applied challenges of developing and deploying quantum-safe information security standards and tools.

Overall, the success of this seminar can be observed not only through the quantity of new results, but also in their diversity and interdisciplinarity. While there exist venues for cryptography and cryptanalysis, for quantum algorithms, and for implementations of quantum information processing, it remains critical that these communities continue to come together to ensure rigorous and broad cryptanalysis of proposed quantum-safe cryptographic algorithms, and to share a well-defined mutual understanding of the quantum-computational resource requirements - and their present availability - for attacking both public and symmetric key cryptography. The security of the world's information depends on it.

The organizers (Michele Mosca, Martin Roetteler, Nicolas Sendrier, and Rainer Steinwandt) are grateful to the participants of this seminar and the team of Schloss Dagstuhl for an inspiring and productive third edition of this seminar series.

Copyright Michele Mosca, Martin Roetteler, Nicolas Sendrier, and Rainer Steinwandt
Participants
Show Participants
  • Gorjan Alagic (University of Copenhagen, DK) [dblp]
  • Aleksandrs Belovs (University of Latvia, LV) [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]
  • Harry Buhrman (CWI - Amsterdam, NL) [dblp]
  • André Chailloux (INRIA Rocquencourt, FR) [dblp]
  • Jintai Ding (University of Cincinnati, US) [dblp]
  • Hang Dinh (Indiana University South Bend, US) [dblp]
  • Jürgen Eschner (Universität des Saarlandes, DE)
  • Jennifer Katherine Fernick (University of Waterloo, CA)
  • Tommaso Gagliardoni (TU Darmstadt, DE) [dblp]
  • Markus Grassl (Universität Erlangen-Nürnberg, DE) [dblp]
  • Sean Hallgren (Pennsylvania State University - University Park, US) [dblp]
  • Peter Hoyer (University of Calgary, CA) [dblp]
  • Andreas Hülsing (TU Eindhoven, NL) [dblp]
  • Stacey Jeffery (CalTech - Pasadena, US) [dblp]
  • Stavros Kousidis (BSI - Bonn, DE) [dblp]
  • Thijs Laarhoven (TU Eindhoven, NL) [dblp]
  • Bradley Lackey (University of Maryland - College Park, US) [dblp]
  • Tanja Lange (TU Eindhoven, NL) [dblp]
  • Anthony Leverrier (INRIA Rocquencourt, FR) [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]
  • Michael Naehrig (Microsoft Research - Redmond, US) [dblp]
  • Maris Ozols (University of Cambridge, GB) [dblp]
  • Ray Perlner (NIST - Gaithersburg, US) [dblp]
  • Martin Roetteler (Microsoft Corporation - Redmond, US) [dblp]
  • Christian Schaffner (University of Amsterdam, NL) [dblp]
  • John M. Schanck (University of Waterloo, CA) [dblp]
  • Claus Peter Schnorr (Goethe-Universität Frankfurt am Main, DE) [dblp]
  • Nicolas Sendrier (INRIA - Le Chesnay, FR) [dblp]
  • Dan J. Shepherd (CESG - Cheltenham, GB) [dblp]
  • Daniel C. Smith-Tone (University of Louisville, US) [dblp]
  • Fang Song (University of Waterloo, CA) [dblp]
  • Rainer Steinwandt (Florida Atlantic University - Boca Raton, US) [dblp]
  • Krysta Svore (Microsoft Corporation - Redmond, US) [dblp]
  • Tsuyoshi Takagi (Kyushu University - Fukuoka, JP) [dblp]
  • Enrico Thomae (operational services GmbH - Zwickau, DE) [dblp]
  • Jean-Pierre Tillich (INRIA - Le Chesnay, FR) [dblp]
  • Joop van de Pol (University of Bristol, GB) [dblp]
  • Frank K. Wilhelm (Universität des Saarlandes, DE) [dblp]
  • Bo-Yin Yang (Academica 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 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
  • quantum circuit complexity
  • quantum hardware and resource estimation
Seminar 15371
© 2025 Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH
ImprintContactAccessibilityPrivacy