http://www.dagstuhl.de/17401

October 1 – 6 , 2017, Dagstuhl Seminar 17401

Quantum Cryptanalysis

Organizers

Michele Mosca (University of Waterloo, CA)
Nicolas Sendrier (INRIA – Le Chesnay, FR)
Rainer Steinwandt (Florida Atlantic University – Boca Raton, US)
Krysta Svore (Microsoft Corporation – Redmond, US)

For support, please contact

Susanne Bach-Bernhard for administrative matters

Andreas Dolzmann for scientific matters

Documents

List of Participants
Shared Documents
Dagstuhl Seminar Wiki
Dagstuhl Seminar Schedule (Upload here)

(Use seminar number and access code to log in)

Motivation

The fact that quantum computers could in principle undermine the security of many deployed crypto¬graphic schemes – including RSA and elliptic curve based digital signatures – is known. With the remark¬able changes to NSA’s Suite B in 2015, it is clear that quantum computing has – despite still being an emerging technology – already tangible effects on deployed cryptographic solutions. This Dagstuhl Seminar on Quantum Cryptanalysis targets the design and study of cryptographic proposals that could be suitable for standardization in the post-quantum setting as well as the study of quantum attacks against currently deployed information processing systems.

Core themes of the seminar are quantum algorithmic innovations to attack today’s cryptographic solutions and post-quantum candidates for encryption, signature, and key establishment. We would like to empha¬size quantitative aspects of quantum cryptanalysis and anticipate that this successor of Dagstuhl Seminars 11381, 13371, and 15371 can effectively inform standardization efforts in post-quantum cryptography. We will have participants across several disciplines from academia, government, and industry. This com¬position of the participant group ensures that scientific findings can be disseminated efficiently and in¬creases the potential for genuine impact.

Seminar Goal & Scope

With the foundations of quantum cryptanalysis having been established, this iteration of the seminar wants to provide scientific results that pave the way for an informed transition to quantum-safe cryptographic standards. The seminar aims at leveraging the full potential of quantum attacks and knowledge about quantum computers to identify plausible post-quantum cryptographic solutions for basic cryptographic tasks. Naturally, we plan to address two main thrusts, which are not independent:

Algorithmic innovation. Here we intend to study problem instances and problem classes for which we believe to have (or hope to find) plausible evidence that they are hard for quantum computers – making them a plausible candidate to have post-quantum security rest on them. Ideally, one can establish a provable reduction of relevant security guarantees to a plausibly quantum hard problem. Complementing this, we are interested in quantum speed-ups of classical attack techniques (hybrid algorithms) and novel cryptographic attacks relying on quantum technology. We do care for moderate (not necessarily asymptotic) speed-ups that might be implementable with a small-scale quantum computer already, as this may affect the life-time of cryptographic standards.

Quantum resource estimation. Here we are interested in quantifying the resources of quantum attacks, e.g., what does it cost to forge a root certificate – can we detail a complete quantum circuit for this task? Constraints of quantum hardware (such as geometric constraints or gate fidelities) should be taken into account to obtain realistic statements – replacing or updating cryptographic solutions can be very costly, so requiring such a change deserves a sound justification. For instance, in hybrid algorithms, the reliability and error-correction needs of a classical control logic and quantum components are likely to differ sub¬stantially. We want to explore the applicability of existing software tools for advancing the cost analysis of quantum attacks – and to stimulate advances in quantum cryptanalysis.

Discussions are expected to focus mostly around popular post-quantum platforms such as error-correcting codes, lattice problems, systems of polynomial equations, and hash-based signing. Still, we want to leave room for exploring less prominent post-quantum candidates, which show potential. The use of isogenies of elliptic curves is a good example for such an approach.

License
  Creative Commons BY 3.0 DE
  Michele Mosca and Nicolas Sendrier and Rainer Steinwandt and Krysta Svore

Dagstuhl Seminar Series

Classification

  • Data Structures / Algorithms / Complexity
  • Security / Cryptology

Keywords

  • Quantum computing
  • Post-quantum cryptography
  • Computational algebra
  • Quantum circuit complexity
  • Quantum hardware and resource estimation

Book exhibition

Books from the participants of the current Seminar 

Book exhibition in the library, ground floor, during the seminar week.

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.