Quantum Cryptanalysis

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.